LeetCode 37 Sudoku Solver(求解数独)(*)

简介:

翻译

写一个程序来通过填充空格求解数独。

空格用'.'表示。

你可以假定这里只有唯一解。

(示例图片看下文)

原文

这里写图片描述

代码

这道题我没写……不过为了博客的连续性,先凑一篇占个位置,以后再修改。

class Solution {
public:
    bool col[10][10],row[10][10],f[10][10];
    bool flag = false;
    void solveSudoku(vector<vector<char>>& board) {
         memset(col,false,sizeof(col));
         memset(row,false,sizeof(row));
         memset(f,false,sizeof(f));
         for(int i = 0; i < 9;i++){
             for(int j = 0; j < 9;j++){
                 if(board[i][j] == '.')   continue;
                 int temp = 3*(i/3)+j/3;
                 int num = board[i][j]-'0';
                 col[j][num] = row[i][num] = f[temp][num] = true;
             }
         }
         dfs(board,0,0);
    }
    void dfs(vector<vector<char>>& board,int i,int j){
        if(flag == true)  return ;
        if(i >= 9){
            flag = true;
            return ;
        }
        if(board[i][j] != '.'){
             if(j < 8)  dfs(board,i,j+1);
             else dfs(board,i+1,0);
             if(flag)  return;
        }

        else{
            int temp = 3*(i/3)+j/3;
            for(int n = 1; n <= 9; n++){
                if(!col[j][n] && !row[i][n] && !f[temp][n]){
                    board[i][j] = n + '0';
                    col[j][n] = row[i][n] = f[temp][n] = true;
                    if(j < 8)  dfs(board,i,j+1);
                    else dfs(board,i+1,0);
                    col[j][n] = row[i][n] = f[temp][n] = false;
                    if(flag)  return;
                }
            }
            board[i][j] = '.';
        }
    }
};
class Solution {
    // Table which allows compute the value of the cell
    // from the unambiguous bit mask as maskToValue[(mask%11)-1] 
    // uses the fact that (1<<i)%11 is unique for i = [0..8] and never produces 0
    const char maskToValue[10] = {'1','2','9','3','5','6','8','4','7','6'};
    struct SudokuSolver {
        // Using mask for each cell which constraints values which can be in the cell
        // Yeap, it is more storage, comparing to rows/cols/sqrs approach
        // but it allows to do super-fast reactive constraint propagation
        array<array<uint16_t,9>,9> board;
        SudokuSolver()
        {
            // Initializing the board with mask, which permits all numbers
            for (int i=0; i<9; i++)
                for (int j=0; j<9; j++)
                    board[i][j] = 0x1ff;
        }

        // adds value v [1..9] to the board, return false if it violates constraints
        bool add(int i, int j, int v)
        {
            return set(i, j, 1<<(v-1));
        }

        // set a value mask to the cell (i,j) and reactively updates constraints
        bool set(int i, int j, uint16_t mask)
        {
            int16_t prev = board[i][j];
            if (prev == mask) return true;
            if (!(prev&mask)) return false;
            board[i][j] = mask;
            return propagate(i,j,mask);
        }

        // propagates constraints as a result of setting i,j to mask
        bool propagate(int i, int j, uint16_t mask)
        {
            for (int k=0; k<9; k++) {
                if (k!=j && !addConstraint(i, k, mask)) return false;
                if (k!=i && !addConstraint(k, j, mask)) return false;
                int ii = (i/3)*3 + (k/3);
                int jj = (j/3)*3 + (k%3);
                if ((i != ii || j != jj) && !addConstraint(ii, jj, mask)) return false;
            }
            return true;
        }

        // prohibits putting value in mask to the cell (i,j)
        bool addConstraint(int i, int j, uint16_t mask)
        {
            int16_t newMask = board[i][j] &~ mask;
            if (newMask != board[i][j]) {
                if (newMask == 0) return false;
                board[i][j] = newMask;
                if (((newMask-1)&newMask)==0) {
                    // good news - we have only one possibility for the cell (i,j)
                    return propagate(i, j, newMask);
                }
            }
            return true;
        }

        // list of cell coordinates with >1 possibilities for values
        vector<pair<int,int>> v;
        void solve()
        {
            // finding all ambiguous cells
            for (int i=0; i<9; i++) {
                for (int j=0; j<9; j++) {
                    uint16_t mask = board[i][j];
                    if (mask&(mask-1)) v.push_back(make_pair(i,j));
                }
            }
            // note: it is also a good idea to sort v by the hamming weight, but
            // without sorting it is still super-fast
            // running backtracking as is
            backtrack(0);
        }

        // backtracking        
        bool backtrack(int k) {
            if (k == v.size()) return true;
            int i = v[k].first;
            int j = v[k].second;
            uint16_t mask = board[i][j];
            if (mask&(mask-1)) {
                // the board state is so compact and backtracking depth is so shallow, so
                // it is cheaper to make a snapshot of the state vs. doing classical
                // undo at each move
                auto snapshot = board;
                for (uint16_t cand = 1; cand<=0x1ff; cand = cand <<1) {
                    if (set(i, j, cand) && backtrack(k+1)) return true;
                    board = snapshot;
                }
                return false;
            }
            else {
                return backtrack(k + 1);
            }
        }

    };

public:
    void solveSudoku(vector<vector<char>>& board) {
        SudokuSolver solver;
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                char c = board[i][j];
                if (c != '.' && !solver.add(i,j,c-'0')) return;
            }
        }
        // At this point 9 of 10 sudokus published in magazines will be solved by constraint propagation
        // only 'hard' sudokus will require some (limited) backtracking 
        solver.solve();
        for (int i=0; i<9; i++)
            for (int j=0; j<9; j++)
                board[i][j] = maskToValue[(solver.board[i][j]%11)-1];
    }
};

一定要每天坚持呐……

目录
相关文章
|
6月前
|
Java
leetcode-37:解数独
leetcode-37:解数独
47 0
|
1月前
|
存储 算法 C++
Leetcode第三十六题(有效的数独)
这篇文章介绍了如何使用C++编写一个算法来验证一个9x9数独是否有效,遵循数独的规则,即数字1-9在每一行、每一列和每个3x3宫内只能出现一次。
38 0
|
3月前
|
存储 算法 索引
LeetCode第36题有效的数独
这篇文章介绍了LeetCode第36题"有效的数独"的解题方法,通过使用三个二维数组分别记录每一行、每一列以及每个3x3宫格内1-9数字出现的次数,来验证给定数独是否有效。
|
5月前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
41 0
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
6月前
leetcode-36:有效的数独
leetcode-36:有效的数独
49 0
|
JavaScript 前端开发 算法
LeetCode 37.解数独(注释完整+JavaScript解题)
LeetCode 37.解数独(注释完整+JavaScript解题)
75 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
108 2