华为2016研发 数独游戏
题目：版权声明：本文为博主原创文章，未经博主允许不得转载。
描述
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。
输入：
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出：
完整的9X9盘面数组
知识点
查找,搜索,排序
运行时间限制
10M
内存限制
128
输入
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出
完整的9X9盘面数组
Sample Input
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
思路：回溯法
代码：
1 #include <iostream>
2 using namespace std;
3
4 int mat;
5 bool flag = false;
6
7 bool isCheck(int n, int key)
8 {
9 //判断横行
10 for (int col = 0; col < 9; ++col)
11 {
12 int row = n / 9;
13 if (mat == key)
14 return false;
15 }
16
17 //判断竖行
18 for (int row = 0; row < 9; ++row)
19 {
20 int col = n % 9;
21 if (mat == key)
22 return false;
23 }
24
25 //计算小九宫格内坐标
26 int x = n / 9 / 3 * 3;
27 int y = n % 9 / 3 * 3;
28
29 //判断九宫格内是否合法
30 for (int row = x; row < x + 3; ++row)
31 {
32 for (int col = y; col < y + 3; ++col)
33 {
34 if (mat == key)
35 return false;
36 }
37 }
38
39 return true;
40 }
41
42 void dfs(int n)
43 {
44 if (n > 80)
45 {
46 flag = true;
47 return;
48 }
49
50 if (mat != 0)
51 dfs(n + 1);
52 else
53 {
54 for (int i = 1; i <= 9; ++i)
55 {
56 if (isCheck(n, i))
57 {
58 mat = i;
59 dfs(n + 1);
60 //如果flag==true说明已经构造完成
61 if (flag == true)
62 return;
63 //不成功，回溯
64 mat = 0;
65 }
66 }
67 }
68 }
69
70 int main()
71 {
72 for (int i = 0; i < 9; ++i)
73 {
74 for (int j = 0; j < 9; ++j)
75 {
76 cin >> mat;
77 }
78 }
79 // int temp = {
80 // 1 ,0 ,3 ,0 ,0, 0, 5, 0, 9,
81 // 0, 0, 2, 1, 0, 9, 4, 0, 0,
82 // 0 ,0 ,0 ,7 ,0 ,4 ,0 ,0 ,0,
83 // 3 ,0 ,0 ,5 ,0 ,2 ,0 ,0 ,6,
84 // 0, 6, 0 ,0, 0 ,0 ,0, 5 ,0,
85 // 7 ,0 ,0 ,8 ,0 ,3 ,0, 0 ,4,
86 // 0 ,0 ,0 ,4 ,0 ,1 ,0 ,0 ,0,
87 // 0 ,0 ,9 ,2, 0 ,5 ,8 ,0 ,0,
88 // 8, 0, 4 ,0, 0 ,0 ,1 ,0 ,7
89 // };
90 // for (int i = 0; i < 9; ++i)
91 // {
92 // for (int j = 0; j < 9; ++j)
93 // {
94 // mat = temp;
95 // }
96 // }
97 dfs(0);
98 for (int i = 0; i < 9; ++i)
99 {
100 for (int j = 0; j < 8; ++j)
101 {
102 cout << mat <<' ';
103 }
104 cout << mat;
105 if(i != 8)
106 cout << endl;
107 }
108 }
页:
[1]