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 trueTime: O(n

^{n})

[Hat tip to ctci]

## No comments:

## Post a Comment