什么是数独
数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
解决思路
1、遍历数独表，找出数字为空（以0填充）的表格；
2、找出每个数据中空的表格中可以填充的数字；
3、找到其中可以填充的数字个数最少的表格；
4、将每个数字分别填充到该表格中；
5、递归重复步骤1-4，直到表格中不再有数字为0的表格
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <iostream>#include <ctime>using namespace std;struct Position{ int row; int col; int *res;};Position* findMinBlank(int board[][9]){ int *validNums(int board[][9], int row, int col); Position *pos = new Position(); pos->res = 0; int *res; int total=0, minum = 10; for(int i=0; i<9; ++i) for(int j=0; j<9; ++j) { if(board[i][j]!=0) continue; res = validNums(board, i, j); total = 0; for(int p=0; p<9; ++p) { if(res[p]!=0) { ++ total; } } if(total<minum) { delete []pos->res; pos->row = i; pos->col = j; pos->res = res; minum = total; } else delete []res; } return pos;}int *validNums(int board[][9], int row, int col){ int *res = new int[9] {1,2,3,4,5,6,7,8,9}; for (int i = 0; i < 9; i++) { res[board[row][i]-1] = 0; res[board[i][col]-1] = 0; } int p = row / 3 * 3; int q = col / 3 * 3; for (int x = p; x < p + 3; x++) for (int y = q; y < q + 3; y++) { res[board[x][y]-1] = 0; } return res;}void printResult(int result[][9] ){ for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cout << result[i][j] << " "; } cout << endl; } cout << endl;}void sudoku(int board[][9]){ Position *pos = findMinBlank(board); if(!pos->res) { cout<<"time:"<<clock()/1e6<<endl; printResult(board); return; } for(int i=0;i<9;++i) { if(pos->res[i]==0) continue; board[pos->row][pos->col] = pos->res[i]; sudoku(board); } board[pos->row][pos->col] = 0; delete pos->res; delete pos;}int main(){ int start = clock(); cout<<start/1e6<<endl; int board[][9] = { 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 4, 0, 7, 0, 0, 8, 0, 0, 0, 3, 0, 0, 0, 0, 1, 0, 9, 0, 0, 0, 0, 3, 0, 0, 4, 0, 0, 2, 0, 0, 0, 5, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 6, 0, 0, 0 }; printResult(board); sudoku(board); int end = clock(); cout <<"time:" << (end - start)/1e6 << endl; return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/zhaoqianglao4005/article/details/119997366
