Easy to understand C++ solution DFS


  • 1
    X

    class Solution {

    private:

    bool check(vector<vector<char>>& board, int row, int column, char fill)
    {
        for(int i = 0; i < 9; ++i)
            if(board[row][i] == fill)
                return false;
        for(int i = 0; i < 9; ++i)
            if(board[i][column] == fill)
                return false;
        for(int i = (row/3)*3; i < (row/3)*3 + 3; ++i)
            for(int j =(column/3)*3; j < (column/3)*3 + 3; ++j)
                if(board[i][j] == fill)
                    return false;
        return true;
    }
    
    int helper(vector<vector<char>> &board, int cell_num)
    {
    	// find the cell to fill
        int row = 0;
        int column = 0;
        for(int i = cell_num; i < 81; ++i)
        {
        	row = i / 9;
        	column = i % 9;
        	if(board[row][column] == '.')
        		break;
        	else if(i == 80) //if last cell is filled, throw exception to main function
                throw i;
        }
        
    	for(int i = 0; i < 9; ++i)
    	{
    		char fill = (char)(i + '1');
    		if(check(board, row, column, fill))
    		{
    			board[row][column] = fill;
    			helper(board, row * 9 + column);
    		}
    	}
    	board[row][column] = '.';
    }
    

    public:

    void solveSudoku(vector<vector<char>>& board) {
        try{
        	helper(board, 0);
        } catch(int){}
    }
    

    };


Log in to reply
 

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