Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Sudoku Solver

Leetcode algorithms 第 37 题:Sudoku Solver。

题目

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.

解答

解数独。直接使用暴力dfs进行求解,遍历每个格子,如果元素为空,找出该行、该列、该九宫格内未使用的数字,填上后进行递归搜索。

具体代码如下:

class Solution {
public:
    bool dfs(int x, vector<vector<char> > &b)
    {
        if (x == 81) return true; //填完了
        int r = x / 9, c = x % 9;
        if (b[r][c] != '.') return dfs(x + 1, b);
        
        bool used[11] = {0};//每个数字是否使用过
        for (int i = 0; i < 9; i++)
        {
            if (b[r][i] != '.') used[b[r][i]-'0'] = 1; //行
            if (b[i][c] != '.') used[b[i][c]-'0'] = 1; //列
        }
        
        int tx = r / 3 * 3, ty = c / 3 * 3;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (b[tx+i][ty+j] != '.') //九宫格
                    used[b[tx+i][ty+j]-'0'] = 1;
                
        for (int i = 1; i <= 9; i++)
            if (!used[i])
            {
                b[r][c] = char(i + '0');
                if (dfs(x+1, b)) return true;
                // b[r][c] = '.';
            }
        return false;
    }
    
    void solveSudoku(vector<vector<char> > &board) {
        dfs(0, board);
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论