The purpose of this post is mainly for keywords for related researches.
Unconstrained N-Rook Problem
Count all possible arrangements of N rooks on an N by M (N<=M) chessboard so that no rooks are attacking each other.
The solution is trivial: C(M,N)N!
Constrained N-Rook Problem
You cannot put a rook at certain places of the chessboard.
For example, if the chessboard is presented as a 0-1 matrix, where 0 are the places you cannot put a rook at. So the solution for the matrix
1 1 1
1 1 1
0 1 1
is 4:
R . . | R . . | . R . | . . R
. R . | . . R | R . . | R . .
. . R | . R . | . . R | . R .
Related Problem
A backtracking algorithm can be easily modified from N-Queen problem. However, now I want to solve a problem for around N=28. This solution is too huge to count 1 by 1, even wiki said
The 27×27 board is the highest-order board that has been completely enumerated.
Chances to Speed Up
There are a few chances I thought of so far to speed up the algorithm.
=====Factorial for Unconstrained Submatrix=====
This is a Divide and Conquer method. e.g. The matrix above
1 1 1
1 1 1
0 1 1
can be divided as
A B
1 1 1 | 0 1 1
1 1 1 |
and the solution is equal to sol(A)*sol(B), where sol(A)=2! which can be calculated at once (factorial is much faster than backtracking).
=============Rearrangement=============
Sometimes rearrangement can help to divide the subproblem. e.g. The matrix
1 1 1
1 0 1
1 1 1
is equivalent to
1 1 1
1 1 1
0 1 1
Question
The rook polynomial, rook coefficient, restricted permutations and permanent are the keywords.
From Theorem 3.1 of Algorithm for Finding the Coefficients of Rook Polynomials
The number of arrangements of n objects with restriction board B is equal to permanent of B.
Here B is what we defined in the question, a 0-1 matrix where 1 is ok, 0 is restricted for a rook. So now we need to efficiently calculate the permanent of a matrix.
Fortunately, from this code golf, Ton Hospel uses Glynn formula with a Gray code and Ryser formula, and reach about 57 seconds on the tester's system for n=36, which is quite enough for the questioner's case.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With