数独(すうどく,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 **************************************************************/
原文链接: https://www.cnblogs.com/notonlycodeit/p/3395128.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/110158
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!