论坛上看到一个回溯算法题，这里小记一下。
原题：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。
为了简化代码突出回溯思想，程序中有很多简化了的东西。
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define N 10
#define INIT -2
#define MARK -1
int num[9];
int mark[N];
int main()
{
int test(int pos);
for(int i=0;i<9;i++)
{
num[i]=INIT;
}
for(int i=0;i<N;i++)
{
mark[i]=INIT;
}
test(0);
return 0;
}
int isPrime(int num)
{
for(int i=2;i<=num/2;i++)
{
if(num%i==0)
{
return 0;
}
}
return 1;
}
int check()
{
if(!isPrime(num[0]+num[1]))
return 0;
if(!isPrime(num[2]+num[1]))
return 0;
if(!isPrime(num[3]+num[4]))
return 0;
if(!isPrime(num[4]+num[5]))
return 0;
if(!isPrime(num[6]+num[7]))
return 0;
if(!isPrime(num[7]+num[8]))
return 0;
if(!isPrime(num[0]+num[3]))
return 0;
if(!isPrime(num[3]+num[6]))
return 0;
if(!isPrime(num[1]+num[4]))
return 0;
if(!isPrime(num[4]+num[7]))
return 0;
if(!isPrime(num[2]+num[5]))
return 0;
if(!isPrime(num[5]+num[8]))
return 0;
return 1;
}
void print_info()
{
for(int i=0;i<9;i++)
{
printf("%d ",num[i]);
}
printf("\n");
}
void test(int pos)
{
if(pos==(9))
{
if(check()==1)
{
print_info();
}
return;
}
for(int i=0;i<N;i++)
{
if(mark[i]!=MARK)
{
num[pos]=i+1;
mark[i]=MARK;
test(pos+1);
mark[i]=INIT;
}
}
}
运行结果：
1 2 5 4 3 8 7 10 9
1 2 5 4 9 8 7 10 3
1 2 5 10 3 8 7 4 9
1 2 5 10 9 8 7 4 3
1 4 7 2 3 10 5 8 9
1 4 7 2 9 10 5 8 3
1 10 7 2 3 4 5 8 9
1 10 7 2 9 4 5 8 3
2 1 6 3 4 7 8 9 10
2 1 6 3 10 7 8 9 4
2 1 6 9 4 7 8 3 10
2 1 6 9 10 7 8 3 4
2 3 8 1 4 9 6 7 10
2 3 8 1 10 9 6 7 4
2 9 8 1 4 3 6 7 10
2 9 8 1 10 3 6 7 4
3 2 5 4 1 6 9 10 7
3 2 5 10 1 6 9 4 7
3 4 7 8 9 10 5 2 1
3 4 7 10 1 6 9 2 5
3 4 9 2 1 10 5 6 7
3 4 9 10 1 2 7 6 5
3 8 5 4 9 2 7 10 1
3 8 5 10 9 2 7 4 1
3 10 7 4 1 6 9 2 5
3 10 7 8 9 4 5 2 1
3 10 9 2 1 4 5 6 7
3 10 9 4 1 2 7 6 5
4 1 6 3 2 5 10 9 8
4 1 6 9 2 5 10 3 8
4 3 8 7 10 9 6 1 2
4 3 8 9 2 5 10 1 6
4 3 10 1 2 9 6 5 8
4 3 10 9 2 1 8 5 6
4 7 6 3 10 1 8 9 2
4 7 6 9 10 1 8 3 2
4 9 8 3 2 5 10 1 6
4 9 8 7 10 3 6 1 2
4 9 10 1 2 3 6 5 8
4 9 10 3 2 1 8 5 6
5 2 1 8 3 4 9 10 7
5 2 1 8 3 10 9 4 7
5 2 1 8 9 4 3 10 7
5 2 1 8 9 10 3 4 7
5 2 3 6 1 4 7 10 9
5 2 3 6 1 10 7 4 9
5 2 9 6 1 4 7 10 3
5 2 9 6 1 10 7 4 3
5 6 7 2 1 4 3 10 9
5 6 7 2 1 4 9 10 3
5 6 7 2 1 10 3 4 9
5 6 7 2 1 10 9 4 3
5 8 3 2 9 4 1 10 7
5 8 3 2 9 10 1 4 7
5 8 9 2 3 4 1 10 7
5 8 9 2 3 10 1 4 7
6 1 2 7 4 3 10 9 8
6 1 2 7 4 9 10 3 8
6 1 2 7 10 3 4 9 8
6 1 2 7 10 9 4 3 8
6 1 4 5 2 3 8 9 10
6 1 4 5 2 9 8 3 10
6 1 10 5 2 3 8 9 4
6 1 10 5 2 9 8 3 4
6 5 8 1 2 3 4 9 10
6 5 8 1 2 3 10 9 4
6 5 8 1 2 9 4 3 10
6 5 8 1 2 9 10 3 4
6 7 4 1 10 3 2 9 8
6 7 4 1 10 9 2 3 8
6 7 10 1 4 3 2 9 8
6 7 10 1 4 9 2 3 8
7 4 1 10 3 2 9 8 5
7 4 1 10 9 2 3 8 5
7 4 3 6 1 10 5 2 9
7 4 3 10 9 8 1 2 5
7 4 9 6 1 10 5 2 3
7 4 9 10 3 8 1 2 5
7 6 5 4 1 2 3 10 9
7 6 5 4 1 2 9 10 3
7 6 5 10 1 2 3 4 9
7 6 5 10 1 2 9 4 3
7 10 1 4 3 2 9 8 5
7 10 1 4 9 2 3 8 5
7 10 3 4 9 8 1 2 5
7 10 3 6 1 4 5 2 9
7 10 9 4 3 8 1 2 5
7 10 9 6 1 4 5 2 3
8 3 2 9 4 1 10 7 6
8 3 2 9 10 1 4 7 6
8 3 4 5 2 9 6 1 10
8 3 4 9 10 7 2 1 6
8 3 10 5 2 9 6 1 4
8 3 10 9 4 7 2 1 6
8 5 6 3 2 1 4 9 10
8 5 6 3 2 1 10 9 4
8 5 6 9 2 1 4 3 10
8 5 6 9 2 1 10 3 4
8 9 2 3 4 1 10 7 6
8 9 2 3 10 1 4 7 6
8 9 4 3 10 7 2 1 6
8 9 4 5 2 3 6 1 10
8 9 10 3 4 7 2 1 6
8 9 10 5 2 3 6 1 4
9 2 5 4 1 6 3 10 7
9 2 5 10 1 6 3 4 7
9 4 3 2 1 10 5 6 7
9 4 3 10 1 2 7 6 5
9 4 7 8 3 10 5 2 1
9 4 7 10 1 6 3 2 5
9 8 5 4 3 2 7 10 1
9 8 5 10 3 2 7 4 1
9 10 3 2 1 4 5 6 7
9 10 3 4 1 2 7 6 5
9 10 7 4 1 6 3 2 5
9 10 7 8 3 4 5 2 1
10 1 6 3 2 5 4 9 8
10 1 6 9 2 5 4 3 8
10 3 4 1 2 9 6 5 8
10 3 4 9 2 1 8 5 6
10 3 8 7 4 9 6 1 2
10 3 8 9 2 5 4 1 6
10 7 6 3 4 1 8 9 2
10 7 6 9 4 1 8 3 2
10 9 4 1 2 3 6 5 8
10 9 4 3 2 1 8 5 6
10 9 8 3 2 5 4 1 6
10 9 8 7 4 3 6 1 2