2014
02-09

# Another Eight Puzzle

Fill the following 8 circles with digits 1~8,with each number exactly once . Conntcted circles cannot be filled with two consecutive numbers.
There are 17 pairs of connected cicles:
A-B , A-C, A-D
B-C, B-E, B-F
C-D, C-E, C-F, C-G
D-F, D-G
E-F, E-H
F-G, F-H
G-H

Filling G with 1 and D with 2 (or G with 2 and D with 1) is illegal since G and D are connected and 1 and 2 are consecutive .However ,filling A with 8 and B with 1 is legal since 8 and 1 are not consecutive .

In this problems,some circles are already filled,your tast is to fill the remaining circles to obtain a solution (if possivle).

The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle.

The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle.

3
7 3 1 4 5 8 0 0
7 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0

Case 1: 7 3 1 4 5 8 6 2
Case 2: Not unique
Case 3: No answer

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
bool g[10][10],fil[10];
//g[10][10]记录点与点之间是否相连，fil[10]记录该数字是否已经选过
int a[10],ans[10],num;
//ans[]保存路径
void dfs(int deep,int move[])
{
if(deep==8)//选完了
{
if(!num)//保存第一个答案
{
for(int i=0;i<8;i++)
ans[i]=move[i];
}
num++;
return ;
}
else if(a[deep]>0)//该点已经给定了数字，直接往下搜
{
move[deep]=a[deep];
dfs(deep+1,move);
}
else {
for(int i=1;i<=8;i++)//枚举8个数字
{
if(fil[i])//该数字已经选过
continue;
int flag=0;
for(int j=0;j<8;j++)//枚举八个点
{
if(g[deep][j] && ((move[j]>0 &&abs(move[j]-i)==1)||(a[j]>0 && abs(a[j]-i)==1)) )//若该点与当前点相连&& 已经选了数字 && 差值等于1
{
flag=1;break;
}
}
if(flag) continue;
move[deep]=i;fil[i]=true;
dfs(deep+1,move);
if(num>1)return ;
move[deep]=0;fil[i]=false;
}
}
}

void init()
{
memset(g,false,sizeof(g));
for(int i=0;i<8;i++)
g[i][i]=true;
for(int i=1;i<=3;i++)
g[i][0]=g[0][i]=true;
g[1][2]=g[2][1]=true;
g[1][4]=g[4][1]=true;
g[1][5]=g[5][1]=true;
for(int i=3;i<=6;i++)
g[2][i]=g[i][2]=true;
g[3][5]=g[5][3]=true;
g[3][6]=g[6][3]=true;
g[4][5]=g[5][4]=true;
g[4][7]=g[7][4]=true;
g[5][6]=g[6][5]=true;
g[5][7]=g[7][5]=true;
g[6][7]=g[7][6]=true;
}
int main()
{
init();
int cas=0,T;
scanf("%d",&T);
while(T--)
{
memset(fil,false,sizeof(fil));
for(int i=0;i<8;i++)
{
scanf("%d",&a[i]);
fil[a[i]]=true;
}
int move[10]={0};
num=0;
dfs(0,move);
printf("Case %d: ",++cas);
if(num==0)
else if(num>1)
printf("Not unique\n");
else {
printf("%d",ans[0]);
for(int i=1;i<8;i++)
printf(" %d",ans[i]);
puts("");
}
}
return 0;
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

3. 不考虑最后将结果排序的话，快排的时间复杂度是O(N) ，而堆排的是O(N*logK),这样比较看，快排快

4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

5. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

6. #include <cstdio>

int main() {