填字游戏

　

填字游戏

题目描述：设计一个算法求解填字游戏问题，在3x3个方格的方阵中要填入0-9内的某9数字，每个方格填一个整数，使所有相邻的两个方格内的两个整数之和为素数。试求出所有满足条件的填法的个数。详见代码及注释，总体思路：DFS + 回溯。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <iOStream>

#include <cmath>

using namespace std;

int square[4][4];

int tag[10];

int ans = 0;

int S (int n) //判断是不是素数

{

for (int i = 2;i <= sqrt(n);i++)

{

     if (n % i == 0)

             return 0;

}

return 1;

}

bool judge(int x,int y,int num)

{

if (tag[num] == 1)

     return false;

if (x - 1 >= 1)  //判断当前位置上面的位置加上该数是不是素数

{

     if (!S(square[x - 1][y] + num))

             return false;

}

if (y - 1 >= 1)  //判断当前位置左侧的位置加上该数是不是素数

{

     if (!S(square[x][y - 1] + num))

             return false;

}

return true;

}

void dfs(int x,int y)

{

if (x == 4)

{

     ans++;

     return;

}

for (int i = 0;i < 10;i++)

{

     if (judge(x,y,i)) //如果判断条件成立

     {

             tag[i] = 1;//将已经用过的数标记为置1

             square[x][y] = i;//将当前位置的数置为i

             if (y!= 3)//如果没有到底，深度搜索

                      dfs(x,y+1);

             else      //否则，x+1

                      dfs(x+1,1);

             square[x][y] = 0; //回溯

             tag[i] = 0;

     }

}

}

int main()

{

memset(tag,0,sizeof(tag));

dfs(1,1);

cout<<ans<<endl;

return 0;

}

相关阅读