LeetCode: 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...

...and its solution numbers marked in red.

---

Use backtracking strategy to solve this problem. First find a blank spot. Then find available candidate values. And go to find next blank spot. If the current solution is unresolvable, go back on step and try another one.

C++ Code:

/*
 * func: find_available
 * goal: find available candidates for current spot
 * @param candidates: candidates set
 * @param board: current sudoku board
 * @param row: row index
 * @param column: column index
 * return:
 */
void find_available(vector<bool>& candidates, const vector<vector<char> > &board, int row, int column){
    for(int i = 0; i < 9; ++i){
        if(board[i][column] != '.'){
            candidates[board[i][column] - '1'] = false;
        }
        
        if(board[row][i] != '.'){
            candidates[board[row][i]-'1'] = false;
        }
        
        if(board[row/3*3 + i/3][column/3*3 + i%3] != '.'){
            candidates[board[row/3*3 + i/3][column/3*3 + i%3] - '1'] = false;
        }
    }
}
/*
 * func: solve_sudoku_helper
 * goal: solve the sudoku problem in backtracking
 * @param board: the sudoku board
 * @param row: current row index
 * @param column: current column index
 * return: true or false
 */
bool solve_sudoku_helper(vector<vector<char> > &board, int row, int column){
    //Find the next empty position
    while(row < 9 && board[row][column] != '.'){
        row = (column == 8) ? row + 1 : row;
        column = (column + 1) % 9;
    }
    if(row == 9){
        return true;
    }
    //Find available candidate for the current spot
    vector<bool> candidates(9, true);
    find_available(candidates, board, row, column);
    for(int i = 0; i < 9; i++){
        if(candidates[i]){
            board[row][column] = i + '1';
            if(solve_sudoku_helper(board, row, column)){
                return true;
            }
        }
    }
    board[row][column] = '.';
    return false;
}
/*
 * func: solve_sudoku
 * goal: solve the given sudoku problem
 * @param board: input sudoku board
 * return: 
 */
void solve_sudoku(vector<vector<char> > &board){
    solve_sudoku_helper(board, 0, 0);
}

For Python code, we can just convert the C++ code and it can pass the test. Here I introduced another solution which looks simpler but cannot pass because of time limit.

def same_row(i, j):
    return i/9 == j/9

def same_col(i, j):
    return (i-j) % 9 == 0

def same_block(i, j):
    return i/27 == j/27 and i%9/3 == j%9/3

def solve_sudoku_helper(board_list, board):
    spot = board_list.find('.')

    if spot == -1:
        for i in xrange(9):
            board[i] = board_list[i*9: (i+1)*9]
        return

    excluded_numbers = set()
    for i in range(81):
        if same_row(spot, i) or same_col(spot, i) or same_block(spot, i):
            excluded_numbers.add(board_list[i])

    for candidate in '123456789':
        if candidate not in excluded_numbers:
            solve_sudoku_helper(board_list[:spot] + candidate + board_list[spot+1:], board)

# func: solve sudoku problem
# @param board: current sudoku board
# @return:
def solve_sudoku(board):
    boardlist = ''.join(x for row in board for x in row)
    solve_sudoku_helper(boardlist, board)

Reference Link:

1.Simple Sudoku solver in python | Bite Sized Python Tips: http://freepythontips.wordpress.com/2013/09/01/sudoku-solver-in-python/