华为2016研发 数独游戏

jy166102

　　题目：



版权声明：本文为博主原创文章，未经博主允许不得转载。



描述
　　问题描述：数独（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[9][9];
  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[row][col] == key)
14             return false;
15     }
16
17     //判断竖行
18     for (int row = 0; row < 9; ++row)
19     {
20         int col = n % 9;
21         if (mat[row][col] == 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[row][col] == 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[n / 9][n % 9] != 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[n / 9][n % 9] = i;
59                 dfs(n + 1);
60                 //如果flag==true说明已经构造完成
61                 if (flag == true)
62                     return;
63                 //不成功，回溯
64                 mat[n / 9][n % 9] = 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[j];
77         }
78     }
79 //      int temp[9][9] = {
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[j] = temp[j];
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[j] <<' ';
103         }
104         cout << mat[8];
105         if(i != 8)
106             cout << endl;
107     }
108 }