LeetCode 0037 - Sudoku Solver

Reck Zhang

发布于 2021-08-11 10:21:25

2010

发布于 2021-08-11 10:21:25

文章被收录于专栏：Reck Zhang

Sudoku Solver

Desicription

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.

Solution

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除

bash