用java写一个数独游戏并生成唯一答案,由人填入数字,检查对错
时间: 2023-12-18 16:02:34 浏览: 32
好的,下面是一个简单的数独游戏的实现,使用 Backtracking 算法生成唯一答案,并且支持填入数字和检查对错。
```java
import java.util.Arrays;
public class Sudoku {
private static final int SIZE = 9;
private static final int EMPTY = 0;
private int[][] board;
public Sudoku() {
board = new int[SIZE][SIZE];
}
public void setBoard(int[][] board) {
this.board = board;
}
public int[][] getBoard() {
return board;
}
public void solve() {
solve(0, 0);
}
private boolean solve(int row, int col) {
if (row == SIZE) {
row = 0;
if (++col == SIZE) {
return true;
}
}
if (board[row][col] != EMPTY) {
return solve(row + 1, col);
}
for (int val = 1; val <= SIZE; ++val) {
if (isValid(row, col, val)) {
board[row][col] = val;
if (solve(row + 1, col)) {
return true;
}
}
}
board[row][col] = EMPTY;
return false;
}
private boolean isValid(int row, int col, int val) {
for (int i = 0; i < SIZE; ++i) {
if (board[row][i] == val || board[i][col] == val) {
return false;
}
}
int boxRow = row - row % 3;
int boxCol = col - col % 3;
for (int i = boxRow; i < boxRow + 3; ++i) {
for (int j = boxCol; j < boxCol + 3; ++j) {
if (board[i][j] == val) {
return false;
}
}
}
return true;
}
public boolean isComplete() {
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
if (board[i][j] == EMPTY) {
return false;
}
}
}
return true;
}
public boolean checkSolution() {
if (!isComplete()) {
return false;
}
for (int i = 0; i < SIZE; ++i) {
boolean[] rowCheck = new boolean[SIZE];
boolean[] colCheck = new boolean[SIZE];
boolean[] boxCheck = new boolean[SIZE];
for (int j = 0; j < SIZE; ++j) {
int rowVal = board[i][j] - 1;
int colVal = board[j][i] - 1;
int boxVal = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3] - 1;
if (rowCheck[rowVal] || colCheck[colVal] || boxCheck[boxVal]) {
return false;
}
rowCheck[rowVal] = true;
colCheck[colVal] = true;
boxCheck[boxVal] = true;
}
}
return true;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < SIZE; ++i) {
if (i % 3 == 0) {
sb.append(" -----------------------\n");
}
for (int j = 0; j < SIZE; ++j) {
if (j % 3 == 0) {
sb.append("| ");
}
sb.append(board[i][j] == EMPTY ? " " : board[i][j] + " ");
}
sb.append("|\n");
}
sb.append(" -----------------------\n");
return sb.toString();
}
public static void main(String[] args) {
Sudoku sudoku = new Sudoku();
sudoku.solve();
System.out.println(sudoku);
// remove some numbers from the solution to create the game
int[][] game = Arrays.copyOf(sudoku.getBoard(), SIZE);
int numToRemove = (int) (0.5 * SIZE * SIZE);
int numRemoved = 0;
while (numRemoved < numToRemove) {
int row = (int) (Math.random() * SIZE);
int col = (int) (Math.random() * SIZE);
if (game[row][col] != EMPTY) {
game[row][col] = EMPTY;
++numRemoved;
}
}
sudoku.setBoard(game);
System.out.println(sudoku);
// check if the game is solved correctly
sudoku.solve();
System.out.println(sudoku.checkSolution() ? "Correct solution!" : "Incorrect solution!");
}
}
```
这个程序的主要思路是使用 Backtracking 算法生成唯一答案,然后随机删除一些数字来创建游戏。最后,检查玩家填入的数字是否正确,如果正确则显示“Correct solution!”,否则显示“Incorrect solution!”。
在 `solve()` 方法中,我们首先检查是否已经填满了整个数独板,如果是,返回true。否则,我们从左上角开始,依次填入数字,如果遇到一个已经填好的数字,则跳过它,继续搜索下一个数字。如果在当前位置填入某个数字后,导致后面无法生成唯一答案,则回溯并尝试下一个数字。
在 `isValid()` 方法中,我们检查当前位置是否可以填入给定的值。我们首先检查当前行和列是否已经有了这个值,如果有,则返回 false。然后,我们检查当前位置所在的 3x3 小正方形是否已经有了这个值。如果有,则返回 false。否则,返回 true。
在 `checkSolution()` 方法中,我们检查玩家填入的数字是否符合数独游戏的要求,即每行、每列和每个 3x3 小正方形都没有重复数字。我们使用三个布尔数组 `rowCheck`、`colCheck` 和 `boxCheck`,来分别记录当前行、当前列和当前 3x3 小正方形中出现过的数字,如果出现重复,则返回 false。
在主方法中,我们首先生成唯一答案,然后随机删除一些数字来创建游戏。最后,检查玩家填入的数字是否正确,如果正确则显示“Correct solution!”,否则显示“Incorrect solution!”。