题解 | #数独#

import java.util.* ;

public class Solution {
    static class Position {
        int x;
        int y;

        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public void solveSudoku(char[][] board) {
        valid(0, getPositionList(board), board);
    }

    // 从待填列表的index位置开始，填充待填列表，如果数独有解，返回true
    private boolean valid(int index, List<Position> positionList, char[][] board) {
        Position curPosition = positionList.get(index);
        int x = curPosition.x;
        int y = curPosition.y;
        List<Character> candinateList = getCandinateList(board, x, y);
        if (candinateList.size() == 0) {
            return false;
        }
        if (index == positionList.size() - 1) {
            if (candinateList.size() == 1) {
                board[x][y] = candinateList.get(0);
                return true;
            } else {
                return false;
            }
        }
        for (Character candinate : candinateList) {
            board[x][y] = candinate;
            boolean valid = valid(index + 1, positionList, board);
            if (valid) {
                return true;
            }
        }
        board[x][y] = '.';
        return false;
    }

    // 获取待填值的坐标列表
    private List<Position> getPositionList(char[][] board) {
        List<Position> positionList = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    positionList.add(new Position(i, j));
                }
            }
        }
        return positionList;
    }

    // 获取当前坐标的候选值
    private List<Character> getCandinateList(char[][] board, int x, int y) {
        // 横向检查、纵向检查
        Set<Character> candinateSet = new HashSet(Arrays.asList('1', '2', '3', '4', '5', '6', '7', '8', '9'));
        for (int i = 0; i < board[0].length; i++) {
            candinateSet.remove(board[x][i]);
            candinateSet.remove(board[i][y]);
        }
        //九宫格检查
        int leftStart = y / 3 * 3;
        int upStart = x / 3 * 3;
        for (int i = upStart; i < upStart + 3; i++) {
            for (int j = leftStart; j < leftStart + 3; j++) {
                candinateSet.remove(board[i][j]);
            }
        }
        return new ArrayList<>(candinateSet);
    }

}