leetcode 37. Sudoku Solver 一个经典的DFS深度优先搜索的做法

梦里梦外; 2022-06-09 09:44 154阅读 0赞

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.

![这里写图片描述][SouthEast]

解决办法就是DFS深度优先搜索，这个你还需要好好学习。

这个是典型的DFS深度优先搜索，其实也是回溯的做法，这道题有一个很明显的递归套路

代码如下：

public class Solution
    {
        
        /*
         * 很明显，这个是一个会回溯问题，回溯的本质就是DFS和剪枝。深度搜索常常
         * 使用递归，遇到 '.'递归遍历求解，若无解，回溯
         * 
         * 一般递归函数都在开头位置判断是否结束，但是对于该问题而言，不大容易判断叶节点。
         * 所以这里采用的是利用返回值true或false来对树的深度进行控制。
         * 如果为solve到false时，就回溯。回溯的手段就是使用更改函数主体复位，并return。
         * */
    
        //正如上述分析，其实很简单，和N Queue很类似
        public void solveSudoku(char[][] board) 
        {
            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 k='1';k<='9';k++)
                        {
                            //设置可能的解
                            board[i][j]=k;
                            //判断是否vaild，和递归判断是否可解
                            if(isValid(board,i,j) && solve(board) )
                                return true;
                            else 
                                //不可解的情况下，回溯，在本题就是复位即可
                                board[i][j]='.';
                        }
                        //遍历完之后，让无答案就是无解
                        return false;
                    }
                }
            }
    
        return true;
    
    }
        //判断当前board是否有效
        boolean isValid(char[][] board,int row ,int col)
        {
            //比较行向量
            for(int i=0;i<board.length;i++)
                if(i!=row && board[i][col]==board[row][col])
                    return false;
    
            //比较列向量
            for(int i=0;i<board[0].length;i++)
                if(i!=col && board[row][i]==board[row][col])
                    return false;
    
            //计算小正方形的开始位置
            int begRow=3*(row/3);
            int begCol=3*(col/3);
    
            //遍历小正方形
            for(int i=begRow;i<begRow+3;i++)
            {
                for(int j=begCol;j<begCol+3;j++)
                {
                    if(i!=row && j!=col && board[i][j]==board[row][col])
                        return false;
                }
            }
    
            return true;
        }
    }

下面是C++的做法，这道题是很经典的DFS深度优先搜索遍历的做法，很值得学习

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        void solveSudoku(vector<vector<char>>& board) 
        {
            solveByDFS(board);
        }
    
        bool solveByDFS(vector<vector<char>>& board)
        {
            for (int i = 0; i < board.size(); i++)
            {
                for (int j = 0; j < board[0].size(); j++)
                {
                    if (board[i][j] == '.')
                    {
                        for (char key = '1'; key <= '9'; key++)
                        {
                            board[i][j] = key;
                            if (isVaild(board, i, j) && solveByDFS(board))
                                return true;
                            else
                                board[i][j] = '.';
                        }
                        return false;
                    }
                }
            }
            return true;
        }
    
        bool isVaild(vector<vector<char>>& board, int row, int col)
        {
            for (int i = 0; i < board[0].size(); i++)
            {
                if (i != col && board[row][i] == board[row][col])
                    return false;
            }
    
            for (int i = 0; i < board.size(); i++)
            {
                if (i != row && board[i][col] == board[row][col])
                    return false;
            }
    
            int a = 3 * (row / 3);
            int b = 3 * (col / 3);
            for (int i = a; i < a + 3; i++)
            {
                for (int j = b; j < b + 3; j++)
                {
                    if (i != row && j != col && board[i][j] == board[row][col])
                        return false;
                }
            }
            return true;
        }
    };

[SouthEast]: /images/20220609/6ebd5ed677054112bc0a28f3659728fd.png