数独

[编程题]数独

热度指数：11604 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请编写一个程序，给数独中的剩余的空格填写上数字

空格用字符'.'表示

假设给定的数独只有唯一的解法

这盘数独的解法是：

红色表示填上的解

示例1

输入

[[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]]

输出

[[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,1,3,9,8,7,5],[3,5,7,9,8,6,2,4,1],[2,6,4,3,1,7,5,9,8],[1,9,8,5,2,4,3,6,7],[9,7,5,8,6,3,1,2,4],[8,3,2,4,9,1,7,5,6],[6,4,1,2,7,5,9,8,3]]

算法知识视频讲解

Java

小谷围做题家

public class Solution {
    private char[][] board;
    public void solveSudoku(char[][] board) {
        this.board=board;
        dfs();
    }
    public boolean dfs(){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.') continue;
                for(int x=1;x<=9;x++){
                    if(check(i,j,x)){
                        board[i][j]=(char)('0'+x);
                        if(dfs()) return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean check(int i,int j,int x){
        for(int k=0;k<9;k++){
            if(board[i][k]=='0'+x) return false;
            if(board[k][j]=='0'+x) return false;
        }
        i/=3;
        j/=3;
        for(int c=i*3;c<i*3+3;c++){
            for(int d=j*3;d<j*3+3;d++){
                if(board[c][d]=='0'+x) return false;
            }
        }
        return true;
    }
}

发表于 2023-08-10 19:15:31 回复(0)

Java

シkid~

public class Solution {
    // 判断行列是否冲突的hash数组
    boolean[][][] flag = new boolean[2][9][9];
    // 判断小宫格是否冲突的hash数组
    boolean[][][] flagMini = new boolean[3][3][9];
    
    public void solveSudoku(char[][] board) {
        // 初始化hash数组
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if (board[i][j] != '.') {
                    int value = board[i][j] - '1';
                    flag[0][i][value] = true;
                    flag[1][value][j] = true;
                    flagMini[i/3][j/3][value] = true;
                }
            }
        }
        sudoku(board, 0, 0);
    }

    // 判断数独是否合法
    public boolean judgeLegal(int row, int col, int value) {
        // 判断行列是否合法 和小三宫格是否合法
        if (flag[0][row][value-1] || flag[1][value-1][col] || flagMini[row/3][col/3][value-1]) {
            return false;
        }
        return true;
    }
    
    
    public boolean sudoku(char[][] board, int rowStart, int colStart) {
        if (rowStart == 9) { // 如果到达了超尾行，说明该数独成立
            return true;
        }
        if (board[rowStart][colStart] != '.') {
            if (colStart == 8) {
                return sudoku(board, rowStart+1, 0);
            } else {
                return sudoku(board, rowStart, colStart+1);
            }
        }
        // 尝试填入数字
        for(int k=1; k<=9; k++) {
            if (judgeLegal(rowStart, colStart, k)) { // 判断是否合法
                // 更新hash数组
                flag[0][rowStart][k-1] = true;
                flag[1][k-1][colStart] = true;
                flagMini[rowStart/3][colStart/3][k-1] = true;
                board[rowStart][colStart] = (char) (k + '0');
                if (colStart == 8) {
                    if (sudoku(board, rowStart+1, 0)) {
                        return true;
                    }
                } else {
                    if (sudoku(board, rowStart, colStart+1)) {
                        return true;
                    }
                }
                // 回溯
                flag[0][rowStart][k-1] = false;
                flag[1][k-1][colStart] = false;
                flagMini[rowStart/3][colStart/3][k-1] = false;
                board[rowStart][colStart] = '.';
            }
        }
        return false;
    }
}

发表于 2022-02-27 12:58:08 回复(0)

Java

城市里的养猫者

Try 1 through 9 for each cell. The time complexity should be 9 ^ m (m represents the number of blanks to be filled in), since each blank can have 9 choices. Details see comments inside code. Let me know your suggestions.

Sorry for being late to answer the time complexity question

public class Solution { public void solveSudoku(char[][] board) { if(board == null || board.length == 0) return;
        solve(board);
    } public boolean solve(char[][] board){ for(int i = 0; i < board.length; i++){ for(int j = 0; j < board[0].length; j++){ if(board[i][j] == '.'){ for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9 if(isValid(board, i, j, c)){
                            board[i][j] = c; //Put c for this cell if(solve(board)) return true; //If it's the solution return true else board[i][j] = '.'; //Otherwise go back }
                    } return false;
                }
            }
        } return true;
    } private boolean isValid(char[][] board, int row, int col, char c){ for(int i = 0; i < 9; i++) {

	if(board[i][col] != '.' && board[i][col] == c) return false;
	
		//check row
	




	if(board[row][i] != '.' && board[row][i] == c) return false;
	
		//check column
	


if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&

	board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
	
		//check 3*3 block
	


} return true;
    }
}