Sunday, April 12, 2015


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.

    // 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
    for col = 0, col < n, col++:
        if !is-square-ok(row, col, way):
        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]
            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(nn)

[Hat tip to ctci]

No comments:

Post a Comment