此贴主要是为了相关研究的关键词。
无约束 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
问题
- 这类问题的关键字是什么?
- 是否有针对此类问题的高效开发技术?
最佳答案
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 秒,这对于提问者的情况来说已经足够了。
关于algorithm - 受约束的 N-Rook 解决方案数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54243664/