leetcode Question 107: Sudoku Solver

Sudoku Solver:

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.
A sudoku puzzle...

Analysis:

I was running this program on the old OJ and always failed because of the "time limit exceeded".
On the new OJ, it seems there are only 6 test samples and my code below passed it using 2304ms.

The idea of this problem is just the searching (either DFS or BFS). In my code below I used BFS, tried to use more space less time. BFS is conducted according to each blank ('.' in this problem) cell, assign a valid number (char actually) satisfying no duplicates in the same row, column, as well as the local block. Then push the new status of the board into the BFS queue, keep searching until no blank cell exists.

Code:


class Solution {
public:
    bool find(vector<vector<char> > &cur, int &i, int &j){
        for (int ii=0;ii<9;ii++){
            for (int jj=0;jj<9;jj++){
                if (cur[ii][jj]=='.'){
                    i=ii;
                    j=jj;
                    return true;
                }
            }
        }
        return false;
    }
    
    unordered_set<char> valid(int i, int j, vector<vector<char> > &cur){
        unordered_set<char> se({'1','2','3','4','5','6','7','8','9'});
        for (int ii=0;ii<9;ii++){
            se.erase(cur[ii][j]);
            se.erase(cur[i][ii]);
        }
        
        for (int ii=0;ii<3;ii++){
            for (int jj=0;jj<3;jj++){
                se.erase(cur[(i/3)*3+ii][(j/3)*3+jj]);
            }
        }
        
        return se;
        
    }
    void solveSudoku(vector<vector<char> > &board) {
        queue<vector<vector<char> > > que;
        que.push(board);
        vector<vector<char> > cur;
        unordered_set<char> se;
        int i=0;
        int j=0;
        while (!que.empty()){
            cur = que.front();
            que.pop();
            if (find(cur,i,j)==false){
                board = cur;
                return;
            }else{
                se = valid(i,j,cur);
                for (const char& x: se){
                    cur[i][j]=x;
                    que.push(cur);  
                }
            }
        }
    }
};

2 comments:

  1. Hi, I do not get what does line 47 mean, "for (const char& x: se)", is there any information about what does it mean for colon before set, also, why use a & here? Thank you!

    ReplyDelete
    Replies
    1. The line 47 is a new way of using loop (called range-based loop), which is a simple way of using loop in newer version of C++. It is the same as using "iterator","se.begin()" "se.end()" fashion.

      Using & is just a reference, a way of avoiding copying the object.
      Using const is to make sure this char cannot be modified.

      Delete