数独解题算法
什么是数独？
数独是一种逻辑谜题，在一个部分填充的 9x9 网格中，需要用 1 到 9 的数字填充，确保每一行和每一列都唯一地包含 1 到 9 的所有数字。此外，每个 3x3 子网格（也称为方框）也唯一地包含 1 到 9 的所有数字。有几种算法可以有效地解决这个难题。在本教程中，我们将学习如何使用回溯法来解决数独难题。
使用回溯法解决数独
假设给定的 9x9 矩阵代表一个数独网格。其中，空白处用 0 表示。最终输出矩阵（数独网格）将用数字填充。如果不存在解，则返回 false。下图展示了给定数独的问题及其解法 −
在简单的数独求解方法中，算法会生成从 1 到 9 的所有可能数字组合来填充空白单元格。在逐个为每个单元格分配数字后，检查该分配是否有效。这种数独求解方法非常耗时且冗长。
步骤
按照以下步骤使用回溯法 − 解决数独问题。
首先，确定由 0 定义的空单元格。
如果找到空单元格，则检查该数字是否已存在于同一行、同一列或 3x3 子网格中，以此判断是否可以在该单元格中输入数字。
如果可以，则将该数字赋值给该单元格。否则，回溯并再次赋值 0。
示例
在本例中，我们将演示如何使用各种编程语言解决数独问题。
#include <stdio.h>
#define N 9
int grid[N][N] = {
{ 3, 1, 0, 5, 7, 8, 4, 0, 2 },
{ 0, 2, 9, 0, 3, 0, 0, 0, 8 },
{ 4, 0, 0, 6, 2, 9, 0, 3, 1 },
{ 2, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 0, 7, 0, 8, 6, 3, 0, 0, 5 },
{ 8, 0, 1, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 6, 9, 2, 0, 5, 0, 0, 7, 4 },
{ 7, 0, 0, 2, 0, 6, 3, 0, 0 }
};
//检查冷号是否存在
int isPresentInCol(int col, int num) {
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return 1;
return 0;
}
//检查行中是否存在数字
int isPresentInRow(int row, int num) {
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return 1;
return 0;
}
//检查 3x3 框中是否存在数字
int isPresentInBox(int boxStartRow, int boxStartCol, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return 1;
return 0;
}
//解答后打印数独网格
void sudokuGrid() {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if(col == 3 || col == 6)
printf(" | ");
printf("%d ", grid[row][col]);
}
if(row == 2 || row == 5) {
printf("
");
for(int i = 0; i<N; i++)
printf("---");
}
printf("
");
}
}
//获取空位置并更新行和列
int findEmptyPlace(int *row, int *col) {
for (*row = 0; *row < N; (*row)++)
for (*col = 0; *col < N; (*col)++)
//标记为 0 为空
if (grid[*row][*col] == 0)
return 1;
return 0;
}
int isValidPlace(int row, int col, int num) {
//当在列、行和当前 3x3 框中未找到项目时
return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}
int solveSudoku() {
int row, col;
//当所有座位都已满时
if (!findEmptyPlace(&row, &col))
return 1;
//有效数字为 1 - 9
for (int num = 1; num <= 9; num++) {
//检查验证，如果是，则将数字放入网格中
if (isValidPlace(row, col, num)) {
grid[row][col] = num;
//递归地寻找网格中的其他房间
if (solveSudoku())
return 1;
//当条件不满足时转向未分配的空间
grid[row][col] = 0;
}
}
return 0;
}
int main() {
if (solveSudoku() == 1)
sudokuGrid();
else
printf("Can't get a solution");
}
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = {
{ 3, 1, 0, 5, 7, 8, 4, 0, 2 },
{ 0, 2, 9, 0, 3, 0, 0, 0, 8 },
{ 4, 0, 0, 6, 2, 9, 0, 3, 1 },
{ 2, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 0, 7, 0, 8, 6, 3, 0, 0, 5 },
{ 8, 0, 1, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 6, 9, 2, 0, 5, 0, 0, 7, 4 },
{ 7, 0, 0, 2, 0, 6, 3, 0, 0 }
};
//检查冷号是否存在
bool isPresentInCol(int col, int num) {
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
//检查行中是否存在数字
bool isPresentInRow(int row, int num) {
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
//检查 3x3 框中是否存在数字
bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
//解答后打印数独网格
void sudokuGrid() {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] <<" ";
}
if(row == 2 || row == 5) {
cout << endl;
for(int i = 0; i<N; i++)
cout << "---";
}
cout << endl;
}
}
//获取空位置并更新行和列
bool findEmptyPlace(int &row, int &col) {
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
//标记为 0 为空
if (grid[row][col] == 0)
return true;
return false;
}
bool isValidPlace(int row, int col, int num) {
//当在列、行和当前 3x3 框中未找到项目时
return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}
bool solveSudoku() {
int row, col;
//当所有座位都已满时
if (!findEmptyPlace(row, col))
return true;
//有效数字为 1 - 9
for (int num = 1; num <= 9; num++) {
//检查验证，如果是，则将数字放入网格中
if (isValidPlace(row, col, num)) {
grid[row][col] = num;
//递归地寻找网格中的其他房间
if (solveSudoku())
return true;
//当条件不满足时转向未分配的空间
grid[row][col] = 0;
}
}
return false;
}
int main() {
if (solveSudoku() == true)
sudokuGrid();
else
cout << "Can't get a solution";
}
public class Main {
static int N = 9;
static int[][] grid = {
{ 3, 1, 0, 5, 7, 8, 4, 0, 2 },
{ 0, 2, 9, 0, 3, 0, 0, 0, 8 },
{ 4, 0, 0, 6, 2, 9, 0, 3, 1 },
{ 2, 0, 3, 0, 1, 0, 0, 8, 0 },
{ 0, 7, 0, 8, 6, 3, 0, 0, 5 },
{ 8, 0, 1, 0, 9, 0, 6, 0, 0 },
{ 1, 3, 0, 0, 0, 0, 2, 5, 0 },
{ 6, 9, 2, 0, 5, 0, 0, 7, 4 },
{ 7, 0, 0, 2, 0, 6, 3, 0, 0 }
};
//检查冷号是否存在
static boolean isPresentInCol(int col, int num) {
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
//检查行中是否存在数字
static boolean isPresentInRow(int row, int num) {
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
//检查 3x3 框中是否存在数字
static boolean isPresentInBox(int boxStartRow, int boxStartCol, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
//解答后打印数独网格
static void sudokuGrid() {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if(col == 3 || col == 6)
System.out.print(" | ");
System.out.print(grid[row][col] + " ");
}
if(row == 2 || row == 5) {
System.out.println();
for(int i = 0; i<N; i++)
System.out.print("---");
}
System.out.println();
}
}
//获取空位置并更新行和列
static int[] findEmptyPlace() {
for (int row = 0; row < N; row++)
for (int col = 0; col < N; col++)
//标记为 0 为空
if (grid[row][col] == 0)
return new int[] {row, col};
return null;
}
static boolean isValidPlace(int row, int col, int num) {
//当在列、行和当前 3x3 框中未找到项目时
return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}
static boolean solveSudoku() {
int row, col;
int[] emptyPlace = findEmptyPlace();
if (emptyPlace == null)
return true;
//有效数字为 1 - 9
for (int num = 1; num <= 9; num++) {
//检查验证，如果是，则将数字放入网格中
if (isValidPlace(emptyPlace[0], emptyPlace[1], num)) {
grid[emptyPlace[0]][emptyPlace[1]] = num;
//递归地寻找网格中的其他房间
if (solveSudoku())
return true;
//当条件不满足时转向未分配的空间
grid[emptyPlace[0]][emptyPlace[1]] = 0;
}
}
return false;
}
public static void main(String[] args) {
if (solveSudoku() == true)
sudokuGrid();
else
System.out.println("Can't get a solution");
}
}
# 定义网格的大小
N = 9
# 初始化网格
grid = [
[3, 1, 0, 5, 7, 8, 4, 0, 2],
[0, 2, 9, 0, 3, 0, 0, 0, 8],
[4, 0, 0, 6, 2, 9, 0, 3, 1],
[2, 0, 3, 0, 1, 0, 0, 8, 0],
[0, 7, 0, 8, 6, 3, 0, 0, 5],
[8, 0, 1, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[6, 9, 2, 0, 5, 0, 0, 7, 4],
[7, 0, 0, 2, 0, 6, 3, 0, 0]
]
# 检查冷号是否存在
def isPresentInCol(col, num):
for row in range(N):
if grid[row][col] == num:
return True
return False
# 检查行中是否存在数字
def isPresentInRow(row, num):
for col in range(N):
if grid[row][col] == num:
return True
return False
# 检查 3x3 框中是否存在数字
def isPresentInBox(boxStartRow, boxStartCol, num):
for row in range(3):
for col in range(3):
if grid[row+boxStartRow][col+boxStartCol] == num:
return True
return False
# 解答后打印数独网格
def sudokuGrid():
for row in range(N):
for col in range(N):
if col == 3 or col == 6:
print(" | ", end="")
print(grid[row][col], end=" ")
if row == 2 or row == 5:
print("
" + "---"*N)
print()
# 获取空位置并更新行和列
def findEmptyPlace():
for row in range(N):
for col in range(N):
# 标记为 0 为空
if grid[row][col] == 0:
return row, col
return None, None
def isValidPlace(row, col, num):
# 当在列、行和当前 3x3 框中未找到项目时
return not isPresentInRow(row, num) and not isPresentInCol(col, num) and not isPresentInBox(row - row%3, col - col%3, num)
def solveSudoku():
row, col = findEmptyPlace()
# 当所有座位都已满时
if row is None and col is None:
return True
# 有效数字为 1 - 9
for num in range(1, 10):
# 检查验证，如果是，则将数字放入网格中
if isValidPlace(row, col, num):
grid[row][col] = num
# 递归地寻找网格中的其他房间
if solveSudoku():
return True
# 当条件不满足时转向未分配的空间
grid[row][col] = 0
return False
if __name__ == "__main__":
if solveSudoku():
sudokuGrid()
else:
print("Can't get a solution")
输出
3 1 6 | 5 7 8 | 4 9 2 5 2 9 | 1 3 4 | 7 6 8 4 8 7 | 6 2 9 | 5 3 1 --------------------------- 2 6 3 | 4 1 5 | 9 8 7 9 7 4 | 8 6 3 | 1 2 5 8 5 1 | 7 9 2 | 6 4 3 --------------------------- 1 3 8 | 9 4 7 | 2 5 6 6 9 2 | 3 5 1 | 8 7 4 7 4 5 | 2 8 6 | 3 1 9
