The $N$-queens problem
is the problem of placing $N$ queens on a $N \times N$ chessboard so that no
queen shares a row, column or a diagonal with any other queen.
Essentially, we are trying to place the queens without any
queen threatening another. For example, the first image below
(without holes in the board) is a solution to the $8$-queens problem.
For this problem, consider the problem we’ll call the ‘holey
Instead of having an everyday chessboard (of arbitrary size),
your chessboard is like the second image above (without
queens): it has holes through some of the squares. You can’t
place a queen on a square that has a hole, but a queen can
threaten another even if there is a hole on the path between
them. Given a holey chessboard, you must find placements for
the $N$ queens so that no
queen threatens another. The third image above (with holes and
queens) shows one such solution.
Input consists of up to $1\,
000$ board descriptions. Each description starts with a
line containing a pair of integers, $3 \le N \le 12$ and $0 \le M \le N^2$, indicating
respectively the size of one side of the board, and the number
of holes. The next $M$
lines each describe the location of a unique hole in the board.
A hole is described by its row and column, each in the range
$[0,N-1]$. The end of
input is marked by values of zero for $N$ and $M$.
For each problem description, print out the number of unique
$N$-queens solutions that
are possible. Two solutions are considered different if any
space is occupied by a queen in one solution but not in the
|Sample Input 1
||Sample Output 1