数独游戏底层算法

数独游戏底层算法

1. 填充数字以后判断是否是有效的数独
2. bfs+回溯的暴利得到数独的解

底层算法 对应leetcode的36,37题目

1.有效的数独 见leetcode 36 力扣

代码如下

解题思想：使用行数组， 列数组，子箱子数组 记录指定位置元素出现的次数，数独游戏要求只能出现一次，故出现大于一次为false,如果9*9的方格都正确则为true.

public class Test023 {
    //判断一个数独是否是一个合适的数独
    //题目地址: leetcode 36
    //https://leetcode.cn/problems/valid-sudoku/description/
    public static void main(String[] args) {
        char[][] board = {
                {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        boolean flag = isValidSudoku(board);
        System.out.println("flag:" + flag);
    }
 
    public static boolean isValidSudoku(char[][] board) {
//        行是9*9
        int[][] rows = new int[9][9];
//        列是9*9
        int[][] cols = new int[9][9];
//        subBox是3*3*9
        int[][][] subBoxes = new int[3][3][9];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    int index = board[i][j] - '0' - 1;
                    rows[i][index]++;
                    cols[j][index]++;
                    subBoxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || cols[j][index] > 1 || subBoxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
 
        return true;
    }
}

2.求数独的唯一解 见leetcode 37 力扣

解题思路：dfs+回溯

1.遍历9*9 把未填的空格加入列表

2.依次遍历未填的列表 dfs+回溯

注意:dfs函数有返回值，如果所有的未填的列表已经填完了，返回true

public class Test024 {
    static boolean[][] rows = new boolean[9][9];
    static boolean[][] cols = new boolean[9][9];
    static boolean[][][] subBoxes = new boolean[3][3][9];
 
    static class Position {
        int x;
        int y;
 
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void main(String[] args) {
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solveSudoku(board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    public static void solveSudoku(char[][] board) {
        List list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    list.add(new Position(i, j));
                } else {
                    int index = board[i][j] - '0' - 1;
                    rows[i][index] = true;
                    cols[j][index] = true;
                    subBoxes[i / 3][j / 3][index] = true;
                }
            }
        }
        solveSudokuHelper(board, list, 0);
    }
 
    //填充数独表格
    //函数为什么要有返回值
    public static boolean solveSudokuHelper(char[][] board, List list, int index) {
        if (index == list.size()) {
            return true;
        }
        Position position = list.get(index);
        for (char k = '1'; k <= '9'; k++) {
            boolean validSudoku = isValidSudoku2(board, position.x, position.y, k);
            if (validSudoku) {
                int index2 = k - '0' - 1;
                rows[position.x][index2] = true;
                cols[position.y][index2] = true;
                subBoxes[position.x / 3][position.y / 3][index2] = true;
                board[position.x][position.y] = k;
                boolean flag = solveSudokuHelper(board, list, index + 1);
                if (flag) {
                    return true;
                }
                board[position.x][position.y] = '.';
                rows[position.x][index2] = false;
                cols[position.y][index2] = false;
                subBoxes[position.x / 3][position.y / 3][index2] = false;
            }
        }
        return false;
    }
 
    public static boolean isValidSudoku(char[][] board, int i, int j, char k) {
        //行检测
        for (int col = 0; col < 9; col++) {
            if (board[i][col] == k) {
                return false;
            }
        }
        //列检测
        for (int row = 0; row < 9; row++) {
            if (board[row][j] == k) {
                return false;
            }
        }
        //9宫格检测
        int startRow = (i / 3) * 3;
        int startCol = (j / 3) * 3;
        for (int p = startRow; p < startRow + 3; p++) {
            for (int q = startCol; q < startCol + 3; q++) {
                if (board[p][q] == k) {
                    return false;
                }
            }
        }
        return true;
    }
 
    //isValidSudoku2比isValidSudoku时间复杂度低
    //isValidSudoku2 只需要比较3次，isValidSudoku需要比较27次
    //优化是否满足数独元素的判断
    //设置行,列，子盒子缓存，只需要3次判断就可确定是否是合格的数独
    public static boolean isValidSudoku2(char[][] board, int i, int j, char k) {
        //行检测
        int index = k - '0' - 1;
        if (!rows[i][index] && !cols[j][index] && !subBoxes[i / 3][j / 3][index]) {
            return true;
        }
        return false;
    }
}