LeetCode - N-Queens | Darren's Blog

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

public ArrayList<String[]> solveNQueens(int n) {

        ArrayList<String[]> result = new ArrayList<String[]>();

        recursiveNQueens(n, 0, new int[n], result);

        return result;

    }

 

    // If "currentRow" is n, we have reached a solution based on "queenInColumn",

    // and put it into "result"; Otherwise, we put a queen at each valid column

    // in Row "currentRow", and recursively work on the next row.

    private void recursiveNQueens(int n, int currentRow, int[] queenInColumn,

                                  ArrayList<String[]> result) {

        if (currentRow == n) {      // We have placed n queens

            // Construct a solution based on "queenInColumn"

            String[] solution = new String[n];

            for (int i = 0; i < n; i++) {

                StringBuilder row = new StringBuilder();

                for (int j = 0; j < n; j++) {

                    if (queenInColumn[i] == j)  // There is a queen at Row i and Column j

                        row.append('Q');

                    else

                        row.append('.');

                }

                solution[i] = row.toString();

            }

            // Add the solution to "result"

            result.add(solution);

        } else {

            // Put a queen at each valid column in the current row, and recursively

            // work on the next row

            for (int j = 0; j < n; j++) {

                if (isValid(j, currentRow, queenInColumn)) {

                    // A queen at Column j in the currentRow is valid

                    queenInColumn[currentRow] = j;

                    recursiveNQueens(n, currentRow+1, queenInColumn, result);

                }

            }

        }

    }

 

    // Indicate whether a queen can be put at (workingRow, attemptedColumn)

    // without violating the rules

    private boolean isValid(int attemptedColumn, int workingRow, int[] queenInColumn) {

        // Verify all the rules

        // No row conflict automatically since we put only one queen in each row

        for (int i = 0; i < workingRow; i++) {

            if (attemptedColumn == queenInColumn[i] ||      // No column conflict

                    (workingRow-i == Math.abs(attemptedColumn-queenInColumn[i])))   // No diagnal conflict

                return false;

        }

 

        return true;

    }

Iterative Version from http://blog.csdn.net/kenden23/article/details/18136889
vector<vector<string> > solveNQueens(int n)
{
vector<string> board(n,string(n, '.'));
vector<vector<string> > rs;
int row = 0;
vector<int> backtrackCol(n, -1);
while (row >= 0)
{
int col = 0;
if (backtrackCol[row] != -1)
{
col = backtrackCol[row]+1;
board[row][col-1] = '.';
}
for (; col < n; col++)
{
if (isLegal(board, row, col))
{
board[row][col] = 'Q';
backtrackCol[row] = col;
if (row == n-1)
{
rs.push_back(board);
backtrackCol[row] = -1;
board[row][col] = '.';
row--;
break;
}
row++;
break;
}
}
if (col == n)
{
backtrackCol[row] = -1;
row--;
}
}
return rs;
}
bool isLegal(const vector<string> &board, int row, int col)
{
for (int i = 0; i < row; i++)
{
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i>=0 && j>=0; i--, j--)
{
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i>=0 && j<board.size(); i--, j++)
{
if (board[i][j] == 'Q') return false;
}
return true;
}
Read full article from LeetCode - N-Queens | Darren's Blog