受约束的 N-Rook 解决方案数量

Question

这个post的目的主要是为了相关研究的关键词。

无约束 N-Rook 问题

数出N乘M(N<=M)个棋盘上N车的所有可能排列，使得没有车互相攻击。

解很简单：C(M,N)N!

约束N-Rook问题

你不能在棋盘的某些地方放车。

例如，如果棋盘显示为 0-1 矩阵，其中 0 是您不能放置车的位置。所以矩阵的解

1 1 1
1 1 1
0 1 1

是 4:

R . . | R . . | . R . | . . R 
. R . | . . R | R . . | R . .
. . R | . R . | . . R | . R .

相关问题

从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说

可以轻松修改回溯算法

The 27×27 board is the highest-order board that has been completely enumerated.

加速机会

到目前为止，我想到了一些加速算法的机会。

=====无约束子矩阵的阶乘=====

这是一种分而治之的方法。例如上面的矩阵

1 1 1
1 1 1
0 1 1

可以分为

  A       B
1 1 1 | 0 1 1
1 1 1 |

解等于 sol(A)*sol(B)，其中 sol(A)=2！可以立即计算（阶乘比回溯快得多）。

=============重排=============

有时重排可以帮助划分子问题。例如矩阵

1 1 1
1 0 1
1 1 1

等同于

1 1 1
1 1 1
0 1 1

问题

Answer 1

车多项式、车系数、限制排列和 permanent 是关键字。

的定理 3.1

The number of arrangements of n objects with restriction board B is equal to permanent of B.

这里的B就是我们在题目中定义的，一个0-1的矩阵，其中1可以，0限制为车。所以现在我们需要高效的计算一个矩阵的常驻

幸运的是，据此code golf, Ton Hospel uses Glynn formula with a Gray code and Ryser formula，在测试者的系统上，n=36 达到了大约 57 秒，这对于提问者的情况来说已经足够了。

Constrained N-Rook Number of Solutions