数独

[编程题]数独

热度指数：11802 时间限制：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

Sen🍓🍀

import java.util.*;

public class Solution {
    private boolean completed = false; // 是否完成 (要全局变量)

    public void solveSudoku(char[][] board) {
        List<int[]> blankList = new ArrayList<>(); // 要填的空格list
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    blankList.add(new int[] {i, j});
                }
            }
        }
        backtrack(board, blankList, 0); // 调用
    }

    // 回溯
    private void backtrack(char[][] board, List<int[]> blankList, int k) {
        if (completed || k == blankList.size()) { // 出口
            if (!completed && k == blankList.size()) {
                completed = true;
            }
            return;
        }

        for (char c = '1'; c <= '9'; c++) { // 0-9都尝试
            int x = blankList.get(k)[0], y = blankList.get(k)[1];
            if (!check(board, x, y, c)) continue;

            board[x][y] = c;
            backtrack(board, blankList, k + 1);
            if (completed) return; // 填完了,不用撤销
            board[x][y] = '.';
        }
    }

    // 判断(x,y)能否填数字c
    private boolean check(char[][] board, int x, int y, char c) {
        //该行
        for (int j = 0; j < board[0].length; j++) {
            if (board[x][j] == c) return false;
        }
        //该列
        for (int i = 0; i < board.length; i++) {
            if (board[i][y] == c) return false;
        }
        //该小矩形 （x0,y0）左上角
        for (int x0 = x / 3 * 3, i = 0; i < 3; i++) {
            for (int y0 = y / 3 * 3, j = 0; j < 3; j++) {
                if (board[x0 + i][y0 + j] == c) return false;
            }
        }
        return true;
    }
}

发表于 2025-03-29 11:06:30 回复(0)

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;
    }
}