说到数独，或者九宫格，我想大家一定都不陌生，初中高中看的各种杂志上都有这种益智游戏，现在的智能手机上也有人写出了这种游戏，闲暇时候玩玩也能活跃一下脑子。还有看《模仿游戏》这部电影里面，图灵在选拔队友的时候好像出的也是数独的题目。
我本来对数独不是太感兴趣，但是一个偶然的机会看到朋友在玩这个游戏，就想写出一个破解算法，来在朋友面前炫耀一下，也可以顺便复习一下最近学习的C语言。
数独事实上就是一个9*9的一个方阵，之所以又叫九宫格，是因为其中每3*3的方阵为一宫，整个大方阵有九个这样的宫。规则是在每一行每一列填上1~9九个数字，使得各行各列填满且不重复，并且每一宫中的数字也是1~9不重复。
对于算法来讲，主要使用递归，对于数据结构来讲，用二维数组来表示9*9的方阵，然而每一个位置都有两个属性，即数值和所在的宫，所以一开始我先声明了一个结构体来包含这两个属性。然后用一个分配算法来分配各个位置的数字所在的宫。具体的破解算法其实就是让程序去测试每一个位置该填什么数字，需要判断每一行，每一列，每一宫是否有重复，都没有重复则表示成功。如果成功则保留，不成功则退回重新测试。通过输入原始数据来让程序运行，程序执行后如果有解则输出方阵，如果没有则输出无解。具体程序如下（C语言）：
#include<stdio.h>#include<stdlib.h>#define _CRT_SECURE_NO_DEPRECATE#pragma warning(disable:4996)#define N 9struct theNums{int num;//数字int pala;//所在的宫};struct theNums tn[N][N];int result = 0; //结果数void sharePal(struct theNums shnum[N][N]){//分配宫格int row, col;for (row = 1; row <= N; row++){for (col = 1; col <= N; col++){if (row >= 1 && row <= 3){if(col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 1;else if (col >= 4&& col <= 6)shnum[row - 1][col - 1].pala = 2;elseshnum[row - 1][col - 1].pala = 3;}else if (row >= 4 && row <= 6){if (col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 4;else if (col >= 4 && col <= 6)shnum[row - 1][col - 1].pala = 5;elseshnum[row - 1][col - 1].pala = 6;}else{if (col >= 1 && col <= 3)shnum[row - 1][col - 1].pala = 7;else if (col >= 4 && col <= 6)shnum[row - 1][col - 1].pala = 8;elseshnum[row - 1][col - 1].pala = 9;}}}}bool check(struct theNums chenum[N][N], int row, int col, int key){int i, j;//判断行for (i = 0; i < N; i++){if (chenum[row][i].num == key)return false;}//判断列for (j = 0; j<N; j++){if (chenum[j][col].num == key)return false;}//判断所在的宫for (i = 0; i < N; i++){for (j = 0; j < N; j++){if (chenum[i][j].pala == chenum[row][col].pala){if (chenum[i][j].num == key)return false;}}}//可行return true;}int printNum(struct theNums num[N][N]){//输出九宫格result++;printf("第%d个填法为：\n", result);int i, j;for (i = 0; i < N; i++){for (j = 0; j < N; j++){printf("%3d", num[i][j].num);if (j == 2 || j == 5)printf("\t");}printf("\n");if (i == 2 || i == 5)printf("\n");}return 0;}void CrossWords(struct theNums CWnum[N][N], int n){//九宫格破解算法struct theNums temp[N][N];int i, j;for (i = 0; i<9; i++){for (j = 0; j < 9; j++){temp[i][j].num = CWnum[i][j].num;temp[i][j].pala = CWnum[i][j].pala;}}i = n / 9; j = n % 9; //求出第n个数的行数和列数if (CWnum[i][j].num != 0) //已经有原始数据{if (n == 80) //是最后一个格子，输出可行解printNum(temp);else //不是最后一个格子，求下一个格子CrossWords(temp, n + 1);}else //没有数据{for (int k = 1; k <= 9; k++){bool flag = check(temp, i, j, k);if (flag) //第i行、第j列可以是k{temp[i][j].num = k; //设为kif (n == 80)printNum(temp);elseCrossWords(temp, n + 1);temp[i][j].num = 0; //恢复为0，判断下一个k}}}}void main(){printf("请输入数独中的原始数据，没有数据的用0代替。\n");for (int i = 0; i<N; i++){printf("Please Input第%d行Numbers：", i + 1);for (int j = 0; j<N; j++)scanf("%d", &tn[i][j].num);}sharePal(tn);printf("数独的解为：\n\n");CrossWords(tn, 0);if (result == 0)printf("Bad Input,无解!");//printNum(tn);//输出九宫格system("pause");}
举个例子，芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的九宫格游戏，而且它只有一个答案（皮埃斯：人家花3个月才搞出来的程序一跑几秒就跑出来了，是对先人的不敬还是时代发展的必然），如下图：
