Uma vez que me deparei com um jogo de pentomino em que era necessário colocar 13 algarismos em um quadrado de 8 por 8. Após um certo período de tempo durante o qual tentei sem sucesso resolver esse problema, decidi que era necessário escrever um programa que fizesse isso por mim. Para isso, foi necessário escolher um algoritmo de solução. A primeira coisa que vem à mente é o algoritmo usual de ramificações e bordas, quando as figuras são empilhadas uma após a outra adjacentes uma à outra (o algoritmo com links de dança não é adequado aqui, pois as figuras são diferentes). Várias heurísticas são geralmente usadas para acelerar esse algoritmo, por exemplo, é preferível ramificação com o menor número de opções. Você pode criar e implementar outras heurísticas nesse algoritmo, mas pensei que muitos truques diferentes para acelerar a solução de tais problemas já foram implementados nos solucionadores SAT. Portanto, é necessário traduzir a tarefa para a linguagem matemática apropriada e usar algum tipo de solucionador SAT. Sobre como isso foi implementado e quais resultados podem ser lidos sob o corte.
No começo, quero lembrá-lo como o jogo é pentamino. Este é um campo quadrado de 8x8, que deve ser lado a lado com 13 figuras - 12 rabiscos, que consistem em 5 quadrados e uma figura 2x2:
Aqui vale a pena dizer qual é o problema de satisfação booleana ou o problema SAT. Em termos gerais, pode ser formulado como a descoberta de tais valores de variáveis booleanas nas quais a expressão dada se torna verdadeira. De um modo geral, essa é uma tarefa completa do NP; no entanto, existem muitos truques que ajudam a resolvê-la de maneira eficaz. Para fazer isso, muitos aplicativos especiais chamados solucionadores SAT foram desenvolvidos. Vou usar um solucionador SAT chamado minisat. Para resolver esse problema, é necessário reescrever a expressão de entrada na forma normal conjuntiva, ou seja, na forma de um produto de somas lógicas de variáveis. Cada colchete na forma conjuntiva normal aqui é chamado de cláusula, que é o “ou” lógico de alguns literais, ou seja, variáveis booleanas ou suas negações. Por exemplo:
(x1 V não x3) (x2 V x4) (x2 V x3 V não X4)
Eu precisava traduzir a tarefa lado a lado na tarefa SAT. Pegue alguma figura do pentamino e coloque-a no campo de jogo de todas as maneiras possíveis, incluindo mudanças, curvas e reflexões. Para cada posição da figura, associamos uma variável booleana e assumimos que, se em nossa solução final essa figura estiver presente nessa posição específica, a variável será verdadeira e, se não, falsa. Fazemos isso para todas as figuras.
Agora, vamos elaborar uma fórmula que descreva nosso problema, ou seja, imporemos restrições a nossas variáveis. A primeira coisa a fazer é garantir que todas as células do nosso campo de jogo sejam cobertas com pelo menos uma figura. Para fazer isso, para cada célula de 64, encontramos todas as figuras e posições dessas figuras que cobrem essa célula e compomos uma cláusula das variáveis atribuídas a essas posições das figuras. A segunda coisa a fazer é eliminar a interseção de formas. Isso pode ser feito em um ciclo duplo, simplesmente classificando todas as posições possíveis de todas as figuras e determinando se o par tem células comuns. Se houver, eles se cruzam e você precisa adicionar uma cláusula do formulário (não x_i V não x_j), onde x_i é a variável atribuída à primeira posição e x_j é a segunda posição. Esta cláusula é verdadeira quando x_i e x_j não são iguais a uma ao mesmo tempo, ou seja, excluem interseções. E, finalmente, a terceira coisa a considerar é que cada figura pode estar presente no campo de jogo apenas uma vez. Para fazer isso, também passamos por todas as posições de cada figura em um ciclo duplo e, para cada par de posições da mesma figura, criamos uma cláusula semelhante à anterior e composta por dois negativos. Ou seja, quando duas figuras idênticas aparecerem (mas em posições diferentes), uma dessas cláusulas dará falso e, consequentemente, excluirá essa solução.
Era tudo uma teoria, e agora vamos à prática. Cada figura tem um número de 1 a d para distingui-lo dos outros e imprimir convenientemente. Em seguida, crie uma matriz do campo de jogo e codifique as células correspondentes do campo de jogo como ocupadas / não ocupadas pela figura:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. 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 . . . . . .
Agora, para cada peça, é necessário encontrar todas as posições possíveis no campo de jogo por meio de turnos, voltas e reflexões. Vamos começar com voltas e reflexões. No total, existem 8 possíveis transformações de voltas e reflexões, incluindo uma transformação trivial que deixa a figura intacta. Para essas transformações, crio 8 matrizes correspondentes, como mostrado abaixo. Após rotação ou reflexão, a figura pode ir além do campo de jogo, por isso é necessário retorná-lo ao campo de jogo. Também deve ser levado em consideração que alguns números podem se transformar após a transformação, e esses casos devem ser excluídos. Eu adiciono opções exclusivas à classe Orientação. O resultado é o seguinte código:
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; }
Esse código é aplicado a cada uma das figuras e, em seguida, as orientações únicas recebidas são deslocadas ao longo dos eixos x e y, criando todas as posições possíveis de cada figura. Como resultado, temos o seguinte número de posições diferentes para cada uma das figuras:
---------- 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
Em seguida, atribuímos uma variável booleana a cada posição possível e criamos uma fórmula, conforme descrito acima. Depois disso, chamamos minisat diretamente do aplicativo, que retorna uma solução - um conjunto de nossas variáveis com os valores atribuídos true ou false. Sabendo a quais posições essas variáveis foram atribuídas, imprimimos a solução:
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
O que vem a seguir
Naturalmente, insistir nisso não seria tão interessante. Portanto, a primeira pergunta que surgiu para mim foi “quantas soluções diferentes existem que não diferem em voltas e reflexões triviais do campo de jogo?”. Para fazer isso, existe um modo no solucionador SAT que permite adicionar cláusulas sem perder as informações existentes, o que acelera significativamente o processo, como se a solução fosse pesquisada do zero. A solução a seguir pode ser encontrada adicionando uma cláusula que contém a negação de todas as variáveis presentes na solução anterior. Depois de adicionar este procedimento e comparar a nova solução com as anteriores, levando em consideração as voltas e reflexões do campo, obtive 1364 opções diferentes.
Outra extensão interessante que implementei foi o estudo de várias outras formas do campo de jogo e das figuras. E, finalmente, o estudo dos campos de jogo tridimensionais foi muito interessante. Mas este é um tópico para outro artigo.
Update
Após adicionar uma condição adicional: para cada figura de uma cláusula - deve haver pelo menos uma posição dessa figura no campo de jogo, o cálculo tornou-se muito mais rápido. Além disso, um erro foi corrigido, como resultado do número de todas as opções exclusivas possíveis é 16146.