CODEWITHSUNDEEP
algorithmpermutationn-queens
hychou
hychou

Reputation: 632

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?

Upvotes: 6

Views: 990

Answers (1)

hychou
hychou

Reputation: 632

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.

Upvotes: 6

Related Questions