leetcode解数独sudoku-solver——二进制解法

向右看齐 2022-12-07 15:05 159阅读 0赞

# 解数独sudoku-solver #

# 代码一 #

package sudoku_solver;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * sudoku-solver * */
    public class Solution { 
        private boolean[][] line = new boolean[9][9];//
        private boolean[][] column = new boolean[9][9];
        private boolean[][][] block = new boolean[3][3][9];
    
        private boolean valid = false;//有一个数独填写完成就退出
        private List<int[]> spaces = new ArrayList<int[]>();//需要填写的空位的下标
    
        public void solveSudoku(char[][] board) { 
        	//首先对整个数独数组进行遍历
            for (int i = 0; i < 9; ++i) { 
                for (int j = 0; j < 9; ++j) { 
                    if (board[i][j] == '.') {         //给定的数独序列只包含数字 1-9 和字符 '.'
                        spaces.add(new int[]{ i, j});
                    } else { 
                        int digit = board[i][j] - '0' - 1;//获取当前位置的数字,减去0是为了自动转型,减去1是为了对应数组下标
                        line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                    }
                }
            }
            //当我们结束了遍历过程之后，就可以开始递归枚举。
            dfs(board, 0);
        }
    
        public void dfs(char[][] board, int pos) { 
            if (pos == spaces.size()) { 
                valid = true;
                return;
            }
    
            int[] space = spaces.get(pos);
            int i = space[0], j = space[1];
            for (int digit = 0; digit < 9 && !valid; ++digit) { 
            	
                if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) { 
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                    board[i][j] = (char) (digit + '0' + 1);//从0-9尝试,加字符0为了自动转型,加1为了对应数字
                    dfs(board, pos + 1);
                    //回溯
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
                }
            }
        }
        
        private void printBoard(char[][] board) { 
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        }
        
        public static void main(String[] args) { 
            char[][] board = new char[][]{ 
                    { '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'}
            };
            Solution solution = new Solution();
            solution.printBoard(board);
            solution.solveSudoku(board);
            solution.printBoard(board);
        }
    }

# 代码二 #

package sudoku_solver;
    
    public class Solution2 { 
        public void solveSudoku(char[][] board) { 
            /** * 记录某行，某位数字是否已经被摆放 */
            boolean[][] row = new boolean[9][9];
            /** * 记录某列，某位数字是否已经被摆放 */
            boolean[][] col = new boolean[9][9];
            /** * 记录某 3x3 宫格内，某位数字是否已经被摆放 */
            boolean[][] block = new boolean[9][9];
    
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    if (board[i][j] != '.') { 
                        int num = board[i][j] - '1';
                        row[i][num] = true;
                        col[j][num] = true;
                        // blockIndex = i / 3 * 3 + j / 3，取整
                        block[i / 3 * 3 + j / 3][num] = true;
                    }
                }
            }
            dfs(board, row, col, block, 0, 0);
        }
    
        private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) { 
            // 找寻空位置
            while (board[i][j] != '.') { 
                if (++j >= 9) { 
                    i++;
                    j = 0;
                }
                if (i >= 9) { 
                    return true;
                }
            }
            for (int num = 0; num < 9; num++) { 
                int blockIndex = i / 3 * 3 + j / 3;
                if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) { 
                    // 递归
                    board[i][j] = (char) ('1' + num);
                    row[i][num] = true;
                    col[j][num] = true;
                    block[blockIndex][num] = true;
                    if (dfs(board, row, col, block, i, j)) { 
                        return true;
                    } else { 
                        // 回溯
                        row[i][num] = false;
                        col[j][num] = false;
                        block[blockIndex][num] = false;
                        board[i][j] = '.';
                    }
                }
            }
            return false;
        }
    
        private void printBoard(char[][] board) { 
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) { 
            char[][] board = new char[][]{ 
                    { '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'}
            };
            Solution2 solution = new Solution2();
            solution.printBoard(board);
            solution.solveSudoku(board);
            solution.printBoard(board);
        }
    }

# 代码三——二进制解法 #

class Solution { 
        private int[] line = new int[9];
        private int[] column = new int[9];
        private int[][] block = new int[3][3];
        private boolean valid = false;
        private List<int[]> spaces = new ArrayList<int[]>();
    
        public void solveSudoku(char[][] board) { 
            for (int i = 0; i < 9; ++i) { 
                for (int j = 0; j < 9; ++j) { 
                    if (board[i][j] == '.') { 
                        spaces.add(new int[]{ i, j});
                    } else { 
                        int digit = board[i][j] - '0' - 1;
                        flip(i, j, digit);
                    }
                }
            }
    
            dfs(board, 0);
        }
    
