程序 = 数据结构+算法
说明：
1. 在计算机内部使用0..8表示1..9。在pc和用户之间的接口使用1..9，这里的人机接口是显示和矩阵初始化配置。
2. 需要一个配置文件，用来配置数独的原始数据，大致内容如下
// memo
// format x,y,v
// line begining with '/' or ' ' will be ignored
1,4,3
1,9,4
数据结构
1. int16_t maze[x][y] 用来表示数独的状态。
a. 如果maze[x][y]<0，那么maze[x][y]上有确定的值为-maze[x][y]。比如，如果maze[0][0]=-7，意思是maze[0][0]是确定的数字为7。
b.如果maze[x][y]>0，表示该x,y位置上可以使用那些可能的数字。比如，如果maze[0][0]=7=B000000111，表示位置[0][0]只可能放0, 1, 2，其他的数字绝对不可能;
2. uint16_t mask[SCALE+1] 用来保存位数的bit表示，比如针对0，mask[0]=000000001。使用mask主要做位运算，计算某个位置上可以放置那些数字
3. int16_t*maze_p[SCALE*3][SCALE] maze_p是对maze的不同视角的解释，包括：以行的角度解释maze，以列的角度解释maze，和以cell(一个宫格)解释的maze。具体作用后面分析算法做解释。
算法：
数独的算法其实很简单，不需要复杂的什么深度搜索，核心思想就是：针对某些element，找到唯一解，然后再多次迭代，依次找到其他的值。如何找唯一解是关键。我们知道，数独的约束条件是：每行、每列和每个cell（宫）都是0..8，不能重复。因此，找唯一解的方法是：统计0..8各个数字出现的可能性，如果可能性只能是1，就是唯一解。
以下面红色maze[0][0]为例：
1. 首先看第一行，maze[0][0]只可能是数字12478，用二进制表示就是 110010110
2. 再看第一列，maze[0][0]只可能是数字023456，用二进制表示就是001111101。和第一个条件与，110010110 && 001111101 = 000010100。这里得出的结论就是，maze[0][0]只能是2和4.
3. 再看第一个cell（宫格）, maze[0][0]只可能是数字125678，用二进制表示就是111100110。和前面的结果与，111100110 && 000010100= 000000100。这里得出的结论就是，maze[0][0]只能是2.
0
5
3
6
3
4
8
7
1
算法的思想是：依次计算每行，每列，和每个宫，计算每个element里面可以存放数字的可能性。如果某个数字的可能性是1，就说明找到了这个element的唯一解。
就这样，多次迭代后，很快就可以算出所有的解。
下面是使用后面的源程序的结果。第一个矩阵是原始数据，'-'表示未确定之数。下面的这个例子经过9次迭代，就算出了结果。
- - - 3 - - - 8 4 - 4 2 5 8 - - - - - - 5 4 - 7 - 9 - 7 8 - 1 - - - 6 - - 6 1 8 5 - - - - - - 3 - 7 - 8 - - - 9 - 7 - - 6 - 8 - 2 - - 4 8 - - - - - 8 - 9 - 4 - 3 - - - 3 - - 5 8 4 - 4 2 5 8 - - - - 8 3 5 4 - 7 - 9 - 7 8 - 1 - - - 6 - - 6 1 8 5 - - - - - - 3 9 7 6 8 - - - 9 - 7 - - 6 - 8 3 2 - - 4 8 - - - - - 8 - 9 - 4 - 3 - - - 3 - - 5 8 4 - 4 2 5 8 - - - - 8 3 5 4 - 7 - 9 - 7 8 - 1 - - - 6 5 - 6 1 8 5 - - - - - - 3 9 7 6 8 - - - 9 - 7 - - 6 - 8 3 2 - 6 4 8 - - - - - 8 2 9 - 4 - 3 - 7 6 3 - - 5 8 4 - 4 2 5 8 - - - - 8 3 5 4 - 7 - 9 - 7 8 - 1 - - - 6 5 - 6 1 8 5 - - - - - - 3 9 7 6 8 - - - 9 - 7 - - 6 2 8 3 2 - 6 4 8 - 5 - 6 - 8 2 9 - 4 - 3 - 7 6 3 - - 5 8 4 - 4 2 5 8 - - - 6 8 3 5 4 6 7 - 9 - 7 8 9 1 - - - 6 5 - 6 1 8 5 - - - - - - 3 9 7 6 8 - - 5 9 - 7 - - 6 2 8 3 2 7 6 4 8 - 5 - 6 1 8 2 9 - 4 - 3 - 7 6 3 - - 5 8 4 - 4 2 5 8 - 7 - 6 8 3 5 4 6 7 - 9 - 7 8 9 1 - 4 - 6 5 - 6 1 8 5 - 9 - 7 - 5 3 9 7 6 8 - - 5 9 4 7 - - 6 2 8 3 2 7 6 4 8 - 5 - 6 1 8 2 9 5 4 7 3 - 7 6 3 - - 5 8 4 - 4 2 5 8 - 7 3 6 8 3 5 4 6 7 - 9 - 7 8 9 1 - 4 3 6 5 - 6 1 8 5 - 9 4 7 - 5 3 9 7 6 8 1 2 5 9 4 7 - - 6 2 8 3 2 7 6 4 8 1 5 9 6 1 8 2 9 5 4 7 3 - 7 6 3 - 2 5 8 4 - 4 2 5 8 9 7 3 6 8 3 5 4 6 7 2 9 1 7 8 9 1 2 4 3 6 5 2 6 1 8 5 3 9 4 7 4 5 3 9 7 6 8 1 2 5 9 4 7 3 1 6 2 8 3 2 7 6 4 8 1 5 9 6 1 8 2 9 5 4 7 3 9 7 6 3 1 2 5 8 4 1 4 2 5 8 9 7 3 6 8 3 5 4 6 7 2 9 1 7 8 9 1 2 4 3 6 5 2 6 1 8 5 3 9 4 7 4 5 3 9 7 6 8 1 2 5 9 4 7 3 1 6 2 8 3 2 7 6 4 8 1 5 9 6 1 8 2 9 5 4 7 3
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include "main.h" int16_t maze[SCALE][SCALE]; uint16_t mask[SCALE+1]; int16_t* maze_p[SCALE*3][SCALE]; char s_buf[1024]; void preConfig() { char *file = "config.txt"; FILE* fh = fopen(file, "r"); char *token; if(!fh) { printf("cannot open %s\n", file); return; } while(fgets(s_buf, 1024, fh)){ int counter = 0; int x=0,y=0,v=0; if(('/' == s_buf[0]) || (' ' == s_buf[0]) || ('\n' == s_buf[0])) continue; token = strtok( s_buf, ","); while(token !=NULL) { if(0 == counter) x = atoi(token); else if(1 == counter) y = atoi(token); else if(2 == counter){ v = atoi(token); break; } counter++; token=strtok(NULL, ","); } //check validation if((x>SCALE) || (y>SCALE) ||(v>SCALE)) { printf("%d %d %d each should be less than %d", x,y,v, SCALE); continue; } else ; //printf("%d %d %d %d\n", x,y,v, counter); if(counter>0) maze[x-1][y-1] = -(v-1); } } void init() { int i,j,m,n; int counter; int x,y; j=1; mask[0]=1; for(i=1;i<SCALE;i++){ j *=2; mask[i]=j; } mask[SCALE] = (2<<(SCALE-1))-1; for(i=0;i<SCALE;i++) for(j=0;j<SCALE;j++) maze[i][j] = mask[SCALE]; counter=0; for(i=0;i<SCALE;i++) { for(j=0;j<SCALE;j++) maze_p[counter][j] = &maze[i][j]; counter++; } for(i=0;i<SCALE;i++) { for(j=0;j<SCALE;j++) maze_p[counter][j] = &maze[j][i]; counter++; } for(i=0;i<CELL_SIZE;i++) for(j=0;j<CELL_SIZE;j++) { for(m=0;m<CELL_SIZE;m++) for(n=0;n<CELL_SIZE;n++) { int t = m*CELL_SIZE+n; x = i*CELL_SIZE + m; y = j*CELL_SIZE + n; maze_p[counter][t] = &maze[x][y]; } counter++; } preConfig(); } char* printB(uint16_t v){ static char string[10]; int i; for(i=0;i<SCALE;i++) string[i] = '0'; i=SCALE; while(i-->0) { string[i] = v%2?'1':'0'; v=v/2; } return string; } void printMaze() { int i,j; for(i=0;i<SCALE;i++) { for(j=0;j<SCALE;j++) { printf("%c ", maze[i][j]>0?'-':(-maze[i][j]+'1')); } printf("\n"); } printf("\n"); } bool isSolved() { int i,j; for(i=0;i<SCALE;i++) for(j=0;j<SCALE;j++) if(maze[i][j]>0) return false; return true; } void statistics(uint8_t* number_static, int16_t value, uint8_t* array, int num) { int i=0; while(i<SCALE) { if(value %2){ number_static[i]++; array[i] = num; //use array to remember the location of the number i } i++; value = value / 2; } } void process() { int i,j; int result; int16_t* element; uint8_t stat[SCALE]; uint8_t loc_marker[SCALE]; for(i=0;i<3*SCALE;i++) { //get the mask for the 9 elements result=0; for(j=0;j<SCALE;j++) { element = maze_p[i][j]; if(*element<=0) result |= mask[-*element]; } //apply the mask to each >0 element for(j=0;j<SCALE;j++) { element = maze_p[i][j]; if(*element>0) *element &= ~result; } //statistics for(j=0;j<SCALE;j++) { stat[j]=0x0; loc_marker[j]=0; } for(j=0;j<SCALE;j++) { element = maze_p[i][j]; if(*element>0) {//to statistics statistics(stat, *element, loc_marker, j); } else { stat[-*element]=0; //means number of j has been decided } } //check statistics results for(j=0;j<SCALE;j++) { if(1 == stat[j]) {//find answer for number of j *maze_p[i][loc_marker[j]] = -j; } } } } int main() { int counter=0; init(); //printMaze(); do{ process(); printMaze(); counter++; }while(!isSolved()); printf("Counter=%d\n",counter); return 1; }
