Блог пользователя acash

Автор acash, история, 5 лет назад, По-английски

Sudoku solver

I have added comments in my solution ,I am getting wrong answer on leetcode

Is below condition correct to check if i can find solution for coming places.Since it is hard to debug of large number of recursive calls Please can anyone help me where I am doing wrong?

if(ok==false){ //if i didn't find a single position to put a number here
     board[i][j]='.'; //then some thing wrong has happened earlier 
     return false;
}

My solution class

    class Solution {
    public:
        bool isvalid(vector<vector<char>>board,int x,int y,char c){  //to check if there is no duplicates
                                                            //according to given condition
            for(int i=1;i<=9;i++){
                if(board[(x+i)%9][y]==c)return false;  //checking in row
                if(board[x][(y+i)%9]==c)return false;  //checking in col

            }
            for(int i=-1;i<=1;i++){
                for(int j=-1;j<=1;j++){      //checking in 3*3 square
                    if(i==0&&j==0)continue;
                    int row = x+i;
                    int col = y+j;
                    if(row>=0 && col<9 && col>=0 && row<9 && board[row][col]==c)return false;
                }
            }
            return true;
        }
        bool solve(vector<vector<char>>board){
            int n = board.size();
            int m = board[0].size();

            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(board[i][j]=='.'){
                        bool ok=false;   //to check  if at least one value can be place 
                        for(char c='0';c<='9';c++){  //at the current pos or not 

                            board[i][j]=c;
                            if(isvalid(board,i,j,c)){
                                ok=true;
                                if(solve(board))return true; //if valid see remaining  board can be solve or not
                            }
                        }
                        if(ok==false){ //if i didn't find a single position to put a number here
                            board[i][j]='.'; //then some thing wrong has happened earlier 
                            return false;
                        }

                    }
                }
            }
            return true;
        }
        void solveSudoku(vector<vector<char>>& board) {
            solve(board);
        }
    };
  • Проголосовать: нравится
  • -33
  • Проголосовать: не нравится