        public void dfs(char[][] board, int pos) { 
            if (pos == spaces.size()) { 
                valid = true;
                return;
            }
    
            int[] space = spaces.get(pos);
            int i = space[0], j = space[1];
            int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
            for (; mask != 0 && !valid; mask &= (mask - 1)) { 
                int digitMask = mask & (-mask);
                int digit = Integer.bitCount(digitMask - 1);
                flip(i, j, digit);
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, pos + 1);
                flip(i, j, digit);
            }
        }
    
        public void flip(int i, int j, int digit) { 
            line[i] ^= (1 << digit);
            column[j] ^= (1 << digit);
            block[i / 3][j / 3] ^= (1 << digit);
        }
    }

# 代码四 #

//数独的长宽大小
            final int N = 9;
            //行
            private int[] rows = new int[N];
            //列
            private int[] cols = new int[N];
            //单元格
            private int[][] cells = new int[3][3];
    
            public void solveSudoku(char[][] board) { 
                //统计未填的个数
                int count = 0;
                for (int i = 0; i < N; i++) { 
                    for (int j = 0; j < N; j++) { 
                        char ch = board[i][j];
                        if (ch == '.') { 
                            count++;
                        } else { 
                            //如果已经有数字，把这个数字标记一下
                            fillNumber(i, j, ch - '1', true);
                        }
                    }
                }
                //上面是一些计算前的准备工作，从这里开始调用回溯算法
                backtrace(board, count);
            }
    
            private boolean backtrace(char[][] board, int count) { 
                //如果可填的位置为0，就是填完了，直接返回true
                if (count == 0) { 
                    return true;
                }
                //找到可选择数字比较少的位置
                int[] pos = getMinOkMaskCountPos(board);
                int x = pos[0], y = pos[1];
                //获取可选择数字比较少的位置的mask
                int mask = getMask(x, y);
                for (char c = '1'; c <= '9'; c++) { 
                    int index = c - '1';
                    //判断这个位置是否可以填字符c
                    if (testMask(mask, index)) { 
                        //如果可填，就把字符c填入到这个位置中
                        fillNumber(x, y, index, true);
                        board[x][y] = c;
                        //如果成功直接返回
                        if (backtrace(board, count - 1))
                            return true;
                        //否则，撤销上面的操作
                        board[x][y] = '.';
                        fillNumber(x, y, index, false);
                    }
                }
                return false;
            }
    
            //如果fill是true就把对应位置的数字从右边数第（n+1）位变为1，如果fill为false就把
            //对应位置的数字从右边数第（n+1）位变为0，
            private void fillNumber(int x, int y, int n, boolean fill) { 
                if (fill) { 
                    int mask = 1 << n;
                    rows[x] = rows[x] | mask;
                    cols[y] = cols[y] | mask;
                    cells[x / 3][y / 3] = cells[x / 3][y / 3] | mask;
                } else { 
                    int mask = ~(1 << n);
                    rows[x] = rows[x] & mask;
                    cols[y] = cols[y] & mask;
                    cells[x / 3][y / 3] = cells[x / 3][y / 3] & mask;
                }
            }
    
            //当前位置的行，列，单元格进行与运算，运算的结果就是如果这个数字的
            //后面9位哪一个位置是0，就表示这个位置可以填对应的数字
            private int getMask(int x, int y) { 
                return rows[x] | cols[y] | cells[x / 3][y / 3];
            }
    
            //统计上面的方法有多少位置还可以填
            private int getCount(int mask) { 
                int count = 0;
                for (int i = 0; i < N; i++) { 
                    if ((mask & (1 << i)) == 0)
                        count++;
                }
                return count;
            }
    
            //判断mask从右边数第（index+1）个位置是否可以填入数字，
            //注意这里的index是从0开始，如果是0，就表示判断右边第1位
            //能不能填入数字
            private boolean testMask(int mask, int index) { 
                return (mask & (1 << index)) == 0;
            }
    
            //统计所有的单元格，判断哪个单元格内可填数字比较少，就返回哪个单元格的坐标
            private int[] getMinOkMaskCountPos(char[][] board) { 
                int[] res = new int[2];
                int min = 10;
                for (int i = 0; i < N; i++) { 
                    for (int j = 0; j < N; j++) { 
                        if (board[i][j] == '.') { 
                            int mask = getMask(i, j);
                            int count = getCount(mask);
                            if (count < min) { 
                                min = count;
                                res[0] = i;
                                res[1] = j;
                            }
                        }
                    }
                }
                return res;
            }

[sdwwld][]

[sdwwld]: https://leetcode-cn.com/problems/sudoku-solver/solution/hui-su-jie-jue-by-sdwwld/