queens

Arrange 8 queens on 8x8 chessboard with no intersecting row, column, or diagonal. There seems to be 92 ways.

Determine if the square can be added using already added squares. The square is in
- same row or column if it has same row or column of an already added square.
- same diagonal if the abs of difference in row and col of an already added square is same.

It is better to have way as int array instead of object array ({row, col}[]) for space.

queens(n):
    // ways is list of way
    ways = new
    // way is int array where index is row and way[index] is col
    way = new [n]
    queens(n, row: 0, way, ways)
    return ways

queens(n, row, way, ways):
    if row == n:
        // need to make copy
        ways.add(way.copy())
        return
    for col = 0, col < n, col++:
        if !is-square-ok(row, col, way):
            continue
        way[row] = col
        queens(n, row +1, way, ways)

// way has the already added squares
is-square-ok(row, col, way):
    for r = 0, r < row; r++:
        c = way[r]
        if 
            r == row // same row (this is not needed)
            || c == col // same col
            || abs(row - r) == abs(col - c): // same diagonal
            return false
    return true

Time: O(nⁿ)

[Hat tip to ctci]