赞
踩
作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
问题描述:数独(Sudoku)是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字,推算出所有剩余空格的数字,并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9,并且不重复。
例如:
输入
输出
包含已知数字的9X9盘面数组[空缺位以数字0表示]
完整的9X9盘面数组
输入:
- 0 9 2 4 8 1 7 6 3
- 4 1 3 7 6 2 9 8 5
- 8 6 7 3 5 9 4 1 2
- 6 2 4 1 9 5 3 7 8
- 7 5 9 8 4 3 1 2 6
- 1 3 8 6 2 7 5 9 4
- 2 7 1 5 3 8 6 4 9
- 3 8 6 9 1 4 2 5 7
- 0 4 5 2 7 6 8 3 1
输出:
- 5 9 2 4 8 1 7 6 3
- 4 1 3 7 6 2 9 8 5
- 8 6 7 3 5 9 4 1 2
- 6 2 4 1 9 5 3 7 8
- 7 5 9 8 4 3 1 2 6
- 1 3 8 6 2 7 5 9 4
- 2 7 1 5 3 8 6 4 9
- 3 8 6 9 1 4 2 5 7
- 9 4 5 2 7 6 8 3 1
本题是数独问题,采用深度优先遍历法,一个个输入,若某个点没有合适数值,则返回到上个点重新找合适点,直到所有点都完美填充。
VaildExist函数用来判断该位置是否能放置数值m,数独中某行某列某个3*3的方针不能有重复数字;Find函数找寻数独表中的下一个0点位置,将row和col刷新,若没0点了,则说明填充完毕了;DFS是深度优先遍历法的主函数,用flag表示当前数据填充是否合适,col满9则row进1,即进入下一行,用Find判断还有0点没,若还有,则将row和col刷新到最近的0点位置,然后1-9依次填充,若有合适值填充进去,则继续执行DFS,DFS如果返回的是错误结果,那之前填充的数值要换掉,继续找下一个合适的,若找完都没有合适的,就再返回到上一个填充数的位置并进行数值更换,以此类推,直到某次DFS返回的是true,则表示完成数独表的填充。
- #include<iostream>
- #include<vector>
- #include<string>
- using namespace std;
- // 判断该位置是否能放置m,即同行同列同3*3方阵是否存在m
- bool ValidExist(vector<vector<int>> sudoku, int i, int j, int m)
- {
- //判断所在行
- for (int k = 0; k < 9; ++k)
- {
- if (sudoku[i][k] == m)
- return false;
- }
- //判断所在列
- for (int k = 0; k < 9; ++k)
- {
- if (sudoku[k][j] == m)
- return false;
- }
- //判断所在3*3方阵
- int Lrow = i / 3 * 3;
- int Lcol = j / 3 * 3;
- for (int row = Lrow; row < Lrow + 3; ++row)
- for (int col = Lcol; col < Lcol + 3; ++col)
- {
- if (sudoku[row][col] == m)
- return false;
- }
- return true;
- }
- // 找寻数独表的0点
- bool Find(vector<vector<int>> sudoku, int &row, int &col)
- {
- int i, j;
- while (row < 9 && col < 9)
- {
- if (sudoku[row][col] == 0)
- return true;
- else
- {
- col++;
- if (col == 9)
- {
- col = 0;
- row++;
- }
- }
- }
- return false;
- }
- // 深度优先遍历法
- bool DFS(vector<vector<int>> &sudoku, int row, int col)
- {
- bool flag = false;
- if (col > 8)
- {
- col = col % 9;
- row++;
- }
- // 如果没有0点了,则表示完成了填充
- if (!Find(sudoku, row, col))
- return true;
- // 从1开始赋值,若填写某个数值后,其他0点位置无法找到合适值,则数值递进再次尝试
- for (int m = 1; m <= 9; m++)
- {
- if (ValidExist(sudoku, row, col, m))
- {
- sudoku[row][col] = m;
- flag= DFS(sudoku, row, col+1);
- if (flag == false)
- continue;
- else
- return true;
- }
- }
- // 若没有合适值,将当前位置置0,返回false,使上个填充数据再更换其他数值尝试
- if (flag == false)
- {
- sudoku[row][col] = 0;
- return false;
- }
- }
-
- int main()
- {
- vector<vector<int>> sudoku(9, vector<int>(9, 0));
- for (int i = 0; i < 9; ++i)
- for (int j = 0; j < 9; ++j)
- cin >> sudoku[i][j];
- DFS(sudoku, 0, 0);
- for (int i = 0; i < 9; ++i)
- {
- for (int j = 0; j < 9; ++j)
- cout << sudoku[i][j] << " ";
- cout << endl;
- }
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。