频道栏目
首页 > 考试 > 其他 > 正文

[Leetcode] 37. Sudoku Solver 解题报告

2017-01-03 09:38:00      个评论    来源:魔豆(Magicbean)的博客  
收藏   我要投稿

题目

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)检查边界条件,如果已经到达边界条件,则直接返回或者将解加入到集合中;2)逐次给当前深度赋予所有可行值,并执行下一层深搜。

回溯法一般而言没有太多的技巧。不过我个人感觉这种题目一般包括两个典型类型:1)只要找到一个可行解即可;2)需要找到所有可行解。如果是类型1),则处理技巧是将深搜的返回值设为bool类型,这样一旦找到一个可行解就可以提前返回。如果是类型2),则将深搜的返回值设为void,同时定义一个全局解集合,每次找到一个可行解时则将其加入到集合中。本题属于类型1)。

代码

class Solution {  
public:  
    void solveSudoku(vector<vector<char>>& board)   
    {  
        DFS(board, 0, 0);  
    }  
private:  
    bool DFS(vector<vector<char>>& board, int row, int col)    
    {    
        if(row == 9)   
            return true;    
        if(col == 9)                                // try next row  
            return DFS(board, row + 1, 0);          
        if(board[row][col] != '.')                  // try next col  
            return DFS(board, row, col + 1);    
        for(int i = 1; i <= 9; i++)    
        {    
            int a, b;  
            for(a = 0; a < 9; a++)   
                if(board[row][a] == '0' + i)   
                    break;    
            if(a != 9)                              // i already exists in this row  
                continue;    
            for(a = 0; a < 9; a++)   
                if(board[a][col] == '0' + i)   
                    break;    
            if(a != 9)                              // i already exists in this col  
                continue;    
            for(a = row/3*3; a < row/3*3+3; a++)    
            {    
                for(b = col/3*3; b < col/3*3+3; b++)    
                    if(board[a][b] == '0'+i)   
                        break;    
                if(b != col/3*3+3)   
                    break;    
            }    
            if(!(a == row/3*3+3 && b == col/3*3+3)) // i already exists in this grid  
                continue;    
            board[row][col] = '0' + i;    
            if(DFS(board, row, col + 1))            // try next col  
                return true;    
            board[row][col] = '.';                  // backtracking  
        }    
        return false;    
    }    
};
上一篇:220. Contains Duplicate III
下一篇:753 A. Santa Claus and Candies
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站