C++ template for Valid Sudoku & Sudoku Solver


  • 0
    F

    Problem 36 ---- Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            bool c1[9][9]={false}, c2[9][9]={false}, c3[9][9]={false};
            for(int i=0; i<9; i++){
                for(int j=0; j<9; j++){
                    if(board[i][j]!='.'){
                        int temp=board[i][j]-'1';
                        int index=(i/3)*3+j/3;
                        if(c1[i][temp] || c2[j][temp] || c3[index][temp])  return false;
                        c1[i][temp]=c2[j][temp]=c3[index][temp]=true;
                    }
                }
            }
            return true;
        }
    };
    

    We can use bitmap to record the existing information like this to save memory ...

       bool isValidSudoku(vector<vector<char>>& board) {
        vector<short> col(9, 0);
        vector<short> block(9, 0);
        vector<short> row(9, 0);
        for (int i = 0; i < 9; i++)
         for (int j = 0; j < 9; j++) {
             if (board[i][j] != '.') {
                 int idx = 1 << (board[i][j] - '0');
                 if (row[i] & idx || col[j] & idx || block[i/3 * 3 + j / 3] & idx)
                    return false;
                row[i] |= idx;
                col[j] |= idx;
                block[i/3 * 3 + j/3] |= idx;
             }
         }
         return true;
      }
    

    37 ---- 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.

    class Solution {
    public:
         void solveSudoku(vector<vector<char>>& board) {
             solve(board);
             return;
         }
    
         bool solve(vector<vector<char>>& board) {
            for(int i=0; i<9; i++){
                for(int j=0; j<9; j++){
                    if(board[i][j]=='.'){
                        for(int k=0; k<9; k++){
                            board[i][j]='1'+k;
                            /*** check all the position util return true ***/
                            if(isValid(board, i, j)){
                                if(solve(board))    return true;
                            }
                            board[i][j]='.';
                        }
                        /*** can not find solution for the first '.' position ***/
                        return false;
                    }
                }
            }
            return true;
        }
    
        bool isValid(const vector<vector<char>> &board, int x, int y){
            int i, j;
            /*** check column y ***/
            for(i=0; i<9; i++){
                if(i!=x && board[i][y]==board[x][y])  return false;
            }
            /*** check row x ***/
            for(j=0; j<9; j++){
                if(j!=y && board[x][j]==board[x][y])  return false;
            }
            /*** check the cute ***/
            for(i=3*(x/3); i<3*(x/3+1); i++){
                for(j=3*(y/3); j<3*(y/3+1); j++){
                    if((i!=x || j!=y) && board[i][j]==board[x][y])
                        return false;
                }
            }
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.