N Queens

A chess queen attacks every square in its row, its column and both of its diagonals. On an n by n board, a peaceful arrangement places n queens so that no queen attacks another, which means exactly one queen in every row and every column.

Some queens may already stand on the board. Write count_queens(n, placed) that returns how many peaceful arrangements include every queen in placed, a list of (row, column) positions counted from 0. If the queens already placed attack each other, the answer is 0.

Examples

count_queens(4, [])                # returns 2
count_queens(4, [(0, 1)])          # returns 1
count_queens(8, [])                # returns 92
count_queens(5, [(0, 0), (1, 1)])  # returns 0

With nothing placed, a 4 by 4 board has two peaceful arrangements: row by row, the queens stand in columns 1, 3, 0, 2 or in columns 2, 0, 3, 1. Only the first has a queen at row 0, column 1.

Constraints

• 1 <= n <= 10
• 0 <= len(placed) <= n, every position is on the board, and no position appears twice.