数独问题

题目描述

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。 输入： 包含已知数字的9X9盘面数组[空缺位以数字0表示] 输出： 完整的9X9盘面数组

输入描述: 包含已知数字的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

代码块

#include <iostream> #include <vector> using namespace std; vector<vector<int>> vec(9, vector<int>(9)); bool flag = false; void output() { for (int i = 0; i < 9; ++i) { for (int j = 0; j < 8; ++j) { cout << vec[i][j] << ' '; } cout << vec[i][8] << endl; } } bool check(int n, int key) { //行 for (int i = 0; i < 9; ++i) { int j = n / 9; if (vec[j][i] == key) { return false; } } //列 for (int i = 0; i < 9; ++i) { int j = n % 9; if (vec[i][j] == key) { return false; } } //九宫格 int m = n / 9 / 3 * 3; int k = n % 9 / 3 * 3; for (int i = m; i < m + 3; ++i) { for (int j = k; j < k + 3; ++j) { if (vec[i][j] == key) { return false; } } } return true; } //递归深度优先 void DFS(int n) { if (n > 80) { flag = true; return; } if (vec[n / 9][n % 9] != 0) { DFS(n + 1); } else { for (int i = 1; i <= 9; ++i) { if (check(n, i)) { vec[n / 9][n % 9] = i; DFS(n + 1); // if (flag) return; vec[n / 9][n % 9] = 0; //不满足则还原当前位 } } } } int main() { for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { cin >> vec[i][j]; } } DFS(0); // 从0格开始 output(); return 0; }