数独问题
题目描述
数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。（50分）
输入描述:
输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的数字。
输出描述:
输出九行，每行九个空格隔开的数字，为解出的答案。
基本思路
需要判断同一列同一行以及同一个九宫格的数值是否有重复，如果有冲突，则需要进行下一个数值的尝试。如果此次没有找到合适的数值，则需要作出栈操作，也就是回溯到上一级。在上一级的基础数值上再进行尝试，请勿再重新头开始。否则从1开始尝试，可以尝试出一个值；但是当处理下一个数值时发现有冲突，需要进行出栈操作。但此时又从1开始尝试，第一次尝试出的值还是之前那个值，此时处理下一个数值还是会发生冲突，也就是无法绕开出现矛盾的那个数值，从而造成了死循环，无法正常得到结果。
代码如下
#include <stdio.h> int main() { int test[9][9] = { 0,9,0,0,0,0,0,6,0, 8,0,1,0,0,0,5,0,9, 0,5,0,3,0,4,0,7,0, 0,0,8,0,7,0,9,0,0, 0,0,0,9,0,8,0,0,0, 0,0,6,0,2,0,7,0,0, 0,8,0,7,0,5,0,4,0, 2,0,5,0,0,0,8,0,7, 0,6,0,0,0,0,0,9,0, }; int i,j; int data[81][2] = {0}; //存储待处理的坐标二维数组，最多需要处理81个数据 int count = 0; //记录待处理的坐标，count表示需处理的坐标总数 for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ if(test[i][j] == 0){ data[count][0] = i; data[count][1] = j; count++; } } } printf("count = %d\n",count); int okflag = 1; int nowstep = 0; //nowstep指示当前处理的待处理位置，nowstep==0为第一个，nowstep==count-1为最后一个 int n = 0; int si,sj; while(nowstep < count){ si = data[nowstep][0]; sj = data[nowstep][1]; // n = 1; n = test[si][sj]; //每次都从当前数继续，因为下面有test[si][sj] = n;一步，表示前面的已不合适，所以没必要再从1开始，会造成矛盾。 // okflag = 1; //冲突检测 while(n <= 9){ okflag = 1; //每一次标志需要重新设置 for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ //冲突检测，此举代码表示当处于检测区域时，如果已经出现n，则表示存在冲突，此时需要进行下一步的检测 //而当检测区域既不处于同一行，也不属于同一列，同时也不属于同一个方格时 //s==i||t==j||((s/3)*3+t/3)==((i/3)*3+j/3)为0，也就没有检测的必要了，减少检测的次数。 //而当处于同一行列和一个方框时，必须要检测是否已经存在的数值n。 // if(i == si||j == sj||(((i/3)*3 + j/3)==((si/3)*3 + sj/3))&&test[i][j] == n){ if((i == si||j == sj||(((i/3)*3 + j/3)==((si/3)*3 + sj/3)))&&test[i][j] == n){ okflag = 0; //发生冲突，退出 break; } } if(okflag == 0){ //发生冲突，n++继续尝试 break; } } if(okflag == 1){ //当前值可用，退出n值尝试的while循环 break; } n++; } //如果标志为1，表示当前n值可以入栈，然后操作下一个为0的数独处 if(okflag == 1){ test[si][sj] = n; nowstep++; } //如果标志为0，表示当前n值有冲突，需要出栈处理，初始化当前冲突除为0，相当于没有检测此步 else if(okflag == 0){ test[si][sj] = 0; nowstep--; } } //结果输出 for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ printf("%d,",test[i][j]); } printf("\n"); } return 0; }
