代码实现用C++
时间: 2023-11-14 16:15:27 浏览: 38
以下是一个基于递归和回溯思想的 C++ 代码实现,用于解决数独问题:
```c++
#include <iostream>
#include <vector>
using namespace std;
bool solveSudoku(vector<vector<int>> &board) {
// Find the first empty cell
int row = -1, col = -1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
row = i;
col = j;
break;
}
}
if (row != -1) {
break;
}
}
// If all cells are filled, the puzzle is solved
if (row == -1) {
return true;
}
// Try all possible values in the empty cell
for (int num = 1; num <= 9; num++) {
if (isValidMove(board, row, col, num)) {
board[row][col] = num;
// Recursively solve the rest of the puzzle
if (solveSudoku(board)) {
return true;
}
// If the recursive call fails, undo the move and try the next value
board[row][col] = 0;
}
}
// If none of the values work, the puzzle is unsolvable
return false;
}
bool isValidMove(vector<vector<int>> &board, int row, int col, int num) {
// Check if the value already exists in the row
for (int j = 0; j < 9; j++) {
if (board[row][j] == num) {
return false;
}
}
// Check if the value already exists in the column
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
}
// Check if the value already exists in the 3x3 box
int box_row = row / 3 * 3, box_col = col / 3 * 3;
for (int i = box_row; i < box_row + 3; i++) {
for (int j = box_col; j < box_col + 3; j++) {
if (board[i][j] == num) {
return false;
}
}
}
// If the move is valid, return true
return true;
}
```
这段代码与前面的 Python 代码类似,使用了递归和回溯思想,用于逐个尝试填充数字,并检查是否满足数独的规则。如果在某个格子中无法填入任何数字,就回溯到上一个格子重新尝试。如果最终填充完成,就说明数独问题已经解决。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)