java编写一个程序创建一个99数独,如果输入的数组满足一个99数独,则输出“yes”,反之则输出“no”(输入的数组没有空格)
时间: 2023-06-07 18:07:09 浏览: 64
此题可以使用回溯算法进行解决。以下是一个Java编写的程序,可以创建一个9x9数独并检查输入数组是否为数独:
```
public class SudokuChecker {
public static void main(String[] args) {
int[][] input = {{5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}}; // example input, solution is valid
if (isValidSudoku(input)) {
System.out.println("yes");
} else {
System.out.println("no");
}
}
public static boolean isValidSudoku(int[][] board) {
return backtrack(board, 0, 0);
}
private static boolean backtrack(int[][] board, int row, int col) {
if (col == 9) {
// end of current row, go to next row
row++;
col = 0;
if (row == 9) {
// end of sudoku grid, solution found
return true;
}
}
if (board[row][col] != 0) {
// current cell already filled, go to next cell
return backtrack(board, row, col + 1);
}
for (int num = 1; num <= 9; num++) {
if (isValid(board, row, col, num)) {
// choose num and backtrack
board[row][col] = num;
if (backtrack(board, row, col + 1)) {
return true;
}
}
}
// undo choice
board[row][col] = 0;
return false;
}
private static boolean isValid(int[][] board, int row, int col, int num) {
// check row
for (int i = 0; i < 9; i++) {
if (board[row][i] == num) {
return false;
}
}
// check column
for (int i = 0; i < 9; i++) {
if (board[i][col] == num) {
return false;
}
}
// check subgrid
int subgridRow = (row / 3) * 3;
int subgridCol = (col / 3) * 3;
for (int i = subgridRow; i < subgridRow + 3; i++) {
for (int j = subgridCol; j < subgridCol + 3; j++) {
if (board[i][j] == num) {
return false;
}
}
}
return true;
}
}
```
程序中,首先定义了一个输入数组 input 作为例子,然后调用 isValidSudoku 方法来检查输入数组是否为数独。isValidSudoku 方法中,调用了 backtrack 方法来进行回溯。backtrack 方法中,分别检查当前位置的数字是否为 0 (即未填充)。若未填充,就检验每个可能的数字是否合法 (即不会与其所在的行、列或子网格中的数字产生冲突),并进行选择。若当前填充的数字不能产生一个合法的数独,就再选择另一个数字,并重复此过程直到找到合法的方案或者所有数字都尝试过。
注意,这个程序的解法不一定是最短的,但足以解决问题。
相关推荐
![](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)
![](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)