受限制的N-Rook解决方案数量

Question

这篇文章的目的主要是针对相关研究的关键词.

无约束的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问题轻松修改回溯算法.但是,现在我想解决N = 28左右的问题.甚至维基说,这个解决方案太大了,不能算是1比1

27×27板是完全枚举的最高级板.

加速的机会

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

=====无约束子矩阵的因子=====

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

1 1 1
1 1 1
0 1 1

可分为

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

溶液等于溶胶(A)*溶胶(B),其中溶胶(A)= 2!这可以一次计算(因子比回溯快得多).

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

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

1 1 1
1 0 1
1 1 1

相当于

1 1 1
1 1 1
0 1 1

题

Answer 1

在车多项式，车系数，限制排列和永久的关键字。

限制板B的n个物体的排列数等于B的永久。

这里 B 是我们在问题中定义的，一个 0-1 矩阵，其中 1 是可以的，0 是车的限制。所以现在我们需要有效地计算矩阵的永久。

幸运的是，从这个代码 Golf 中，Ton Hospel 使用了Glynn 公式和格雷码和Ryser 公式，在测试者的系统上达到了大约 57 秒 n=36，这对于提问者的情况来说已经足够了。