问题描述:
数独(Sudoku)是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字,推算出所有剩余空格的数字,并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9,并且不重复。
例如:
输入
输出:
数据范围:输入一个 9*9 的矩阵
输入描述:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出描述:
完整的9X9盘面数组
示例1
输入:
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
完整代码
#include<iostream>
#include<vector>
#include<set>
using namespace std;
void sudoku(vector<vector<int>>& val, int i, int j, bool& flag) {//判断是否遍历成功if (i >= 9 || j >= 9) {flag = 1;//遍历成功,置为一return;}set<int> s;if (val[i][j] == 0) {for (int k = 0; k < 9; k++) {s.insert(val[i][k]);s.insert(val[k][j]);}int r = i / 3, l = j / 3;for (int h = r * 3; h < r * 3 + 3; h++) {for (int k = l * 3; k < l * 3 + 3; k++) {s.insert(val[h][k]);}}for (int k = 1; k < 10; k++) {if (!flag && s.find(k) == s.end()) {val[i][j] = k;if (j < 8)sudoku(val, i, j + 1, flag);elsesudoku(val, i + 1, 0, flag);}}if (flag == 0) {val[i][j] = 0;return;}}else {if (j < 8)sudoku(val, i, j + 1, flag);elsesudoku(val, i + 1, 0, flag);}
}
int main() {vector<vector<int>> val(9, vector<int>(9));for (int i = 0; i < 9; i++)for (int j = 0; j < 9; j++)cin >> val[i][j];bool flag = false;sudoku(val, 0, 0, flag);for (int i = 0; i < 9; i++) {for (int j = 0; j < 8; j++)cout << val[i][j] << " ";cout << val[i][8] << endl;}return 0;
}