LeetCode 37 Sudoku Solver

    
        标签：
        
            回溯法
        
            LeetCode
        
    发布于：2022-02-22 17:01:01
    编辑于：2022-02-22 17:38:40
    浏览量：680

概述

https://leetcode.com/problems/sudoku-solver/

回溯法

又到了找 bug 时间，下面的代码越界了：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board, 0, 0);
    }
    
    void backtrack(vector<vector<char>>& board, int i, int j) {
        if (i == 9 && j == 0) return;
        int nextI = i;
        int nextJ = j + 1;
        if (nextJ == 9) {
            nextJ = 0;
            nextI ++;
        }
        if (board[i][j] == '.') {
            for (int i = 0; i < 9; i ++) {  // bug #1: i 重复了哦，不能用 i
                char c = i + '0';  // bug #2: 数独里起始字符是 1 哦
                if (isValid(board, i, j, c)) {
                    board[i][j] = c;
                    backtrack(board, nextI, nextJ);
                    board[i][j] = '.';
                }
            }
        } else {
            backtrack(board, nextI, nextJ);
        }
    }
    
    bool isValid(vector<vector<char>>& board, int r, int c, char t) {
        for (int i = 0; i < 9; i ++) {
            if (board[r][i] == t || board[i][c] == t) return false;
        }
        
        for (int i = 3 * (r / 3); i < 3 * (r / 3) + 3; i ++) {
            for (int j = 3 * (c / 3); j < 3 * (j / 3) + 3; j ++) {   // bug #3: c 写成了 j
                if (board[i][j] == t) return false;
            }
        }
        return true;
    }
};

改正后的解答：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board, 0, 0);
    }
    
    bool backtrack(vector<vector<char>>& board, int i, int j) {
        if (i == 9 && j == 0) return true;
        int nextI = i;
        int nextJ = j + 1;
        if (nextJ == 9) {
            nextJ = 0;
            nextI ++;
        }
        if (board[i][j] == '.') {
            for (char c = '1'; c <= '9'; c ++) {
                if (isValid(board, i, j, c)) {
                    board[i][j] = c;
                    if (backtrack(board, nextI, nextJ)) return true;
                    board[i][j] = '.';
                }
            }
        } else {
            if (backtrack(board, nextI, nextJ)) return true;
        }
        return false;
    }
    
    bool isValid(vector<vector<char>>& board, int r, int c, char t) {
        for (int i = 0; i < 9; i ++) {
            if (board[r][i] == t || board[i][c] == t) return false;
        }
        
        for (int i = 3 * (r / 3); i < 3 * (r / 3) + 3; i ++) {
            for (int j = 3 * (c / 3); j < 3 * (c / 3) + 3; j ++) {
                if (board[i][j] == t) return false;
            }
        }
        return true;
    }
};

Links: leetcode-37-sudoku-solver