时间戳

首页 > 解决方案 > 受约束的 N-Rook 解数

algorithm - 受约束的 N-Rook 解数

问题描述

这篇文章的目的主要是为相关研究提供关键词。

无约束 N-Rook 问题

计算 N x 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 左右的问题。这个解决方案太大了，无法逐个计算，甚至wiki都说

27×27板是已经完全列举的最高阶板。

加速的机会

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

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

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

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. 有没有针对此类问题的有效开发技术？

标签： algorithmpermutationn-queens

解决方案

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

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.

推荐阅读