algorithm - 受约束的 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 计数，即使是 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

问题

1. 这类问题的关键字是什么？
2. 是否有针对此类问题的高效开发技术？

Answer 1

rook polynomial、rook coefficient、restricted permutations 和permanent 是关键字。

来自 Algorithm for Finding the Coefficients of Rook Polynomials 的定理 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 使用 Glynn formula用Gray code和 Ryser formula , 并在 n=36 的测试者系统上达到大约 57 秒，这对于提问者的情况来说已经足够了。