leetcode 37问题

来源:8-8 回溯法是经典人工智能的基础 N Queens

讲武德的年轻人

2022-04-23

bobo老师,我借鉴您在github的思路,修改了我的代码,唯一的区别就是dfs函数没有返回值,我debug了很久,还是没有发现问题所在。能否请问简单看下,问题可能出在哪里?我继续debug..谢谢!

class Solution {
    
    private boolean[][] row;
    private boolean[][] col;
    private boolean[][] block;
    private char[][] board;
    
    public void solveSudoku(char[][] board) {
        
        this.board = board;
        row = new boolean[9][10];
        col = new boolean[9][10];
        block = new boolean[9][10];
        
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    row[i][num] = true;
                    col[j][num] = true;
                    block[3 * (i / 3) + j / 3][num] = true;
                }
            }
        }
        
    
        for (int k = 0; k < 81; k ++) {
            if (board[k / 9][k % 9] == '.'){
                dfs(k);
            }
        }
    }
    
    private void dfs(int k) {
        
        if (k == 81) {
            return;
        }
        
        int next = k + 1;
        for(; next < 81; next ++)
            if(board[next / 9][next % 9] == '.')
                break;
        
        int x = k / 9, y = k % 9;
        
        for (int i = 1; i <= 9; i ++) {
            
            if (row[x][i] || col[y][i] || block[3 * (x / 3) + y / 3][i])
                continue;
            
            row[x][i] = true;
            col[y][i] = true;
            block[3 * (x / 3) + y / 3][i] = true;
            board[x][y] = (char) (i + '0');
            
            dfs(next);
            
            row[x][i] = false;
            col[y][i] = false;
            block[3 * (x / 3) + y / 3][i] = false;
            board[x][y] = '.';
            
        }    
    }
}


写回答

3回答

liuyubobobo

2022-04-23

我没有看你的代码的具体逻辑,但是你当前的代码肯定有问题的地方在于,对于已经找到的解,在回溯的过程中,会不断把解抹掉(你的 62 行做的事情)。


我的代码中:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情,就是在有解的时候返回, 而不去执行下面的 board[x][y] = '.';


继续加油!:)

0
1
讲武德的年轻人
谢谢老师! 不好意思,刚刚看到您的回复。我没有收到慕课的自动提醒
2022-05-11
共1条回复

liuyubobobo

2022-04-23

测试一下是否可以回答问题。

0
0

liuyubobobo

2022-04-23

我没有看你的代码的具体逻辑,但是你当前的代码肯定有问题的地方在于,对于已经找到的解,在回溯的过程中,会不断把解抹掉(你的 62 行做的事情)。


我的代码中:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情,就是在有解的时候返回, 而不去执行下面的 board[x][y] = '.';


继续加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程