LeetCode开心刷题二十一天——37. Sudoku Solver

男娘i 2023-08-17 15:14 104阅读 0赞

37. Sudoku Solver

Hard

95062FavoriteShare

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1.  Each of the digits `1-9` must occur exactly once in each row.
2.  Each of the digits `1-9` must occur exactly once in each column.
3.  Each of the the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

Empty cells are indicated by the character `'.'`.

![250px-Sudoku-by-L2G-20050714.svg.png][]  
A sudoku puzzle...

![250px-Sudoku-by-L2G-20050714_solution.svg.png][]  
...and its solution numbers marked in red.

Note:

*  The given board contain only digits `1-9` and the character `'.'`.
 *  You may assume that the given Sudoku puzzle will have a single unique solution.
 *  The given board size is always `9x9`.

Idea Statement:like 8 queen problem,we have to use tranverse.but the way we easier this action is to add limitations to the tranverse.

#include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<stack>
    #include<string>
    #include<memory>
    #include<memory.h>
    #include<hash_map>
    #include<map>
    #include<set>
    #include<unordered_map>
    using namespace std;
    class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            rows_ = vector<vector<int>>(9, vector<int>(10));
            cols_ = vector<vector<int>>(9, vector<int>(10));
            boxes_ = vector<vector<int>>(9, vector<int>(10));
            for(int i=0;i<9;i++)
            {
                for(int j=0;j<9;j++)
                {
                    const char c=board[i][j];
                    if(c!='.')
                    {
                        int n=c-'0';
                        int bx=j/3;
                        int by=i/3;
                        rows_[i][n] = 1;
                        cols_[j][n] = 1;
                        boxes_[by * 3 + bx][n] = 1;
                    }
                }
            }
             fill(board, 0, 0);
        }
    private:
        vector<vector<int>> rows_,cols_,boxes_;
        bool fill(vector<vector<char>>& board,int x,int y)
        {
            if(y==9) return true;
            int nx=(x+1)%9;
            int ny=(nx==0)?y+1:y;
            if(board[y][x]!='.') return fill(board,nx,ny);
    
            for(int i=1;i<=9;i++)
            {
                int bx=x/3;
                int by=y/3;
                int box_key=by*3+bx;
                if(!rows_[y][i]&&!cols_[x][i]&&!boxes_[box_key][i])
                {
                    rows_[y][i]=1;
                    cols_[x][i]=1;
                    boxes_[box_key][i]=1;
                    board[y][x]=i+'0';
                    if(fill(board,nx,ny)) return true;
                    board[y][x] = '.';
                    boxes_[box_key][i] = 0;
                    cols_[x][i] = 0;
                    rows_[y][i] = 0;
                }
    
            }
            return false;
        }
    };
    int main()
    {
        vector<vector<char>> board={
        {
             '.','.','4','.','.','.','6','3','.'},
        {
             '.','.','.','.','.','.','.','.','.'},
        {
             '5','.','.','.','.','.','.','9','.'},
        {
             '.','.','.','5','6','.','.','.','.'},
        {
             '4','.','3','.','.','.','.','.','1'},
        {
             '.','.','.','7','.','.','.','.','.'},
        {
             '.','.','.','5','.','.','.','.','.'},
        {
             '.','.','.','.','.','.','.','.','.'},
        {
             '.','.','.','.','.','.','.','.','.'}
        };
        Solution s;
        s.solveSudoku(board);
        for(vector<vector<char>>::iterator ite=board.begin();ite!=board.end();++ite)
        {
            vector<char> temp=*ite;
            for(vector<char>::iterator itee=temp.begin();itee!=temp.end();++itee)
            {
                cout<<*itee;
            }
            cout<<endl;
        }
    
    //    for(auto t:board)
    //    {
    //        cout<<t;
    //    }
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11205083.html

[250px-Sudoku-by-L2G-20050714.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png
[250px-Sudoku-by-L2G-20050714_solution.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png