LeetCode 37.Sudoku Solver题目解析-wowAC

Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.


A sudoku puzzle…


…and its solution numbers marked in red.

题目复述

    给你一个数独游戏棋盘,找出一组答案。题目保证只有一个解。

    数独游戏规则:

        (1).同行数字不重复,即为1,2,3,4,5,6,7,8,9

        (2).同列数字不重复,同(1)

        (3).每个3*3小格子内的数字也不重复,同(1)

题目解析

 

1.暴力枚举法

    因为每个待填的格子会有多个待填的值,因此我们采用深度优先遍历的方法搜索答案,从左到右从上到下遇到空格依次枚举填写[1-9]9个数字。如果填了某个数字和规则冲突,则可以剪枝。

    在实现的时候待填的格子用一个整数dept表示,当前行r(dept/列宽)和列c(dept%列宽)都可以从dept解析出来。

class Solution {
public:
    
    //检查r行c列是不是可以填num
    bool check(int r, int c, int num, vector<vector<char>>& board) {
        //检查行
        for(int i=0; i<board[0].size(); i++) {
            if(board[r][i] == '.') continue;
            if(board[r][i]-'0' == num) return false;
        }
        //检查列
        for(int i=0; i<board.size(); i++) {
            if(board[i][c] == '.') continue;
            if(board[i][c]-'0' == num) return false;
        }
        //检查方块
        for(int i=(r/3)*3; i<(r/3)*3+3; i++)
            for(int j=(c/3)*3; j<(c/3)*3+3; j++) {
                if(board[i][j] == '.') continue;
                if(board[i][j]-'0' == num) return false;
            }
        return true;
    }
    
    bool dfs(int dept, vector<vector<char>>& board) {
        if(dept == board.size()*board[0].size()) return true;
        
        bool res = false;   //是否找到解
        int r = dept/board[0].size(), c = dept%board[0].size();
        if(board[r][c] != '.') return dfs(dept+1, board);
        else {
            for(int num=1; num<=9; num++) {  //枚举要填的数
                bool can = check(r, c, num, board);
                if(!can) continue;          //发现不满足规则,剪枝。
                board[r][c] = num + '0';
                res = res || dfs(dept+1, board);
                if(res) break;        //找到答案 直接跳出
                board[r][c] = '.';
            }
        }
        return res;
    }
    void solveSudoku(vector<vector<char>>& board) {
        dfs(0, board);
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注