A simple DFS solution


  • 22
    J
    class Solution {
    public:
    	bool isValidSudoku(vector<vector<char> > &board) {
    		return true;
    	}
    	void solveSudoku(vector<vector<char> > &board) {
    		util(board, 0);
    	}
    	bool util(vector<vector<char>>& board, int pos)
    	{
    		if (pos >= 81)
    			return true;
    		int i = pos / 9;
    		int j = pos % 9;
    		if (board[i][j] != '.')
    			return util(board, pos + 1);
    		else
    		{
    			for (char c = '1'; c <= '9'; c++)
    			{
    				if (!isInRow(board, i,c) && !isInCol(board, j, c) && !isInRec(board, i, j, c))
    				{
    					board[i][j] = c;
    					if (util(board, pos + 1))
    						return true;
    					else
    						board[i][j] = '.';
    				}
    			}
    			return false;
    		}
    	}
    
    	bool isInRow(vector<vector<char>>& board, int i, char c)
    	{
    		vector<char>& row = board[i];
    		for (int k = 0; k < 9; k++)
    		{
    			if (row[k] == c)
    				return true;
    		}
    		return false;
    	}
    	bool isInCol(vector<vector<char>>& board,int j, char c)
    	{
    		for (int k = 0; k < 9; k++)
    		{
    			if (board[k][j] == c)
    				return true;
    		}
    		return false;
    	}
    	bool isInRec(vector<vector<char>>& board, int i, int j, char c)
    	{
    		int bigrow = i / 3, bigcol = j / 3;
    		for (int m = 3 * bigrow; m < 3 * (bigrow + 1); m++)
    		{
    			for (int n = 3 * bigcol; n < 3 * (bigcol + 1); n++)
    				if (board[m][n] == c)
    					return true;
    		}
    		return false;
    	}
    };

  • 9
    J

    my solution use 3 hash table to save the filled numbers, this leads more efficiency

    void solveSudoku(vector<vector<char> > &board) {
    	if (board.size() != 9 || board[0].size() != 9)
    	{
    		return;
    	}
    
    	int rowhash[9][9] = {{0}}, colhash[9][9] = {{0}}, blockhash[9][3][3] = {{{0}}};
    	for ( int i = 0; i < 9; i++)
    	{
    		for ( int j = 0; j < 9; j++)
    		{
    			if (board[i][j] != '.')
    			{
    				int num = board[i][j] - '1';
    				rowhash[num][i] = 1;
    				colhash[num][j] = 1;
    				blockhash[num][i/3][j/3] = 1;
    			}
    		}
    	}
    	
    	solveSudoku_DFS(board, 0, rowhash, colhash, blockhash);
    }
    bool solveSudoku_DFS(vector<vector<char> > &board, int pos, int rowhash[9][9], int colhash[9][9], int blockhash[9][3][3])
    {
    	if ( pos >= 81)
    	{
    		return true;
    	}
    	int i = pos / 9, j = pos % 9;
    
    	if (board[i][j] != '.')
    	{
    		return solveSudoku_DFS(board, pos+1, rowhash, colhash, blockhash);
    	} 
    	else
    	{
    		for ( int num = 0; num < 9; num++)
    		{
    			if (rowhash[num][i] != 1 && colhash[num][j] != 1 && blockhash[num][i/3][j/3] != 1)
    			{
    				board[i][j] = '1' + num;
    				rowhash[num][i] = 1;
    				colhash[num][j] = 1;
    				blockhash[num][i/3][j/3] = 1;
    				if (solveSudoku_DFS(board, pos+1, rowhash, colhash, blockhash))
    				{
    					return true;
    				} 
    				else
    				{
    					board[i][j] = '.';
    					rowhash[num][i] = 0;
    					colhash[num][j] = 0;
    					blockhash[num][i/3][j/3] = 0;
    				}
    			}
    		}
    
    		return false;
    	}
    }

  • 0
    L

    I wish I could upvote your comment


  • 0
    J

    I can not find the votes button in editing page of my comment


  • 0
    T

    isn't the sudoku problem exactly the same as 8-queen, with just a different verification method ?


  • 1
    M

    just follow your idea, make the checking part simpler

    void solveSudoku(vector<vector<char>>& board) {
        solve(board, 0);
    }
    bool solve(vector<vector<char>>& board, int ind){
        if(ind==81) return true; 
        int i=ind/9, j=ind%9;
        if(board[i][j]!='.') return solve(board, ind+1);
        else{
            for(char f = '1'; f <= '9'; f++)
            {
                if(isValidFill(board, i, j, f))
                {
                    board[i][j]= f;
                    if(solve(board, ind+1)) return true;                
                    board[i][j]='.';
                }
            }
            return false;
        }
    }
    bool isValidFill(vector<vector<char>>& board, int i, int j, char fill) {
        for(int k=0; k<9; k++)
        {
            if(board[i][k]==fill) return false; //check the row
            if(board[k][j]==fill) return false; //check the column
            int r= i/3*3+j/3;   //select the block
            if(board[r/3*3+k/3][r%3*3+k%3]==fill) return false; //check the block
        }            
        return true;
    }

  • 0
    J

    really smart.thanks for it.


  • 0
    A

    Following the same idea with hashtable, but using bit vector to save on space

        class Solution {
            
            vector<int> rowhash{vector<int>(9,0)};   // bit vector 000000000, each 1<<j represent whether index i+1 is already in row j
            vector<int> colhash{vector<int>(9,0)};
            vector<int> blockhash{vector<int>(9,0)};     // bit vector 000000000, each 1<<j represent whether index i+1 is already in superblock j
            int sz = 9;
        public:
            void solveSudoku(vector<vector<char>>& board) {
                if (board.size() != sz || board[0].size() != sz) return;
                
                for (int i=0; i<sz; i++) {
                    for (int j=0; j<sz; j++) {
                        if (board[i][j] != '.') {
                            int num = board[i][j]-'1';
                            rowhash[num] |= (1<<i);
                            colhash[num] |= (1<<j);
                            int r = i/3*3+j/3;  // select the superblock that (i,j) reside
                            blockhash[num] |= (1<<r);
                        }
                    }
                }
                
                solveSudoku(board, 0);  // 9x9 board has 0->80 positions
            }
            
            // DFS solution, recurse all the way down, if false, then backtrack
            bool solveSudoku(vector<vector<char>>& board, int pos) {
                if (pos == 81) return true; // filled the entire board
                int i = pos/9;
                int j = pos%9;
                int r = i/3*3+j/3;  // select the superblock that (i,j) reside
                
                if (board[i][j] != '.') return solveSudoku(board, pos+1);
                
                for (char c = '1'; c <= '9'; c++) {
                    int num = c-'1';
                    if (!(rowhash[num]&(1<<i)) && !(colhash[num]&(1<<j)) && !(blockhash[num]&(1<<r))) { // checks if board is valid
                        board[i][j] = c;
                        rowhash[num] |= (1<<i); // mark that num is in row i
                        colhash[num] |= (1<<j); // mark that num is in col j
                        blockhash[num] |= (1<<r);   // mark that num is in superblock r
                        
                        if (solveSudoku(board,pos+1)) return true;  // DFS
                        
                        board[i][j] = '.'; // backtrack
                        rowhash[num] &= ~(1<<i);
                        colhash[num] &= ~(1<<j);
                        blockhash[num] &= ~(1<<r);
                    }
                }
                
                return false;
            }
        };

Log in to reply
 

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