Пентамино на Алголе

[vak]

А вот вам еще один древний пример на Алголе-60. Программа упаковывает фигурки пентамино в коробку 6x10. Исходный текст: pentomino.a60.

Кто написал этот код - достоверно неизвестно. Вероятно, сам Франц Круземан Арец: программа приведена в качестве примера в его статье "A comparison between the ALGOL 60 implementations on the Electrologica X1 and the Electrologica X8".

Подробное исследование проблемы опубликовал в 1971 году профессор Николас Де Брёйн, в голландском журнале "Monthly magazine for the didactics of mathematics". Смотрите страницы 8-22 в файле 047_1971-72_03.pdf. Решение Ареца похоже, но не идентично. В частности, нумерация матрицы делается по строкам, а не по столбцам. Я гуглоперевёл эту статью на английский для облегчения восприятия: github.com/sergev/vak-opensource/wiki/pentomino.



Известно, что упаковок пентамино в прямоугольник 6x10 имеется всего 2339 штук, если не считать тривиальные повороты и зеркальные отражения всего прямоугольника целиком. Алгольная программа показывает только первые семь размещений.

$ cd x1-algol-compiler/examples
$ ./pentomino.sh

The first 7 solutions:


 - - - - - - - - - - - - - - - - - - - - 
I           I           I               I
     - -     - - - -         - - - - - - 
I   I   I   I       I   I   I           I
 - -     - -     - -     - -         - - 
I           I   I   I   I   I       I   I
 - -     - -         - -     - - - -     
I   I   I       I       I       I       I
     - - - - - -     - - - -     - -     
I           I       I       I       I   I
     - - - - - - - - - -     - - - -     
I   I                   I           I   I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I           I               I
     - -     - - - -     - - - - - -     
I   I   I   I       I   I           I   I
 - -     - -     - -     - -         - - 
I           I   I   I   I   I       I   I
 - -     - -         - -     - - - -     
I   I   I       I       I       I       I
     - - - - - -     - - - -     - -     
I           I       I       I       I   I
     - - - - - - - - - -     - - - -     
I   I                   I           I   I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I               I   I       I
     - -     - - - - - -                 
I   I   I   I       I   I   I   I       I
 - -     - -     - -     - -     - -     
I           I   I   I       I       I   I
 - -     - -         - -     - -     - - 
I   I   I       I       I       I   I   I
     - - - - - -     - - - - - - - -     
I           I       I               I   I
     - - - - - - - - - -     - - - -     
I   I                   I   I           I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I               I       I   I
     - -     - - - - - -                 
I   I   I   I       I   I   I       I   I
 - -     - -     - -     - -     - -     
I           I   I   I       I   I       I
 - -     - -         - -     - -     - - 
I   I   I       I       I       I   I   I
     - - - - - -     - - - - - - - -     
I           I       I               I   I
     - - - - - - - - - -     - - - -     
I   I                   I   I           I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I           I               I
     - -         - - - -     - - - - - - 
I   I   I   I   I       I   I       I   I
 - -     - -     - -     - -             
I           I   I   I   I           I   I
 - -     - - - -         - - - - - -     
I   I   I           I       I   I       I
     - - - -     - - - - - -     - -     
I           I   I           I       I   I
     - - - - - - - - - -     - -     - - 
I   I                   I       I       I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I           I       I       I
     - -         - - - -     - -     - - 
I   I   I   I   I           I       I   I
 - -     - -     - - - - - -     - -     
I           I   I   I       I   I       I
 - -     - - - -         - - - - - -     
I   I   I           I   I           I   I
     - - - -     - -     - -             
I           I   I       I   I       I   I
     - - - - - - - - - -     - - - - - - 
I   I                   I               I
 - - - - - - - - - - - - - - - - - - - - 


 - - - - - - - - - - - - - - - - - - - - 
I           I   I           I   I       I
     - -         - - - -         - -     
I   I   I   I           I   I       I   I
 - -     - - - - - -                     
I           I   I   I   I   I       I   I
 - -     - -         - - - - - - - -     
I   I   I       I       I           I   I
     - - - -     - -     - - - -     - - 
I           I       I       I   I       I
     - - - - - - - - - - - -     - - - - 
I   I                   I               I
 - - - - - - - - - - - - - - - - - - - -

Comments

[dom3d]

Like

[spamsink]

Что-то мне подсказывает, что алгольный алгоритм поэффективнее будет - он просто не оставляет дырок в колонках, которые формирует слева направо. Если ему оставить две позиции для F для прямоугольных досок, и одну - для квадратной, то решения, отличающиеся только поворотом или отражением, не будут находиться.