LeetCode: N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

---

A straight forward approach is to check every possible solution with back-tracking.

C++ Code:

/*
 * func: check_solution
 * goal: check if current position can be put a queen
 * @param row: row index
 * @param column: column index
 * @param n: total number of queens
 * @param solution: current solution to check
 * return: true or false
 */
bool check_solution(int row, int column, int n, const vector<string> &solution){
    //Check column
    for(int i = 0; i < n; ++i){
        if(solution[i][column] == 'Q'){
            return false;
        }
    }
    //Check right downside
    for(int i=1; row+i < n && column+i < n; ++i){
        if(solution[row+i][column+i] == 'Q'){
            return false;
        }
    }
    //Check left upside
    for(int i=1; row-i >= 0 && column-i >= 0; ++i){
        if(solution[row-i][column-i] == 'Q'){
            return false;
        }
    }
    //Check right upside
    for(int i=1; row-i >= 0 && column+i < n; ++i){
        if(solution[row-i][column+i] == 'Q'){
            return false;
        }
    }
    //Check left downside
    for(int i=1; row+i < n && column-i >= 0; ++i){
        if(solution[row+i][column-i] == 'Q'){
            return false;
        }
    }
    return true;
}

/*
 * func: solve_nqueens_helper
 * goal: helper function for solve_nqueens
 * @param current_row: current row to deal with
 * @param n: the number of queens
 * @param solution: current solution
 * @param result: final result set
 * return:
 */
void solve_nqueens_helper(int current_row, int n, vector<string> &solution, vector<vector<string> > &result){
    if(current_row == n){
        result.emplace_back(solution);
        return;
    }
    for(int i = 0; i < n; i++){
        if(check_solution(current_row, i, n, solution)){
            solution[current_row][i] = 'Q';
            solve_nqueens_helper(current_row+1, n, solution, result);
        }
        solution[current_row][i] = '.';
    }
}

/*
 * func: solve_nqueens
 * goal: solve the problem n queens
 * @param n: the number of queens
 * return: all possible solutions
 */
vector<vector<string> > solve_nqueens(int n){
    assert(n > 0);
    vector<vector<string> > result;
    vector<string> solution(n, string(n,'.'));
    solve_nqueens_helper(0, n, solution, result);
    return result;
}

Python Code:

# func: check if current position can be set to 'Q'
# @param solution: current solution
# @param row: row index
# @param column: column index
# @param n: dimension
# @return: True or False
def check_ok(solution, row, column, n):
        #check column
        i = 0
        while i < n:
            if i != row and solution[i][column] == 'Q':
                return False
            else:
                i += 1

        #check diagonal
        i = row-1
        j = column-1
        while i >= 0 and j >= 0:
            if solution[i][j] == 'Q':
                return False
            else:
                i -= 1
                j -= 1

        i = row+1
        j = column+1
        while i < n and j < n:
            if solution[i][j] == 'Q':
                return False
            else:
                i += 1
                j += 1

        i = row+1
        j = column - 1
        while i < n and j >= 0:
            if solution[i][j] == 'Q':
                return False
            else:
                i += 1
                j -= 1

        i = row-1
        j = column+1
        while i >= 0 and j < n:
            if solution[i][j] == 'Q':
                return False
            else:
                i -= 1
                j += 1

        return True

# func: helper function for solve n-queens
# @param current_row: current row
# @param n: dimension
# @solution: current solution
# @result: final result set
def solve_nqueens_helper(current_row, n, solution, result):
    if current_row == n:
        result.append(solution)
        return

    for i in xrange(n):
        solution[current_row] = '.'*i + 'Q' + '.'*(n-1-i)
        if check_ok(solution, current_row, i, n):
            solve_nqueens_helper(current_row+1, n, solution[:], result)
        solution[current_row] = '.' * n

# func: solve the given n-queens problem
# @param n: given dimension n
# @return: all possible solution
def solve_nqueens(n):
    if n <= 0:
        return [[]]
    solution = []
    for _ in xrange(n):
        solution.append('.' * n)
    result = []
    solve_nqueens_helper(0, n, solution, result)
    return result