Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Constrained N-Rook Number of Solutions

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

  1. What is the keyword for this kind of problem?
  2. Are there any efficient developed technique for this kind of problem?
like image 893
hychou Avatar asked Jan 17 '19 20:01

hychou


1 Answers

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.

like image 152
hychou Avatar answered Oct 04 '22 20:10

hychou