给定一个整数 k，我们的任务是在遵守以下规则集的前提下，生成一个包含 k 个空单元格的 9×9 数独网格：
- 在所有 9 个 3×3 子矩阵中，元素应为 1-9，且不能重复。
- 在所有行中，应包含 1-9 之间的元素，且不能重复。
- 在所有列中，应包含 1-9 之间的元素，且不能重复。
朴素方法
- 随机选取 1-9 之间的任意数字。
- 检查将其放入当前单元格（行、列和宫）是否安全。
- 如果安全，则放置该数字，并递增移动到下一个位置，然后回到步骤 1。
- 如果不安全，则不递增，直接回到步骤 1。
- 一旦矩阵被填满，随机移除 k 个元素以完成游戏。
高效方法
如果我们能理解这个游戏中的模式，我们就可以优化解决方案。我们可以观察到，最初所有对角线上的 3×3 矩阵与其他 3×3 相邻矩阵是独立的，因为其他的矩阵都是空的。
> 3 8 5 0 0 0 0 0 0
> 9 2 1 0 0 0 0 0 0
> 6 4 7 0 0 0 0 0 0
> 0 0 0 1 2 3 0 0 0
> 0 0 0 7 8 4 0 0 0
> 0 0 0 6 9 5 0 0 0
> 0 0 0 0 0 0 8 7 3
> 0 0 0 0 0 0 9 6 2
> 0 0 0 0 0 0 1 4 5
我们可以观察到，在上面的矩阵中，对角线矩阵最初与其他空矩阵是独立的。因此，如果我们先填充它们，我们只需要进行宫检查，从而不需要列/行检查。
其次，当我们填充剩余的非对角线元素时，我们不需要使用随机生成器，但我们可以通过检查 1 到 9 来递归地填充。
逐步方法：
- 填充所有对角线 3×3 矩阵。
- 递归地填充剩余的非对角线 矩阵。对于每一个要填充的单元格，我们会尝试所有数字，直到找到一个可以放置的安全数字。
- 一旦矩阵完全填满，随机移除 k 个元素以完成游戏。
C++
`
// C++ program to generate a valid sudoku
// with k empty cells
#include
using namespace std;
// Returns false if given 3x3 block contains num
// Ensure the number is not used in the box
bool unUsedInBox(vector<vector> &grid, int rowStart, int colStart, int num) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[rowStart + i][colStart + j] == num) {
return false;
}
}
}
return true;
}
// Fill a 3x3 matrix
// Assign valid random numbers to the 3x3 subgrid
void fillBox(vector<vector> &grid, int row, int col) {
int num;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
do {
// Generate a random number between 1 and 9
num = (rand() % 9) + 1;
} while (!unUsedInBox(grid, row, col, num));
grid[row + i][col + j] = num;
}
}
}
// Check if it's safe to put num in row i
// Ensure num is not already used in the row
bool unUsedInRow(vector<vector> &grid, int i, int num) {
for (int j = 0; j < 9; j++) {
if (grid[i][j] == num) {
return false;
}
}
return true;
}
// Check if it's safe to put num in column j
// Ensure num is not already used in the column
bool unUsedInCol(vector<vector> &grid, int j, int num) {
for (int i = 0; i < 9; i++) {
if (grid[i][j] == num) {
return false;
}
}
return true;
}
// Check if it's safe to put num in the cell (i, j)
// Ensure num is not used in row, column, or box
bool checkIfSafe(vector<vector> &grid, int i, int j, int num) {
return (unUsedInRow(grid, i, num) && unUsedInCol(grid, j, num) &&
unUsedInBox(grid, i - i % 3, j - j % 3, num));
}
// Fill the diagonal 3x3 matrices
// The diagonal blocks are filled to simplify the process
void fillDiagonal(vector<vector> &grid) {
for (int i = 0; i < 9; i = i + 3) {
// Fill each 3x3 subgrid diagonally
fillBox(grid, i, i);
}
}
// Fill remaining blocks in the grid
// Recursively fill the remaining cells with valid numbers
bool fillRemaining(vector<vector> &grid, int i, int j) {
// If we‘ve reached the end of the grid
if (i == 9) {
return true;
}
// Move to next row when current row is finished
if (j == 9) {
return fillRemaining(grid, i + 1, 0);
}
// Skip if cell is already filled
if (grid[i][j] != 0) {
return fillRemaining(grid, i, j + 1);
}
// Try numbers 1-9 in current cell
for (int num = 1; num <= 9; num++) {
if (checkIfSafe(grid, i, j, num)) {
grid[i][j] = num;
if (fillRemaining(grid, i, j + 1)) {
return true;
}
grid[i][j] = 0;
}
}
return false;
}