The twelve pentominoes fill a rectangle 6 x 10 in 2339 ways, a rectangle 3 x 20 in only 2, and the square 8 x 8 with a hole of 2 x 2 in the middle in 65 (Dana Scott found them all in 1958, by one of the first backtracking programs); the seven pieces of the Soma cube of Piet Hein fill a cube 3 x 3 x 3. In this page the solution is found by no search procedure: every placement \(p\) of a piece in the tray (a translation of one of its orientations) is a binary variable \(y_p\), and an integer program maximizes the area covered; hence, the tray is full at an optimal solution, and every other feasible solution leaves holes. The program was solved offline by HiGHS (through scipy).
I dodici pentamini riempiono un rettangolo 6 x 10 in 2339 modi, un rettangolo 3 x 20 in 2 soli, e il quadrato 8 x 8 con un foro di 2 x 2 al centro in 65 (Dana Scott li ha trovati tutti nel 1958, con uno dei primi programmi di backtracking); i sette pezzi del cubo Soma di Piet Hein riempiono un cubo 3 x 3 x 3. In questa pagina la soluzione non viene da un algoritmo di ricerca: ogni piazzamento \(p\) di un pezzo nel vassoio (una traslazione di una delle sue orientazioni) è una variabile binaria \(y_p\), e un programma intero massimizza l'area coperta; quindi il vassoio è pieno in una soluzione ottima, e ogni altra soluzione ammissibile lascia dei buchi. Il programma è stato risolto offline da HiGHS (tramite scipy).
\(\max \sum_p |p|\, y_p \quad \text{s.t.} \quad \sum_{p \ni c} y_p \le 1 \ \ \forall\, c, \quad \sum_{p \in P_i} y_p \le 1 \ \ \forall\, i, \quad y \in \{0,1\}\)
The tray and the pieces laid out beside it, separate bodies in one file, in the puzzle chosen above; the clearance is the gap between two neighbors, taken half from each piece and half from the pocket (0.2 to 0.3 mm usually suits a printer), and the pieces stand 1 mm above the rim, so that they can be picked out.
Il vassoio e i pezzi disposti accanto, corpi separati in un solo file, per il puzzle scelto sopra; il gioco è lo spazio fra due vicini, preso per metà da ogni pezzo e per metà dalla tasca (da 0.2 a 0.3 mm di solito va bene), e i pezzi sporgono di 1 mm dal bordo per poterli estrarre.