数独 java解题

数独 Java解题教程导言

数独是一种逻辑推理游戏。通过填充9x9网格，每行、每列和每个3x3网格都包含1-9个数字，数字不重复。本文将教你如何使用Java编程来解决数独问题。

解决数独问题的一般流程如下：

现在让我们一步一步地完成这个过程。

首先，我们需要阅读数独主题并将其存储在二维数组中。Java中的Scanner可以用来实现。

import java.util.Scanner;public class SudokuSolver {    private int[][] board;    public SudokuSolver() {        board = new int[9][9];    }    public void readInput() {        Scanner scanner = new Scanner(System.in);        for (int i = 0; i < 9; i++) {            for (int j = 0; j < 9; j++) {                board[i][j] = scanner.nextInt();            }        }        scanner.close();    }}

接下来，我们需要在数独主题中找到一个空白格子。空白格子用0表示。我们可以使用两个循环遍历数独主题的每个格子。如果我们找到一个空白格子，我们可以返回它的坐标。

public class SudokuSolver {    // ...    public int[] findEmptyCell() {        for (int i = 0; i < 9; i++) {            for (int j = 0; j < 9; j++) {                if (board[i][j] == 0) {                    return new int[] { i, j };                }            }        }        return null;    }}

填写数字的过程是将空白网格中的0替换为1-9中的合适数字。我们可以在1-9中尝试每个数字的循环。

public class SudokuSolver {    // ...    public boolean solveSudoku() {        int[] cell = findEmptyCell();        if (cell == null) {            return true; // 数独已解决        }        int row = cell[0];        int col = cell[1];        for (int num = 1; num <= 9; num++) {            if (isValid(num, row, col)) {                board[row][col] = num;                if (solveSudoku()) {                    return true;                }                board[row][col] = 0; // 回溯            }        }        return false;    }}

在尝试填写数字之前，我们需要检查数字是否与当前行、当前列和当前3x3小格子中的其他数字发生冲突。我们可以使用辅助函数来实现此功能。

public class SudokuSolver {    // ...    private boolean isValid(int num, int row, int col) {        // 检查当前行动是否合法        for (int i = 0; i < 9; i++) {            if (board[row][i] == num) {                return false;            }        }        // 检查当前列是否合法        for (int i = 0; i < 9; i++) {            if (board[i][col] == num) {                return false;            }        }        // 检查3x3小格子是否合法        int startRow = (row / 3) * 3;        int startCol = (col / 3) * 3;        for (int i = startRow; i < startRow + 3; i++) {            for (int j = startCol; j < startCol + 3; j++) {                if (board[i][j] == num) {                    return false;                }            }        }        return true;    }}