九宫格数独求解

1. 数独规则简介

数独（Sudoku）是经典的约束满足问题。标准九宫格数独是一个 9 x 9 的棋盘，需要在空格中填入 1 ~ 9，并满足以下约束：

1. 每一行不能出现重复数字。
2. 每一列不能出现重复数字。
3. 每一个 3 x 3 的小宫格中不能出现重复数字。

从算法角度看，数独非常适合用回溯法解决。因为它本质上是一个“试填 + 检查 + 撤销”的搜索过程。

2. 问题求解

该代码实现了一个数独求解器，使用回溯算法穷举所有可能的填法，求解 N×N（N=9）的标准数独问题。

主要功能：

• isValid 函数：检查在指定位置 (x, y) 填入数字 k 是否合法，需满足数独规则——即该数字在所在行、列和 3×3 宫内不重复。
• backtracking 函数：采用回溯法递归填充空格（值为0的位置），每找到一个空格尝试填入1~9中合法的数字，直到填满整个棋盘，输出一个解，并统计总解数。
• solve 函数：初始化一个全零的 N×N 棋盘，并启动回溯求解过程。
• main 函数：读取输入（实际未使用，固定求解 9×9 空数独），调用 solve(N) 开始计算。

TIP

⚠️ 注意：当前代码求解的是空数独（初始棋盘全为0），会枚举所有可能的完整数独终盘，因此解的数量非常庞大（9×9 数独共有约 6.67×10²¹ 个有效解），实际运行将极其耗时。

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int N = 9;
int result = 0;

bool isValid(vector<vector<int>>& board, int x, int y, int k) {
  int n = board.size();
  for (int i = 0; i < n; i++) {
    if (board[i][y] == k) return false;  // 列检查
  }
  for (int j = 0; j < n; j++) {
    if (board[x][j] == k) return false;  // 行检查
  }
  int t = sqrt(n);
  int startX = (x / t) * t;
  int startY = (y / t) * t;
  for (int i = startX; i < startX + t; i++) {
    for (int j = startY; j < startY + t; j++) {
      if (board[i][j] == k) { return false; }
    }
  }
  return true;
}

void backtracking(vector<vector<int>>& board, int n, int last) {
  if (last == 0) {
    result++;
    cout << "Solution " << result << ":\n";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        cout << board[i][j] << (j == n - 1 ? '\n' : ' ');
      }
    }
    cout << endl;
    return;
  }

  // 找到第一个空格
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (board[i][j] == 0) {
        for (int k = 1; k <= n; k++) {
          if (isValid(board, i, j, k)) {
            board[i][j] = k;
            backtracking(board, n, last - 1);
            board[i][j] = 0;
          }
        }
        return;  // 只处理一个空格，避免重复遍历
      }
    }
  }
}

void solve(int n) {
  vector<vector<int>> board(n, vector<int>(n, 0));
  backtracking(board, n, n * n);
  cout << "Total solutions = " << result << endl;
}

int main() {
  int n;
  cin >> n;
  solve(N);
  return 0;
}