当我遇到一个五角棋游戏时，有必要将13个数字乘以8乘8的正方形。在一段时间内我未能成功解决此问题后，我决定有必要编写一个程序来为我完成此任务。 为此，必须选择一种求解算法。 首先想到的是通常的分支和边界算法，当图形彼此相邻地堆叠时（带有跳舞链接的算法在这里不适用，因为图形不同）。 通常使用各种启发式方法来加快此算法的速度，例如，最好使用最少数量的选项进行分支。 您可以在此算法中提出并实现其他启发式方法，但是后来我认为在SAT解算器中已经实现了许多加快解决此类问题的技巧。 因此，有必要将任务翻译成适当的数学语言并使用某种SAT求解器。 关于如何实现此方法以及在切割下可以读取什么结果。
一开始，我想提醒您什么游戏是pentamino。 这是一个8x8正方形的字段，需要平铺13个图形-12个花体，由5个正方形和一个2x2图形组成：
在这里值得一说的是布尔可满足性问题或SAT问题。 一般而言，可以将其表述为对这样的布尔变量值的发现，其中给定表达式变为真。 一般来说，这是NP的完整任务，但是，有许多技巧可以有效地解决它。 为此，已经开发了许多称为SAT解算器的特殊应用。 我将使用一个名为minisat的SAT求解器。 为了解决该问题，有必要以合取范式重写输入表达式，即以变量逻辑和的乘积形式重写输入表达式。 每个合取范式中的每个括号都称为子句，它是某些文字的逻辑“或”，即布尔变量或它们的拒绝。 例如：
（x1 V不是x3）（x2 V x4）（x2 V x3 V不是X4）
我需要将平铺任务转换为SAT任务。 拍摄一些五角氨基的图形，并以各种可能的方式将其放置在运动场中，包括移动，转弯和反射。 对于图的每个这样的位置，我们关联一个布尔变量，并且我们假设，如果在最终解决方案中该图出现在该特定位置，则该变量将为true，否则为false。 我们针对所有数据执行此操作。
现在，让我们草拟一个描述我们问题的公式，也就是说，我们实际上将对变量施加限制。 首先要做的是确保我们比赛场地的所有单元都被至少一个数字覆盖。 为此，对于每个64个单元格，我们找到覆盖该单元格的所有图形和这些图形的位置，并根据分配给这些图形位置的变量组成一个子句。 第二件事是消除形状的交集。 这可以在一个双周期中完成，只需将所有图形的所有可能位置分类，然后确定该对是否具有公共单元即可。 如果存在，则它们相交，您需要添加以下形式的子句（不是x_i V而不是x_j），其中x_i是分配给第一个位置的变量，x_j是第二个位置。 当x_i和x_j同时不等于1时（即，排除交集），此子句为true。 最后，要考虑的第三件事是每个人物只能出现在运动场上一次。 为此，我们还要在一个双循环中遍历每个图形的所有位置，对于同一图形的每对位置，我们制作一个类似于前一个子句的子句，并由两个负数组成。 也就是说，当出现两个相同的数字（但位置不同）时，这些子句之一将给出错误，因此将排除这种解决方案。
这全都是理论，现在让我们继续练习。 每个图形都有一个从1到d的数字，以区别于其他图形并方便打印。 然后创建一个运动场矩阵，并将运动场的相应单元格编码为该图所占据/未占据：
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. 1 1 . . . . .
1 1 . . . . . .
. 1 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .
2 . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
3 . . . . . . .
3 . . . . . . .
3 . . . . . . .
3 3 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
4 . . . . . . .
4 . . . . . . .
4 4 . . . . . .
. 4 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
5 5 . . . . . .
5 5 . . . . . .
5 . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
6 6 6 . . . . .
. 6 . . . . . .
. 6 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
7 . 7 . . . . .
7 7 7 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
8 . . . . . . .
8 . . . . . . .
8 8 8 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . 9 . . . . .
. 9 9 . . . . .
9 9 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. a . . . . . .
aaa . . . . .
. a . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
b . . . . . . .
bb . . . . . .
b . . . . . . .
b . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. cc . . . . .
. c . . . . . .
cc . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
dd . . . . . .
dd . . . . . .
现在，对于每块棋子，都有必要通过移动，转弯和反射找到运动场上所有可能的位置。 让我们从转弯和反思开始。 总共有8种可能的转向和反射变换，其中包括一个使图形完整无缺的琐碎变换。 对于这些转换，我创建了8个对应的矩阵，如下所示。 旋转或反射后，人物可能会超出运动场，因此有必要将其返回到运动场。 还应考虑到某些数字可以在转换后转换为自身，并且这种情况应排除在外。 我向Orientation类添加了唯一的选项。 结果是以下代码：
int dimension_ = 2; const unsigned int MATRIX_SIZE = dimension_ * dimension_; int * matrix = new int[ MATRIX_SIZE ]; for( unsigned int i = 0; i < MATRIX_SIZE; i++ ) { matrix[ i ] = 0; } for( unsigned int i = 0; i < dimension_; i++ ) { int * matrix1 = new int[ MATRIX_SIZE ]; std::copy( matrix, matrix + MATRIX_SIZE, matrix1 ); matrix1[ i ] = 1; for( unsigned int j = dimension_; j < 2 * dimension_; j++ ) { if( !matrix1[ j - dimension_ ] ) { int * matrix2 = new int[ MATRIX_SIZE ]; std::copy( matrix1, matrix1 + MATRIX_SIZE, matrix2 ); matrix2[ j ] = 1; unsigned int NUMBER = 1 << dimension_; for( unsigned int l = 0; l < NUMBER; l++ ) { int * matrix3 = new int[ MATRIX_SIZE ]; std::copy( matrix2, matrix2 + MATRIX_SIZE, matrix3 ); if( l & 1 ) { for( unsigned int l1 = 0; l1 < dimension_; l1++ ) { matrix3[ l1 ] = -matrix3[ l1 ]; } } if( l & 2 ) { for( unsigned int l1 = dimension_; l1 < 2 * dimension_; l1++ ) { matrix3[ l1 ] = -matrix3[ l1 ]; } } Orientation * orientation = new Orientation( figure ); for( std::vector<Point *>::const_iterator h = figure->points().begin(); h != figure->points().end(); ++h ) { const Point * p = *h; int x = 0; for( unsigned int i1 = 0; i1 < dimension_; i1++ ) { x = x + p->coord( i1 ) * matrix3[ i1 ]; } int y = 0; for( unsigned int i1 = 0; i1 < dimension_; i1++ ) { y = y + p->coord( i1 ) * matrix3[ dimension_ + i1 ]; } Point p1( x, y ); orientation->createPoint( p1.coord( 0 ), p1.coord( 1 ) ); } orientation->moveToOrigin(); if( isUnique( orientations, orientation ) ) { orientations.push_back( orientation ); } else { delete orientation; } delete [] matrix3; } delete [] matrix2; } } delete [] matrix1; }
将此代码应用于每个图形，然后，将接收到的唯一方向沿x和y轴移动，从而创建每个图形的所有可能位置。 因此，每个图都有以下数量的不同位置：
---------- Figure 1
Count = 288
---------- Figure 2
Count = 64
---------- Figure 3
Count = 280
---------- Figure 4
Count = 280
---------- Figure 5
Count = 336
---------- Figure 6
Count = 144
---------- Figure 7
Count = 168
---------- Figure 8
Count = 144
---------- Figure 9
Count = 144
---------- Figure a
Count = 36
---------- Figure b
Count = 280
---------- Figure c
Count = 144
---------- Figure d
Count = 49
然后，如上所述，我们将布尔变量分配给每个可能的位置并创建一个公式。 之后，我们直接从应用程序中调用minisat，这将返回一个解决方案-一组分配了值为true或false的变量。 知道这些变量分配到的位置后，我们打印解决方案：
bbbb 3 3 3 3
ddbc 8 8 8 3
dd 1 ccc 8 2
5 5 1 1 1 c 8 2
5 5 5 1 4 4 4 2
7 7 a 4 4 9 6 2
7 aaa 9 9 6 2
7 7 a 9 9 6 6 6
接下来是什么
自然地，对此一无所知。 因此，对我提出的第一个问题是“存在多少种不同的解决方案，这些解决方案在琐碎的转弯和对运动场的反映方面没有差异？”。 为此，SAT解算器中提供了一种模式，该模式允许您添加子句而不丢失现有信息，与从头开始搜索解决方案相比，这可以大大加快过程。 通过添加一个子句，可以找到以下解决方案，该子句包含否定了先前解决方案中存在的所有变量。 在添加了此过程并将新解决方案与以前的解决方案进行比较之后，考虑到比赛场地的转弯和反射，我得到了1364个不同的选项。
我实现的另一个有趣的扩展是对各种其他形式的运动场和人物的研究。 最后，对三维运动场的研究非常有趣。 但这是另一篇文章的主题。
更新资料
添加一个附加条件后：对于一个子句的每个图形-该图形在运动场中至少应有一个位置，计算变得更快了。 此外，已修复一个错误，所有可能的唯一选项的数量为16146。