My cpp solution using 3 hash-maps


  • 0
    X
    class Solution {
    public:
    		void solveSudoku(vector<vector<char> >& board)
    		{
    			vector<pair<int, int> > emptyCells;
    			vector<map<char,bool> > rowSet, colSet, matrixSet;
    			map<char,bool> row, col, matrix;
    			for ( size_t i = 0 ; i < 9; ++i )
    			{
    				for ( char v = '1' ; v <= '9'; ++v ) { row[v] = col[v] = matrix[v] = false; }
    				for ( size_t j = 0 ; j < 9; ++j )
    				{
    					if (board[i][j]!='.'){
    						row[board[i][j]] = true;
    					}
    					else{
    						emptyCells.push_back(make_pair(i, j));
    					}
    					if (board[j][i]!='.') col[board[j][i]]=true;
    					int r = j/3+(i/3)*3, c = j%3+(i%3)*3;
    					if (board[r][c]!='.') matrix[board[r][c]]=true;
    				}
    				rowSet.push_back(row); colSet.push_back(col); matrixSet.push_back(matrix);
    			}
    			Solution::dfs(board, emptyCells, rowSet, colSet, matrixSet);
    		}
    		static bool dfs(
    			vector<vector<char> >& board,
    			vector<pair<int, int> >& emptyCell,  
    			vector<map<char,bool> >& rowSet,
    			vector<map<char,bool> >& colSet,
    			vector<map<char,bool> >& matrixSet)
    		{
    			if ( emptyCell.empty() ) return true;
    			int i = emptyCell.back().first, j = emptyCell.back().second;
    			for ( char v = '1'; v<='9'; ++v )
    			{
    				if (!rowSet[i][v] && !colSet[j][v] &&  !matrixSet[(i/3)*3+j/3][v] )
    				{
    					board[i][j] = v;
    					rowSet[i][v] = colSet[j][v] = matrixSet[(i/3)*3+j/3][v] = true;
    					emptyCell.pop_back();
    					if ( Solution::dfs(board, emptyCell, rowSet, colSet, matrixSet) ){
    						return true;
    					}
    					else{
    						emptyCell.push_back(make_pair(i, j));
    						rowSet[i][v] = colSet[j][v] = matrixSet[(i/3)*3+j/3][v] = false;
    					}
    				}
    			}
    			return false;
    		}
    };

Log in to reply
 

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