在本节中,我们将尝试解决称为Sudoku的著名数字迷宫问题。数独是一个9 x 9的数字网格,整个网格也分为3 x 3个框。有一些规则可以解决数独。
我们必须使用数字1到9来解决此问题。
不能在一行,一列或一个3 x 3框中重复一位数字。
使用回溯算法,我们将尝试解决数独问题。当某个单元格用数字填充时,它将检查其是否有效。无效时,它将检查其他数字。如果所有数字均从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 End
isPresentInRow(row,num)
输入-行和目标编号。
输出-当给定列中存在数字时为True。
Begin for each column c in the grid, do if grid[row, c] = num, then return true done return false otherwise End
isPresentInBox(boxStartRow,boxStartCol,num)
输入-3 x 3框的起始行和列以及目标编号。
输出- 当框中显示数字时为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 End
findEmptyPlace(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 End
isValidPlace(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 End
SolveSudoku(数独网格)
输入: 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