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
$N$queens problem’.
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
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,N1]$. The end of
input is marked by values of zero for $N$ and $M$.
Output
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
other.
Sample Input 1 
Sample Output 1 
8 0
8 3
0 3
5 4
3 7
0 0

92
50
