N-Queens

Place n queens on an n × n board so that no two share a row, column or diagonal.

Time O(n!)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Place one queen per row, top to bottom. In each row try the columns left to right and keep the first safe one. If a row has no safe column, go back up and move the previous queen.

Code

C++PythonC#

bool isSafe(int row, int c, const vector<int>& cols) {
    for (int r = 0; r < row; r++)
        if (cols[r] == c || abs(cols[r] - c) == row - r) return false;
    return true;
}

bool solve(int row, int n, vector<int>& cols) {
    if (row == n) return true;
    for (int c = 0; c < n; c++) {
        if (!isSafe(row, c, cols)) continue;
        cols[row] = c;
        if (solve(row + 1, n, cols)) return true;
        cols[row] = -1; // backtrack
    }
    return false;
}

def solve(row: int, n: int, cols: list[int]) -> bool:
    if row == n: return True
    for c in range(n):
        if not is_safe(row, c, cols): continue
        cols[row] = c
        if solve(row + 1, n, cols): return True
        cols[row] = -1  # backtrack
    return False

def is_safe(row: int, c: int, cols: list[int]) -> bool:
    return all(cols[r] != c and abs(cols[r] - c) != row - r for r in range(row))

public static bool Solve(int row, int n, int[] cols) {
    if (row == n) return true;
    for (int c = 0; c < n; c++) {
        if (!IsSafe(row, c, cols)) continue;
        cols[row] = c;
        if (Solve(row + 1, n, cols)) return true;
        cols[row] = -1; // backtrack
    }
    return false;
}

static bool IsSafe(int row, int c, int[] cols) {
    for (int r = 0; r < row; r++)
        if (cols[r] == c || Math.Abs(cols[r] - c) == row - r) return false;
    return true;
}

Tips

Two queens share a diagonal when their column distance equals their row distance.
Checking safety before recursing prunes most of the nⁿ possible boards.

In the .NET library

cols is an int[] where cols[row] is the column of that row's queen. One queen per row is built into the representation, so rows never need checking.