数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 数独求解器
假设我们有一个数独网格，我们需要解决这个著名的数字谜题——数独。我们知道数独是一个 9 x 9 的数字网格，整个网格也细分为 3 x 3 的小方格。有一些规则需要遵循才能解决数独。
我们需要使用数字 1 到 9 来解决这个问题。
同一行、同一列或同一个 3 x 3 方格内不能重复使用同一个数字。
我们将使用回溯算法来尝试解决数独问题。当某个单元格填充了一个数字后，它会检查该数字是否有效。如果无效，则会检查其他数字。如果已经检查了 1 到 9 的所有数字，并且没有找到有效的数字可以放置，则回溯到之前的选择。
所以如果输入是这样的：
输出将是：
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 isPresentInCol() 的方法，它将接收列和数字作为参数。
对于网格中的每一行 r，执行：
如果 grid[r, col] = num，则返回 true
否则返回 false
定义一个名为 isPresentInRow() 的方法，它将接收行和数字作为参数。
对于网格中的每一列 c，执行：
如果 grid[row, c] = num，则返回 true
否则返回 false
定义一个名为 isPresentInBox() 的方法，它将接收方格起始行、方格起始列和数字作为参数。
对于从 boxStartRow 到接下来的 3 行的每一行 r，执行：
对于从 boxStartCol 到接下来的 3 列的每一列 c，执行：
如果 grid[r, c] = num，则返回 true
否则返回 false
定义一个名为 findEmptyPlace() 的方法，它将接收行和列作为参数。
对于网格中的每一行 r，执行：
对于网格中的每一列 c，执行：
如果 grid[r, c] = 0，则返回 true
返回 false
定义一个名为 isValidPlace() 的方法，它将接收行、列和数字作为参数。
如果 isPresentInRow(row, num)、isPresentInCol(col, num) 和 isPresentInBox(row – row % 3, col – col % 3, num) 全部为 false，则返回 true
定义一个名为 solveSudoku() 的方法，它将接收网格作为参数。
如果网格中没有空位置，则返回 true
对于数字 1 到 9，执行：
如果 isValidPlace(row, col, number) 为 true，则：
grid[row, col] := number
如果 solveSudoku() 返回 true，则返回 true
grid[row, col] := 0
返回 false
示例 (C++)
让我们看看下面的实现来更好地理解：
#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){
//when item not found in col, row and current 3x3 box
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, 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}输出
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
16K+ 次浏览
