Thursday, October 10, 2013

Sudoku Solver [Leetcode]

Write a program to solve a Sudoku puzzle by filling the empty cells. (Sudoku Puzzles - The Rules)
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: backtracking.

class Solution {
public:
    const int SIZE = 9;
    bool isCollision(int& hashmap, char val){
            if(isdigit(val)){
                int digit = val-'0';
                if((hashmap & (1<<digit)) ==0)
                    hashmap |= (1<<digit);
                else
                    return true;
            }
            return false;
    }
    bool isValid(vector<vector<char> > &board, int x, int y){
        if(x>=SIZE || y>=SIZE || x<0 || y<0) return false;
        //the x-th row has any number in [1-9] occuring just once
        int hashmap = 0;
        for(int i=0; i<SIZE; ++i)
            if(isCollision(hashmap, board[x][i]))
                return false;
        //the y-th col has any number in [1-9] occuring just once
        hashmap = 0;
        for(int i=0; i<SIZE; ++i)
            if(isCollision(hashmap, board[i][y]))
                return false;
        //the subbox containing (x,y) has any number in [1-9] occuring just once
        hashmap = 0;
        x = x/3; y = y/3; //locate the subbox
        for(int i=0; i<3; ++i)
            for(int j=0; j<3; ++j){
                int X = x*3+i, Y = y*3+j;
                if(X>=0 && X<SIZE && Y>=0 && Y<SIZE){
                    if(isCollision(hashmap, board[X][Y]))
                        return false;
                }
            }
        return true;
    }
    bool solveSudoKuHelper(vector<vector<char> > &board, int x, int y){
        if(x>=SIZE || y>=SIZE)
            return true;
        if(board[x][y]!='.'){
            if(solveSudoKuHelper(board, x+(y+1)/SIZE, (y+1)%SIZE))
                //all the rest empty cells can be filled out successfully
                return true;
            return false;
        }
        else{
            for(int i=0; i<SIZE; ++i){
                board[x][y] = '1'+i;
                if(isValid(board, x, y) && solveSudoKuHelper(board, x+(y+1)/SIZE, (y+1)%SIZE))
                    //the current cell and all the rest empty cells can be filled out successfully
                    return true;
            }
            board[x][y] = '.';
            return false;
        }
    }
    void solveSudoku(vector<vector<char> > &board) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        solveSudoKuHelper(board, 0, 0);
    }
};

No comments:

Post a Comment