数独求解算法
在本节中，我们将尝试解决称为Sudoku的著名数字迷宫问题。数独是一个9x9的数字网格，整个网格也分为3x3个框。有一些规则可以解决数独。
我们必须使用数字1到9来解决此问题。
不能在一行，一列或一个3x3框中重复一位数字。
使用回溯算法，我们将尝试解决数独问题。当某个单元格用数字填充时，它将检查其是否有效。无效时，它将检查其他数字。如果所有数字均从1到9进行检查，并且找不到有效的数字，它将回溯到上一个选项。
输入输出
Input: This will take a 9 x 9 matrix as Sudoku grid. Some values are placed in the grid. The blank spaces are denoted by 0.Output: The final matrix (Sudoku grid) filled with numbers. If the solution does not exist, it will return false. 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
算法
isPresentInCol(col,num)
输入： 列和目标编号。
输出- 当给定列中存在数字时为True。
Begin
for each row r in the grid, do
if grid[r, col] = num, then
return true
done
return false otherwise
EndisPresentInRow(row,num)
输入-行和目标编号。
输出-当给定列中存在数字时为True。
Begin
for each column c in the grid, do
if grid[row, c] = num, then
return true
done
return false otherwise
EndisPresentInBox(boxStartRow,boxStartCol,num)
输入-3x3框的起始行和列以及目标编号。
输出- 当框中显示数字时为True。
Begin
for each row r in boxStartRow to next 3 rows, do
for each col r in boxStartCol to next 3 columns, do
if grid[r, c] = num, then
return true
done
done
return false otherwise
EndfindEmptyPlace(row,col)
输入： 网格中的行和列。
输出-如果grid[row，col]为空，则返回true，否则返回false。
Begin
for each row r in the grid, do
for each column c in the grid, do
if grid[r, c] = 0, then
return true
done
done
return false
EndisValidPlace(row,col,num)
输入： 行，网格的一列以及要检查的数字。
输出： 正确，将数字放在位置grid[row，col]时有效。
Begin
if isPresentInRow(row, num) and isPresentInCol(col, num) and
isPresntInBox(row – row mod 3, col – col mod 3, num) all are false, then
return true
EndSolveSudoku（数独网格）
输入： Sudoku的未解决的网格。
输出：求解后的网格。
Begin
if no place in the grid is empty, then
return true
for number 1 to 9, do
if isValidPlace(row, col, number), then
grid[row, col] := number
if solveSudoku = true, then
return true
grid[row, col] := 0
done
return false
End示例
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
bool isPresentInCol(int col, int num) { //check whether num is present in col or not
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInRow(int row, int num) { //check whether num is present in row or not
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num) { //check whether num is present in 3x3 box or not
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() { //print the sudoku grid after solve
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) { //get empty location and update row and column
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) //marked with 0 is empty
return true;
return false;
}
bool isValidPlace(int row, int col, int num) {
//当在col，row和当前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; //when all places are filled
for (int num = 1; num <= 9; num++) { //valid numbers are 1 - 9
if (isValidPlace(row, col, num)) { //check validation, if yes, put the number in the grid
grid[row][col] = num;
if (solveSudoku()) //recursively go for other rooms in the grid
return true;
grid[row][col] = 0; //turn to unassigned space when conditions are not satisfied
}
}
return false;
}
int main() {
if (solveSudoku() == true)
sudokuGrid();
else
cout << "No solution exists";
}输出结果
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