欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 37 解数独

程序员文章站 2022-05-20 13:00:14
...

题目

leetcode 37 解数独
编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

回溯分析

  • 每次可以在1~9中选择,路径上的每个节点的解空间是[1~9]
  • 终止条件:路径长度超过81
  • 解的判断条件:如果每个空白节点填入的数字都经过规则check,那么终止时,将有一个解,当出现一个解后,直接退出回溯算法,不再搜索解
  • 减枝:填入当前节点的值需要符合数组规则

code

class Solution {
    bool ok =false;
    bool check(vector<vector<char>>& board,int row,int col,char v){
        int a = (row/3)*3;
        int b = (col/3)*3;
        for(int i = 0; i < 9;++i){
            if(v == board[row][i]  || v == board[i][col])
                return false;
        }
        for(int i = a; i < a+3;++i ){
            for(int j = b;j < b+3;++j)
                if(v == board[i][j]) return false;
        }
        return true;
    }
    void backtrace(vector<vector<char>>& board,int n){
        if(n>80){
            ok = true;
            return;
        }
        int row = n / 9;
        int col = n % 9;
        //不用填充
        if(board[row][col] != '.'){    
            return backtrace(board,n+1);
        }
        for(int i = 1; i <10;++i){
            if(check(board,row,col,i+'0')){
                board[row][col] = i+'0';
                backtrace(board,n+1);
                //如果找到了解,直接退出,否则回溯
                if(ok) return;;
                board[row][col] = '.';
            }
        }
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrace(board,0);
    }
};
相关标签: leetcode解题