首页 > itarticle > 【leetcode】 sudoku solver

【leetcode】 sudoku solver

admin 11月 13, 2020 0

地址

https://leetcode.com/problems/sudoku-solver/description/

题目

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.

思路

第一眼暴力，然后觉得不可能这么sb,还以为要用dancing-link，后来觉得做个leetcode怎么可能会需要用到这种东西。百度一发题解，果然如此，就是sb暴力

代码

class  {
public:
    int ff=0,ur[10][10],ul[10][10],uu[10][10];
    vector<vector<char>> mp,ans;
    void init(void)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=1;j<=9;j++)
                ur[i][j]=ul[i][j]=uu[i][j]=1;
            for(int j=0;j<9;j++)
            {
                if(mp[i][j]!='.')
                    ur[i][mp[i][j]-'0']=0;
                if(mp[j][i]!='.')
                    ul[i][mp[j][i]-'0']=0;
            }
        }
        for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        if(mp[i][j]!='.')
            uu[i/3*3+j/3][mp[i][j]-'0']=0;
    }
    void dfs(int x,int y)
    {
        if(ff) return;
        if(x==9)
        {
            ff=1,ans=mp;
            return;
        }
        if(mp[x][y]!='.')
        {
            dfs(x+(y==8),(y+1)%9);
            return ;
        }
        for(int i=1;i<10;i++)
        if(ur[x][i]&&ul[y][i]&&uu[x/3*3+y/3][i])
        {
            ur[x][i]=ul[y][i]=uu[x/3*3+y/3][i]=0;
            mp[x][y]='0'+i;
            dfs(x+(y==8),(y+1)%9);
            mp[x][y]='.';
            ur[x][i]=ul[y][i]=uu[x/3*3+y/3][i]=1;
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        mp=board;
        init();
        dfs(0,0);
        board=ans;
    }
};