数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 实现部分填充数独格子的程序
假设我们有一个部分填充的数独网格，我们需要解决它。我们知道数独是一个 9 × 9 的数字网格，整个网格也分成 3 × 3 的小方格。有一些规则需要遵循来解决数独。
我们需要使用数字 1 到 9 来解决这个问题。
同一行、同一列或同一 3 × 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 列的每一列 r，执行以下操作：
如果 grid[r, c] 等于 num，则返回 true
否则返回 false
定义一个名为 findEmptyPlace() 的方法，它将接收行和列作为参数
对于网格中的每一行 r，执行以下操作：
对于网格中的每一列 c，执行以下操作：
如果 grid[r, c] 等于 0，则返回 true
返回 false
定义一个名为 isValidPlace() 的方法，它将接收行、列和数字作为参数
如果 isPresentInRow(row, num)、isPresentInCol(col, num) 和 isPresntInBox(row − row mod 3, col − col mod 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
让我们看下面的实现来更好地理解：
示例
#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) &&
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) &&
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
263 次浏览
