数独

数独（すうどく，Sudoku）是一种逻辑性的数字填充游戏。玩家需要根据 9×9 方格上的已知数字，推理出所有剩余空格的数字，使其满足每一行、列、宫中的数字均含1-9，不重复。游戏设计者会提供一部份数字，使其有且仅有一个答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

以下是使用回溯法求解数独问题的 C++ 实现代码：

 1 /**************************************************************
 2 problem : 回溯法求解数独问题
 3 author  : 林秋伟
 4 time    : 2013-10-29
 5 **************************************************************/
 6 #include <iostream>
 7 #include <cstring>
 8 using namespace std;
 9 
10 int sudoku[10][10];     //sudoku[i][j]用于存储第i行,第j列的数字
11 bool row[10][10];       //row[i][num]用于标识第i行是否出现数字num
12 bool col[10][10];       //col[i][num]用于标识第i列是否出现数字num
13 bool grid[4][4][10];    //grid[ith][jth][num]用于标识第ith行,第jth列的宫(3×3)是否出现数字num
14 
15 //搜索方向：1,1 -> 1,9 -> 2,1 -> 2,9 -> ... -> 9,1 -> 9,9
16 bool DFS(int x, int y){
17     if(x==10) return 1;
18     bool flag=0;
19     if(sudoku[x][y]!=0){
20         if(y==9) flag=DFS(x+1, 1);
21         else flag=DFS(x, y+1);
22         if(flag) return 1;
23     }
24     else{
25         int ith=(x+2)/3;
26         int jth=(y+2)/3;
27         for(int num=1; num<=9; num++){
28             if(!row[x][num] && !col[y][num] && !grid[ith][jth][num]){
29                 sudoku[x][y]=num;
30                 row[x][num]=1;
31                 col[y][num]=1;
32                 grid[ith][jth][num]=1;
33                 if(y==9) flag=DFS(x+1, 1);
34                 else flag=DFS(x, y+1);
35                 if(flag) return 1;
36                 //回溯
37                 sudoku[x][y]=0;
38                 row[x][num]=0;
39                 col[y][num]=0;
40                 grid[ith][jth][num]=0;
41             }
42         }
43     }
44     return 0;
45 }
46 
47 int main(){
48     int i, j;
49     memset(row, 0, sizeof(row));
50     memset(col, 0, sizeof(col));
51     memset(grid, 0, sizeof(grid));
52     //按照从左到右,从上到下的顺序输入,要填的位置用0代替
53     for(i=1; i<=9; i++){
54         for(j=1; j<=9; j++){
55             cin>>sudoku[i][j];
56             int num=sudoku[i][j];
57             if(num!=0){
58                 row[i][num]=1;
59                 col[j][num]=1;
60                 int ith=(i+2)/3;
61                 int jth=(j+2)/3;
62                 grid[ith][jth][num]=1;
63             }
64         }
65     }
66     DFS(1, 1);
67     cout<<"the solution is:"<<endl;
68     for(i=1; i<=9; i++){
69         cout<<sudoku[i][1];
70         for(j=2; j<=9; j++) cout<<" "<<sudoku[i][j];
71         cout<<endl;
72     }
73     return 0;
74 }
75 /**************************************************************
76 TestCase
77 Input:
78 5 3 0 0 7 0 0 0 0
79 6 0 0 1 9 5 0 0 0
80 0 9 8 0 0 0 0 6 0
81 8 0 0 0 6 0 0 0 3
82 4 0 0 8 0 3 0 0 1
83 7 0 0 0 2 0 0 0 6
84 0 6 0 0 0 0 2 8 0
85 0 0 0 4 1 9 0 0 5
86 0 0 0 0 8 0 0 7 9
87 Output:
88 the solution is:
89 5 3 4 6 7 8 9 1 2
90 6 7 2 1 9 5 3 4 8
91 1 9 8 3 4 2 5 6 7
92 8 5 9 7 6 1 4 2 3
93 4 2 6 8 5 3 7 9 1
94 7 1 3 9 2 4 8 5 6
95 9 6 1 5 3 7 2 8 4
96 2 8 7 4 1 9 6 3 5
97 3 4 5 2 8 6 1 7 9
98 **************************************************************/