Pentomino tiling: Difference between revisions
m (→{{header|Java}}: rand doesn't have to be global) |
m (→{{header|Wren}}: Minor tidy) |
||
(45 intermediate revisions by 17 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
A [[wp:Pentomino|pentomino]] is a polyomino that consists of 5 squares. There are 12 pentomino shapes, |
A [[wp:Pentomino|pentomino]] is a polyomino that consists of 5 squares. There are 12 pentomino shapes, |
||
Line 13: | Line 13: | ||
A Pentomino tiling is an example of an [[wp:Exact_cover|exact cover]] problem and can take on many forms. |
A Pentomino tiling is an example of an [[wp:Exact_cover|exact cover]] problem and can take on many forms. |
||
A traditional tiling |
A traditional tiling presents an 8 by 8 grid, where 4 cells are left uncovered. The other cells are covered |
||
by the 12 pentomino shapes, without overlaps, with every shape only used once. |
by the 12 pentomino shapes, without overlaps, with every shape only used once. |
||
The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable. |
The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable. |
||
'''The task''': create an 8 by 8 tiling and print the result. |
|||
;Task |
|||
For instance: |
|||
Create an 8 by 8 tiling and print the result. |
|||
;Example |
|||
<pre>F I I I I I L N |
<pre>F I I I I I L N |
||
Line 32: | Line 35: | ||
;Related tasks |
|||
;Cf. |
|||
* [[Free_polyominoes_enumeration|Free polyominoes enumeration]] |
* [[Free_polyominoes_enumeration|Free polyominoes enumeration]] |
||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="11l"> |
|||
F nonrandom(n) |
|||
UInt32 :seed = 0 |
|||
:seed = 1664525 * :seed + 1013904223 |
|||
R (:seed >> 16) % n |
|||
-V |
|||
SF = [[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0], |
|||
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1], |
|||
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1]] |
|||
SI = [[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0]] |
|||
SL = [[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0], |
|||
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0]] |
|||
SN = [[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1], |
|||
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1], |
|||
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1], |
|||
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1]] |
|||
SP = [[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1], |
|||
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1], |
|||
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0], |
|||
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0]] |
|||
ST = [[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0]] |
|||
SU = [[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1], |
|||
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1]] |
|||
SV = [[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0], |
|||
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2]] |
|||
SW = [[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1], |
|||
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1]] |
|||
SX = [[1, -1, 1, 0, 1, 1, 2, 0]] |
|||
SY = [[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0], |
|||
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0]] |
|||
SZ = [[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2], |
|||
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2]] |
|||
Shapes = [SF, SI, SL, SN, SP, ST, SU, SV, SW, SX, SY, SZ] |
|||
Symbols = Array(‘FILNPTUVWXYZ-’) |
|||
NRows = 8 |
|||
NCols = 8 |
|||
Blank = Shapes.len |
|||
T Tiling |
|||
[[[Int]]] shapes |
|||
[Char] symbols |
|||
[[Int]] grid |
|||
[Bool] placed |
|||
F () |
|||
V indexes = [4, 6, 11, 7, 10, 3, 9, 5, 1, 8, 0, 2] |
|||
L(index) indexes |
|||
.shapes.append(Shapes[index]) |
|||
.symbols.append(Symbols[index]) |
|||
.symbols.append(Symbols.last) |
|||
.grid = [[-1] * NCols] * NRows |
|||
L 4 |
|||
L |
|||
V randRow = nonrandom(NRows) |
|||
V randCol = nonrandom(NCols) |
|||
I .grid[randRow][randCol] != Blank |
|||
.grid[randRow][randCol] = Blank |
|||
L.break |
|||
.placed = [0B] * Shapes.len |
|||
F tryPlaceOrientation(o, r, c, shapeIndex) |
|||
L(i) (0 .< o.len).step(2) |
|||
V x = c + o[i + 1] |
|||
V y = r + o[i] |
|||
I x !C 0 .< NCols | y !C 0 .< NRows | .grid[y][x] != -1 |
|||
R 0B |
|||
.grid[r][c] = shapeIndex |
|||
L(i) (0 .< o.len).step(2) |
|||
.grid[r + o[i]][c + o[i + 1]] = shapeIndex |
|||
R 1B |
|||
F removeOrientation(o, r, c) |
|||
.grid[r][c] = -1 |
|||
L(i) (0 .< o.len).step(2) |
|||
.grid[r + o[i]][c + o[i + 1]] = -1 |
|||
F solve(pos, numPlaced) |
|||
I numPlaced == .shapes.len |
|||
R 1B |
|||
V row = pos I/ NCols |
|||
V col = pos % NCols |
|||
I .grid[row][col] != -1 |
|||
R .solve(pos + 1, numPlaced) |
|||
L(i) 0 .< .shapes.len |
|||
I !.placed[i] |
|||
L(orientation) .shapes[i] |
|||
I !.tryPlaceOrientation(orientation, row, col, i) |
|||
L.continue |
|||
.placed[i] = 1B |
|||
I .solve(pos + 1, numPlaced + 1) |
|||
R 1B |
|||
.removeOrientation(orientation, row, col) |
|||
.placed[i] = 0B |
|||
R 0B |
|||
F printResult() |
|||
L(r) .grid |
|||
print(r.map(i -> @.symbols[i]).join(‘ ’)) |
|||
V tiling = Tiling() |
|||
I tiling.solve(0, 0) |
|||
tiling.printResult() |
|||
E |
|||
print(‘No solution’) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
P P U U U V V V |
|||
P P U X U L L V |
|||
T P X X X L - V |
|||
T T T X F L Z Z |
|||
T - F F F L Z Y |
|||
N N N F W Z Z Y |
|||
- - N N W W Y Y |
|||
I I I I I W W Y |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|Visual Basic .NET}}=== |
|||
{{trans|Java}}via{{trans|C#}} |
|||
Instead of having a large declaration for each rotation of each pentomino, a small array of encoded positions is supplied '''(seeds)''', and it is expanded into the set of 63 possible orientations. However, the additional expansion routines code does take up about 2/3 of the space that would have been taken by the elaborate Integer array definitions. |
|||
<syntaxhighlight lang="vbnet">Module Module1 |
|||
Dim symbols As Char() = "XYPFTVNLUZWI█".ToCharArray(), |
|||
nRows As Integer = 8, nCols As Integer = 8, |
|||
target As Integer = 12, blank As Integer = 12, |
|||
grid As Integer()() = New Integer(nRows - 1)() {}, |
|||
placed As Boolean() = New Boolean(target - 1) {}, |
|||
pens As List(Of List(Of Integer())), rand As Random, |
|||
seeds As Integer() = {291, 292, 293, 295, 297, 329, 330, 332, 333, 335, 378, 586} |
|||
Sub Main() |
|||
Unpack(seeds) : rand = New Random() : ShuffleShapes(2) |
|||
For r As Integer = 0 To nRows - 1 |
|||
grid(r) = Enumerable.Repeat(-1, nCols).ToArray() : Next |
|||
For i As Integer = 0 To 3 |
|||
Dim rRow, rCol As Integer : Do : rRow = rand.Next(nRows) : rCol = rand.Next(nCols) |
|||
Loop While grid(rRow)(rCol) = blank : grid(rRow)(rCol) = blank |
|||
Next |
|||
If Solve(0, 0) Then |
|||
PrintResult() |
|||
Else |
|||
Console.WriteLine("no solution for this configuration:") : PrintResult() |
|||
End If |
|||
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
|||
End Sub |
|||
Sub ShuffleShapes(count As Integer) ' changes order of the pieces for a more random solution |
|||
For i As Integer = 0 To count : For j = 0 To pens.Count - 1 |
|||
Dim r As Integer : Do : r = rand.Next(pens.Count) : Loop Until r <> j |
|||
Dim tmp As List(Of Integer()) = pens(r) : pens(r) = pens(j) : pens(j) = tmp |
|||
Dim ch As Char = symbols(r) : symbols(r) = symbols(j) : symbols(j) = ch |
|||
Next : Next |
|||
End Sub |
|||
Sub PrintResult() ' display results |
|||
For Each r As Integer() In grid : For Each i As Integer In r |
|||
Console.Write("{0} ", If(i < 0, ".", symbols(i))) |
|||
Next : Console.WriteLine() : Next |
|||
End Sub |
|||
' returns first found solution only |
|||
Function Solve(ByVal pos As Integer, ByVal numPlaced As Integer) As Boolean |
|||
If numPlaced = target Then Return True |
|||
Dim row As Integer = pos \ nCols, col As Integer = pos Mod nCols |
|||
If grid(row)(col) <> -1 Then Return Solve(pos + 1, numPlaced) |
|||
For i As Integer = 0 To pens.Count - 1 : If Not placed(i) Then |
|||
For Each orientation As Integer() In pens(i) |
|||
If Not TPO(orientation, row, col, i) Then Continue For |
|||
placed(i) = True : If Solve(pos + 1, numPlaced + 1) Then Return True |
|||
RmvO(orientation, row, col) : placed(i) = False |
|||
Next : End If : Next : Return False |
|||
End Function |
|||
' removes a placed orientation |
|||
Sub RmvO(ByVal ori As Integer(), ByVal row As Integer, ByVal col As Integer) |
|||
grid(row)(col) = -1 : For i As Integer = 0 To ori.Length - 1 Step 2 |
|||
grid(row + ori(i))(col + ori(i + 1)) = -1 : Next |
|||
End Sub |
|||
' checks an orientation, if possible it is placed, else returns false |
|||
Function TPO(ByVal ori As Integer(), ByVal row As Integer, ByVal col As Integer, |
|||
ByVal sIdx As Integer) As Boolean |
|||
For i As Integer = 0 To ori.Length - 1 Step 2 |
|||
Dim x As Integer = col + ori(i + 1), y As Integer = row + ori(i) |
|||
If x < 0 OrElse x >= nCols OrElse y < 0 OrElse y >= nRows OrElse |
|||
grid(y)(x) <> -1 Then Return False |
|||
Next : grid(row)(col) = sIdx |
|||
For i As Integer = 0 To ori.Length - 1 Step 2 |
|||
grid(row + ori(i))(col + ori(i + 1)) = sIdx |
|||
Next : Return True |
|||
End Function |
|||
'!' the following routines expand the seed values into the 63 orientation arrays. |
|||
' source code space savings comparison: |
|||
' around 2000 chars for the expansion code, verses about 3000 chars for the integer array defs. |
|||
' perhaps not worth the savings? |
|||
Sub Unpack(sv As Integer()) ' unpacks a list of seed values into a set of 63 rotated pentominoes |
|||
pens = New List(Of List(Of Integer())) : For Each item In sv |
|||
Dim Gen As New List(Of Integer()), exi As List(Of Integer) = Expand(item), |
|||
fx As Integer() = ToP(exi) : Gen.Add(fx) : For i As Integer = 1 To 7 |
|||
If i = 4 Then Mir(exi) Else Rot(exi) |
|||
fx = ToP(exi) : If Not Gen.Exists(Function(Red) TheSame(Red, fx)) Then Gen.Add(ToP(exi)) |
|||
Next : pens.Add(Gen) : Next |
|||
End Sub |
|||
' expands an integer into a set of directions |
|||
Function Expand(i As Integer) As List(Of Integer) |
|||
Expand = {0}.ToList() : For j As Integer = 0 To 3 : Expand.Insert(1, i And 15) : i >>= 4 : Next |
|||
End Function |
|||
' converts a set of directions to an array of y, x pairs |
|||
Function ToP(p As List(Of Integer)) As Integer() |
|||
Dim tmp As List(Of Integer) = {0}.ToList() : For Each item As Integer In p.Skip(1) |
|||
tmp.Add(tmp.Item(item >> 2) + {1, 8, -1, -8}(item And 3)) : Next |
|||
tmp.Sort() : For i As Integer = tmp.Count - 1 To 0 Step -1 : tmp.Item(i) -= tmp.Item(0) : Next |
|||
Dim res As New List(Of Integer) : For Each item In tmp.Skip(1) |
|||
Dim adj = If((item And 7) > 4, 8, 0) |
|||
res.Add((adj + item) \ 8) : res.Add((item And 7) - adj) |
|||
Next : Return res.ToArray() |
|||
End Function |
|||
' compares integer arrays for equivalency |
|||
Function TheSame(a As Integer(), b As Integer()) As Boolean |
|||
For i As Integer = 0 To a.Count - 1 : If a(i) <> b(i) Then Return False |
|||
Next : Return True |
|||
End Function |
|||
Sub Rot(ByRef p As List(Of Integer)) ' rotates a set of directions by 90 degrees |
|||
For i As Integer = 0 To p.Count - 1 : p(i) = (p(i) And -4) Or ((p(i) + 1) And 3) : Next |
|||
End Sub |
|||
Sub Mir(ByRef p As List(Of Integer)) ' mirrors a set of directions |
|||
For i As Integer = 0 To p.Count - 1 : p(i) = (p(i) And -4) Or (((p(i) Xor 1) + 1) And 3) : Next |
|||
End Sub |
|||
End Module |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
Solution found result ''(typical output)'': |
|||
<pre>Y F F █ L L L L |
|||
Y Y F F L P P P |
|||
Y T F N N N P P |
|||
Y T N N █ V V V |
|||
T T T W W Z Z V |
|||
U U X █ W W Z V |
|||
U X X X █ W Z Z |
|||
U U X I I I I I </pre> |
|||
Impossible to solve result ''(a somewhat rare occurrence)'': |
|||
<pre>no solution for this configuration: |
|||
. █ . . . . . . |
|||
█ . . █ . . . . |
|||
. . . . . . . . |
|||
. . . . █ . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . |
|||
. . . . . . . . </pre> |
|||
====VB .NET alternative output ''(corner characters)''==== |
|||
This output may appear better in a command window |
|||
[https://tio.run/##rRlLc9u4@e5fgeoQExNKI8nOxvHE7iS20/HUSTySs952eoEoSIJDEVyAlKXNZKbTcw896LCHPfbY4x731@iPpN8H8AWKspN2lRnSBPC938hi1A6k4l@@vJXjNOTEvnp7ZI/A71zMiV7NRzLU5JUmZzOmPEpOSOuHv1y/ufn@3dWHv95etludG4lbr5RiK4/6BhR/0UDeG8DLKOFTrgDyyCfRWYauulrAJExNeeJu9/o@GYUs@ri1XIBNlRhXdj1q@HzH74sVy0yb9HDr0@cSNA5ZwA3waylDzqICNP/OeEJYF5JHRpAroRPv/aR4F0xQ6hPFIoN8AG85L4E152PtsAxUP/Vf9HzSf9HHxwE@nuHjuU8O@i/gcdDFRx8fB/iA3YPnoNNnR999zmw2TEfkLRMgRUHqQxSz4KNnKFJybFmyIlquPFwdztLJJOTDGYu59vol@BupiHJV3yU3khQaLU7mlvAUCnMRpXOu2CjknQGPOUu8di8zPwWXydwFKL/jy8ShJhqoHThU0DMV0Af9Ar7q8WNyLlFG2ARQFLWD@K39jfQI4OwYjhz0V1LG5HYmICKsPABMPYREwawvHu/cKlA5gl1OyFCGC@6BDbuU3Mx45NC8ViJKBlynYVKx3UWouXPsTEYa3LJzq0TCr0TEvVYkCSyliZARmYD6kpnQJJDRRExTxXD5uIWS76AAznA5cdhc6YTPO@eCTSOpExHozjkfpVNQb@dSv0oSFswgYlCCgp0BZ@M/81WGF3GCI1Zc0vWuQKZRNcgp2SfBjEVTrolUYzCjnIAYnMSCB7CGUjEyh0xl7CbnhcCP@o0ldWz27/JFjNzOmdmp@2/hXU1O5fhNiQSVa1zmQ5SIEI69PCV3jViTeVzNGGWmAMyIDyPnuPgrW7sr1u5wDXA04g5meZKGQ1natvgqH@XOXXXHIA5mDl4Ushqd20Z1HApMOBYasumKTFgUrIgyG3rP0So3OW@YAOQUSNo/OhfzOFk5prwAH3NsAAQuI5vnj8sTjsVhX21pBik@KQgB4BwSUetT93PLB1/3BHlJICBbHfjMlSEgcTdpIkPVgn9PyGJ0NannLic2vTOpIq742Du/9QA0R@qqcR@wJqmCQjIRSifg6SnsF@Eso9Dq5U0aBWbF5pDXq@9ZSGJZrSA@sauQdq@LmlYEWFnfqqFenj3JS68J64FhityolLv2g6zqxBiy8Deb1H2ItXB7F1oKu1@la1MnZs4AEyfES7vnULZiIvxTglUj55M@GvBubIOJgNw7mWR1Hoy7nXodp5NK8CgxaXPL/UwQCroFnEmFZG6u33sVFD6qzGjGJxlpdJNERClHmo2oSlZPjAmsELtUgp90t9mqv8F8sYM7k2IqZN@weuGpBIItGZn3wysjW8LggdxjK44@lwsIIZa3XBVGipRiOLR@DNuOAXL/dn0wX3V9j@65/UjhaSfoaMc7nQdodq54NE1mxnmGCY9Jv6G/ARae4mHMFYg4/zK2KKjsSJ1Y63jwETQREccYYoIRowW0TEQkBKq41ZRPOGi2zBSFnousgF73/2vN33Yae0xfjpePZZP/XaWYWJYuZF2lPlm5B6oW2KuF4RJzOnmvsHeCj9OTbObIVlbV7ZXZNp2sXdlSgTH4inrLpjTlhkkWDlsuh@r7HfT0la7nUHMjtEgMTQH6h33Tck1kGMp7LM9KQhGKIGL5MsaRAXdxiCALFqawDMVfmsXvDpysybCz153M12HUkakKONh0DPAwisCTLYAANqnzmCmhoUMtTsOPKVMF@91uF9tCpbO2lltONBJBbD5ZcKUxpYyAVXKwfV5kOjYskTGfVNiKuYJuVJMIsva9VKB3I6Bl7Y@VNiefnxZOYGHDk5odTGkhdHTYtG7ph8GS2QElKQkagn0oI4mci0hy7Q6Tdih7YJ50eh9o0rEo6cVWNP2Jm9pVRVYigWyyFA1dqJnZjKU9RE23s8FkWR9Yb@S1B9iQL6DZeTUee5MlbU6wPfTy53sNdVPA7qGNq7dCWYQmOgcyMV9NnDjEs@KLPFwsQSzt5d7tDaBpQNxDNuf44QMwzeplznOOqbHtMw0FnoLT9KGsbsPEpPXc71wXGAvFDVPazd651usptm6gcmazAXlCoI@FUdqco8WQ0zA8Y9E2MJ3LSHOVeNBAADnA0XuGgIKcnqINatJt1XCYKiHkEt0kE0FRs@jHnZUPyTdm0NbWahUou2kKotTxrr3H5ybarIEyOtzhIO4MP4rY67lWBtTGuvi@BCDj/KAO0qeQUj@Boo58gjcX7aPPdg/VdkC3bi4QwRDyiLfD/3G/7EvBKl2b5E2rUFKnpH1Sfna3yFTGqIb4bswQhrMG0REVG@NUDJNQKdtzSk7JoZG76wIAXaMrD6GeGvwU2v8jaqcju1fF00b8dEc1QojiHughn8MiYfNpmcxtjuc/pgKyLYd5s@ZkWcCzWjM0quXwb2hkWH2qYGgs6AlG@VDxYFfwFSXYNMCQ8l6vBhxaweYY2c/KSHMMjlbkRRcK3VTxSnHZOSs5IsW29ffMGw3YPqTQFRHPrpgxw/r@w9cCmMMfEWEulJJK70yNvwfTdukHwNL7SuaxBSqaHnQve5EBK3GauP4FM33lJoNWLjX2yVim2MFzyJQr04@wIDG1gGh7hC8DHifQM0R8gpeyZWzf1u5EqtFcud/Bqo@XUrd4HwHrTzCA4X1iriV80mrBUDejX5/OLcvtezGGNojpQAiSoNtm9SvIrjJMv5WPa4UuiouOZo04mQtl1h51LoF0ZxiHIvGQd/rt10U5Wuckpkb74bUIaMPS7dK8xbZDRcj04zfPBrTSmjsZETHAQUP/2L7yGyJLUtDy5ug6/emnkHsIYzmi2UVS841xmSbhWA4LUH6zdJ0rhkWwKuEDWRUSCNidmzIB8kIbbY0J9h5z@J6jKNgQg@0xNDMfyC7JXAfIeGOlBbJEm/nCt9sUsqvHckkgw2Z/Zml2hMqs64CVJiqON@N7WcfHmvCNSnxsC9/uGlEA9fcariFbpNffrNeHm/XPm/XfN@tfjzbrf2zW/9ysf9ms/7VZ/3uz/s9m/VvLg3hmNrOxYgTu@iaT1cZdb5QdqJ81/UuJB6uUWT/M1kfFeglzROljvtjkUvhp/@vwy5f/Ag Try it online!] |
|||
{{out}} |
|||
Solution found result ''(typical output)'': |
|||
<pre>┌─────┬─────┬─┬─┐ |
|||
│ ┌─┐ ├─┐ │ │ │ |
|||
├─┼─┴─┴─┴─┬─┘ │ │ |
|||
│ └───┬─┐ │ ┌─┤ │ |
|||
│ ┌───┼─┼─┴─┘ │ │ |
|||
├─┘ ┌─┘ └─┐ ┌─┼─┤ |
|||
│ ┌─┼─┐ ┌─┴─┘ │ │ |
|||
├─┴─┘ └─┤ ┌───┘ │ |
|||
└───────┴─┴─────┘</pre> |
|||
Impossible to solve result ''(a somewhat rare occurrence)'': |
|||
<pre>no solution for this configuration: |
|||
┌─┬─┬─┬─┬───────┐ |
|||
│ └─┘ └─┘ │ |
|||
│ ┌─┐ │ |
|||
├─┼─┘ │ |
|||
├─┘ │ |
|||
│ │ |
|||
│ │ |
|||
│ │ |
|||
└───────────────┘</pre> |
|||
=={{header|C sharp|C#}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Linq; |
|||
namespace PentominoTiling |
|||
{ |
|||
class Program |
|||
{ |
|||
static readonly char[] symbols = "FILNPTUVWXYZ-".ToCharArray(); |
|||
static readonly int nRows = 8; |
|||
static readonly int nCols = 8; |
|||
static readonly int target = 12; |
|||
static readonly int blank = 12; |
|||
static int[][] grid = new int[nRows][]; |
|||
static bool[] placed = new bool[target]; |
|||
static void Main(string[] args) |
|||
{ |
|||
var rand = new Random(); |
|||
for (int r = 0; r < nRows; r++) |
|||
grid[r] = Enumerable.Repeat(-1, nCols).ToArray(); |
|||
for (int i = 0; i < 4; i++) |
|||
{ |
|||
int randRow, randCol; |
|||
do |
|||
{ |
|||
randRow = rand.Next(nRows); |
|||
randCol = rand.Next(nCols); |
|||
} |
|||
while (grid[randRow][randCol] == blank); |
|||
grid[randRow][randCol] = blank; |
|||
} |
|||
if (Solve(0, 0)) |
|||
{ |
|||
PrintResult(); |
|||
} |
|||
else |
|||
{ |
|||
Console.WriteLine("no solution"); |
|||
} |
|||
Console.ReadKey(); |
|||
} |
|||
private static void PrintResult() |
|||
{ |
|||
foreach (int[] r in grid) |
|||
{ |
|||
foreach (int i in r) |
|||
Console.Write("{0} ", symbols[i]); |
|||
Console.WriteLine(); |
|||
} |
|||
} |
|||
private static bool Solve(int pos, int numPlaced) |
|||
{ |
|||
if (numPlaced == target) |
|||
return true; |
|||
int row = pos / nCols; |
|||
int col = pos % nCols; |
|||
if (grid[row][col] != -1) |
|||
return Solve(pos + 1, numPlaced); |
|||
for (int i = 0; i < shapes.Length; i++) |
|||
{ |
|||
if (!placed[i]) |
|||
{ |
|||
foreach (int[] orientation in shapes[i]) |
|||
{ |
|||
if (!TryPlaceOrientation(orientation, row, col, i)) |
|||
continue; |
|||
placed[i] = true; |
|||
if (Solve(pos + 1, numPlaced + 1)) |
|||
return true; |
|||
RemoveOrientation(orientation, row, col); |
|||
placed[i] = false; |
|||
} |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
private static void RemoveOrientation(int[] orientation, int row, int col) |
|||
{ |
|||
grid[row][col] = -1; |
|||
for (int i = 0; i < orientation.Length; i += 2) |
|||
grid[row + orientation[i]][col + orientation[i + 1]] = -1; |
|||
} |
|||
private static bool TryPlaceOrientation(int[] orientation, int row, int col, int shapeIndex) |
|||
{ |
|||
for (int i = 0; i < orientation.Length; i += 2) |
|||
{ |
|||
int x = col + orientation[i + 1]; |
|||
int y = row + orientation[i]; |
|||
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1) |
|||
return false; |
|||
} |
|||
grid[row][col] = shapeIndex; |
|||
for (int i = 0; i < orientation.Length; i += 2) |
|||
grid[row + orientation[i]][col + orientation[i + 1]] = shapeIndex; |
|||
return true; |
|||
} |
|||
// four (x, y) pairs are listed, (0,0) not included |
|||
static readonly int[][] F = { |
|||
new int[] {1, -1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 2, 0}, |
|||
new int[] {1, 0, 1, 1, 1, 2, 2, 1}, new int[] {1, 0, 1, 1, 2, -1, 2, 0}, |
|||
new int[] {1, -2, 1, -1, 1, 0, 2, -1}, new int[] {0, 1, 1, 1, 1, 2, 2, 1}, |
|||
new int[] {1, -1, 1, 0, 1, 1, 2, -1}, new int[] {1, -1, 1, 0, 2, 0, 2, 1}}; |
|||
static readonly int[][] I = { |
|||
new int[] { 0, 1, 0, 2, 0, 3, 0, 4 }, new int[] { 1, 0, 2, 0, 3, 0, 4, 0 } }; |
|||
static readonly int[][] L = { |
|||
new int[] {1, 0, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, 0, 3, -1, 3, 0}, |
|||
new int[] {0, 1, 0, 2, 0, 3, 1, 3}, new int[] {0, 1, 1, 0, 2, 0, 3, 0}, |
|||
new int[] {0, 1, 1, 1, 2, 1, 3, 1}, new int[] {0, 1, 0, 2, 0, 3, 1, 0}, |
|||
new int[] {1, 0, 2, 0, 3, 0, 3, 1}, new int[] {1, -3, 1, -2, 1, -1, 1, 0}}; |
|||
static readonly int[][] N = { |
|||
new int[] {0, 1, 1, -2, 1, -1, 1, 0}, new int[] {1, 0, 1, 1, 2, 1, 3, 1}, |
|||
new int[] {0, 1, 0, 2, 1, -1, 1, 0}, new int[] {1, 0, 2, 0, 2, 1, 3, 1}, |
|||
new int[] {0, 1, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, -1, 2, 0, 3, -1}, |
|||
new int[] {0, 1, 0, 2, 1, 2, 1, 3}, new int[] {1, -1, 1, 0, 2, -1, 3, -1}}; |
|||
static readonly int[][] P = { |
|||
new int[] {0, 1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 0, 2, 1, 0, 1, 1}, |
|||
new int[] {1, 0, 1, 1, 2, 0, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 1, 1}, |
|||
new int[] {0, 1, 1, 0, 1, 1, 1, 2}, new int[] {1, -1, 1, 0, 2, -1, 2, 0}, |
|||
new int[] {0, 1, 0, 2, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 1, 1, 2, 0}}; |
|||
static readonly int[][] T = { |
|||
new int[] {0, 1, 0, 2, 1, 1, 2, 1}, new int[] {1, -2, 1, -1, 1, 0, 2, 0}, |
|||
new int[] {1, 0, 2, -1, 2, 0, 2, 1}, new int[] {1, 0, 1, 1, 1, 2, 2, 0}}; |
|||
static readonly int[][] U = { |
|||
new int[] {0, 1, 0, 2, 1, 0, 1, 2}, new int[] {0, 1, 1, 1, 2, 0, 2, 1}, |
|||
new int[] {0, 2, 1, 0, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 2, 0, 2, 1}}; |
|||
static readonly int[][] V = { |
|||
new int[] {1, 0, 2, 0, 2, 1, 2, 2}, new int[] {0, 1, 0, 2, 1, 0, 2, 0}, |
|||
new int[] {1, 0, 2, -2, 2, -1, 2, 0}, new int[] {0, 1, 0, 2, 1, 2, 2, 2}}; |
|||
static readonly int[][] W = { |
|||
new int[] {1, 0, 1, 1, 2, 1, 2, 2}, new int[] {1, -1, 1, 0, 2, -2, 2, -1}, |
|||
new int[] {0, 1, 1, 1, 1, 2, 2, 2}, new int[] {0, 1, 1, -1, 1, 0, 2, -1}}; |
|||
static readonly int[][] X = { new int[] { 1, -1, 1, 0, 1, 1, 2, 0 } }; |
|||
static readonly int[][] Y = { |
|||
new int[] {1, -2, 1, -1, 1, 0, 1, 1}, new int[] {1, -1, 1, 0, 2, 0, 3, 0}, |
|||
new int[] {0, 1, 0, 2, 0, 3, 1, 1}, new int[] {1, 0, 2, 0, 2, 1, 3, 0}, |
|||
new int[] {0, 1, 0, 2, 0, 3, 1, 2}, new int[] {1, 0, 1, 1, 2, 0, 3, 0}, |
|||
new int[] {1, -1, 1, 0, 1, 1, 1, 2}, new int[] {1, 0, 2, -1, 2, 0, 3, 0}}; |
|||
static readonly int[][] Z = { |
|||
new int[] {0, 1, 1, 0, 2, -1, 2, 0}, new int[] {1, 0, 1, 1, 1, 2, 2, 2}, |
|||
new int[] {0, 1, 1, 1, 2, 1, 2, 2}, new int[] {1, -2, 1, -1, 1, 0, 2, -2}}; |
|||
static readonly int[][][] shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z }; |
|||
} |
|||
}</syntaxhighlight> |
|||
<pre>I N F F - - L L |
|||
I N N F F P P L |
|||
I - N F W P P L |
|||
I Y N W W X P L |
|||
I Y W W X X X - |
|||
Y Y T T T X Z V |
|||
U Y U T Z Z Z V |
|||
U U U T Z V V V</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="c++"> |
|||
#include <algorithm> |
|||
#include <cstdint> |
|||
#include <iostream> |
|||
#include <random> |
|||
#include <vector> |
|||
const std::vector<std::vector<int32_t>> F = { { 1, -1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 1, -1, 1, 0, 2, 0 }, |
|||
{ 1, 0, 1, 1, 1, 2, 2, 1 }, { 1, 0, 1, 1, 2, -1, 2, 0 }, { 1, -2, 1, -1, 1, 0, 2, -1 }, |
|||
{ 0, 1, 1, 1, 1, 2, 2, 1 }, { 1, -1, 1, 0, 1, 1, 2, -1 }, { 1, -1, 1, 0, 2, 0, 2, 1 } }; |
|||
const std::vector<std::vector<int32_t>> I = { { 0, 1, 0, 2, 0, 3, 0, 4 }, { 1, 0, 2, 0, 3, 0, 4, 0 } }; |
|||
const std::vector<std::vector<int32_t>> L = { { 1, 0, 1, 1, 1, 2, 1, 3 }, { 1, 0, 2, 0, 3, -1, 3, 0 }, |
|||
{ 0, 1, 0, 2, 0, 3, 1, 3 }, { 0, 1, 1, 0, 2, 0, 3, 0 }, { 0, 1, 1, 1, 2, 1, 3, 1 }, |
|||
{ 0, 1, 0, 2, 0, 3, 1, 0 }, { 1, 0, 2, 0, 3, 0, 3, 1 }, { 1, -3, 1, -2, 1, -1, 1, 0 } }; |
|||
const std::vector<std::vector<int32_t>> N = { { 0, 1, 1, -2, 1, -1, 1, 0 }, { 1, 0, 1, 1, 2, 1, 3, 1 }, |
|||
{ 0, 1, 0, 2, 1, -1, 1, 0 }, { 1, 0, 2, 0, 2, 1, 3, 1 }, { 0, 1, 1, 1, 1, 2, 1, 3 }, |
|||
{ 1, 0, 2, -1, 2, 0, 3, -1 }, { 0, 1, 0, 2, 1, 2, 1, 3 }, { 1, -1, 1, 0, 2, -1, 3, -1 } }; |
|||
const std::vector<std::vector<int32_t>> P = { { 0, 1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 0, 2, 1, 0, 1, 1 }, |
|||
{ 1, 0, 1, 1, 2, 0, 2, 1 }, { 0, 1, 1, -1, 1, 0, 1, 1 }, { 0, 1, 1, 0, 1, 1, 1, 2 }, |
|||
{ 1, -1, 1, 0, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 1, 1, 2 }, { 0, 1, 1, 0, 1, 1, 2, 0 } }; |
|||
const std::vector<std::vector<int32_t>> T = { { 0, 1, 0, 2, 1, 1, 2, 1 }, { 1, -2, 1, -1, 1, 0, 2, 0 }, |
|||
{ 1, 0, 2, -1, 2, 0, 2, 1 }, { 1, 0, 1, 1, 1, 2, 2, 0 } }; |
|||
const std::vector<std::vector<int32_t>> U = { { 0, 1, 0, 2, 1, 0, 1, 2 }, { 0, 1, 1, 1, 2, 0, 2, 1 }, |
|||
{ 0, 2, 1, 0, 1, 1, 1, 2 }, { 0, 1, 1, 0, 2, 0, 2, 1 } }; |
|||
const std::vector<std::vector<int32_t>> V = { { 1, 0, 2, 0, 2, 1, 2, 2 }, { 0, 1, 0, 2, 1, 0, 2, 0 }, |
|||
{ 1, 0, 2, -2, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 2, 2, 2 } }; |
|||
const std::vector<std::vector<int32_t>> W = { { 1, 0, 1, 1, 2, 1, 2, 2 }, { 1, -1, 1, 0, 2, -2, 2, -1 }, |
|||
{ 0, 1, 1, 1, 1, 2, 2, 2 }, { 0, 1, 1, -1, 1, 0, 2, -1 } }; |
|||
const std::vector<std::vector<int32_t>> X = { { 1, -1, 1, 0, 1, 1, 2, 0 } }; |
|||
const std::vector<std::vector<int32_t>> Y = { { 1, -2, 1, -1, 1, 0, 1, 1 }, { 1, -1, 1, 0, 2, 0, 3, 0 }, |
|||
{ 0, 1, 0, 2, 0, 3, 1, 1 }, { 1, 0, 2, 0, 2, 1, 3, 0 }, { 0, 1, 0, 2, 0, 3, 1, 2 }, |
|||
{ 1, 0, 1, 1, 2, 0, 3, 0 }, { 1, -1, 1, 0, 1, 1, 1, 2 }, { 1, 0, 2, -1, 2, 0, 3, 0 } }; |
|||
const std::vector<std::vector<int32_t>> Z = { { 0, 1, 1, 0, 2, -1, 2, 0 }, { 1, 0, 1, 1, 1, 2, 2, 2 }, |
|||
{ 0, 1, 1, 1, 2, 1, 2, 2 }, { 1, -2, 1, -1, 1, 0, 2, -2 } }; |
|||
const int32_t blank_index = 12; |
|||
const int32_t nRows = 8; |
|||
const int32_t nCols = 8; |
|||
std::vector<std::vector<std::vector<int32_t>>> shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z }; |
|||
std::vector<char> symbols = { 'F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '-' }; |
|||
std::vector<std::vector<int32_t>> grid{nRows, std::vector<int32_t>(nCols, -1)}; |
|||
std::vector<bool> placed(symbols.size() - 1, false); |
|||
std::random_device random; |
|||
std::mt19937 generator(random()); |
|||
std::uniform_real_distribution<double> distribution(0.0F, 1.0F); |
|||
void display() { |
|||
for ( const std::vector<int32_t>& row : grid ) { |
|||
for ( const int32_t& index : row ) { |
|||
std::cout << symbols[index] << " "; |
|||
} |
|||
std::cout << std::endl; |
|||
} |
|||
} |
|||
void shuffle_shapes() { |
|||
uint64_t size = shapes.size(); |
|||
while ( size > 1 ) { |
|||
int32_t random = static_cast<int32_t>( distribution(generator) * ( size-- ) ); |
|||
const std::vector<std::vector<int32_t>> temp = shapes[random]; |
|||
shapes[random] = shapes[size]; |
|||
shapes[size] = temp; |
|||
const char temp_symbol = symbols[random]; |
|||
symbols[random] = symbols[size]; |
|||
symbols[size] = temp_symbol; |
|||
} |
|||
} |
|||
bool place_orientation(const std::vector<int32_t>& orientation, |
|||
const int32_t& row, const int32_t& col, const int32_t& shape_index) { |
|||
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) { |
|||
int32_t x = col + orientation[i + 1]; |
|||
int32_t y = row + orientation[i]; |
|||
if ( x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 ) { |
|||
return false; |
|||
} |
|||
} |
|||
grid[row][col] = shape_index; |
|||
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) { |
|||
grid[row + orientation[i]][col + orientation[i + 1]] = shape_index; |
|||
} |
|||
return true; |
|||
} |
|||
void remove_orientation(const std::vector<int32_t>& oorientation, const int32_t& row, const int32_t& col) { |
|||
grid[row][col] = -1; |
|||
for ( uint64_t i = 0; i < oorientation.size(); i += 2 ) { |
|||
grid[row + oorientation[i]][col + oorientation[i + 1]] = -1; |
|||
} |
|||
} |
|||
bool solve(const int32_t& position, const uint64_t& number_placed) { |
|||
if ( number_placed == shapes.size() ) { |
|||
return true; |
|||
} |
|||
int32_t row = position / nCols; |
|||
int32_t col = position % nCols; |
|||
if ( grid[row][col] != -1 ) { |
|||
return solve(position + 1, number_placed); |
|||
} |
|||
for ( uint64_t i = 0; i < shapes.size(); ++i ) { |
|||
if ( ! placed[i] ) { |
|||
for ( const std::vector<int32_t>& orientation : shapes[i] ) { |
|||
if ( ! place_orientation(orientation, row, col, i) ) { |
|||
continue; |
|||
} |
|||
placed[i] = true; |
|||
if ( solve(position + 1, number_placed + 1) ) { |
|||
return true; |
|||
} |
|||
remove_orientation(orientation, row, col); |
|||
placed[i] = false; |
|||
} |
|||
} |
|||
} |
|||
return false; |
|||
} |
|||
int main() { |
|||
shuffle_shapes(); |
|||
for ( int32_t i = 0; i < 4; ++i ) { |
|||
int32_t random_row, random_col; |
|||
do { |
|||
random_row = static_cast<int32_t>(distribution(generator) * nRows); |
|||
random_col = static_cast<int32_t>(distribution(generator) * nCols); |
|||
} while ( grid[random_row][random_col] == blank_index ); |
|||
grid[random_row][random_col] = blank_index; |
|||
} |
|||
if ( solve(0, 0) ) { |
|||
display(); |
|||
} else { |
|||
std::cout << "No solution found" << std::endl; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
Y Y Y Y X V V V |
|||
U Y U X X X - V |
|||
U U U T X W W V |
|||
I T T T W W F - |
|||
I L Z T W F F F |
|||
I L Z Z Z F P P |
|||
I L N N Z - P P |
|||
I L L N N N - P |
|||
</pre> |
|||
=={{header|Go}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
|||
"fmt" |
|||
"math/rand" |
|||
"time" |
|||
) |
|||
var F = [][]int{ |
|||
{1, -1, 1, 0, 1, 1, 2, 1}, {0, 1, 1, -1, 1, 0, 2, 0}, |
|||
{1, 0, 1, 1, 1, 2, 2, 1}, {1, 0, 1, 1, 2, -1, 2, 0}, |
|||
{1, -2, 1, -1, 1, 0, 2, -1}, {0, 1, 1, 1, 1, 2, 2, 1}, |
|||
{1, -1, 1, 0, 1, 1, 2, -1}, {1, -1, 1, 0, 2, 0, 2, 1}, |
|||
} |
|||
var I = [][]int{{0, 1, 0, 2, 0, 3, 0, 4}, {1, 0, 2, 0, 3, 0, 4, 0}} |
|||
var L = [][]int{ |
|||
{1, 0, 1, 1, 1, 2, 1, 3}, {1, 0, 2, 0, 3, -1, 3, 0}, |
|||
{0, 1, 0, 2, 0, 3, 1, 3}, {0, 1, 1, 0, 2, 0, 3, 0}, {0, 1, 1, 1, 2, 1, 3, 1}, |
|||
{0, 1, 0, 2, 0, 3, 1, 0}, {1, 0, 2, 0, 3, 0, 3, 1}, {1, -3, 1, -2, 1, -1, 1, 0}, |
|||
} |
|||
var N = [][]int{ |
|||
{0, 1, 1, -2, 1, -1, 1, 0}, {1, 0, 1, 1, 2, 1, 3, 1}, |
|||
{0, 1, 0, 2, 1, -1, 1, 0}, {1, 0, 2, 0, 2, 1, 3, 1}, {0, 1, 1, 1, 1, 2, 1, 3}, |
|||
{1, 0, 2, -1, 2, 0, 3, -1}, {0, 1, 0, 2, 1, 2, 1, 3}, {1, -1, 1, 0, 2, -1, 3, -1}, |
|||
} |
|||
var P = [][]int{ |
|||
{0, 1, 1, 0, 1, 1, 2, 1}, {0, 1, 0, 2, 1, 0, 1, 1}, |
|||
{1, 0, 1, 1, 2, 0, 2, 1}, {0, 1, 1, -1, 1, 0, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 2}, |
|||
{1, -1, 1, 0, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 1, 1, 2}, {0, 1, 1, 0, 1, 1, 2, 0}, |
|||
} |
|||
var T = [][]int{ |
|||
{0, 1, 0, 2, 1, 1, 2, 1}, {1, -2, 1, -1, 1, 0, 2, 0}, |
|||
{1, 0, 2, -1, 2, 0, 2, 1}, {1, 0, 1, 1, 1, 2, 2, 0}, |
|||
} |
|||
var U = [][]int{ |
|||
{0, 1, 0, 2, 1, 0, 1, 2}, {0, 1, 1, 1, 2, 0, 2, 1}, |
|||
{0, 2, 1, 0, 1, 1, 1, 2}, {0, 1, 1, 0, 2, 0, 2, 1}, |
|||
} |
|||
var V = [][]int{ |
|||
{1, 0, 2, 0, 2, 1, 2, 2}, {0, 1, 0, 2, 1, 0, 2, 0}, |
|||
{1, 0, 2, -2, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 2, 2, 2}, |
|||
} |
|||
var W = [][]int{ |
|||
{1, 0, 1, 1, 2, 1, 2, 2}, {1, -1, 1, 0, 2, -2, 2, -1}, |
|||
{0, 1, 1, 1, 1, 2, 2, 2}, {0, 1, 1, -1, 1, 0, 2, -1}, |
|||
} |
|||
var X = [][]int{{1, -1, 1, 0, 1, 1, 2, 0}} |
|||
var Y = [][]int{ |
|||
{1, -2, 1, -1, 1, 0, 1, 1}, {1, -1, 1, 0, 2, 0, 3, 0}, |
|||
{0, 1, 0, 2, 0, 3, 1, 1}, {1, 0, 2, 0, 2, 1, 3, 0}, {0, 1, 0, 2, 0, 3, 1, 2}, |
|||
{1, 0, 1, 1, 2, 0, 3, 0}, {1, -1, 1, 0, 1, 1, 1, 2}, {1, 0, 2, -1, 2, 0, 3, 0}, |
|||
} |
|||
var Z = [][]int{ |
|||
{0, 1, 1, 0, 2, -1, 2, 0}, {1, 0, 1, 1, 1, 2, 2, 2}, |
|||
{0, 1, 1, 1, 2, 1, 2, 2}, {1, -2, 1, -1, 1, 0, 2, -2}, |
|||
} |
|||
var shapes = [][][]int{F, I, L, N, P, T, U, V, W, X, Y, Z} |
|||
var symbols = []byte("FILNPTUVWXYZ-") |
|||
const ( |
|||
nRows = 8 |
|||
nCols = 8 |
|||
blank = 12 |
|||
) |
|||
var grid [nRows][nCols]int |
|||
var placed [12]bool |
|||
func tryPlaceOrientation(o []int, r, c, shapeIndex int) bool { |
|||
for i := 0; i < len(o); i += 2 { |
|||
x := c + o[i+1] |
|||
y := r + o[i] |
|||
if x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 { |
|||
return false |
|||
} |
|||
} |
|||
grid[r][c] = shapeIndex |
|||
for i := 0; i < len(o); i += 2 { |
|||
grid[r+o[i]][c+o[i+1]] = shapeIndex |
|||
} |
|||
return true |
|||
} |
|||
func removeOrientation(o []int, r, c int) { |
|||
grid[r][c] = -1 |
|||
for i := 0; i < len(o); i += 2 { |
|||
grid[r+o[i]][c+o[i+1]] = -1 |
|||
} |
|||
} |
|||
func solve(pos, numPlaced int) bool { |
|||
if numPlaced == len(shapes) { |
|||
return true |
|||
} |
|||
row := pos / nCols |
|||
col := pos % nCols |
|||
if grid[row][col] != -1 { |
|||
return solve(pos+1, numPlaced) |
|||
} |
|||
for i := range shapes { |
|||
if !placed[i] { |
|||
for _, orientation := range shapes[i] { |
|||
if !tryPlaceOrientation(orientation, row, col, i) { |
|||
continue |
|||
} |
|||
placed[i] = true |
|||
if solve(pos+1, numPlaced+1) { |
|||
return true |
|||
} |
|||
removeOrientation(orientation, row, col) |
|||
placed[i] = false |
|||
} |
|||
} |
|||
} |
|||
return false |
|||
} |
|||
func shuffleShapes() { |
|||
rand.Shuffle(len(shapes), func(i, j int) { |
|||
shapes[i], shapes[j] = shapes[j], shapes[i] |
|||
symbols[i], symbols[j] = symbols[j], symbols[i] |
|||
}) |
|||
} |
|||
func printResult() { |
|||
for _, r := range grid { |
|||
for _, i := range r { |
|||
fmt.Printf("%c ", symbols[i]) |
|||
} |
|||
fmt.Println() |
|||
} |
|||
} |
|||
func main() { |
|||
rand.Seed(time.Now().UnixNano()) |
|||
shuffleShapes() |
|||
for r := 0; r < nRows; r++ { |
|||
for i := range grid[r] { |
|||
grid[r][i] = -1 |
|||
} |
|||
} |
|||
for i := 0; i < 4; i++ { |
|||
var randRow, randCol int |
|||
for { |
|||
randRow = rand.Intn(nRows) |
|||
randCol = rand.Intn(nCols) |
|||
if grid[randRow][randCol] != blank { |
|||
break |
|||
} |
|||
} |
|||
grid[randRow][randCol] = blank |
|||
} |
|||
if solve(0, 0) { |
|||
printResult() |
|||
} else { |
|||
fmt.Println("No solution") |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
Sample output: |
|||
<pre> |
|||
Z I I I I I - Y |
|||
Z Z Z V - F Y Y |
|||
U U Z V - F F Y |
|||
U V V V F F X Y |
|||
U U P P W X X X |
|||
T P P P W W X - |
|||
T T T N N W W L |
|||
T N N N L L L L |
|||
</pre> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
<lang |
<syntaxhighlight lang="java">package pentominotiling; |
||
import java.util.*; |
|||
public class PentominoTiling { |
public class PentominoTiling { |
||
static final char[] symbols = "FILNPTUVWXYZ-".toCharArray(); |
static final char[] symbols = "FILNPTUVWXYZ-".toCharArray(); |
||
static final Random rand = new Random(); |
|||
static final int nRows = 8; |
static final int nRows = 8; |
||
static final int nCols = 8; |
static final int nCols = 8; |
||
static final int target = 12; |
|||
static final int blank = 12; |
static final int blank = 12; |
||
static int[][] grid = new int[nRows][nCols]; |
static int[][] grid = new int[nRows][nCols]; |
||
static boolean[] placed = new boolean[ |
static boolean[] placed = new boolean[symbols.length - 1]; |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
shuffleShapes(); |
|||
for (int r = 0; r < nRows; r++) |
for (int r = 0; r < nRows; r++) |
||
Arrays.fill(grid[r], -1); |
Arrays.fill(grid[r], -1); |
||
for (int i = 0; i < 4; i++) |
for (int i = 0; i < 4; i++) { |
||
int randRow, randCol; |
|||
grid[rand.nextInt(nRows)][rand.nextInt(nCols)] = blank; |
|||
do { |
|||
randRow = rand.nextInt(nRows); |
|||
randCol = rand.nextInt(nCols); |
|||
} while (grid[randRow][randCol] == blank); |
|||
grid[randRow][randCol] = blank; |
|||
} |
|||
if (solve(0, 0)) { |
if (solve(0, 0)) { |
||
Line 63: | Line 940: | ||
} else { |
} else { |
||
System.out.println("no solution"); |
System.out.println("no solution"); |
||
} |
|||
} |
|||
static void shuffleShapes() { |
|||
int n = shapes.length; |
|||
while (n > 1) { |
|||
int r = rand.nextInt(n--); |
|||
int[][] tmp = shapes[r]; |
|||
shapes[r] = shapes[n]; |
|||
shapes[n] = tmp; |
|||
char tmpSymbol = symbols[r]; |
|||
symbols[r] = symbols[n]; |
|||
symbols[n] = tmpSymbol; |
|||
} |
} |
||
} |
} |
||
Line 74: | Line 966: | ||
} |
} |
||
static boolean tryPlaceOrientation(int[] o, int r, int c, int |
static boolean tryPlaceOrientation(int[] o, int r, int c, int shapeIndex) { |
||
for (int i = 0; i < o.length; i += 2) { |
for (int i = 0; i < o.length; i += 2) { |
||
int x = c + o[i + 1]; |
|||
int y = r + o[i]; |
|||
|| |
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1) |
||
|| grid[r + o[i]][c + o[i + 1]] != -1) |
|||
return false; |
return false; |
||
} |
} |
||
grid[r][c] = |
grid[r][c] = shapeIndex; |
||
for (int i = 0; i < o.length; i += 2) |
for (int i = 0; i < o.length; i += 2) |
||
grid[r + o[i]][c + o[i + 1]] = |
grid[r + o[i]][c + o[i + 1]] = shapeIndex; |
||
return true; |
return true; |
||
Line 98: | Line 989: | ||
static boolean solve(int pos, int numPlaced) { |
static boolean solve(int pos, int numPlaced) { |
||
if (numPlaced == |
if (numPlaced == shapes.length) |
||
return true; |
return true; |
||
Line 108: | Line 999: | ||
for (int i = 0; i < shapes.length; i++) { |
for (int i = 0; i < shapes.length; i++) { |
||
if (!placed[i]) { |
if (!placed[i]) { |
||
for (int[] orientation : shapes[i]) { |
for (int[] orientation : shapes[i]) { |
||
Line 169: | Line 1,058: | ||
static final int[][][] shapes = {F, I, L, N, P, T, U, V, W, X, Y, Z}; |
static final int[][][] shapes = {F, I, L, N, P, T, U, V, W, X, Y, Z}; |
||
}</ |
}</syntaxhighlight> |
||
<pre>F I I I I I L L |
<pre>F I I I I I L L |
||
Line 179: | Line 1,068: | ||
U X U W Y T T T |
U X U W Y T T T |
||
U U U Y Y Y Y T </pre> |
U U U Y Y Y Y T </pre> |
||
=={{header|Julia}}== |
|||
{{trans|Zkl}} |
|||
<syntaxhighlight lang="julia">using Random |
|||
struct GridPoint x::Int; y::Int end |
|||
const nrows, ncols, target = 8, 8, 12 |
|||
const grid = fill('*', nrows, ncols) |
|||
const shapeletters = ['F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] |
|||
const shapevec = [ |
|||
[(1,-1, 1,0, 1,1, 2,1), (0,1, 1,-1, 1,0, 2,0), |
|||
(1,0 , 1,1, 1,2, 2,1), (1,0, 1,1, 2,-1, 2,0), (1,-2, 1,-1, 1,0, 2,-1), |
|||
(0,1, 1,1, 1,2, 2,1), (1,-1, 1,0, 1,1, 2,-1), (1,-1, 1,0, 2,0, 2,1)], |
|||
[(0,1, 0,2, 0,3, 0,4), (1,0, 2,0, 3,0, 4,0)], |
|||
[(1,0, 1,1, 1,2, 1,3), (1,0, 2,0, 3,-1, 3,0), |
|||
(0,1, 0,2, 0,3, 1,3), (0,1, 1,0, 2,0, 3,0), (0,1, 1,1, 2,1, 3,1), |
|||
(0,1, 0,2, 0,3, 1,0), (1,0, 2,0, 3,0, 3,1), (1,-3, 1,-2, 1,-1, 1,0)], |
|||
[(0,1, 1,-2, 1,-1, 1,0), (1,0, 1,1, 2,1, 3,1), |
|||
(0,1, 0,2, 1,-1, 1,0), (1,0, 2,0, 2,1, 3,1), (0,1, 1,1, 1,2, 1,3), |
|||
(1,0, 2,-1, 2,0, 3,-1), (0,1, 0,2, 1,2, 1,3), (1,-1, 1,0, 2,-1, 3,-1)], |
|||
[(0,1, 1,0, 1,1, 2,1), (0,1, 0,2, 1,0, 1,1), |
|||
(1,0, 1,1, 2,0, 2,1), (0,1, 1,-1, 1,0, 1,1), (0,1, 1,0, 1,1, 1,2), |
|||
(1,-1, 1,0, 2,-1, 2,0), (0,1, 0,2, 1,1, 1,2), (0,1, 1,0, 1,1, 2,0)], |
|||
[(0,1, 0,2, 1,1, 2,1), (1,-2, 1,-1, 1,0, 2,0), |
|||
(1,0, 2,-1, 2,0, 2,1), (1,0, 1,1, 1,2, 2,0)], |
|||
[(0,1, 0,2, 1,0, 1,2), (0,1, 1,1, 2,0, 2,1), |
|||
(0,2, 1,0, 1,1, 1,2), (0,1, 1,0, 2,0, 2,1)], |
|||
[(1,0, 2,0, 2,1, 2,2), (0,1, 0,2, 1,0, 2,0), |
|||
(1,0, 2,-2, 2,-1, 2,0), (0,1, 0,2, 1,2, 2,2)], |
|||
[(1,0, 1,1, 2,1, 2,2), (1,-1, 1,0, 2,-2, 2,-1), |
|||
(0,1, 1,1, 1,2, 2,2), (0,1, 1,-1, 1,0, 2,-1)], |
|||
[(1,-1, 1,0, 1,1, 2,0)], |
|||
[(1,-2, 1,-1, 1,0, 1,1), (1,-1, 1,0, 2,0, 3,0), |
|||
(0,1, 0,2, 0,3, 1,1), (1,0, 2,0, 2,1, 3,0), (0,1, 0,2, 0,3, 1,2), |
|||
(1,0, 1,1, 2,0, 3,0), (1,-1, 1,0, 1,1, 1,2), (1,0, 2,-1, 2,0, 3,0)], |
|||
[(0,1, 1,0, 2,-1, 2,0), (1,0, 1,1, 1,2, 2,2), |
|||
(0,1, 1,1, 2,1, 2,2), (1,-2, 1,-1, 1,0, 2,-2)]] |
|||
const shapes = Dict{Char,Vector{Vector{GridPoint}}}() |
|||
const placed = Dict{Char,Bool}() |
|||
for (ltr, vec) in zip(shapeletters, shapevec) |
|||
shapes[ltr] = [[GridPoint(v[i], v[i + 1]) for i in 1:2:7] for v in vec] |
|||
placed[ltr] = false |
|||
end |
|||
printgrid(m, w, h) = for x in 1:w for y in 1:h print(m[x, y], " ") end; println() end |
|||
function tryplaceorientation(o, R, C, shapeindex) |
|||
for p in o |
|||
r, c = R + p.x, C + p.y |
|||
if r < 1 || r > nrows || c < 1 || c > ncols || grid[r, c] != '*' |
|||
return false |
|||
end |
|||
end |
|||
grid[R, C] = shapeindex |
|||
for p in o |
|||
grid[R + p.x, C + p.y] = shapeindex |
|||
end |
|||
true |
|||
end |
|||
function removeorientation(o, r, c) |
|||
grid[r, c] = '*' |
|||
for p in o |
|||
grid[r + p.x, c + p.y] = '*' |
|||
end |
|||
end |
|||
function solve(pos, nplaced) |
|||
if nplaced == target |
|||
return true |
|||
end |
|||
row, col = divrem(pos, ncols) .+ 1 |
|||
if grid[row, col] != '*' |
|||
return solve(pos + 1, nplaced) |
|||
end |
|||
for i in keys((shapes)) |
|||
if !placed[i] |
|||
for orientation in shapes[i] |
|||
if tryplaceorientation(orientation, row, col, i) |
|||
placed[i] = true |
|||
if solve(pos + 1, nplaced + 1) |
|||
return true |
|||
else |
|||
removeorientation(orientation, row, col) |
|||
placed[i] = false |
|||
end |
|||
end |
|||
end |
|||
end |
|||
end |
|||
false |
|||
end |
|||
function placepentominoes() |
|||
for p in zip(shuffle(collect(1:nrows))[1:4], shuffle(collect(1:ncols))[1:4]) |
|||
grid[p[1], p[2]] = ' ' |
|||
end |
|||
if solve(0, 0) |
|||
printgrid(grid, nrows, ncols) |
|||
else |
|||
println("No solution found.") |
|||
end |
|||
end |
|||
placepentominoes() |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
Z Z X P P P V |
|||
I Z X X X P P V |
|||
I Z Z X L V V V |
|||
I T T T L L L L |
|||
I N T F F U U |
|||
I N T W F F U |
|||
N N W W F Y U U |
|||
N W W Y Y Y Y |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="scala">// Version 1.1.4-3 |
|||
import java.util.Random |
|||
val F = arrayOf( |
|||
intArrayOf(1, -1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 2, 0), |
|||
intArrayOf(1, 0, 1, 1, 1, 2, 2, 1), intArrayOf(1, 0, 1, 1, 2, -1, 2, 0), |
|||
intArrayOf(1, -2, 1, -1, 1, 0, 2, -1), intArrayOf(0, 1, 1, 1, 1, 2, 2, 1), |
|||
intArrayOf(1, -1, 1, 0, 1, 1, 2, -1), intArrayOf(1, -1, 1, 0, 2, 0, 2, 1) |
|||
) |
|||
val I = arrayOf( |
|||
intArrayOf(0, 1, 0, 2, 0, 3, 0, 4), intArrayOf(1, 0, 2, 0, 3, 0, 4, 0) |
|||
) |
|||
val L = arrayOf( |
|||
intArrayOf(1, 0, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, 0, 3, -1, 3, 0), |
|||
intArrayOf(0, 1, 0, 2, 0, 3, 1, 3), intArrayOf(0, 1, 1, 0, 2, 0, 3, 0), |
|||
intArrayOf(0, 1, 1, 1, 2, 1, 3, 1), intArrayOf(0, 1, 0, 2, 0, 3, 1, 0), |
|||
intArrayOf(1, 0, 2, 0, 3, 0, 3, 1), intArrayOf(1, -3, 1, -2, 1, -1, 1, 0) |
|||
) |
|||
val N = arrayOf( |
|||
intArrayOf(0, 1, 1, -2, 1, -1, 1, 0), intArrayOf(1, 0, 1, 1, 2, 1, 3, 1), |
|||
intArrayOf(0, 1, 0, 2, 1, -1, 1, 0), intArrayOf(1, 0, 2, 0, 2, 1, 3, 1), |
|||
intArrayOf(0, 1, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, -1, 2, 0, 3, -1), |
|||
intArrayOf(0, 1, 0, 2, 1, 2, 1, 3), intArrayOf(1, -1, 1, 0, 2, -1, 3, -1) |
|||
) |
|||
val P = arrayOf( |
|||
intArrayOf(0, 1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 0, 2, 1, 0, 1, 1), |
|||
intArrayOf(1, 0, 1, 1, 2, 0, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 1, 1), |
|||
intArrayOf(0, 1, 1, 0, 1, 1, 1, 2), intArrayOf(1, -1, 1, 0, 2, -1, 2, 0), |
|||
intArrayOf(0, 1, 0, 2, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 1, 1, 2, 0) |
|||
) |
|||
val T = arrayOf( |
|||
intArrayOf(0, 1, 0, 2, 1, 1, 2, 1), intArrayOf(1, -2, 1, -1, 1, 0, 2, 0), |
|||
intArrayOf(1, 0, 2, -1, 2, 0, 2, 1), intArrayOf(1, 0, 1, 1, 1, 2, 2, 0) |
|||
) |
|||
val U = arrayOf( |
|||
intArrayOf(0, 1, 0, 2, 1, 0, 1, 2), intArrayOf(0, 1, 1, 1, 2, 0, 2, 1), |
|||
intArrayOf(0, 2, 1, 0, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 2, 0, 2, 1) |
|||
) |
|||
val V = arrayOf( |
|||
intArrayOf(1, 0, 2, 0, 2, 1, 2, 2), intArrayOf(0, 1, 0, 2, 1, 0, 2, 0), |
|||
intArrayOf(1, 0, 2, -2, 2, -1, 2, 0), intArrayOf(0, 1, 0, 2, 1, 2, 2, 2) |
|||
) |
|||
val W = arrayOf( |
|||
intArrayOf(1, 0, 1, 1, 2, 1, 2, 2), intArrayOf(1, -1, 1, 0, 2, -2, 2, -1), |
|||
intArrayOf(0, 1, 1, 1, 1, 2, 2, 2), intArrayOf(0, 1, 1, -1, 1, 0, 2, -1) |
|||
) |
|||
val X = arrayOf(intArrayOf(1, -1, 1, 0, 1, 1, 2, 0)) |
|||
val Y = arrayOf( |
|||
intArrayOf(1, -2, 1, -1, 1, 0, 1, 1), intArrayOf(1, -1, 1, 0, 2, 0, 3, 0), |
|||
intArrayOf(0, 1, 0, 2, 0, 3, 1, 1), intArrayOf(1, 0, 2, 0, 2, 1, 3, 0), |
|||
intArrayOf(0, 1, 0, 2, 0, 3, 1, 2), intArrayOf(1, 0, 1, 1, 2, 0, 3, 0), |
|||
intArrayOf(1, -1, 1, 0, 1, 1, 1, 2), intArrayOf(1, 0, 2, -1, 2, 0, 3, 0) |
|||
) |
|||
val Z = arrayOf( |
|||
intArrayOf(0, 1, 1, 0, 2, -1, 2, 0), intArrayOf(1, 0, 1, 1, 1, 2, 2, 2), |
|||
intArrayOf(0, 1, 1, 1, 2, 1, 2, 2), intArrayOf(1, -2, 1, -1, 1, 0, 2, -2) |
|||
) |
|||
val shapes = arrayOf(F, I, L, N, P, T, U, V, W, X, Y, Z) |
|||
val rand = Random() |
|||
val symbols = "FILNPTUVWXYZ-".toCharArray() |
|||
val nRows = 8 |
|||
val nCols = 8 |
|||
val blank = 12 |
|||
val grid = Array(nRows) { IntArray(nCols) } |
|||
val placed = BooleanArray(symbols.size - 1) |
|||
fun tryPlaceOrientation(o: IntArray, r: Int, c: Int, shapeIndex: Int): Boolean { |
|||
for (i in 0 until o.size step 2) { |
|||
val x = c + o[i + 1] |
|||
val y = r + o[i] |
|||
if (x !in (0 until nCols) || y !in (0 until nRows) || grid[y][x] != - 1) return false |
|||
} |
|||
grid[r][c] = shapeIndex |
|||
for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = shapeIndex |
|||
return true |
|||
} |
|||
fun removeOrientation(o: IntArray, r: Int, c: Int) { |
|||
grid[r][c] = -1 |
|||
for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = -1 |
|||
} |
|||
fun solve(pos: Int, numPlaced: Int): Boolean { |
|||
if (numPlaced == shapes.size) return true |
|||
val row = pos / nCols |
|||
val col = pos % nCols |
|||
if (grid[row][col] != -1) return solve(pos + 1, numPlaced) |
|||
for (i in 0 until shapes.size) { |
|||
if (!placed[i]) { |
|||
for (orientation in shapes[i]) { |
|||
if (!tryPlaceOrientation(orientation, row, col, i)) continue |
|||
placed[i] = true |
|||
if (solve(pos + 1, numPlaced + 1)) return true |
|||
removeOrientation(orientation, row, col) |
|||
placed[i] = false |
|||
} |
|||
} |
|||
} |
|||
return false |
|||
} |
|||
fun shuffleShapes() { |
|||
var n = shapes.size |
|||
while (n > 1) { |
|||
val r = rand.nextInt(n--) |
|||
val tmp = shapes[r] |
|||
shapes[r] = shapes[n] |
|||
shapes[n] = tmp |
|||
val tmpSymbol= symbols[r] |
|||
symbols[r] = symbols[n] |
|||
symbols[n] = tmpSymbol |
|||
} |
|||
} |
|||
fun printResult() { |
|||
for (r in grid) { |
|||
for (i in r) print("${symbols[i]} ") |
|||
println() |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
shuffleShapes() |
|||
for (r in 0 until nRows) grid[r].fill(-1) |
|||
for (i in 0..3) { |
|||
var randRow: Int |
|||
var randCol: Int |
|||
do { |
|||
randRow = rand.nextInt(nRows) |
|||
randCol = rand.nextInt(nCols) |
|||
} |
|||
while (grid[randRow][randCol] == blank) |
|||
grid[randRow][randCol] = blank |
|||
} |
|||
if (solve(0, 0)) printResult() |
|||
else println("No solution") |
|||
}</syntaxhighlight> |
|||
Sample output: |
|||
<pre> |
|||
I I I I I F - W |
|||
N N N F F F W W |
|||
U U N N F W W - |
|||
- U V L L L L T |
|||
U U V L Z T T T |
|||
V V V X Z Z Z T |
|||
P P X X X Y Z - |
|||
P P P X Y Y Y Y |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|Kotlin}} |
|||
<syntaxhighlight lang="nim">import random, sequtils, strutils |
|||
const |
|||
F = @[[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0], |
|||
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1], |
|||
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1]] |
|||
I = @[[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0]] |
|||
L = @[[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0], |
|||
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0]] |
|||
N = @[[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1], |
|||
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1], |
|||
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1], |
|||
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1]] |
|||
P = @[[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1], |
|||
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1], |
|||
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0], |
|||
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0]] |
|||
T = @[[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0]] |
|||
U = @[[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1], |
|||
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1]] |
|||
V = @[[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0], |
|||
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2]] |
|||
W = @[[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1], |
|||
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1]] |
|||
X = @[[1, -1, 1, 0, 1, 1, 2, 0]] |
|||
Y = @[[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0], |
|||
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0]] |
|||
Z = @[[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2], |
|||
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2]] |
|||
Shapes = [F, I, L, N, P, T, U, V, W, X, Y, Z] |
|||
Symbols = @"FILNPTUVWXYZ-" |
|||
NRows = 8 |
|||
NCols = 8 |
|||
Blank = Shapes.len |
|||
type Tiling = object |
|||
shapes: array[Shapes.len, seq[array[8, int]]] # Shuffled shapes. |
|||
symbols: array[Symbols.len, char] # Associated symbols. |
|||
grid: array[NRows, array[NCols, int]] |
|||
placed: array[Shapes.len, bool] |
|||
proc initTiling(): Tiling = |
|||
# Build list of shapes and symbols. |
|||
var indexes = toSeq(0..11) |
|||
indexes.shuffle() |
|||
for i, index in indexes: |
|||
result.shapes[i] = Shapes[index] |
|||
result.symbols[i] = Symbols[index] |
|||
result.symbols[^1] = Symbols[^1] |
|||
# Fill grid. |
|||
for r in result.grid.mitems: |
|||
for c in r.mitems: |
|||
c = -1 |
|||
for i in 0..3: |
|||
while true: |
|||
let randRow = rand(NRows - 1) |
|||
let randCol = rand(NCols - 1) |
|||
if result.grid[randRow][randCol] != Blank: |
|||
result.grid[randRow][randCol] = Blank |
|||
break |
|||
func tryPlaceOrientation(t: var Tiling; o: openArray[int]; r, c, shapeIndex: int): bool = |
|||
for i in countup(0, o.len - 2, 2): |
|||
let x = c + o[i + 1] |
|||
let y = r + o[i] |
|||
if x notin 0..<NCols or y notin 0..<NRows or t.grid[y][x] != - 1: return false |
|||
t.grid[r][c] = shapeIndex |
|||
for i in countup(0, o.len - 2, 2): t.grid[r + o[i]][c + o[i + 1]] = shapeIndex |
|||
result = true |
|||
func removeOrientation(t: var Tiling; o: openArray[int]; r, c: int) = |
|||
t.grid[r][c] = -1 |
|||
for i in countup(0, o.len - 2, 2): t.grid[r + o[i]][c + o[i + 1]] = -1 |
|||
func solve(t: var Tiling; pos, numPlaced: int): bool = |
|||
if numPlaced == t.shapes.len: return true |
|||
let row = pos div NCols |
|||
let col = pos mod NCols |
|||
if t.grid[row][col] != -1: return t.solve(pos + 1, numPlaced) |
|||
for i in 0..<t.shapes.len: |
|||
if not t.placed[i]: |
|||
for orientation in t.shapes[i]: |
|||
if not t.tryPlaceOrientation(orientation, row, col, i): continue |
|||
t.placed[i] = true |
|||
if t.solve(pos + 1, numPlaced + 1): return true |
|||
t.removeOrientation(orientation, row, col) |
|||
t.placed[i] = false |
|||
proc printResult(t: Tiling) = |
|||
for r in t.grid: |
|||
echo r.mapIt(t.symbols[it]).join(" ") |
|||
when isMainModule: |
|||
randomize() |
|||
var tiling = initTiling() |
|||
if tiling.solve(0, 0): tiling.printResult |
|||
else: echo "No solution"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>T T T F - P P P |
|||
Y T F F F X P P |
|||
Y T F W X X X - |
|||
Y Y W W U X U I |
|||
Y W W Z U U U I |
|||
- Z Z Z N N V I |
|||
L Z N N N - V I |
|||
L L L L V V V I</pre> |
|||
=={{header|Perl}}== |
|||
Generates one tiling at random. To generate more during one run, change the "exit" to "return". |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use feature 'bitwise'; |
|||
my $size = shift // 8; |
|||
sub rotate |
|||
{ |
|||
local $_ = shift; |
|||
my $ans = ''; |
|||
$ans .= "\n" while s/.$/$ans .= $&; ''/gem; |
|||
$ans; |
|||
} |
|||
sub topattern |
|||
{ |
|||
local $_ = shift; |
|||
s/.+/ $& . ' ' x ($size - length $&)/ge; |
|||
s/^\s+|\s+\z//g; |
|||
[ tr/ \nA-Z/.. /r, lc tr/ \n/\0/r, substr $_, 0, 1 ]; # pattern, xor-update |
|||
} |
|||
my %all; |
|||
@all{ " FF\nFF \n F \n", "IIIII\n", "LLLL\nL \n", "NNN \n NN\n", |
|||
"PPP\nPP \n", "TTT\n T \n T \n", "UUU\nU U\n", "VVV\nV \nV \n", |
|||
"WW \n WW\n W\n", " X \nXXX\n X \n", "YYYY\n Y \n", "ZZ \n Z \n ZZ\n", |
|||
} = (); |
|||
@all{map rotate($_), keys %all} = () for 1 .. 3; # all four rotations |
|||
@all{map s/.+/reverse $&/ger, keys %all} = (); # mirror |
|||
my @all = map topattern($_), keys %all; |
|||
my $grid = ( ' ' x $size . "\n" ) x $size; |
|||
my %used; |
|||
find( $grid ); |
|||
# looks for the first open space |
|||
sub find |
|||
{ |
|||
my $grid = shift; |
|||
%used >= 12 and exit not print $grid; |
|||
for ( grep ! $used{ $_->[2] }, @all ) |
|||
{ |
|||
my ($pattern, $pentomino, $letter) = @$_; |
|||
local $used{$letter} = 1; |
|||
$grid =~ /^[^ ]*\K$pattern/s and find( $grid ^. "\0" x $-[0] . $pentomino ); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
FNNNTTTP |
|||
FFFNNTPP |
|||
IFUUZTPP |
|||
ILLUZZZY |
|||
ILUUWWZY |
|||
ILVWWXYY |
|||
ILVWXXXY |
|||
VVVX |
|||
</pre> |
|||
=={{header|Phix}}== |
|||
Apart from the shape table creation, the solving part is a translation of Go.<br> |
|||
I also added a fast unsolveable() check routine, not that it desperately needed it. |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">pentominoes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""" |
|||
......I................................................................ |
|||
......I.....L......N.........................................Y......... |
|||
.FF...I.....L.....NN....PP....TTT...........V.....W....X....YY.....ZZ.. |
|||
FF....I.....L.....N.....PP.....T....U.U.....V....WW...XXX....Y.....Z... |
|||
.F....I.....LL....N.....P......T....UUU...VVV...WW.....X.....Y....ZZ..."""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- </span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_shapes</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pentominoes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">by</span> <span style="color: #000000;">6</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- scan left/right, and up/down, both ways, to give 8 orientations |
|||
-- (computes the equivalent of those hard-coded tables in |
|||
-- other examples, albeit in a slightly different order.) |
|||
--</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">shapes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">letter</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">orientation</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">7</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">shape</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">fr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fc</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rr</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orientation</span><span style="color: #0000FF;">,</span><span style="color: #000000;">#01</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">6</span><span style="color: #0000FF;">-</span><span style="color: #000000;">r</span><span style="color: #0000FF;">:</span><span style="color: #000000;">r</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">cc</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orientation</span><span style="color: #0000FF;">,</span><span style="color: #000000;">#02</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">6</span><span style="color: #0000FF;">-</span><span style="color: #000000;">c</span><span style="color: #0000FF;">:</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orientation</span><span style="color: #0000FF;">,</span><span style="color: #000000;">#04</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pentominoes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">+</span><span style="color: #000000;">cc</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">found</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">letter</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">shape</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">fr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">-</span><span style="color: #000000;">fc</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shape</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">shapes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shape</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">letter</span><span style="color: #0000FF;">&</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">shapes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_shapes</span><span style="color: #0000FF;">(),</span> |
|||
<span style="color: #000000;">nRows</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">nCols</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nCols</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nRows</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">placed</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">re_place</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">can_place</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">y</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">nCols</span> |
|||
<span style="color: #008080;">or</span> <span style="color: #000000;">y</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">></span><span style="color: #000000;">nRows</span> |
|||
<span style="color: #008080;">or</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">re_place</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">numPlaced</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">numPlaced</span> <span style="color: #0000FF;">==</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">row</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">/</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">col</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">row</span><span style="color: #0000FF;">][</span><span style="color: #000000;">col</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">numPlaced</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">placed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">can_place</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">placed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">numPlaced</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">re_place</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">row</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">col</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">placed</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">unsolveable</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #000080;font-style:italic;">-- |
|||
-- The only unsolvable grids seen have |
|||
-- -.- or -..- or -... at edge/corner, |
|||
-- - -- --- - |
|||
-- or somewhere in the middle a -.- |
|||
-- - |
|||
-- |
|||
-- Simply place all shapes at all positions/orientations, |
|||
-- all the while checking for any untouchable cells. |
|||
--</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">griddled</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shapes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">can_place</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> |
|||
<span style="color: #000000;">griddled</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> |
|||
<span style="color: #000000;">griddled</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">griddled</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">'-'</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">add_four_randomly</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">4</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'-'</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #000000;">add_four_randomly</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">unsolveable</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"No solution\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
FFPPPVVV |
|||
YFFPPX-V |
|||
YFUUXXXV |
|||
YYU-ZX-I |
|||
YTUUZZZI |
|||
-TTTWWZI |
|||
LTNNNWWI |
|||
LLLLNNWI |
|||
</pre> |
|||
=={{header|Picat}}== |
|||
<syntaxhighlight lang="picat"> |
|||
import sat, util. |
|||
rotate(Q) = Res => % rotate right by 90 degrees |
|||
NZ = len(Q[1]), NS = len(Q), Res = new_array(NZ,NS), |
|||
foreach(Z in 1..NZ, S in 1..NS) Res[Z,S] = Q[S,NZ+1-Z] end. |
|||
matprint(Q) => |
|||
NZ = len(Q), NS = len(Q[1]), |
|||
foreach(Z in 1..NZ, S in 1..NS) |
|||
printf("%d|", Q[Z,S]), |
|||
if S=NS then nl end |
|||
end, nl. |
|||
generate(Res) => |
|||
P0 = [{{1,1,1,1}, % L |
|||
{1,0,0,0}}, |
|||
{{0,1,1,1}, % N |
|||
{1,1,0,0}}, |
|||
{{1,1,1,1}, % Y |
|||
{0,1,0,0}}, |
|||
{{1,1,0}, % F |
|||
{0,1,1}, |
|||
{0,1,0}}, |
|||
{{1,1,1}, % T |
|||
{0,1,0}, |
|||
{0,1,0}}, |
|||
{{0,0,1}, % W |
|||
{0,1,1}, |
|||
{1,1,0}}, |
|||
{{1,1,1}, % P |
|||
{1,1,0}}, |
|||
{{0,0,1}, % V |
|||
{0,0,1}, |
|||
{1,1,1}}, |
|||
{{1,0,1}, % U |
|||
{1,1,1}}, |
|||
{{1,0,0}, % Z |
|||
{1,1,1}, |
|||
{0,0,1}}, |
|||
{{1,1,1,1,1}}, % I |
|||
{{0,1,0}, % X |
|||
{1,1,1}, |
|||
{0,1,0}}], |
|||
Np = len(P0), P = [], |
|||
foreach(I in 1..Np) |
|||
VarI = [P0[I]], |
|||
foreach(_ in 1..3) VarI := [rotate(head(VarI))|VarI] end, |
|||
P := [VarI|P] |
|||
end, |
|||
Res = P. |
|||
main => |
|||
N = 8, M = new_array(N+4,N+4), |
|||
foreach(R in N+1..N+4, C in 1..N) M[R,C] #= 0 end, |
|||
foreach(R in 1..N, C in N+1..N+4) M[R,C] #= 0 end, |
|||
generate(P), % P[1] = X-Pentomino, then P[2] = I, P[3] = Z, and so on U, V, P, X, W, T, F, Y, N, L |
|||
Np = len(P), M :: 0..Np, |
|||
foreach(I in 1..Np) count(I, vars(M), 5) end, % 12 pentomino |
|||
Idx = new_list(Np), % X has 1 rotation variant, I and Z each 2, the rest 4: |
|||
Idx[1] #= 1, [Idx[2],Idx[3]] :: 1..2, Idx :: 1..4, |
|||
DZ = new_list(Np), DZ :: 0..N-1, % translation of I.th pentomino |
|||
DS = new_list(Np), DS :: 0..N-1, |
|||
foreach(I in 1..Np, J in 1..4) % Constraint only if Idx[I] #= J! |
|||
NZ = len(P[I,J]), NS = len(P[I,J,1]), |
|||
foreach(DZI in 0..N-1, DSI in 0..N-1, Z in 1..NZ, S in 1..NS, P[I,J,Z,S]=1) |
|||
(Idx[I] #= J #/\ DZ[I] #= DZI #/\ DS[I] #= DSI) #=> M[DZI+Z,DSI+S] #= I |
|||
end |
|||
end, |
|||
solve(vars(M) ++ DZ ++ DS ++ Idx), |
|||
Chr = " XIZUVPWTFYNL", |
|||
foreach(Z in 1..N) |
|||
foreach(S in 1..N) |
|||
printf("%c|", Chr[1 + M[Z,S]]) |
|||
end, nl |
|||
end. |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre>Y|Y|Y|Y|P|P|Z|Z| |
|||
L|Y|X|P|P|P|Z|I| |
|||
L|X|X|X|F|Z|Z|I| |
|||
L| |X|F|F|U|U|I| |
|||
L|L|T|W|F|F|U|I| |
|||
V| |T|W|W|U|U|I| |
|||
V|T|T|T|W|W|N|N| |
|||
V|V|V| |N|N|N| |</pre> |
|||
=={{header|Racket}}== |
|||
{{trans|Java}} |
|||
(although purely functional, so no need to undo the tiling attempts) |
|||
<syntaxhighlight lang="racket">#lang racket |
|||
(require racket/hash) |
|||
(module+ main (Pentomino-tiling)) |
|||
(define n-rows 8) |
|||
(define n-cols 8) |
|||
(define blank '-) |
|||
(define (build-grid) |
|||
(for/fold ((grid (for*/hash ((r n-rows) (c n-cols)) (values (cons r c) #f)))) ((_ 4)) |
|||
(hash-set grid (cons (random n-rows) (random n-cols)) blank))) |
|||
(define (make-shapes-map) |
|||
(hash 'F (F) 'I (I) 'L (L) 'N (N) 'P (P) 'T (T) 'U (U) 'V (V) 'W (W) 'X (X) 'Y (Y) 'Z (Z))) |
|||
(define (print-grid grid) |
|||
(for ((r n-rows) #:when (when (positive? r) (newline)) (c n-cols)) |
|||
(write (hash-ref grid (cons r c)))) |
|||
(newline)) |
|||
(define (Pentomino-tiling (grid (build-grid))) |
|||
(define solution (solve 0 grid (make-shapes-map))) |
|||
(if solution (print-grid solution) (displayln "no solution"))) |
|||
(define (solve p grid shapes (failed-shapes (hash))) |
|||
(define-values (r c) (quotient/remainder p n-cols)) |
|||
(cond [(not grid) #f] |
|||
[(hash-empty? shapes) (and (hash-empty? failed-shapes) grid)] |
|||
[(hash-ref grid (cons r c) #f) (solve (add1 p) grid shapes failed-shapes)] |
|||
[else |
|||
(define s (car (hash-keys shapes))) |
|||
(define os (hash-ref shapes s)) |
|||
(define shapes-s (hash-remove shapes s)) |
|||
(define (try-place-orientation o) |
|||
(and (for/and ((dy.dx o)) |
|||
(let ((y (+ r (car dy.dx))) (x (+ c (cdr dy.dx)))) |
|||
(and (>= x 0) (>= y 0) (< x n-cols) (< y n-rows) (not (hash-ref grid (cons y x)))))) |
|||
(for/fold ((grid (hash-set grid (cons r c) s))) ((dy.dx o)) |
|||
(hash-set grid (cons (+ r (car dy.dx)) (+ c (cdr dy.dx))) s)))) |
|||
(or (for*/first |
|||
((o os) |
|||
(solution (in-value (solve (add1 p) |
|||
(try-place-orientation o) |
|||
(hash-union shapes-s failed-shapes)))) |
|||
#:when solution) |
|||
solution) |
|||
(solve p grid shapes-s (hash-set failed-shapes s os)))])) |
|||
(define (F) '(((1 . -1) (1 . 0) (1 . 1) (2 . 1)) |
|||
((0 . 1) (1 . -1) (1 . 0) (2 . 0)) |
|||
((1 . 0) (1 . 1) (1 . 2) (2 . 1)) |
|||
((1 . 0) (1 . 1) (2 . -1) (2 . 0)) |
|||
((1 . -2) (1 . -1) (1 . 0) (2 . -1)) |
|||
((0 . 1) (1 . 1) (1 . 2) (2 . 1)) |
|||
((1 . -1) (1 . 0) (1 . 1) (2 . -1)) |
|||
((1 . -1) (1 . 0) (2 . 0) (2 . 1)))) |
|||
(define (I) '(((0 . 1) (0 . 2) (0 . 3) (0 . 4)) |
|||
((1 . 0) (2 . 0) (3 . 0) (4 . 0)))) |
|||
(define (L) '(((1 . 0) (1 . 1) (1 . 2) (1 . 3)) |
|||
((1 . 0) (2 . 0) (3 . -1) (3 . 0)) |
|||
((0 . 1) (0 . 2) (0 . 3) (1 . 3)) |
|||
((0 . 1) (1 . 0) (2 . 0) (3 . 0)) |
|||
((0 . 1) (1 . 1) (2 . 1) (3 . 1)) |
|||
((0 . 1) (0 . 2) (0 . 3) (1 . 0)) |
|||
((1 . 0) (2 . 0) (3 . 0) (3 . 1)) |
|||
((1 . -3) (1 . -2) (1 . -1) (1 . 0)))) |
|||
(define (N) '(((0 . 1) (1 . -2) (1 . -1) (1 . 0)) |
|||
((1 . 0) (1 . 1) (2 . 1) (3 . 1)) |
|||
((0 . 1) (0 . 2) (1 . -1) (1 . 0)) |
|||
((1 . 0) (2 . 0) (2 . 1) (3 . 1)) |
|||
((0 . 1) (1 . 1) (1 . 2) (1 . 3)) |
|||
((1 . 0) (2 . -1) (2 . 0) (3 . -1)) |
|||
((0 . 1) (0 . 2) (1 . 2) (1 . 3)) |
|||
((1 . -1) (1 . 0) (2 . -1) (3 . -1)))) |
|||
(define (P) '(((0 . 1) (1 . 0) (1 . 1) (2 . 1)) |
|||
((0 . 1) (0 . 2) (1 . 0) (1 . 1)) |
|||
((1 . 0) (1 . 1) (2 . 0) (2 . 1)) |
|||
((0 . 1) (1 . -1) (1 . 0) (1 . 1)) |
|||
((0 . 1) (1 . 0) (1 . 1) (1 . 2)) |
|||
((1 . -1) (1 . 0) (2 . -1) (2 . 0)) |
|||
((0 . 1) (0 . 2) (1 . 1) (1 . 2)) |
|||
((0 . 1) (1 . 0) (1 . 1) (2 . 0)))) |
|||
(define (T) '(((0 . 1) (0 . 2) (1 . 1) (2 . 1)) |
|||
((1 . -2) (1 . -1) (1 . 0) (2 . 0)) |
|||
((1 . 0) (2 . -1) (2 . 0) (2 . 1)) |
|||
((1 . 0) (1 . 1) (1 . 2) (2 . 0)))) |
|||
(define (U) '(((0 . 1) (0 . 2) (1 . 0) (1 . 2)) |
|||
((0 . 1) (1 . 1) (2 . 0) (2 . 1)) |
|||
((0 . 2) (1 . 0) (1 . 1) (1 . 2)) |
|||
((0 . 1) (1 . 0) (2 . 0) (2 . 1)))) |
|||
(define (V) '(((1 . 0) (2 . 0) (2 . 1) (2 . 2)) |
|||
((0 . 1) (0 . 2) (1 . 0) (2 . 0)) |
|||
((1 . 0) (2 . -2) (2 . -1) (2 . 0)) |
|||
((0 . 1) (0 . 2) (1 . 2) (2 . 2)))) |
|||
(define (W) '(((1 . 0) (1 . 1) (2 . 1) (2 . 2)) |
|||
((1 . -1) (1 . 0) (2 . -2) (2 . -1)) |
|||
((0 . 1) (1 . 1) (1 . 2) (2 . 2)) |
|||
((0 . 1) (1 . -1) (1 . 0) (2 . -1)))) |
|||
(define (X) '(((1 . -1) (1 . 0) (1 . 1) (2 . 0)))) |
|||
(define (Y) '(((1 . -2) (1 . -1) (1 . 0) (1 . 1)) |
|||
((1 . -1) (1 . 0) (2 . 0) (3 . 0)) |
|||
((0 . 1) (0 . 2) (0 . 3) (1 . 1)) |
|||
((1 . 0) (2 . 0) (2 . 1) (3 . 0)) |
|||
((0 . 1) (0 . 2) (0 . 3) (1 . 2)) |
|||
((1 . 0) (1 . 1) (2 . 0) (3 . 0)) |
|||
((1 . -1) (1 . 0) (1 . 1) (1 . 2)) |
|||
((1 . 0) (2 . -1) (2 . 0) (3 . 0)))) |
|||
(define (Z) '(((0 . 1) (1 . 0) (2 . -1) (2 . 0)) |
|||
((1 . 0) (1 . 1) (1 . 2) (2 . 2)) |
|||
((0 . 1) (1 . 1) (2 . 1) (2 . 2)) |
|||
((1 . -2) (1 . -1) (1 . 0) (2 . -2)))) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>-UUUPPPI |
|||
NUXUPPTI |
|||
NXXXTTTI |
|||
NNXVVVTI |
|||
-NZ-WVFI |
|||
ZZZWWVFF |
|||
ZYWWLFF- |
|||
YYYYLLLL</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python">from itertools import product |
|||
minos = (((197123, 7, 6), (1797, 6, 7), (1287, 6, 7), (196867, 7, 6)), |
|||
((263937, 6, 6), (197126, 6, 6), (393731, 6, 6), (67332, 6, 6)), |
|||
((16843011, 7, 5), (2063, 5, 7), (3841, 5, 7), (271, 5, 7), (3848, 5, 7), (50463234, 7, 5), (50397441, 7, 5), (33686019, 7, 5)), |
|||
((131843, 7, 6), (1798, 6, 7), (775, 6, 7), (1795, 6, 7), (1543, 6, 7), (197377, 7, 6), (197378, 7, 6), (66307, 7, 6)), |
|||
((132865, 6, 6), (131846, 6, 6), (198146, 6, 6), (132611, 6, 6), (393986, 6, 6), (263938, 6, 6), (67330, 6, 6), (132868, 6, 6)), |
|||
((1039, 5, 7), (33751554, 7, 5), (16843521, 7, 5), (16974081, 7, 5), (33686274, 7, 5), (3842, 5, 7), (3844, 5, 7), (527, 5, 7)), |
|||
((1804, 5, 7), (33751297, 7, 5), (33686273, 7, 5), (16974338, 7, 5), (16843522, 7, 5), (782, 5, 7), (3079, 5, 7), (3587, 5, 7)), |
|||
((263683, 6, 6), (198148, 6, 6), (66310, 6, 6), (393985, 6, 6)), |
|||
((67329, 6, 6), (131591, 6, 6), (459266, 6, 6), (263940, 6, 6)), |
|||
((459780, 6, 6), (459009, 6, 6), (263175, 6, 6), (65799, 6, 6)), |
|||
((4311810305, 8, 4), (31, 4, 8)), |
|||
((132866, 6, 6),)) |
|||
boxchar_double_width = ' ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋' |
|||
boxchar_single_width = [c + ' ─━'[i%3] for i, c in enumerate(boxchar_double_width)] |
|||
# choose drawing alphabet based on terminal font |
|||
patterns = boxchar_single_width |
|||
tiles = [] |
|||
for row in reversed(minos): |
|||
tiles.append([]) |
|||
for n, x, y in row: |
|||
for shift in (b*8 + a for a, b in product(range(x), range(y))): |
|||
tiles[-1].append(n << shift) |
|||
def img(seq): |
|||
b = [[0]*10 for _ in range(10)] |
|||
for i, s in enumerate(seq): |
|||
for j, k in product(range(8), range(8)): |
|||
if s & (1<<(j*8 + k)): |
|||
b[j + 1][k + 1] = i + 1 |
|||
idices = [[0]*9 for _ in range(9)] |
|||
for i, j in product(range(9), range(9)): |
|||
n = (b[i+1][j+1], b[i][j+1], b[i][j], b[i+1][j], b[i+1][j+1]) |
|||
idices[i][j] = sum((a != b)*(1 + (not a or not b))*3**i for i, (a,b) in enumerate(zip(n, n[1:]))) |
|||
return '\n'.join(''.join(patterns[i] for i in row) for row in idices) |
|||
def tile(board=0, seq=tuple(), tiles=tiles): |
|||
if not tiles: |
|||
yield img(seq) |
|||
return |
|||
for c in tiles[0]: |
|||
b = board | c |
|||
tnext = [] # not using list comprehension ... |
|||
for t in tiles[1:]: |
|||
tnext.append(tuple(n for n in t if not n&b)) |
|||
if not tnext[-1]: break # because early break is faster |
|||
else: |
|||
yield from tile(b, seq + (c,), tnext) |
|||
for x in tile(): |
|||
print(x)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> ┏━┯━━━┯━━━━━━━┓ |
|||
┏━┛ └─┐ └─┬─┐ ┌─┨ |
|||
┠─┐ ┌─╆━┓ │ └─┘ ┃ |
|||
┃ ├─┤ ┗━┹─╆━┱───┨ |
|||
┃ │ └───┐ ┡━┹─┐ ┃ |
|||
┃ │ ┌─┬─┴─┘ ┌─┤ ┃ |
|||
┃ ┢━┪ ├───┬─┘ │ ┃ |
|||
┠─┺━┛ │ └─┐ └─┨ |
|||
┗━━━━━┷━━━━━┷━━━┛ |
|||
┏━┯━━━┓ ┏━┯━━━┓ |
|||
┏━┛ └─┐ ┗━┩ └─┐ ┃ |
|||
┠─┐ ┌─╆━┓ │ ┌─┘ ┃ |
|||
┃ ├─┤ ┗━┹─┤ ├───┨ |
|||
┃ │ └───┐ ├─┴─┐ ┃ |
|||
┃ │ ┌─┬─┴─┘ ┌─┤ ┃ |
|||
┃ ┢━┪ ├───┬─┘ │ ┃ |
|||
┠─┺━┛ │ └─┐ └─┨ |
|||
┗━━━━━┷━━━━━┷━━━┛ |
|||
(goes on and on) |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="raku" line># 20201028 Raku programming solution |
|||
my \F = [ <1 -1 1 0 1 1 2 1>, <0 1 1 -1 1 0 2 0>, <1 0 1 1 1 2 2 1>, |
|||
<1 0 1 1 2 -1 2 0>, <1 -2 1 -1 1 0 2 -1>, <0 1 1 1 1 2 2 1>, |
|||
<1 -1 1 0 1 1 2 -1>, <1 -1 1 0 2 0 2 1> ]; |
|||
my \I = [ <0 1 0 2 0 3 0 4>, <1 0 2 0 3 0 4 0> ]; |
|||
my \L = [ <1 0 1 1 1 2 1 3>, <1 0 2 0 3 0 3 1>, <0 1 0 2 0 3 1 3>, |
|||
<0 1 1 0 2 0 3 0>, <0 1 1 1 2 1 3 1>, <0 1 0 2 0 3 1 0>, |
|||
<1 0 2 0 3 -1 3 0>, <1 -3 1 -2 1 -1 1 0> ]; |
|||
my \N = [ <0 1 1 -2 1 -1 1 0>, <1 0 1 1 2 1 3 1>, <0 1 0 2 1 -1 1 0>, |
|||
<1 0 2 0 2 1 3 1>, <0 1 1 1 1 2 1 3>, <1 0 2 -1 2 0 3 -1>, |
|||
<0 1 0 2 1 2 1 3>, <1 -1 1 0 2 -1 3 -1> ]; |
|||
my \P = [ <0 1 1 0 1 1 2 1>, <0 1 0 2 1 0 1 1>, <1 0 1 1 2 0 2 1>, |
|||
<0 1 1 -1 1 0 1 1>, <0 1 1 0 1 1 1 2>, <1 -1 1 0 2 -1 2 0>, |
|||
<0 1 0 2 1 1 1 2>, <0 1 1 0 1 1 2 0> ]; |
|||
my \T = [ <0 1 0 2 1 1 2 1>, <1 -2 1 -1 1 0 2 0>, |
|||
<1 0 2 -1 2 0 2 1>, <1 0 1 1 1 2 2 0> ]; |
|||
my \U = [ <0 1 0 2 1 0 1 2>, <0 1 1 1 2 0 2 1>, |
|||
<0 2 1 0 1 1 1 2>, <0 1 1 0 2 0 2 1> ]; |
|||
my \V = [ <1 0 2 0 2 1 2 2>, <0 1 0 2 1 0 2 0>, |
|||
<1 0 2 -2 2 -1 2 0>, <0 1 0 2 1 2 2 2> ]; |
|||
my \W = [ <1 0 1 1 2 1 2 2>, <1 -1 1 0 2 -2 2 -1>, |
|||
<0 1 1 1 1 2 2 2>, <0 1 1 -1 1 0 2 -1> ]; |
|||
my \X = [ <1 -1 1 0 1 1 2 0> , ]; # self-ref: reddit.com/r/rakulang/comments/jpys5p/gbi71jt/ |
|||
my \Y = [ <1 -2 1 -1 1 0 1 1>, <1 -1 1 0 2 0 3 0>, <0 1 0 2 0 3 1 1>, |
|||
<1 0 2 0 2 1 3 0>, <0 1 0 2 0 3 1 2>, <1 0 1 1 2 0 3 0>, |
|||
<1 -1 1 0 1 1 1 2>, <1 0 2 -1 2 0 3 0> ]; |
|||
my \Z = [ <0 1 1 0 2 -1 2 0>, <1 0 1 1 1 2 2 2>, |
|||
<0 1 1 1 2 1 2 2>, <1 -2 1 -1 1 0 2 -2> ]; |
|||
our @shapes = F, I, L, N, P, T, U, V, W, X, Y, Z ; |
|||
my @symbols = "FILNPTUVWXYZ-".comb; |
|||
my %symbols = @symbols.pairs; |
|||
my $nRows = my $nCols = 8; my $blank = 12; |
|||
my @grid = [ [-1 xx $nCols ] xx $nRows ]; |
|||
my @placed; |
|||
sub shuffleShapes { |
|||
my @rand = (0 ..^+@shapes).pick(*); |
|||
for (0 ..^+@shapes) -> \i { |
|||
(@shapes[i], @shapes[@rand[i]]) = (@shapes[@rand[i]], @shapes[i]); |
|||
(@symbols[i], @symbols[@rand[i]]) = (@symbols[@rand[i]], @symbols[i]) |
|||
} |
|||
} |
|||
sub solve($pos,$numPlaced) { |
|||
return True if $numPlaced == +@shapes; |
|||
my \row = $pos div $nCols; |
|||
my \col = $pos mod $nCols; |
|||
return solve($pos + 1, $numPlaced) if @grid[row;col] != -1; |
|||
for ^+@shapes -> \i { |
|||
if !@placed[i] { |
|||
for @shapes[i] -> @orientation { |
|||
for @orientation -> @o { |
|||
next if !tryPlaceOrientation(@o, row, col, i); |
|||
@placed[i] = True; |
|||
return True if solve($pos + 1, $numPlaced + 1); |
|||
removeOrientation(@o, row, col); |
|||
@placed[i] = False; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return False |
|||
} |
|||
sub tryPlaceOrientation (@o, $r, $c, $shapeIndex) { |
|||
loop (my $i = 0; $i < +@o; $i += 2) { |
|||
my \x = $c + @o[$i + 1]; |
|||
my \y = $r + @o[$i]; |
|||
return False if |
|||
(x < 0 or x ≥ $nCols or y < 0 or y ≥ $nRows or @grid[y;x] != -1) |
|||
} |
|||
@grid[$r;$c] = $shapeIndex; |
|||
loop ($i = 0; $i < +@o; $i += 2) { |
|||
@grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = $shapeIndex; |
|||
} |
|||
return True |
|||
} |
|||
sub removeOrientation(@o, $r, $c) { |
|||
@grid[$r;$c] = -1; |
|||
loop (my $i = 0; $i < +@o; $i += 2) { |
|||
@grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = -1; |
|||
} |
|||
} |
|||
sub PrintResult { |
|||
my $output; |
|||
for @grid[*] -> @line { |
|||
$output ~= "%symbols{$_} " for @line; |
|||
$output ~= "\n" |
|||
} |
|||
if my \Embedded_Marketing_Mode = True { |
|||
$output .= subst('-', $_.chr) for < 0x24c7 0x24b6 0x24c0 0x24ca > |
|||
} |
|||
say $output |
|||
} |
|||
#shuffleShapes(); # xkcd.com/221 |
|||
for ^4 { |
|||
loop { |
|||
if @grid[my \R = (^$nRows).roll;my \C = (^$nCols).roll] != $blank |
|||
{ @grid[R;C] = $blank and last } |
|||
} |
|||
} |
|||
PrintResult() if solve 0,0</syntaxhighlight> |
|||
{{out}} |
|||
<pre>F F Ⓡ I I I I I |
|||
Ⓐ F F N L L L L |
|||
P F N N X U U L |
|||
P P N X X X U Ⓚ |
|||
P P N W X U U T |
|||
V Z Ⓤ W W T T T |
|||
V Z Z Z W W Y T |
|||
V V V Z Y Y Y Y</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-iterate}} |
|||
<syntaxhighlight lang="wren">import "random" for Random |
|||
import "./iterate" for Stepped |
|||
var F = [ |
|||
[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0], |
|||
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1], |
|||
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1] |
|||
] |
|||
var I = [ |
|||
[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0] |
|||
] |
|||
var L = [ |
|||
[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0], |
|||
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0] |
|||
] |
|||
var N = [ |
|||
[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1], |
|||
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1], |
|||
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1], |
|||
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1] |
|||
] |
|||
var P = [ |
|||
[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1], |
|||
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1], |
|||
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0], |
|||
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0] |
|||
] |
|||
var T = [ |
|||
[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0], |
|||
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0] |
|||
] |
|||
var U = [ |
|||
[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1], |
|||
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1] |
|||
] |
|||
var V = [ |
|||
[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0], |
|||
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2] |
|||
] |
|||
var W = [ |
|||
[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1], |
|||
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1] |
|||
] |
|||
var X = [[1, -1, 1, 0, 1, 1, 2, 0]] |
|||
var Y = [ |
|||
[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0], |
|||
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0], |
|||
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0] |
|||
] |
|||
var Z = [ |
|||
[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2], |
|||
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2] |
|||
] |
|||
var shapes = [F, I, L, N, P, T, U, V, W, X, Y, Z] |
|||
var rand = Random.new() |
|||
var symbols = "FILNPTUVWXYZ-".toList |
|||
var nRows = 8 |
|||
var nCols = 8 |
|||
var blank = 12 |
|||
var grid = List.filled(nRows, null) |
|||
for (i in 0...nRows) grid[i] = List.filled(nCols, 0) |
|||
var placed = List.filled(symbols.count - 1, false) |
|||
var tryPlaceOrientation = Fn.new { |o, r, c, shapeIndex| |
|||
for (i in Stepped.new(0...o.count, 2)) { |
|||
var x = c + o[i + 1] |
|||
var y = r + o[i] |
|||
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != - 1) return false |
|||
} |
|||
grid[r][c] = shapeIndex |
|||
for (i in Stepped.new(0...o.count, 2)) grid[r + o[i]][c + o[i + 1]] = shapeIndex |
|||
return true |
|||
} |
|||
var removeOrientation = Fn.new { |o, r, c| |
|||
grid[r][c] = -1 |
|||
for (i in Stepped.new(0...o.count, 2)) grid[r + o[i]][c + o[i + 1]] = -1 |
|||
} |
|||
var solve // recursive |
|||
solve = Fn.new { |pos, numPlaced| |
|||
if (numPlaced == shapes.count) return true |
|||
var row = (pos / nCols).floor |
|||
var col = pos % nCols |
|||
if (grid[row][col] != -1) return solve.call(pos + 1, numPlaced) |
|||
for (i in 0...shapes.count) { |
|||
if (!placed[i]) { |
|||
for (orientation in shapes[i]) { |
|||
if (!tryPlaceOrientation.call(orientation, row, col, i)) continue |
|||
placed[i] = true |
|||
if (solve.call(pos + 1, numPlaced + 1)) return true |
|||
removeOrientation.call(orientation, row, col) |
|||
placed[i] = false |
|||
} |
|||
} |
|||
} |
|||
return false |
|||
} |
|||
var shuffleShapes = Fn.new { |
|||
var n = shapes.count |
|||
while (n > 1) { |
|||
var r = rand.int(n) |
|||
n = n - 1 |
|||
shapes.swap(r, n) |
|||
symbols.swap(r, n) |
|||
} |
|||
} |
|||
var printResult = Fn.new { |
|||
for (r in grid) { |
|||
for (i in r) System.write("%(symbols[i]) ") |
|||
System.print() |
|||
} |
|||
} |
|||
shuffleShapes.call() |
|||
for (r in 0...nRows) { |
|||
for (c in 0...grid[r].count) grid[r][c] = -1 |
|||
} |
|||
for (i in 0..3) { |
|||
var randRow |
|||
var randCol |
|||
while (true) { |
|||
randRow = rand.int(nRows) |
|||
randCol = rand.int(nCols) |
|||
if (grid[randRow][randCol] != blank) break |
|||
} |
|||
grid[randRow][randCol] = blank |
|||
} |
|||
if (solve.call(0, 0)) printResult.call() else System.print("No solution")</syntaxhighlight> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
L L L L V U U U |
|||
Y Z Z L V U - U |
|||
Y Y Z - V V V T |
|||
Y W Z Z X T T T |
|||
Y W W X X X F T |
|||
P P W W X F F F |
|||
P P N N N F - - |
|||
P N N I I I I I |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="zkl">fcn printResult |
|||
{ foreach row in (grid){ row.apply(symbols.get).concat(" ").println() } } |
|||
fcn tryPlaceOrientation(o, R,C, shapeIndex){ |
|||
foreach ro,co in (o){ r,c:=R+ro, C+co; |
|||
if(r<0 or r>=nRows or c<0 or c>=nCols or grid[r][c]!=-1) return(False); |
|||
} |
|||
grid[R][C]=shapeIndex; foreach ro,co in (o){ grid[R+ro][C+co]=shapeIndex } |
|||
True |
|||
} |
|||
fcn removeOrientation(o, r,c) |
|||
{ grid[r][c]=-1; foreach ro,co in (o){ grid[r+ro][c+co]=-1 } } |
|||
fcn solve(pos,numPlaced){ |
|||
if(numPlaced==target) return(True); |
|||
row,col:=pos.divr(nCols); |
|||
if(grid[row][col]!=-1) return(solve(pos+1,numPlaced)); |
|||
foreach i in (shapes.len()){ |
|||
if(not placed[i]){ |
|||
foreach orientation in (shapes[i]){ |
|||
if(not tryPlaceOrientation(orientation, row,col, i)) continue; |
|||
placed[i]=True; |
|||
if(solve(pos+1,numPlaced+1)) return(True); |
|||
removeOrientation(orientation, row,col); |
|||
placed[i]=False; |
|||
} |
|||
} |
|||
} |
|||
False |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">reg [private] // the shapes are made of groups of 4 (r,c) pairs |
|||
_F=T(T(1,-1, 1,0, 1,1, 2,1), T(0,1, 1,-1, 1,0, 2,0), |
|||
T(1,0 , 1,1, 1,2, 2,1), T(1,0, 1,1, 2,-1, 2,0), T(1,-2, 1,-1, 1,0, 2,-1), |
|||
T(0,1, 1,1, 1,2, 2,1), T(1,-1, 1,0, 1,1, 2,-1), T(1,-1, 1,0, 2,0, 2,1)), |
|||
_I=T(T(0,1, 0,2, 0,3, 0,4), T(1,0, 2,0, 3,0, 4,0)), |
|||
_L=T(T(1,0, 1,1, 1,2, 1,3), T(1,0, 2,0, 3,-1, 3,0), |
|||
T(0,1, 0,2, 0,3, 1,3), T(0,1, 1,0, 2,0, 3,0), T(0,1, 1,1, 2,1, 3,1), |
|||
T(0,1, 0,2, 0,3, 1,0), T(1,0, 2,0, 3,0, 3,1), T(1,-3, 1,-2, 1,-1, 1,0)), |
|||
_N=T(T(0,1, 1,-2, 1,-1, 1,0), T(1,0, 1,1, 2,1, 3,1), |
|||
T(0,1, 0,2, 1,-1, 1,0), T(1,0, 2,0, 2,1, 3,1), T(0,1, 1,1, 1,2, 1,3), |
|||
T(1,0, 2,-1, 2,0, 3,-1),T(0,1, 0,2, 1,2, 1,3), T(1,-1, 1,0, 2,-1, 3,-1)), |
|||
_P=T(T(0,1, 1,0, 1,1, 2,1), T(0,1, 0,2, 1,0, 1,1), |
|||
T(1,0, 1,1, 2,0, 2,1), T(0,1, 1,-1, 1,0, 1,1), T(0,1, 1,0, 1,1, 1,2), |
|||
T(1,-1, 1,0, 2,-1, 2,0), T(0,1, 0,2, 1,1, 1,2), T(0,1, 1,0, 1,1, 2,0)), |
|||
_T=T(T(0,1, 0,2, 1,1, 2,1), T(1,-2, 1,-1, 1,0, 2,0), |
|||
T(1,0, 2,-1, 2,0, 2,1), T(1,0, 1,1, 1,2, 2,0)), |
|||
_U=T(T(0,1, 0,2, 1,0, 1,2), T(0,1, 1,1, 2,0, 2,1), |
|||
T(0,2, 1,0, 1,1, 1,2), T(0,1, 1,0, 2,0, 2,1)), |
|||
_V=T(T(1,0, 2,0, 2,1, 2,2), T(0,1, 0,2, 1,0, 2,0), |
|||
T(1,0, 2,-2, 2,-1, 2,0), T(0,1, 0,2, 1,2, 2,2)), |
|||
_W=T(T(1,0, 1,1, 2,1, 2,2), T(1,-1, 1,0, 2,-2, 2,-1), |
|||
T(0,1, 1,1, 1,2, 2,2), T(0,1, 1,-1, 1,0, 2,-1)), |
|||
_X=T(T(1,-1, 1,0, 1,1, 2,0)), |
|||
_Y=T(T(1,-2, 1,-1, 1,0, 1,1), T(1,-1, 1,0, 2,0, 3,0), |
|||
T(0,1, 0,2, 0,3, 1,1), T(1,0, 2,0, 2,1, 3,0), T(0,1, 0,2, 0,3, 1,2), |
|||
T(1,0, 1,1, 2,0, 3,0), T(1,-1, 1,0, 1,1, 1,2), T(1,0, 2,-1, 2,0, 3,0)), |
|||
_Z=T(T(0,1, 1,0, 2,-1, 2,0), T(1,0, 1,1, 1,2, 2,2), |
|||
T(0,1, 1,1, 2,1, 2,2), T(1,-2, 1,-1, 1,0, 2,-2)); |
|||
const nRows=8, nCols=8, target=12, blank=12; |
|||
var [const] |
|||
grid = nRows.pump(List(),nCols.pump(List(),-1).copy), |
|||
placed = target.pump(List(),False), |
|||
symbols="FILNPTUVWXYZ-".split(""), |
|||
shapes=T(_F,_I,_L,_N,_P,_T,_U,_V,_W,_X,_Y,_Z) // ((a,b, c,d))-->(((a,b),(c,d))) |
|||
.pump(List,List("pump",List,List("pump",List,Void.Read,T.create)));</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">foreach r,c in ([0..nRows-1].walk().shuffle().zip([0..nCols-1].walk().shuffle())[0,4]) |
|||
{ grid[r][c]=blank } // make sure 4 unique random spots |
|||
if(solve(0,0)) printResult(); |
|||
else println("No solution");</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
F Y Y Y Y U U U |
|||
F F F Y - U X U |
|||
I F W W L X X X |
|||
I W W N L - X T |
|||
I W N N L T T T |
|||
I V N L L Z Z T |
|||
I V N P P P Z - |
|||
- V V V P P Z Z |
|||
</pre> |
Latest revision as of 11:43, 24 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A pentomino is a polyomino that consists of 5 squares. There are 12 pentomino shapes, if you don't count rotations and reflections. Most pentominoes can form their own mirror image through rotation, but some of them have to be flipped over.
I I L N Y FF I L NN PP TTT V W X YY ZZ FF I L N PP T U U V WW XXX Y Z F I LL N P T UUU VVV WW X Y ZZ
A Pentomino tiling is an example of an exact cover problem and can take on many forms.
A traditional tiling presents an 8 by 8 grid, where 4 cells are left uncovered. The other cells are covered
by the 12 pentomino shapes, without overlaps, with every shape only used once.
The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable.
- Task
Create an 8 by 8 tiling and print the result.
- Example
F I I I I I L N F F F L L L L N W F - X Z Z N N W W X X X Z N V T W W X - Z Z V T T T P P V V V T Y - P P U U U Y Y Y Y P U - U
- Related tasks
11l
F nonrandom(n)
UInt32 :seed = 0
:seed = 1664525 * :seed + 1013904223
R (:seed >> 16) % n
-V
SF = [[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0],
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0],
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1],
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1]]
SI = [[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0]]
SL = [[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0],
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0],
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0]]
SN = [[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1],
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1],
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1],
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1]]
SP = [[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1],
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0],
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0]]
ST = [[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0],
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0]]
SU = [[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1],
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1]]
SV = [[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0],
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2]]
SW = [[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1],
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1]]
SX = [[1, -1, 1, 0, 1, 1, 2, 0]]
SY = [[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0],
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0]]
SZ = [[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2],
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2]]
Shapes = [SF, SI, SL, SN, SP, ST, SU, SV, SW, SX, SY, SZ]
Symbols = Array(‘FILNPTUVWXYZ-’)
NRows = 8
NCols = 8
Blank = Shapes.len
T Tiling
[[[Int]]] shapes
[Char] symbols
[[Int]] grid
[Bool] placed
F ()
V indexes = [4, 6, 11, 7, 10, 3, 9, 5, 1, 8, 0, 2]
L(index) indexes
.shapes.append(Shapes[index])
.symbols.append(Symbols[index])
.symbols.append(Symbols.last)
.grid = [[-1] * NCols] * NRows
L 4
L
V randRow = nonrandom(NRows)
V randCol = nonrandom(NCols)
I .grid[randRow][randCol] != Blank
.grid[randRow][randCol] = Blank
L.break
.placed = [0B] * Shapes.len
F tryPlaceOrientation(o, r, c, shapeIndex)
L(i) (0 .< o.len).step(2)
V x = c + o[i + 1]
V y = r + o[i]
I x !C 0 .< NCols | y !C 0 .< NRows | .grid[y][x] != -1
R 0B
.grid[r][c] = shapeIndex
L(i) (0 .< o.len).step(2)
.grid[r + o[i]][c + o[i + 1]] = shapeIndex
R 1B
F removeOrientation(o, r, c)
.grid[r][c] = -1
L(i) (0 .< o.len).step(2)
.grid[r + o[i]][c + o[i + 1]] = -1
F solve(pos, numPlaced)
I numPlaced == .shapes.len
R 1B
V row = pos I/ NCols
V col = pos % NCols
I .grid[row][col] != -1
R .solve(pos + 1, numPlaced)
L(i) 0 .< .shapes.len
I !.placed[i]
L(orientation) .shapes[i]
I !.tryPlaceOrientation(orientation, row, col, i)
L.continue
.placed[i] = 1B
I .solve(pos + 1, numPlaced + 1)
R 1B
.removeOrientation(orientation, row, col)
.placed[i] = 0B
R 0B
F printResult()
L(r) .grid
print(r.map(i -> @.symbols[i]).join(‘ ’))
V tiling = Tiling()
I tiling.solve(0, 0)
tiling.printResult()
E
print(‘No solution’)
- Output:
P P U U U V V V P P U X U L L V T P X X X L - V T T T X F L Z Z T - F F F L Z Y N N N F W Z Z Y - - N N W W Y Y I I I I I W W Y
BASIC
Visual Basic .NET
via
Instead of having a large declaration for each rotation of each pentomino, a small array of encoded positions is supplied (seeds), and it is expanded into the set of 63 possible orientations. However, the additional expansion routines code does take up about 2/3 of the space that would have been taken by the elaborate Integer array definitions.
Module Module1
Dim symbols As Char() = "XYPFTVNLUZWI█".ToCharArray(),
nRows As Integer = 8, nCols As Integer = 8,
target As Integer = 12, blank As Integer = 12,
grid As Integer()() = New Integer(nRows - 1)() {},
placed As Boolean() = New Boolean(target - 1) {},
pens As List(Of List(Of Integer())), rand As Random,
seeds As Integer() = {291, 292, 293, 295, 297, 329, 330, 332, 333, 335, 378, 586}
Sub Main()
Unpack(seeds) : rand = New Random() : ShuffleShapes(2)
For r As Integer = 0 To nRows - 1
grid(r) = Enumerable.Repeat(-1, nCols).ToArray() : Next
For i As Integer = 0 To 3
Dim rRow, rCol As Integer : Do : rRow = rand.Next(nRows) : rCol = rand.Next(nCols)
Loop While grid(rRow)(rCol) = blank : grid(rRow)(rCol) = blank
Next
If Solve(0, 0) Then
PrintResult()
Else
Console.WriteLine("no solution for this configuration:") : PrintResult()
End If
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
Sub ShuffleShapes(count As Integer) ' changes order of the pieces for a more random solution
For i As Integer = 0 To count : For j = 0 To pens.Count - 1
Dim r As Integer : Do : r = rand.Next(pens.Count) : Loop Until r <> j
Dim tmp As List(Of Integer()) = pens(r) : pens(r) = pens(j) : pens(j) = tmp
Dim ch As Char = symbols(r) : symbols(r) = symbols(j) : symbols(j) = ch
Next : Next
End Sub
Sub PrintResult() ' display results
For Each r As Integer() In grid : For Each i As Integer In r
Console.Write("{0} ", If(i < 0, ".", symbols(i)))
Next : Console.WriteLine() : Next
End Sub
' returns first found solution only
Function Solve(ByVal pos As Integer, ByVal numPlaced As Integer) As Boolean
If numPlaced = target Then Return True
Dim row As Integer = pos \ nCols, col As Integer = pos Mod nCols
If grid(row)(col) <> -1 Then Return Solve(pos + 1, numPlaced)
For i As Integer = 0 To pens.Count - 1 : If Not placed(i) Then
For Each orientation As Integer() In pens(i)
If Not TPO(orientation, row, col, i) Then Continue For
placed(i) = True : If Solve(pos + 1, numPlaced + 1) Then Return True
RmvO(orientation, row, col) : placed(i) = False
Next : End If : Next : Return False
End Function
' removes a placed orientation
Sub RmvO(ByVal ori As Integer(), ByVal row As Integer, ByVal col As Integer)
grid(row)(col) = -1 : For i As Integer = 0 To ori.Length - 1 Step 2
grid(row + ori(i))(col + ori(i + 1)) = -1 : Next
End Sub
' checks an orientation, if possible it is placed, else returns false
Function TPO(ByVal ori As Integer(), ByVal row As Integer, ByVal col As Integer,
ByVal sIdx As Integer) As Boolean
For i As Integer = 0 To ori.Length - 1 Step 2
Dim x As Integer = col + ori(i + 1), y As Integer = row + ori(i)
If x < 0 OrElse x >= nCols OrElse y < 0 OrElse y >= nRows OrElse
grid(y)(x) <> -1 Then Return False
Next : grid(row)(col) = sIdx
For i As Integer = 0 To ori.Length - 1 Step 2
grid(row + ori(i))(col + ori(i + 1)) = sIdx
Next : Return True
End Function
'!' the following routines expand the seed values into the 63 orientation arrays.
' source code space savings comparison:
' around 2000 chars for the expansion code, verses about 3000 chars for the integer array defs.
' perhaps not worth the savings?
Sub Unpack(sv As Integer()) ' unpacks a list of seed values into a set of 63 rotated pentominoes
pens = New List(Of List(Of Integer())) : For Each item In sv
Dim Gen As New List(Of Integer()), exi As List(Of Integer) = Expand(item),
fx As Integer() = ToP(exi) : Gen.Add(fx) : For i As Integer = 1 To 7
If i = 4 Then Mir(exi) Else Rot(exi)
fx = ToP(exi) : If Not Gen.Exists(Function(Red) TheSame(Red, fx)) Then Gen.Add(ToP(exi))
Next : pens.Add(Gen) : Next
End Sub
' expands an integer into a set of directions
Function Expand(i As Integer) As List(Of Integer)
Expand = {0}.ToList() : For j As Integer = 0 To 3 : Expand.Insert(1, i And 15) : i >>= 4 : Next
End Function
' converts a set of directions to an array of y, x pairs
Function ToP(p As List(Of Integer)) As Integer()
Dim tmp As List(Of Integer) = {0}.ToList() : For Each item As Integer In p.Skip(1)
tmp.Add(tmp.Item(item >> 2) + {1, 8, -1, -8}(item And 3)) : Next
tmp.Sort() : For i As Integer = tmp.Count - 1 To 0 Step -1 : tmp.Item(i) -= tmp.Item(0) : Next
Dim res As New List(Of Integer) : For Each item In tmp.Skip(1)
Dim adj = If((item And 7) > 4, 8, 0)
res.Add((adj + item) \ 8) : res.Add((item And 7) - adj)
Next : Return res.ToArray()
End Function
' compares integer arrays for equivalency
Function TheSame(a As Integer(), b As Integer()) As Boolean
For i As Integer = 0 To a.Count - 1 : If a(i) <> b(i) Then Return False
Next : Return True
End Function
Sub Rot(ByRef p As List(Of Integer)) ' rotates a set of directions by 90 degrees
For i As Integer = 0 To p.Count - 1 : p(i) = (p(i) And -4) Or ((p(i) + 1) And 3) : Next
End Sub
Sub Mir(ByRef p As List(Of Integer)) ' mirrors a set of directions
For i As Integer = 0 To p.Count - 1 : p(i) = (p(i) And -4) Or (((p(i) Xor 1) + 1) And 3) : Next
End Sub
End Module
- Output:
Solution found result (typical output):
Y F F █ L L L L Y Y F F L P P P Y T F N N N P P Y T N N █ V V V T T T W W Z Z V U U X █ W W Z V U X X X █ W Z Z U U X I I I I I
Impossible to solve result (a somewhat rare occurrence):
no solution for this configuration: . █ . . . . . . █ . . █ . . . . . . . . . . . . . . . . █ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
VB .NET alternative output (corner characters)
This output may appear better in a command window Try it online!
- Output:
Solution found result (typical output):
┌─────┬─────┬─┬─┐ │ ┌─┐ ├─┐ │ │ │ ├─┼─┴─┴─┴─┬─┘ │ │ │ └───┬─┐ │ ┌─┤ │ │ ┌───┼─┼─┴─┘ │ │ ├─┘ ┌─┘ └─┐ ┌─┼─┤ │ ┌─┼─┐ ┌─┴─┘ │ │ ├─┴─┘ └─┤ ┌───┘ │ └───────┴─┴─────┘
Impossible to solve result (a somewhat rare occurrence):
no solution for this configuration: ┌─┬─┬─┬─┬───────┐ │ └─┘ └─┘ │ │ ┌─┐ │ ├─┼─┘ │ ├─┘ │ │ │ │ │ │ │ └───────────────┘
C#
using System;
using System.Linq;
namespace PentominoTiling
{
class Program
{
static readonly char[] symbols = "FILNPTUVWXYZ-".ToCharArray();
static readonly int nRows = 8;
static readonly int nCols = 8;
static readonly int target = 12;
static readonly int blank = 12;
static int[][] grid = new int[nRows][];
static bool[] placed = new bool[target];
static void Main(string[] args)
{
var rand = new Random();
for (int r = 0; r < nRows; r++)
grid[r] = Enumerable.Repeat(-1, nCols).ToArray();
for (int i = 0; i < 4; i++)
{
int randRow, randCol;
do
{
randRow = rand.Next(nRows);
randCol = rand.Next(nCols);
}
while (grid[randRow][randCol] == blank);
grid[randRow][randCol] = blank;
}
if (Solve(0, 0))
{
PrintResult();
}
else
{
Console.WriteLine("no solution");
}
Console.ReadKey();
}
private static void PrintResult()
{
foreach (int[] r in grid)
{
foreach (int i in r)
Console.Write("{0} ", symbols[i]);
Console.WriteLine();
}
}
private static bool Solve(int pos, int numPlaced)
{
if (numPlaced == target)
return true;
int row = pos / nCols;
int col = pos % nCols;
if (grid[row][col] != -1)
return Solve(pos + 1, numPlaced);
for (int i = 0; i < shapes.Length; i++)
{
if (!placed[i])
{
foreach (int[] orientation in shapes[i])
{
if (!TryPlaceOrientation(orientation, row, col, i))
continue;
placed[i] = true;
if (Solve(pos + 1, numPlaced + 1))
return true;
RemoveOrientation(orientation, row, col);
placed[i] = false;
}
}
}
return false;
}
private static void RemoveOrientation(int[] orientation, int row, int col)
{
grid[row][col] = -1;
for (int i = 0; i < orientation.Length; i += 2)
grid[row + orientation[i]][col + orientation[i + 1]] = -1;
}
private static bool TryPlaceOrientation(int[] orientation, int row, int col, int shapeIndex)
{
for (int i = 0; i < orientation.Length; i += 2)
{
int x = col + orientation[i + 1];
int y = row + orientation[i];
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1)
return false;
}
grid[row][col] = shapeIndex;
for (int i = 0; i < orientation.Length; i += 2)
grid[row + orientation[i]][col + orientation[i + 1]] = shapeIndex;
return true;
}
// four (x, y) pairs are listed, (0,0) not included
static readonly int[][] F = {
new int[] {1, -1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 2, 0},
new int[] {1, 0, 1, 1, 1, 2, 2, 1}, new int[] {1, 0, 1, 1, 2, -1, 2, 0},
new int[] {1, -2, 1, -1, 1, 0, 2, -1}, new int[] {0, 1, 1, 1, 1, 2, 2, 1},
new int[] {1, -1, 1, 0, 1, 1, 2, -1}, new int[] {1, -1, 1, 0, 2, 0, 2, 1}};
static readonly int[][] I = {
new int[] { 0, 1, 0, 2, 0, 3, 0, 4 }, new int[] { 1, 0, 2, 0, 3, 0, 4, 0 } };
static readonly int[][] L = {
new int[] {1, 0, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, 0, 3, -1, 3, 0},
new int[] {0, 1, 0, 2, 0, 3, 1, 3}, new int[] {0, 1, 1, 0, 2, 0, 3, 0},
new int[] {0, 1, 1, 1, 2, 1, 3, 1}, new int[] {0, 1, 0, 2, 0, 3, 1, 0},
new int[] {1, 0, 2, 0, 3, 0, 3, 1}, new int[] {1, -3, 1, -2, 1, -1, 1, 0}};
static readonly int[][] N = {
new int[] {0, 1, 1, -2, 1, -1, 1, 0}, new int[] {1, 0, 1, 1, 2, 1, 3, 1},
new int[] {0, 1, 0, 2, 1, -1, 1, 0}, new int[] {1, 0, 2, 0, 2, 1, 3, 1},
new int[] {0, 1, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, -1, 2, 0, 3, -1},
new int[] {0, 1, 0, 2, 1, 2, 1, 3}, new int[] {1, -1, 1, 0, 2, -1, 3, -1}};
static readonly int[][] P = {
new int[] {0, 1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 0, 2, 1, 0, 1, 1},
new int[] {1, 0, 1, 1, 2, 0, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 1, 1},
new int[] {0, 1, 1, 0, 1, 1, 1, 2}, new int[] {1, -1, 1, 0, 2, -1, 2, 0},
new int[] {0, 1, 0, 2, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 1, 1, 2, 0}};
static readonly int[][] T = {
new int[] {0, 1, 0, 2, 1, 1, 2, 1}, new int[] {1, -2, 1, -1, 1, 0, 2, 0},
new int[] {1, 0, 2, -1, 2, 0, 2, 1}, new int[] {1, 0, 1, 1, 1, 2, 2, 0}};
static readonly int[][] U = {
new int[] {0, 1, 0, 2, 1, 0, 1, 2}, new int[] {0, 1, 1, 1, 2, 0, 2, 1},
new int[] {0, 2, 1, 0, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 2, 0, 2, 1}};
static readonly int[][] V = {
new int[] {1, 0, 2, 0, 2, 1, 2, 2}, new int[] {0, 1, 0, 2, 1, 0, 2, 0},
new int[] {1, 0, 2, -2, 2, -1, 2, 0}, new int[] {0, 1, 0, 2, 1, 2, 2, 2}};
static readonly int[][] W = {
new int[] {1, 0, 1, 1, 2, 1, 2, 2}, new int[] {1, -1, 1, 0, 2, -2, 2, -1},
new int[] {0, 1, 1, 1, 1, 2, 2, 2}, new int[] {0, 1, 1, -1, 1, 0, 2, -1}};
static readonly int[][] X = { new int[] { 1, -1, 1, 0, 1, 1, 2, 0 } };
static readonly int[][] Y = {
new int[] {1, -2, 1, -1, 1, 0, 1, 1}, new int[] {1, -1, 1, 0, 2, 0, 3, 0},
new int[] {0, 1, 0, 2, 0, 3, 1, 1}, new int[] {1, 0, 2, 0, 2, 1, 3, 0},
new int[] {0, 1, 0, 2, 0, 3, 1, 2}, new int[] {1, 0, 1, 1, 2, 0, 3, 0},
new int[] {1, -1, 1, 0, 1, 1, 1, 2}, new int[] {1, 0, 2, -1, 2, 0, 3, 0}};
static readonly int[][] Z = {
new int[] {0, 1, 1, 0, 2, -1, 2, 0}, new int[] {1, 0, 1, 1, 1, 2, 2, 2},
new int[] {0, 1, 1, 1, 2, 1, 2, 2}, new int[] {1, -2, 1, -1, 1, 0, 2, -2}};
static readonly int[][][] shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z };
}
}
I N F F - - L L I N N F F P P L I - N F W P P L I Y N W W X P L I Y W W X X X - Y Y T T T X Z V U Y U T Z Z Z V U U U T Z V V V
C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
const std::vector<std::vector<int32_t>> F = { { 1, -1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 1, -1, 1, 0, 2, 0 },
{ 1, 0, 1, 1, 1, 2, 2, 1 }, { 1, 0, 1, 1, 2, -1, 2, 0 }, { 1, -2, 1, -1, 1, 0, 2, -1 },
{ 0, 1, 1, 1, 1, 2, 2, 1 }, { 1, -1, 1, 0, 1, 1, 2, -1 }, { 1, -1, 1, 0, 2, 0, 2, 1 } };
const std::vector<std::vector<int32_t>> I = { { 0, 1, 0, 2, 0, 3, 0, 4 }, { 1, 0, 2, 0, 3, 0, 4, 0 } };
const std::vector<std::vector<int32_t>> L = { { 1, 0, 1, 1, 1, 2, 1, 3 }, { 1, 0, 2, 0, 3, -1, 3, 0 },
{ 0, 1, 0, 2, 0, 3, 1, 3 }, { 0, 1, 1, 0, 2, 0, 3, 0 }, { 0, 1, 1, 1, 2, 1, 3, 1 },
{ 0, 1, 0, 2, 0, 3, 1, 0 }, { 1, 0, 2, 0, 3, 0, 3, 1 }, { 1, -3, 1, -2, 1, -1, 1, 0 } };
const std::vector<std::vector<int32_t>> N = { { 0, 1, 1, -2, 1, -1, 1, 0 }, { 1, 0, 1, 1, 2, 1, 3, 1 },
{ 0, 1, 0, 2, 1, -1, 1, 0 }, { 1, 0, 2, 0, 2, 1, 3, 1 }, { 0, 1, 1, 1, 1, 2, 1, 3 },
{ 1, 0, 2, -1, 2, 0, 3, -1 }, { 0, 1, 0, 2, 1, 2, 1, 3 }, { 1, -1, 1, 0, 2, -1, 3, -1 } };
const std::vector<std::vector<int32_t>> P = { { 0, 1, 1, 0, 1, 1, 2, 1 }, { 0, 1, 0, 2, 1, 0, 1, 1 },
{ 1, 0, 1, 1, 2, 0, 2, 1 }, { 0, 1, 1, -1, 1, 0, 1, 1 }, { 0, 1, 1, 0, 1, 1, 1, 2 },
{ 1, -1, 1, 0, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 1, 1, 2 }, { 0, 1, 1, 0, 1, 1, 2, 0 } };
const std::vector<std::vector<int32_t>> T = { { 0, 1, 0, 2, 1, 1, 2, 1 }, { 1, -2, 1, -1, 1, 0, 2, 0 },
{ 1, 0, 2, -1, 2, 0, 2, 1 }, { 1, 0, 1, 1, 1, 2, 2, 0 } };
const std::vector<std::vector<int32_t>> U = { { 0, 1, 0, 2, 1, 0, 1, 2 }, { 0, 1, 1, 1, 2, 0, 2, 1 },
{ 0, 2, 1, 0, 1, 1, 1, 2 }, { 0, 1, 1, 0, 2, 0, 2, 1 } };
const std::vector<std::vector<int32_t>> V = { { 1, 0, 2, 0, 2, 1, 2, 2 }, { 0, 1, 0, 2, 1, 0, 2, 0 },
{ 1, 0, 2, -2, 2, -1, 2, 0 }, { 0, 1, 0, 2, 1, 2, 2, 2 } };
const std::vector<std::vector<int32_t>> W = { { 1, 0, 1, 1, 2, 1, 2, 2 }, { 1, -1, 1, 0, 2, -2, 2, -1 },
{ 0, 1, 1, 1, 1, 2, 2, 2 }, { 0, 1, 1, -1, 1, 0, 2, -1 } };
const std::vector<std::vector<int32_t>> X = { { 1, -1, 1, 0, 1, 1, 2, 0 } };
const std::vector<std::vector<int32_t>> Y = { { 1, -2, 1, -1, 1, 0, 1, 1 }, { 1, -1, 1, 0, 2, 0, 3, 0 },
{ 0, 1, 0, 2, 0, 3, 1, 1 }, { 1, 0, 2, 0, 2, 1, 3, 0 }, { 0, 1, 0, 2, 0, 3, 1, 2 },
{ 1, 0, 1, 1, 2, 0, 3, 0 }, { 1, -1, 1, 0, 1, 1, 1, 2 }, { 1, 0, 2, -1, 2, 0, 3, 0 } };
const std::vector<std::vector<int32_t>> Z = { { 0, 1, 1, 0, 2, -1, 2, 0 }, { 1, 0, 1, 1, 1, 2, 2, 2 },
{ 0, 1, 1, 1, 2, 1, 2, 2 }, { 1, -2, 1, -1, 1, 0, 2, -2 } };
const int32_t blank_index = 12;
const int32_t nRows = 8;
const int32_t nCols = 8;
std::vector<std::vector<std::vector<int32_t>>> shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z };
std::vector<char> symbols = { 'F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '-' };
std::vector<std::vector<int32_t>> grid{nRows, std::vector<int32_t>(nCols, -1)};
std::vector<bool> placed(symbols.size() - 1, false);
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
void display() {
for ( const std::vector<int32_t>& row : grid ) {
for ( const int32_t& index : row ) {
std::cout << symbols[index] << " ";
}
std::cout << std::endl;
}
}
void shuffle_shapes() {
uint64_t size = shapes.size();
while ( size > 1 ) {
int32_t random = static_cast<int32_t>( distribution(generator) * ( size-- ) );
const std::vector<std::vector<int32_t>> temp = shapes[random];
shapes[random] = shapes[size];
shapes[size] = temp;
const char temp_symbol = symbols[random];
symbols[random] = symbols[size];
symbols[size] = temp_symbol;
}
}
bool place_orientation(const std::vector<int32_t>& orientation,
const int32_t& row, const int32_t& col, const int32_t& shape_index) {
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) {
int32_t x = col + orientation[i + 1];
int32_t y = row + orientation[i];
if ( x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 ) {
return false;
}
}
grid[row][col] = shape_index;
for ( uint64_t i = 0; i < orientation.size(); i += 2 ) {
grid[row + orientation[i]][col + orientation[i + 1]] = shape_index;
}
return true;
}
void remove_orientation(const std::vector<int32_t>& oorientation, const int32_t& row, const int32_t& col) {
grid[row][col] = -1;
for ( uint64_t i = 0; i < oorientation.size(); i += 2 ) {
grid[row + oorientation[i]][col + oorientation[i + 1]] = -1;
}
}
bool solve(const int32_t& position, const uint64_t& number_placed) {
if ( number_placed == shapes.size() ) {
return true;
}
int32_t row = position / nCols;
int32_t col = position % nCols;
if ( grid[row][col] != -1 ) {
return solve(position + 1, number_placed);
}
for ( uint64_t i = 0; i < shapes.size(); ++i ) {
if ( ! placed[i] ) {
for ( const std::vector<int32_t>& orientation : shapes[i] ) {
if ( ! place_orientation(orientation, row, col, i) ) {
continue;
}
placed[i] = true;
if ( solve(position + 1, number_placed + 1) ) {
return true;
}
remove_orientation(orientation, row, col);
placed[i] = false;
}
}
}
return false;
}
int main() {
shuffle_shapes();
for ( int32_t i = 0; i < 4; ++i ) {
int32_t random_row, random_col;
do {
random_row = static_cast<int32_t>(distribution(generator) * nRows);
random_col = static_cast<int32_t>(distribution(generator) * nCols);
} while ( grid[random_row][random_col] == blank_index );
grid[random_row][random_col] = blank_index;
}
if ( solve(0, 0) ) {
display();
} else {
std::cout << "No solution found" << std::endl;
}
}
- Output:
Y Y Y Y X V V V U Y U X X X - V U U U T X W W V I T T T W W F - I L Z T W F F F I L Z Z Z F P P I L N N Z - P P I L L N N N - P
Go
package main
import (
"fmt"
"math/rand"
"time"
)
var F = [][]int{
{1, -1, 1, 0, 1, 1, 2, 1}, {0, 1, 1, -1, 1, 0, 2, 0},
{1, 0, 1, 1, 1, 2, 2, 1}, {1, 0, 1, 1, 2, -1, 2, 0},
{1, -2, 1, -1, 1, 0, 2, -1}, {0, 1, 1, 1, 1, 2, 2, 1},
{1, -1, 1, 0, 1, 1, 2, -1}, {1, -1, 1, 0, 2, 0, 2, 1},
}
var I = [][]int{{0, 1, 0, 2, 0, 3, 0, 4}, {1, 0, 2, 0, 3, 0, 4, 0}}
var L = [][]int{
{1, 0, 1, 1, 1, 2, 1, 3}, {1, 0, 2, 0, 3, -1, 3, 0},
{0, 1, 0, 2, 0, 3, 1, 3}, {0, 1, 1, 0, 2, 0, 3, 0}, {0, 1, 1, 1, 2, 1, 3, 1},
{0, 1, 0, 2, 0, 3, 1, 0}, {1, 0, 2, 0, 3, 0, 3, 1}, {1, -3, 1, -2, 1, -1, 1, 0},
}
var N = [][]int{
{0, 1, 1, -2, 1, -1, 1, 0}, {1, 0, 1, 1, 2, 1, 3, 1},
{0, 1, 0, 2, 1, -1, 1, 0}, {1, 0, 2, 0, 2, 1, 3, 1}, {0, 1, 1, 1, 1, 2, 1, 3},
{1, 0, 2, -1, 2, 0, 3, -1}, {0, 1, 0, 2, 1, 2, 1, 3}, {1, -1, 1, 0, 2, -1, 3, -1},
}
var P = [][]int{
{0, 1, 1, 0, 1, 1, 2, 1}, {0, 1, 0, 2, 1, 0, 1, 1},
{1, 0, 1, 1, 2, 0, 2, 1}, {0, 1, 1, -1, 1, 0, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 2},
{1, -1, 1, 0, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 1, 1, 2}, {0, 1, 1, 0, 1, 1, 2, 0},
}
var T = [][]int{
{0, 1, 0, 2, 1, 1, 2, 1}, {1, -2, 1, -1, 1, 0, 2, 0},
{1, 0, 2, -1, 2, 0, 2, 1}, {1, 0, 1, 1, 1, 2, 2, 0},
}
var U = [][]int{
{0, 1, 0, 2, 1, 0, 1, 2}, {0, 1, 1, 1, 2, 0, 2, 1},
{0, 2, 1, 0, 1, 1, 1, 2}, {0, 1, 1, 0, 2, 0, 2, 1},
}
var V = [][]int{
{1, 0, 2, 0, 2, 1, 2, 2}, {0, 1, 0, 2, 1, 0, 2, 0},
{1, 0, 2, -2, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 2, 2, 2},
}
var W = [][]int{
{1, 0, 1, 1, 2, 1, 2, 2}, {1, -1, 1, 0, 2, -2, 2, -1},
{0, 1, 1, 1, 1, 2, 2, 2}, {0, 1, 1, -1, 1, 0, 2, -1},
}
var X = [][]int{{1, -1, 1, 0, 1, 1, 2, 0}}
var Y = [][]int{
{1, -2, 1, -1, 1, 0, 1, 1}, {1, -1, 1, 0, 2, 0, 3, 0},
{0, 1, 0, 2, 0, 3, 1, 1}, {1, 0, 2, 0, 2, 1, 3, 0}, {0, 1, 0, 2, 0, 3, 1, 2},
{1, 0, 1, 1, 2, 0, 3, 0}, {1, -1, 1, 0, 1, 1, 1, 2}, {1, 0, 2, -1, 2, 0, 3, 0},
}
var Z = [][]int{
{0, 1, 1, 0, 2, -1, 2, 0}, {1, 0, 1, 1, 1, 2, 2, 2},
{0, 1, 1, 1, 2, 1, 2, 2}, {1, -2, 1, -1, 1, 0, 2, -2},
}
var shapes = [][][]int{F, I, L, N, P, T, U, V, W, X, Y, Z}
var symbols = []byte("FILNPTUVWXYZ-")
const (
nRows = 8
nCols = 8
blank = 12
)
var grid [nRows][nCols]int
var placed [12]bool
func tryPlaceOrientation(o []int, r, c, shapeIndex int) bool {
for i := 0; i < len(o); i += 2 {
x := c + o[i+1]
y := r + o[i]
if x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 {
return false
}
}
grid[r][c] = shapeIndex
for i := 0; i < len(o); i += 2 {
grid[r+o[i]][c+o[i+1]] = shapeIndex
}
return true
}
func removeOrientation(o []int, r, c int) {
grid[r][c] = -1
for i := 0; i < len(o); i += 2 {
grid[r+o[i]][c+o[i+1]] = -1
}
}
func solve(pos, numPlaced int) bool {
if numPlaced == len(shapes) {
return true
}
row := pos / nCols
col := pos % nCols
if grid[row][col] != -1 {
return solve(pos+1, numPlaced)
}
for i := range shapes {
if !placed[i] {
for _, orientation := range shapes[i] {
if !tryPlaceOrientation(orientation, row, col, i) {
continue
}
placed[i] = true
if solve(pos+1, numPlaced+1) {
return true
}
removeOrientation(orientation, row, col)
placed[i] = false
}
}
}
return false
}
func shuffleShapes() {
rand.Shuffle(len(shapes), func(i, j int) {
shapes[i], shapes[j] = shapes[j], shapes[i]
symbols[i], symbols[j] = symbols[j], symbols[i]
})
}
func printResult() {
for _, r := range grid {
for _, i := range r {
fmt.Printf("%c ", symbols[i])
}
fmt.Println()
}
}
func main() {
rand.Seed(time.Now().UnixNano())
shuffleShapes()
for r := 0; r < nRows; r++ {
for i := range grid[r] {
grid[r][i] = -1
}
}
for i := 0; i < 4; i++ {
var randRow, randCol int
for {
randRow = rand.Intn(nRows)
randCol = rand.Intn(nCols)
if grid[randRow][randCol] != blank {
break
}
}
grid[randRow][randCol] = blank
}
if solve(0, 0) {
printResult()
} else {
fmt.Println("No solution")
}
}
- Output:
Sample output:
Z I I I I I - Y Z Z Z V - F Y Y U U Z V - F F Y U V V V F F X Y U U P P W X X X T P P P W W X - T T T N N W W L T N N N L L L L
Java
package pentominotiling;
import java.util.*;
public class PentominoTiling {
static final char[] symbols = "FILNPTUVWXYZ-".toCharArray();
static final Random rand = new Random();
static final int nRows = 8;
static final int nCols = 8;
static final int blank = 12;
static int[][] grid = new int[nRows][nCols];
static boolean[] placed = new boolean[symbols.length - 1];
public static void main(String[] args) {
shuffleShapes();
for (int r = 0; r < nRows; r++)
Arrays.fill(grid[r], -1);
for (int i = 0; i < 4; i++) {
int randRow, randCol;
do {
randRow = rand.nextInt(nRows);
randCol = rand.nextInt(nCols);
} while (grid[randRow][randCol] == blank);
grid[randRow][randCol] = blank;
}
if (solve(0, 0)) {
printResult();
} else {
System.out.println("no solution");
}
}
static void shuffleShapes() {
int n = shapes.length;
while (n > 1) {
int r = rand.nextInt(n--);
int[][] tmp = shapes[r];
shapes[r] = shapes[n];
shapes[n] = tmp;
char tmpSymbol = symbols[r];
symbols[r] = symbols[n];
symbols[n] = tmpSymbol;
}
}
static void printResult() {
for (int[] r : grid) {
for (int i : r)
System.out.printf("%c ", symbols[i]);
System.out.println();
}
}
static boolean tryPlaceOrientation(int[] o, int r, int c, int shapeIndex) {
for (int i = 0; i < o.length; i += 2) {
int x = c + o[i + 1];
int y = r + o[i];
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1)
return false;
}
grid[r][c] = shapeIndex;
for (int i = 0; i < o.length; i += 2)
grid[r + o[i]][c + o[i + 1]] = shapeIndex;
return true;
}
static void removeOrientation(int[] o, int r, int c) {
grid[r][c] = -1;
for (int i = 0; i < o.length; i += 2)
grid[r + o[i]][c + o[i + 1]] = -1;
}
static boolean solve(int pos, int numPlaced) {
if (numPlaced == shapes.length)
return true;
int row = pos / nCols;
int col = pos % nCols;
if (grid[row][col] != -1)
return solve(pos + 1, numPlaced);
for (int i = 0; i < shapes.length; i++) {
if (!placed[i]) {
for (int[] orientation : shapes[i]) {
if (!tryPlaceOrientation(orientation, row, col, i))
continue;
placed[i] = true;
if (solve(pos + 1, numPlaced + 1))
return true;
removeOrientation(orientation, row, col);
placed[i] = false;
}
}
}
return false;
}
static final int[][] F = {{1, -1, 1, 0, 1, 1, 2, 1}, {0, 1, 1, -1, 1, 0, 2, 0},
{1, 0, 1, 1, 1, 2, 2, 1}, {1, 0, 1, 1, 2, -1, 2, 0}, {1, -2, 1, -1, 1, 0, 2, -1},
{0, 1, 1, 1, 1, 2, 2, 1}, {1, -1, 1, 0, 1, 1, 2, -1}, {1, -1, 1, 0, 2, 0, 2, 1}};
static final int[][] I = {{0, 1, 0, 2, 0, 3, 0, 4}, {1, 0, 2, 0, 3, 0, 4, 0}};
static final int[][] L = {{1, 0, 1, 1, 1, 2, 1, 3}, {1, 0, 2, 0, 3, -1, 3, 0},
{0, 1, 0, 2, 0, 3, 1, 3}, {0, 1, 1, 0, 2, 0, 3, 0}, {0, 1, 1, 1, 2, 1, 3, 1},
{0, 1, 0, 2, 0, 3, 1, 0}, {1, 0, 2, 0, 3, 0, 3, 1}, {1, -3, 1, -2, 1, -1, 1, 0}};
static final int[][] N = {{0, 1, 1, -2, 1, -1, 1, 0}, {1, 0, 1, 1, 2, 1, 3, 1},
{0, 1, 0, 2, 1, -1, 1, 0}, {1, 0, 2, 0, 2, 1, 3, 1}, {0, 1, 1, 1, 1, 2, 1, 3},
{1, 0, 2, -1, 2, 0, 3, -1}, {0, 1, 0, 2, 1, 2, 1, 3}, {1, -1, 1, 0, 2, -1, 3, -1}};
static final int[][] P = {{0, 1, 1, 0, 1, 1, 2, 1}, {0, 1, 0, 2, 1, 0, 1, 1},
{1, 0, 1, 1, 2, 0, 2, 1}, {0, 1, 1, -1, 1, 0, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 2},
{1, -1, 1, 0, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 1, 1, 2}, {0, 1, 1, 0, 1, 1, 2, 0}};
static final int[][] T = {{0, 1, 0, 2, 1, 1, 2, 1}, {1, -2, 1, -1, 1, 0, 2, 0},
{1, 0, 2, -1, 2, 0, 2, 1}, {1, 0, 1, 1, 1, 2, 2, 0}};
static final int[][] U = {{0, 1, 0, 2, 1, 0, 1, 2}, {0, 1, 1, 1, 2, 0, 2, 1},
{0, 2, 1, 0, 1, 1, 1, 2}, {0, 1, 1, 0, 2, 0, 2, 1}};
static final int[][] V = {{1, 0, 2, 0, 2, 1, 2, 2}, {0, 1, 0, 2, 1, 0, 2, 0},
{1, 0, 2, -2, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 2, 2, 2}};
static final int[][] W = {{1, 0, 1, 1, 2, 1, 2, 2}, {1, -1, 1, 0, 2, -2, 2, -1},
{0, 1, 1, 1, 1, 2, 2, 2}, {0, 1, 1, -1, 1, 0, 2, -1}};
static final int[][] X = {{1, -1, 1, 0, 1, 1, 2, 0}};
static final int[][] Y = {{1, -2, 1, -1, 1, 0, 1, 1}, {1, -1, 1, 0, 2, 0, 3, 0},
{0, 1, 0, 2, 0, 3, 1, 1}, {1, 0, 2, 0, 2, 1, 3, 0}, {0, 1, 0, 2, 0, 3, 1, 2},
{1, 0, 1, 1, 2, 0, 3, 0}, {1, -1, 1, 0, 1, 1, 1, 2}, {1, 0, 2, -1, 2, 0, 3, 0}};
static final int[][] Z = {{0, 1, 1, 0, 2, -1, 2, 0}, {1, 0, 1, 1, 1, 2, 2, 2},
{0, 1, 1, 1, 2, 1, 2, 2}, {1, -2, 1, -1, 1, 0, 2, -2}};
static final int[][][] shapes = {F, I, L, N, P, T, U, V, W, X, Y, Z};
}
F I I I I I L L F F F P P V L - Z F P P P V L N Z Z Z V V V L N - X Z - W W N N X X X W W - N T U X U W Y T T T U U U Y Y Y Y T
Julia
using Random
struct GridPoint x::Int; y::Int end
const nrows, ncols, target = 8, 8, 12
const grid = fill('*', nrows, ncols)
const shapeletters = ['F', 'I', 'L', 'N', 'P', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
const shapevec = [
[(1,-1, 1,0, 1,1, 2,1), (0,1, 1,-1, 1,0, 2,0),
(1,0 , 1,1, 1,2, 2,1), (1,0, 1,1, 2,-1, 2,0), (1,-2, 1,-1, 1,0, 2,-1),
(0,1, 1,1, 1,2, 2,1), (1,-1, 1,0, 1,1, 2,-1), (1,-1, 1,0, 2,0, 2,1)],
[(0,1, 0,2, 0,3, 0,4), (1,0, 2,0, 3,0, 4,0)],
[(1,0, 1,1, 1,2, 1,3), (1,0, 2,0, 3,-1, 3,0),
(0,1, 0,2, 0,3, 1,3), (0,1, 1,0, 2,0, 3,0), (0,1, 1,1, 2,1, 3,1),
(0,1, 0,2, 0,3, 1,0), (1,0, 2,0, 3,0, 3,1), (1,-3, 1,-2, 1,-1, 1,0)],
[(0,1, 1,-2, 1,-1, 1,0), (1,0, 1,1, 2,1, 3,1),
(0,1, 0,2, 1,-1, 1,0), (1,0, 2,0, 2,1, 3,1), (0,1, 1,1, 1,2, 1,3),
(1,0, 2,-1, 2,0, 3,-1), (0,1, 0,2, 1,2, 1,3), (1,-1, 1,0, 2,-1, 3,-1)],
[(0,1, 1,0, 1,1, 2,1), (0,1, 0,2, 1,0, 1,1),
(1,0, 1,1, 2,0, 2,1), (0,1, 1,-1, 1,0, 1,1), (0,1, 1,0, 1,1, 1,2),
(1,-1, 1,0, 2,-1, 2,0), (0,1, 0,2, 1,1, 1,2), (0,1, 1,0, 1,1, 2,0)],
[(0,1, 0,2, 1,1, 2,1), (1,-2, 1,-1, 1,0, 2,0),
(1,0, 2,-1, 2,0, 2,1), (1,0, 1,1, 1,2, 2,0)],
[(0,1, 0,2, 1,0, 1,2), (0,1, 1,1, 2,0, 2,1),
(0,2, 1,0, 1,1, 1,2), (0,1, 1,0, 2,0, 2,1)],
[(1,0, 2,0, 2,1, 2,2), (0,1, 0,2, 1,0, 2,0),
(1,0, 2,-2, 2,-1, 2,0), (0,1, 0,2, 1,2, 2,2)],
[(1,0, 1,1, 2,1, 2,2), (1,-1, 1,0, 2,-2, 2,-1),
(0,1, 1,1, 1,2, 2,2), (0,1, 1,-1, 1,0, 2,-1)],
[(1,-1, 1,0, 1,1, 2,0)],
[(1,-2, 1,-1, 1,0, 1,1), (1,-1, 1,0, 2,0, 3,0),
(0,1, 0,2, 0,3, 1,1), (1,0, 2,0, 2,1, 3,0), (0,1, 0,2, 0,3, 1,2),
(1,0, 1,1, 2,0, 3,0), (1,-1, 1,0, 1,1, 1,2), (1,0, 2,-1, 2,0, 3,0)],
[(0,1, 1,0, 2,-1, 2,0), (1,0, 1,1, 1,2, 2,2),
(0,1, 1,1, 2,1, 2,2), (1,-2, 1,-1, 1,0, 2,-2)]]
const shapes = Dict{Char,Vector{Vector{GridPoint}}}()
const placed = Dict{Char,Bool}()
for (ltr, vec) in zip(shapeletters, shapevec)
shapes[ltr] = [[GridPoint(v[i], v[i + 1]) for i in 1:2:7] for v in vec]
placed[ltr] = false
end
printgrid(m, w, h) = for x in 1:w for y in 1:h print(m[x, y], " ") end; println() end
function tryplaceorientation(o, R, C, shapeindex)
for p in o
r, c = R + p.x, C + p.y
if r < 1 || r > nrows || c < 1 || c > ncols || grid[r, c] != '*'
return false
end
end
grid[R, C] = shapeindex
for p in o
grid[R + p.x, C + p.y] = shapeindex
end
true
end
function removeorientation(o, r, c)
grid[r, c] = '*'
for p in o
grid[r + p.x, c + p.y] = '*'
end
end
function solve(pos, nplaced)
if nplaced == target
return true
end
row, col = divrem(pos, ncols) .+ 1
if grid[row, col] != '*'
return solve(pos + 1, nplaced)
end
for i in keys((shapes))
if !placed[i]
for orientation in shapes[i]
if tryplaceorientation(orientation, row, col, i)
placed[i] = true
if solve(pos + 1, nplaced + 1)
return true
else
removeorientation(orientation, row, col)
placed[i] = false
end
end
end
end
end
false
end
function placepentominoes()
for p in zip(shuffle(collect(1:nrows))[1:4], shuffle(collect(1:ncols))[1:4])
grid[p[1], p[2]] = ' '
end
if solve(0, 0)
printgrid(grid, nrows, ncols)
else
println("No solution found.")
end
end
placepentominoes()
- Output:
Z Z X P P P V I Z X X X P P V I Z Z X L V V V I T T T L L L L I N T F F U U I N T W F F U N N W W F Y U U N W W Y Y Y Y
Kotlin
// Version 1.1.4-3
import java.util.Random
val F = arrayOf(
intArrayOf(1, -1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 2, 0),
intArrayOf(1, 0, 1, 1, 1, 2, 2, 1), intArrayOf(1, 0, 1, 1, 2, -1, 2, 0),
intArrayOf(1, -2, 1, -1, 1, 0, 2, -1), intArrayOf(0, 1, 1, 1, 1, 2, 2, 1),
intArrayOf(1, -1, 1, 0, 1, 1, 2, -1), intArrayOf(1, -1, 1, 0, 2, 0, 2, 1)
)
val I = arrayOf(
intArrayOf(0, 1, 0, 2, 0, 3, 0, 4), intArrayOf(1, 0, 2, 0, 3, 0, 4, 0)
)
val L = arrayOf(
intArrayOf(1, 0, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, 0, 3, -1, 3, 0),
intArrayOf(0, 1, 0, 2, 0, 3, 1, 3), intArrayOf(0, 1, 1, 0, 2, 0, 3, 0),
intArrayOf(0, 1, 1, 1, 2, 1, 3, 1), intArrayOf(0, 1, 0, 2, 0, 3, 1, 0),
intArrayOf(1, 0, 2, 0, 3, 0, 3, 1), intArrayOf(1, -3, 1, -2, 1, -1, 1, 0)
)
val N = arrayOf(
intArrayOf(0, 1, 1, -2, 1, -1, 1, 0), intArrayOf(1, 0, 1, 1, 2, 1, 3, 1),
intArrayOf(0, 1, 0, 2, 1, -1, 1, 0), intArrayOf(1, 0, 2, 0, 2, 1, 3, 1),
intArrayOf(0, 1, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, -1, 2, 0, 3, -1),
intArrayOf(0, 1, 0, 2, 1, 2, 1, 3), intArrayOf(1, -1, 1, 0, 2, -1, 3, -1)
)
val P = arrayOf(
intArrayOf(0, 1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 0, 2, 1, 0, 1, 1),
intArrayOf(1, 0, 1, 1, 2, 0, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 1, 1),
intArrayOf(0, 1, 1, 0, 1, 1, 1, 2), intArrayOf(1, -1, 1, 0, 2, -1, 2, 0),
intArrayOf(0, 1, 0, 2, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 1, 1, 2, 0)
)
val T = arrayOf(
intArrayOf(0, 1, 0, 2, 1, 1, 2, 1), intArrayOf(1, -2, 1, -1, 1, 0, 2, 0),
intArrayOf(1, 0, 2, -1, 2, 0, 2, 1), intArrayOf(1, 0, 1, 1, 1, 2, 2, 0)
)
val U = arrayOf(
intArrayOf(0, 1, 0, 2, 1, 0, 1, 2), intArrayOf(0, 1, 1, 1, 2, 0, 2, 1),
intArrayOf(0, 2, 1, 0, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 2, 0, 2, 1)
)
val V = arrayOf(
intArrayOf(1, 0, 2, 0, 2, 1, 2, 2), intArrayOf(0, 1, 0, 2, 1, 0, 2, 0),
intArrayOf(1, 0, 2, -2, 2, -1, 2, 0), intArrayOf(0, 1, 0, 2, 1, 2, 2, 2)
)
val W = arrayOf(
intArrayOf(1, 0, 1, 1, 2, 1, 2, 2), intArrayOf(1, -1, 1, 0, 2, -2, 2, -1),
intArrayOf(0, 1, 1, 1, 1, 2, 2, 2), intArrayOf(0, 1, 1, -1, 1, 0, 2, -1)
)
val X = arrayOf(intArrayOf(1, -1, 1, 0, 1, 1, 2, 0))
val Y = arrayOf(
intArrayOf(1, -2, 1, -1, 1, 0, 1, 1), intArrayOf(1, -1, 1, 0, 2, 0, 3, 0),
intArrayOf(0, 1, 0, 2, 0, 3, 1, 1), intArrayOf(1, 0, 2, 0, 2, 1, 3, 0),
intArrayOf(0, 1, 0, 2, 0, 3, 1, 2), intArrayOf(1, 0, 1, 1, 2, 0, 3, 0),
intArrayOf(1, -1, 1, 0, 1, 1, 1, 2), intArrayOf(1, 0, 2, -1, 2, 0, 3, 0)
)
val Z = arrayOf(
intArrayOf(0, 1, 1, 0, 2, -1, 2, 0), intArrayOf(1, 0, 1, 1, 1, 2, 2, 2),
intArrayOf(0, 1, 1, 1, 2, 1, 2, 2), intArrayOf(1, -2, 1, -1, 1, 0, 2, -2)
)
val shapes = arrayOf(F, I, L, N, P, T, U, V, W, X, Y, Z)
val rand = Random()
val symbols = "FILNPTUVWXYZ-".toCharArray()
val nRows = 8
val nCols = 8
val blank = 12
val grid = Array(nRows) { IntArray(nCols) }
val placed = BooleanArray(symbols.size - 1)
fun tryPlaceOrientation(o: IntArray, r: Int, c: Int, shapeIndex: Int): Boolean {
for (i in 0 until o.size step 2) {
val x = c + o[i + 1]
val y = r + o[i]
if (x !in (0 until nCols) || y !in (0 until nRows) || grid[y][x] != - 1) return false
}
grid[r][c] = shapeIndex
for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = shapeIndex
return true
}
fun removeOrientation(o: IntArray, r: Int, c: Int) {
grid[r][c] = -1
for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = -1
}
fun solve(pos: Int, numPlaced: Int): Boolean {
if (numPlaced == shapes.size) return true
val row = pos / nCols
val col = pos % nCols
if (grid[row][col] != -1) return solve(pos + 1, numPlaced)
for (i in 0 until shapes.size) {
if (!placed[i]) {
for (orientation in shapes[i]) {
if (!tryPlaceOrientation(orientation, row, col, i)) continue
placed[i] = true
if (solve(pos + 1, numPlaced + 1)) return true
removeOrientation(orientation, row, col)
placed[i] = false
}
}
}
return false
}
fun shuffleShapes() {
var n = shapes.size
while (n > 1) {
val r = rand.nextInt(n--)
val tmp = shapes[r]
shapes[r] = shapes[n]
shapes[n] = tmp
val tmpSymbol= symbols[r]
symbols[r] = symbols[n]
symbols[n] = tmpSymbol
}
}
fun printResult() {
for (r in grid) {
for (i in r) print("${symbols[i]} ")
println()
}
}
fun main(args: Array<String>) {
shuffleShapes()
for (r in 0 until nRows) grid[r].fill(-1)
for (i in 0..3) {
var randRow: Int
var randCol: Int
do {
randRow = rand.nextInt(nRows)
randCol = rand.nextInt(nCols)
}
while (grid[randRow][randCol] == blank)
grid[randRow][randCol] = blank
}
if (solve(0, 0)) printResult()
else println("No solution")
}
Sample output:
I I I I I F - W N N N F F F W W U U N N F W W - - U V L L L L T U U V L Z T T T V V V X Z Z Z T P P X X X Y Z - P P P X Y Y Y Y
Nim
import random, sequtils, strutils
const
F = @[[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0],
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0],
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1],
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1]]
I = @[[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0]]
L = @[[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0],
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0],
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0]]
N = @[[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1],
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1],
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1],
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1]]
P = @[[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1],
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0],
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0]]
T = @[[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0],
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0]]
U = @[[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1],
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1]]
V = @[[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0],
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2]]
W = @[[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1],
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1]]
X = @[[1, -1, 1, 0, 1, 1, 2, 0]]
Y = @[[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0],
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0]]
Z = @[[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2],
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2]]
Shapes = [F, I, L, N, P, T, U, V, W, X, Y, Z]
Symbols = @"FILNPTUVWXYZ-"
NRows = 8
NCols = 8
Blank = Shapes.len
type Tiling = object
shapes: array[Shapes.len, seq[array[8, int]]] # Shuffled shapes.
symbols: array[Symbols.len, char] # Associated symbols.
grid: array[NRows, array[NCols, int]]
placed: array[Shapes.len, bool]
proc initTiling(): Tiling =
# Build list of shapes and symbols.
var indexes = toSeq(0..11)
indexes.shuffle()
for i, index in indexes:
result.shapes[i] = Shapes[index]
result.symbols[i] = Symbols[index]
result.symbols[^1] = Symbols[^1]
# Fill grid.
for r in result.grid.mitems:
for c in r.mitems:
c = -1
for i in 0..3:
while true:
let randRow = rand(NRows - 1)
let randCol = rand(NCols - 1)
if result.grid[randRow][randCol] != Blank:
result.grid[randRow][randCol] = Blank
break
func tryPlaceOrientation(t: var Tiling; o: openArray[int]; r, c, shapeIndex: int): bool =
for i in countup(0, o.len - 2, 2):
let x = c + o[i + 1]
let y = r + o[i]
if x notin 0..<NCols or y notin 0..<NRows or t.grid[y][x] != - 1: return false
t.grid[r][c] = shapeIndex
for i in countup(0, o.len - 2, 2): t.grid[r + o[i]][c + o[i + 1]] = shapeIndex
result = true
func removeOrientation(t: var Tiling; o: openArray[int]; r, c: int) =
t.grid[r][c] = -1
for i in countup(0, o.len - 2, 2): t.grid[r + o[i]][c + o[i + 1]] = -1
func solve(t: var Tiling; pos, numPlaced: int): bool =
if numPlaced == t.shapes.len: return true
let row = pos div NCols
let col = pos mod NCols
if t.grid[row][col] != -1: return t.solve(pos + 1, numPlaced)
for i in 0..<t.shapes.len:
if not t.placed[i]:
for orientation in t.shapes[i]:
if not t.tryPlaceOrientation(orientation, row, col, i): continue
t.placed[i] = true
if t.solve(pos + 1, numPlaced + 1): return true
t.removeOrientation(orientation, row, col)
t.placed[i] = false
proc printResult(t: Tiling) =
for r in t.grid:
echo r.mapIt(t.symbols[it]).join(" ")
when isMainModule:
randomize()
var tiling = initTiling()
if tiling.solve(0, 0): tiling.printResult
else: echo "No solution"
- Output:
T T T F - P P P Y T F F F X P P Y T F W X X X - Y Y W W U X U I Y W W Z U U U I - Z Z Z N N V I L Z N N N - V I L L L L V V V I
Perl
Generates one tiling at random. To generate more during one run, change the "exit" to "return".
use strict;
use warnings;
use feature 'bitwise';
my $size = shift // 8;
sub rotate
{
local $_ = shift;
my $ans = '';
$ans .= "\n" while s/.$/$ans .= $&; ''/gem;
$ans;
}
sub topattern
{
local $_ = shift;
s/.+/ $& . ' ' x ($size - length $&)/ge;
s/^\s+|\s+\z//g;
[ tr/ \nA-Z/.. /r, lc tr/ \n/\0/r, substr $_, 0, 1 ]; # pattern, xor-update
}
my %all;
@all{ " FF\nFF \n F \n", "IIIII\n", "LLLL\nL \n", "NNN \n NN\n",
"PPP\nPP \n", "TTT\n T \n T \n", "UUU\nU U\n", "VVV\nV \nV \n",
"WW \n WW\n W\n", " X \nXXX\n X \n", "YYYY\n Y \n", "ZZ \n Z \n ZZ\n",
} = ();
@all{map rotate($_), keys %all} = () for 1 .. 3; # all four rotations
@all{map s/.+/reverse $&/ger, keys %all} = (); # mirror
my @all = map topattern($_), keys %all;
my $grid = ( ' ' x $size . "\n" ) x $size;
my %used;
find( $grid );
# looks for the first open space
sub find
{
my $grid = shift;
%used >= 12 and exit not print $grid;
for ( grep ! $used{ $_->[2] }, @all )
{
my ($pattern, $pentomino, $letter) = @$_;
local $used{$letter} = 1;
$grid =~ /^[^ ]*\K$pattern/s and find( $grid ^. "\0" x $-[0] . $pentomino );
}
}
- Output:
FNNNTTTP FFFNNTPP IFUUZTPP ILLUZZZY ILUUWWZY ILVWWXYY ILVWXXXY VVVX
Phix
Apart from the shape table creation, the solving part is a translation of Go.
I also added a fast unsolveable() check routine, not that it desperately needed it.
with javascript_semantics constant pentominoes = split(""" ......I................................................................ ......I.....L......N.........................................Y......... .FF...I.....L.....NN....PP....TTT...........V.....W....X....YY.....ZZ.. FF....I.....L.....N.....PP.....T....U.U.....V....WW...XXX....Y.....Z... .F....I.....LL....N.....P......T....UUU...VVV...WW.....X.....Y....ZZ...""",'\n') ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- function get_shapes() sequence res = {} for offset=0 to length(pentominoes[1]) by 6 do -- -- scan left/right, and up/down, both ways, to give 8 orientations -- (computes the equivalent of those hard-coded tables in -- other examples, albeit in a slightly different order.) -- sequence shapes = {} integer letter for orientation=0 to 7 do sequence shape = {} bool found = false integer fr, fc for r=1 to 5 do for c=1 to 5 do integer rr = iff(and_bits(orientation,#01)?6-r:r), cc = iff(and_bits(orientation,#02)?6-c:c) if and_bits(orientation,#04) then {rr,cc} = {cc,rr} end if integer ch = pentominoes[rr,offset+cc] if ch!='.' then if not found then {found,fr,fc,letter} = {true,r,c,ch} else shape &= {r-fr,c-fc} end if end if end for end for if not find(shape,shapes) then shapes = append(shapes,shape) end if end for res = append(res,{letter&"",shapes}) end for return res end function constant shapes = get_shapes(), nRows = 8, nCols = 8 sequence grid = repeat(repeat(' ',nCols),nRows), placed = repeat(false,length(shapes)) procedure re_place(sequence o, integer r, c, ch=' ') grid[r][c] = ch for i=1 to length(o) by 2 do grid[r+o[i]][c+o[i+1]] = ch end for end procedure function can_place(sequence o, integer r, c, ch) for i=1 to length(o) by 2 do integer x := c + o[i+1], y := r + o[i] if x<1 or x>nCols or y<1 or y>nRows or grid[y][x]!=' ' then return false end if end for re_place(o,r,c,ch) return true end function function solve(integer pos=0, numPlaced=0) if numPlaced == length(shapes) then return true end if integer row = floor(pos/8)+1, col = mod(pos,8)+1 if grid[row][col]!=' ' then return solve(pos+1, numPlaced) end if for i=1 to length(shapes) do if not placed[i] then integer ch = shapes[i][1][1] for j=1 to length(shapes[i][2]) do sequence o = shapes[i][2][j] if can_place(o, row, col, ch) then placed[i] = true if solve(pos+1, numPlaced+1) then return true end if re_place(o, row, col) placed[i] = false end if end for end if end for return false end function function unsolveable() -- -- The only unsolvable grids seen have -- -.- or -..- or -... at edge/corner, -- - -- --- - -- or somewhere in the middle a -.- -- - -- -- Simply place all shapes at all positions/orientations, -- all the while checking for any untouchable cells. -- sequence griddled = deep_copy(grid) for r=1 to 8 do for c=1 to 8 do if grid[r][c]=' ' then for i=1 to length(shapes) do integer ch = shapes[i][1][1] for j=1 to length(shapes[i][2]) do sequence o = shapes[i][2][j] if can_place(o, r, c, ch) then grid[r][c] = ' ' griddled[r][c] = '-' for k=1 to length(o) by 2 do grid[r+o[k]][c+o[k+1]] = ' ' griddled[r+o[k]][c+o[k+1]] = '-' end for end if end for end for if griddled[r][c]!='-' then return true end if end if end for end for return false end function procedure add_four_randomly() integer count = 0 while count<4 do integer r = rand(8), c = rand(8) if grid[r][c]=' ' then grid[r][c] = '-' count += 1 end if end while end procedure procedure main() add_four_randomly() if unsolveable() then puts(1,"No solution\n") else if not solve() then ?9/0 end if end if puts(1,join(grid,"\n")&"\n") end procedure main()
- Output:
FFPPPVVV YFFPPX-V YFUUXXXV YYU-ZX-I YTUUZZZI -TTTWWZI LTNNNWWI LLLLNNWI
Picat
import sat, util.
rotate(Q) = Res => % rotate right by 90 degrees
NZ = len(Q[1]), NS = len(Q), Res = new_array(NZ,NS),
foreach(Z in 1..NZ, S in 1..NS) Res[Z,S] = Q[S,NZ+1-Z] end.
matprint(Q) =>
NZ = len(Q), NS = len(Q[1]),
foreach(Z in 1..NZ, S in 1..NS)
printf("%d|", Q[Z,S]),
if S=NS then nl end
end, nl.
generate(Res) =>
P0 = [{{1,1,1,1}, % L
{1,0,0,0}},
{{0,1,1,1}, % N
{1,1,0,0}},
{{1,1,1,1}, % Y
{0,1,0,0}},
{{1,1,0}, % F
{0,1,1},
{0,1,0}},
{{1,1,1}, % T
{0,1,0},
{0,1,0}},
{{0,0,1}, % W
{0,1,1},
{1,1,0}},
{{1,1,1}, % P
{1,1,0}},
{{0,0,1}, % V
{0,0,1},
{1,1,1}},
{{1,0,1}, % U
{1,1,1}},
{{1,0,0}, % Z
{1,1,1},
{0,0,1}},
{{1,1,1,1,1}}, % I
{{0,1,0}, % X
{1,1,1},
{0,1,0}}],
Np = len(P0), P = [],
foreach(I in 1..Np)
VarI = [P0[I]],
foreach(_ in 1..3) VarI := [rotate(head(VarI))|VarI] end,
P := [VarI|P]
end,
Res = P.
main =>
N = 8, M = new_array(N+4,N+4),
foreach(R in N+1..N+4, C in 1..N) M[R,C] #= 0 end,
foreach(R in 1..N, C in N+1..N+4) M[R,C] #= 0 end,
generate(P), % P[1] = X-Pentomino, then P[2] = I, P[3] = Z, and so on U, V, P, X, W, T, F, Y, N, L
Np = len(P), M :: 0..Np,
foreach(I in 1..Np) count(I, vars(M), 5) end, % 12 pentomino
Idx = new_list(Np), % X has 1 rotation variant, I and Z each 2, the rest 4:
Idx[1] #= 1, [Idx[2],Idx[3]] :: 1..2, Idx :: 1..4,
DZ = new_list(Np), DZ :: 0..N-1, % translation of I.th pentomino
DS = new_list(Np), DS :: 0..N-1,
foreach(I in 1..Np, J in 1..4) % Constraint only if Idx[I] #= J!
NZ = len(P[I,J]), NS = len(P[I,J,1]),
foreach(DZI in 0..N-1, DSI in 0..N-1, Z in 1..NZ, S in 1..NS, P[I,J,Z,S]=1)
(Idx[I] #= J #/\ DZ[I] #= DZI #/\ DS[I] #= DSI) #=> M[DZI+Z,DSI+S] #= I
end
end,
solve(vars(M) ++ DZ ++ DS ++ Idx),
Chr = " XIZUVPWTFYNL",
foreach(Z in 1..N)
foreach(S in 1..N)
printf("%c|", Chr[1 + M[Z,S]])
end, nl
end.
Output:
Y|Y|Y|Y|P|P|Z|Z| L|Y|X|P|P|P|Z|I| L|X|X|X|F|Z|Z|I| L| |X|F|F|U|U|I| L|L|T|W|F|F|U|I| V| |T|W|W|U|U|I| V|T|T|T|W|W|N|N| V|V|V| |N|N|N| |
Racket
(although purely functional, so no need to undo the tiling attempts)
#lang racket
(require racket/hash)
(module+ main (Pentomino-tiling))
(define n-rows 8)
(define n-cols 8)
(define blank '-)
(define (build-grid)
(for/fold ((grid (for*/hash ((r n-rows) (c n-cols)) (values (cons r c) #f)))) ((_ 4))
(hash-set grid (cons (random n-rows) (random n-cols)) blank)))
(define (make-shapes-map)
(hash 'F (F) 'I (I) 'L (L) 'N (N) 'P (P) 'T (T) 'U (U) 'V (V) 'W (W) 'X (X) 'Y (Y) 'Z (Z)))
(define (print-grid grid)
(for ((r n-rows) #:when (when (positive? r) (newline)) (c n-cols))
(write (hash-ref grid (cons r c))))
(newline))
(define (Pentomino-tiling (grid (build-grid)))
(define solution (solve 0 grid (make-shapes-map)))
(if solution (print-grid solution) (displayln "no solution")))
(define (solve p grid shapes (failed-shapes (hash)))
(define-values (r c) (quotient/remainder p n-cols))
(cond [(not grid) #f]
[(hash-empty? shapes) (and (hash-empty? failed-shapes) grid)]
[(hash-ref grid (cons r c) #f) (solve (add1 p) grid shapes failed-shapes)]
[else
(define s (car (hash-keys shapes)))
(define os (hash-ref shapes s))
(define shapes-s (hash-remove shapes s))
(define (try-place-orientation o)
(and (for/and ((dy.dx o))
(let ((y (+ r (car dy.dx))) (x (+ c (cdr dy.dx))))
(and (>= x 0) (>= y 0) (< x n-cols) (< y n-rows) (not (hash-ref grid (cons y x))))))
(for/fold ((grid (hash-set grid (cons r c) s))) ((dy.dx o))
(hash-set grid (cons (+ r (car dy.dx)) (+ c (cdr dy.dx))) s))))
(or (for*/first
((o os)
(solution (in-value (solve (add1 p)
(try-place-orientation o)
(hash-union shapes-s failed-shapes))))
#:when solution)
solution)
(solve p grid shapes-s (hash-set failed-shapes s os)))]))
(define (F) '(((1 . -1) (1 . 0) (1 . 1) (2 . 1))
((0 . 1) (1 . -1) (1 . 0) (2 . 0))
((1 . 0) (1 . 1) (1 . 2) (2 . 1))
((1 . 0) (1 . 1) (2 . -1) (2 . 0))
((1 . -2) (1 . -1) (1 . 0) (2 . -1))
((0 . 1) (1 . 1) (1 . 2) (2 . 1))
((1 . -1) (1 . 0) (1 . 1) (2 . -1))
((1 . -1) (1 . 0) (2 . 0) (2 . 1))))
(define (I) '(((0 . 1) (0 . 2) (0 . 3) (0 . 4))
((1 . 0) (2 . 0) (3 . 0) (4 . 0))))
(define (L) '(((1 . 0) (1 . 1) (1 . 2) (1 . 3))
((1 . 0) (2 . 0) (3 . -1) (3 . 0))
((0 . 1) (0 . 2) (0 . 3) (1 . 3))
((0 . 1) (1 . 0) (2 . 0) (3 . 0))
((0 . 1) (1 . 1) (2 . 1) (3 . 1))
((0 . 1) (0 . 2) (0 . 3) (1 . 0))
((1 . 0) (2 . 0) (3 . 0) (3 . 1))
((1 . -3) (1 . -2) (1 . -1) (1 . 0))))
(define (N) '(((0 . 1) (1 . -2) (1 . -1) (1 . 0))
((1 . 0) (1 . 1) (2 . 1) (3 . 1))
((0 . 1) (0 . 2) (1 . -1) (1 . 0))
((1 . 0) (2 . 0) (2 . 1) (3 . 1))
((0 . 1) (1 . 1) (1 . 2) (1 . 3))
((1 . 0) (2 . -1) (2 . 0) (3 . -1))
((0 . 1) (0 . 2) (1 . 2) (1 . 3))
((1 . -1) (1 . 0) (2 . -1) (3 . -1))))
(define (P) '(((0 . 1) (1 . 0) (1 . 1) (2 . 1))
((0 . 1) (0 . 2) (1 . 0) (1 . 1))
((1 . 0) (1 . 1) (2 . 0) (2 . 1))
((0 . 1) (1 . -1) (1 . 0) (1 . 1))
((0 . 1) (1 . 0) (1 . 1) (1 . 2))
((1 . -1) (1 . 0) (2 . -1) (2 . 0))
((0 . 1) (0 . 2) (1 . 1) (1 . 2))
((0 . 1) (1 . 0) (1 . 1) (2 . 0))))
(define (T) '(((0 . 1) (0 . 2) (1 . 1) (2 . 1))
((1 . -2) (1 . -1) (1 . 0) (2 . 0))
((1 . 0) (2 . -1) (2 . 0) (2 . 1))
((1 . 0) (1 . 1) (1 . 2) (2 . 0))))
(define (U) '(((0 . 1) (0 . 2) (1 . 0) (1 . 2))
((0 . 1) (1 . 1) (2 . 0) (2 . 1))
((0 . 2) (1 . 0) (1 . 1) (1 . 2))
((0 . 1) (1 . 0) (2 . 0) (2 . 1))))
(define (V) '(((1 . 0) (2 . 0) (2 . 1) (2 . 2))
((0 . 1) (0 . 2) (1 . 0) (2 . 0))
((1 . 0) (2 . -2) (2 . -1) (2 . 0))
((0 . 1) (0 . 2) (1 . 2) (2 . 2))))
(define (W) '(((1 . 0) (1 . 1) (2 . 1) (2 . 2))
((1 . -1) (1 . 0) (2 . -2) (2 . -1))
((0 . 1) (1 . 1) (1 . 2) (2 . 2))
((0 . 1) (1 . -1) (1 . 0) (2 . -1))))
(define (X) '(((1 . -1) (1 . 0) (1 . 1) (2 . 0))))
(define (Y) '(((1 . -2) (1 . -1) (1 . 0) (1 . 1))
((1 . -1) (1 . 0) (2 . 0) (3 . 0))
((0 . 1) (0 . 2) (0 . 3) (1 . 1))
((1 . 0) (2 . 0) (2 . 1) (3 . 0))
((0 . 1) (0 . 2) (0 . 3) (1 . 2))
((1 . 0) (1 . 1) (2 . 0) (3 . 0))
((1 . -1) (1 . 0) (1 . 1) (1 . 2))
((1 . 0) (2 . -1) (2 . 0) (3 . 0))))
(define (Z) '(((0 . 1) (1 . 0) (2 . -1) (2 . 0))
((1 . 0) (1 . 1) (1 . 2) (2 . 2))
((0 . 1) (1 . 1) (2 . 1) (2 . 2))
((1 . -2) (1 . -1) (1 . 0) (2 . -2))))
- Output:
-UUUPPPI NUXUPPTI NXXXTTTI NNXVVVTI -NZ-WVFI ZZZWWVFF ZYWWLFF- YYYYLLLL
Python
from itertools import product
minos = (((197123, 7, 6), (1797, 6, 7), (1287, 6, 7), (196867, 7, 6)),
((263937, 6, 6), (197126, 6, 6), (393731, 6, 6), (67332, 6, 6)),
((16843011, 7, 5), (2063, 5, 7), (3841, 5, 7), (271, 5, 7), (3848, 5, 7), (50463234, 7, 5), (50397441, 7, 5), (33686019, 7, 5)),
((131843, 7, 6), (1798, 6, 7), (775, 6, 7), (1795, 6, 7), (1543, 6, 7), (197377, 7, 6), (197378, 7, 6), (66307, 7, 6)),
((132865, 6, 6), (131846, 6, 6), (198146, 6, 6), (132611, 6, 6), (393986, 6, 6), (263938, 6, 6), (67330, 6, 6), (132868, 6, 6)),
((1039, 5, 7), (33751554, 7, 5), (16843521, 7, 5), (16974081, 7, 5), (33686274, 7, 5), (3842, 5, 7), (3844, 5, 7), (527, 5, 7)),
((1804, 5, 7), (33751297, 7, 5), (33686273, 7, 5), (16974338, 7, 5), (16843522, 7, 5), (782, 5, 7), (3079, 5, 7), (3587, 5, 7)),
((263683, 6, 6), (198148, 6, 6), (66310, 6, 6), (393985, 6, 6)),
((67329, 6, 6), (131591, 6, 6), (459266, 6, 6), (263940, 6, 6)),
((459780, 6, 6), (459009, 6, 6), (263175, 6, 6), (65799, 6, 6)),
((4311810305, 8, 4), (31, 4, 8)),
((132866, 6, 6),))
boxchar_double_width = ' ╶╺╵└┕╹┖┗╴─╼┘┴┶┚┸┺╸╾━┙┵┷┛┹┻╷┌┍│├┝╿┞┡┐┬┮┤┼┾┦╀╄┑┭┯┥┽┿┩╃╇╻┎┏╽┟┢┃┠┣┒┰┲┧╁╆┨╂╊┓┱┳┪╅╈┫╉╋'
boxchar_single_width = [c + ' ─━'[i%3] for i, c in enumerate(boxchar_double_width)]
# choose drawing alphabet based on terminal font
patterns = boxchar_single_width
tiles = []
for row in reversed(minos):
tiles.append([])
for n, x, y in row:
for shift in (b*8 + a for a, b in product(range(x), range(y))):
tiles[-1].append(n << shift)
def img(seq):
b = [[0]*10 for _ in range(10)]
for i, s in enumerate(seq):
for j, k in product(range(8), range(8)):
if s & (1<<(j*8 + k)):
b[j + 1][k + 1] = i + 1
idices = [[0]*9 for _ in range(9)]
for i, j in product(range(9), range(9)):
n = (b[i+1][j+1], b[i][j+1], b[i][j], b[i+1][j], b[i+1][j+1])
idices[i][j] = sum((a != b)*(1 + (not a or not b))*3**i for i, (a,b) in enumerate(zip(n, n[1:])))
return '\n'.join(''.join(patterns[i] for i in row) for row in idices)
def tile(board=0, seq=tuple(), tiles=tiles):
if not tiles:
yield img(seq)
return
for c in tiles[0]:
b = board | c
tnext = [] # not using list comprehension ...
for t in tiles[1:]:
tnext.append(tuple(n for n in t if not n&b))
if not tnext[-1]: break # because early break is faster
else:
yield from tile(b, seq + (c,), tnext)
for x in tile():
print(x)
- Output:
┏━┯━━━┯━━━━━━━┓ ┏━┛ └─┐ └─┬─┐ ┌─┨ ┠─┐ ┌─╆━┓ │ └─┘ ┃ ┃ ├─┤ ┗━┹─╆━┱───┨ ┃ │ └───┐ ┡━┹─┐ ┃ ┃ │ ┌─┬─┴─┘ ┌─┤ ┃ ┃ ┢━┪ ├───┬─┘ │ ┃ ┠─┺━┛ │ └─┐ └─┨ ┗━━━━━┷━━━━━┷━━━┛ ┏━┯━━━┓ ┏━┯━━━┓ ┏━┛ └─┐ ┗━┩ └─┐ ┃ ┠─┐ ┌─╆━┓ │ ┌─┘ ┃ ┃ ├─┤ ┗━┹─┤ ├───┨ ┃ │ └───┐ ├─┴─┐ ┃ ┃ │ ┌─┬─┴─┘ ┌─┤ ┃ ┃ ┢━┪ ├───┬─┘ │ ┃ ┠─┺━┛ │ └─┐ └─┨ ┗━━━━━┷━━━━━┷━━━┛ (goes on and on)
Raku
# 20201028 Raku programming solution
my \F = [ <1 -1 1 0 1 1 2 1>, <0 1 1 -1 1 0 2 0>, <1 0 1 1 1 2 2 1>,
<1 0 1 1 2 -1 2 0>, <1 -2 1 -1 1 0 2 -1>, <0 1 1 1 1 2 2 1>,
<1 -1 1 0 1 1 2 -1>, <1 -1 1 0 2 0 2 1> ];
my \I = [ <0 1 0 2 0 3 0 4>, <1 0 2 0 3 0 4 0> ];
my \L = [ <1 0 1 1 1 2 1 3>, <1 0 2 0 3 0 3 1>, <0 1 0 2 0 3 1 3>,
<0 1 1 0 2 0 3 0>, <0 1 1 1 2 1 3 1>, <0 1 0 2 0 3 1 0>,
<1 0 2 0 3 -1 3 0>, <1 -3 1 -2 1 -1 1 0> ];
my \N = [ <0 1 1 -2 1 -1 1 0>, <1 0 1 1 2 1 3 1>, <0 1 0 2 1 -1 1 0>,
<1 0 2 0 2 1 3 1>, <0 1 1 1 1 2 1 3>, <1 0 2 -1 2 0 3 -1>,
<0 1 0 2 1 2 1 3>, <1 -1 1 0 2 -1 3 -1> ];
my \P = [ <0 1 1 0 1 1 2 1>, <0 1 0 2 1 0 1 1>, <1 0 1 1 2 0 2 1>,
<0 1 1 -1 1 0 1 1>, <0 1 1 0 1 1 1 2>, <1 -1 1 0 2 -1 2 0>,
<0 1 0 2 1 1 1 2>, <0 1 1 0 1 1 2 0> ];
my \T = [ <0 1 0 2 1 1 2 1>, <1 -2 1 -1 1 0 2 0>,
<1 0 2 -1 2 0 2 1>, <1 0 1 1 1 2 2 0> ];
my \U = [ <0 1 0 2 1 0 1 2>, <0 1 1 1 2 0 2 1>,
<0 2 1 0 1 1 1 2>, <0 1 1 0 2 0 2 1> ];
my \V = [ <1 0 2 0 2 1 2 2>, <0 1 0 2 1 0 2 0>,
<1 0 2 -2 2 -1 2 0>, <0 1 0 2 1 2 2 2> ];
my \W = [ <1 0 1 1 2 1 2 2>, <1 -1 1 0 2 -2 2 -1>,
<0 1 1 1 1 2 2 2>, <0 1 1 -1 1 0 2 -1> ];
my \X = [ <1 -1 1 0 1 1 2 0> , ]; # self-ref: reddit.com/r/rakulang/comments/jpys5p/gbi71jt/
my \Y = [ <1 -2 1 -1 1 0 1 1>, <1 -1 1 0 2 0 3 0>, <0 1 0 2 0 3 1 1>,
<1 0 2 0 2 1 3 0>, <0 1 0 2 0 3 1 2>, <1 0 1 1 2 0 3 0>,
<1 -1 1 0 1 1 1 2>, <1 0 2 -1 2 0 3 0> ];
my \Z = [ <0 1 1 0 2 -1 2 0>, <1 0 1 1 1 2 2 2>,
<0 1 1 1 2 1 2 2>, <1 -2 1 -1 1 0 2 -2> ];
our @shapes = F, I, L, N, P, T, U, V, W, X, Y, Z ;
my @symbols = "FILNPTUVWXYZ-".comb;
my %symbols = @symbols.pairs;
my $nRows = my $nCols = 8; my $blank = 12;
my @grid = [ [-1 xx $nCols ] xx $nRows ];
my @placed;
sub shuffleShapes {
my @rand = (0 ..^+@shapes).pick(*);
for (0 ..^+@shapes) -> \i {
(@shapes[i], @shapes[@rand[i]]) = (@shapes[@rand[i]], @shapes[i]);
(@symbols[i], @symbols[@rand[i]]) = (@symbols[@rand[i]], @symbols[i])
}
}
sub solve($pos,$numPlaced) {
return True if $numPlaced == +@shapes;
my \row = $pos div $nCols;
my \col = $pos mod $nCols;
return solve($pos + 1, $numPlaced) if @grid[row;col] != -1;
for ^+@shapes -> \i {
if !@placed[i] {
for @shapes[i] -> @orientation {
for @orientation -> @o {
next if !tryPlaceOrientation(@o, row, col, i);
@placed[i] = True;
return True if solve($pos + 1, $numPlaced + 1);
removeOrientation(@o, row, col);
@placed[i] = False;
}
}
}
}
return False
}
sub tryPlaceOrientation (@o, $r, $c, $shapeIndex) {
loop (my $i = 0; $i < +@o; $i += 2) {
my \x = $c + @o[$i + 1];
my \y = $r + @o[$i];
return False if
(x < 0 or x ≥ $nCols or y < 0 or y ≥ $nRows or @grid[y;x] != -1)
}
@grid[$r;$c] = $shapeIndex;
loop ($i = 0; $i < +@o; $i += 2) {
@grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = $shapeIndex;
}
return True
}
sub removeOrientation(@o, $r, $c) {
@grid[$r;$c] = -1;
loop (my $i = 0; $i < +@o; $i += 2) {
@grid[ $r + @o[$i] ; $c + @o[$i + 1] ] = -1;
}
}
sub PrintResult {
my $output;
for @grid[*] -> @line {
$output ~= "%symbols{$_} " for @line;
$output ~= "\n"
}
if my \Embedded_Marketing_Mode = True {
$output .= subst('-', $_.chr) for < 0x24c7 0x24b6 0x24c0 0x24ca >
}
say $output
}
#shuffleShapes(); # xkcd.com/221
for ^4 {
loop {
if @grid[my \R = (^$nRows).roll;my \C = (^$nCols).roll] != $blank
{ @grid[R;C] = $blank and last }
}
}
PrintResult() if solve 0,0
- Output:
F F Ⓡ I I I I I Ⓐ F F N L L L L P F N N X U U L P P N X X X U Ⓚ P P N W X U U T V Z Ⓤ W W T T T V Z Z Z W W Y T V V V Z Y Y Y Y
Wren
import "random" for Random
import "./iterate" for Stepped
var F = [
[1, -1, 1, 0, 1, 1, 2, 1], [0, 1, 1, -1, 1, 0, 2, 0],
[1, 0, 1, 1, 1, 2, 2, 1], [1, 0, 1, 1, 2, -1, 2, 0],
[1, -2, 1, -1, 1, 0, 2, -1], [0, 1, 1, 1, 1, 2, 2, 1],
[1, -1, 1, 0, 1, 1, 2, -1], [1, -1, 1, 0, 2, 0, 2, 1]
]
var I = [
[0, 1, 0, 2, 0, 3, 0, 4], [1, 0, 2, 0, 3, 0, 4, 0]
]
var L = [
[1, 0, 1, 1, 1, 2, 1, 3], [1, 0, 2, 0, 3, -1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 3], [0, 1, 1, 0, 2, 0, 3, 0],
[0, 1, 1, 1, 2, 1, 3, 1], [0, 1, 0, 2, 0, 3, 1, 0],
[1, 0, 2, 0, 3, 0, 3, 1], [1, -3, 1, -2, 1, -1, 1, 0]
]
var N = [
[0, 1, 1, -2, 1, -1, 1, 0], [1, 0, 1, 1, 2, 1, 3, 1],
[0, 1, 0, 2, 1, -1, 1, 0], [1, 0, 2, 0, 2, 1, 3, 1],
[0, 1, 1, 1, 1, 2, 1, 3], [1, 0, 2, -1, 2, 0, 3, -1],
[0, 1, 0, 2, 1, 2, 1, 3], [1, -1, 1, 0, 2, -1, 3, -1]
]
var P = [
[0, 1, 1, 0, 1, 1, 2, 1], [0, 1, 0, 2, 1, 0, 1, 1],
[1, 0, 1, 1, 2, 0, 2, 1], [0, 1, 1, -1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 1, 1, 2], [1, -1, 1, 0, 2, -1, 2, 0],
[0, 1, 0, 2, 1, 1, 1, 2], [0, 1, 1, 0, 1, 1, 2, 0]
]
var T = [
[0, 1, 0, 2, 1, 1, 2, 1], [1, -2, 1, -1, 1, 0, 2, 0],
[1, 0, 2, -1, 2, 0, 2, 1], [1, 0, 1, 1, 1, 2, 2, 0]
]
var U = [
[0, 1, 0, 2, 1, 0, 1, 2], [0, 1, 1, 1, 2, 0, 2, 1],
[0, 2, 1, 0, 1, 1, 1, 2], [0, 1, 1, 0, 2, 0, 2, 1]
]
var V = [
[1, 0, 2, 0, 2, 1, 2, 2], [0, 1, 0, 2, 1, 0, 2, 0],
[1, 0, 2, -2, 2, -1, 2, 0], [0, 1, 0, 2, 1, 2, 2, 2]
]
var W = [
[1, 0, 1, 1, 2, 1, 2, 2], [1, -1, 1, 0, 2, -2, 2, -1],
[0, 1, 1, 1, 1, 2, 2, 2], [0, 1, 1, -1, 1, 0, 2, -1]
]
var X = [[1, -1, 1, 0, 1, 1, 2, 0]]
var Y = [
[1, -2, 1, -1, 1, 0, 1, 1], [1, -1, 1, 0, 2, 0, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 1], [1, 0, 2, 0, 2, 1, 3, 0],
[0, 1, 0, 2, 0, 3, 1, 2], [1, 0, 1, 1, 2, 0, 3, 0],
[1, -1, 1, 0, 1, 1, 1, 2], [1, 0, 2, -1, 2, 0, 3, 0]
]
var Z = [
[0, 1, 1, 0, 2, -1, 2, 0], [1, 0, 1, 1, 1, 2, 2, 2],
[0, 1, 1, 1, 2, 1, 2, 2], [1, -2, 1, -1, 1, 0, 2, -2]
]
var shapes = [F, I, L, N, P, T, U, V, W, X, Y, Z]
var rand = Random.new()
var symbols = "FILNPTUVWXYZ-".toList
var nRows = 8
var nCols = 8
var blank = 12
var grid = List.filled(nRows, null)
for (i in 0...nRows) grid[i] = List.filled(nCols, 0)
var placed = List.filled(symbols.count - 1, false)
var tryPlaceOrientation = Fn.new { |o, r, c, shapeIndex|
for (i in Stepped.new(0...o.count, 2)) {
var x = c + o[i + 1]
var y = r + o[i]
if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != - 1) return false
}
grid[r][c] = shapeIndex
for (i in Stepped.new(0...o.count, 2)) grid[r + o[i]][c + o[i + 1]] = shapeIndex
return true
}
var removeOrientation = Fn.new { |o, r, c|
grid[r][c] = -1
for (i in Stepped.new(0...o.count, 2)) grid[r + o[i]][c + o[i + 1]] = -1
}
var solve // recursive
solve = Fn.new { |pos, numPlaced|
if (numPlaced == shapes.count) return true
var row = (pos / nCols).floor
var col = pos % nCols
if (grid[row][col] != -1) return solve.call(pos + 1, numPlaced)
for (i in 0...shapes.count) {
if (!placed[i]) {
for (orientation in shapes[i]) {
if (!tryPlaceOrientation.call(orientation, row, col, i)) continue
placed[i] = true
if (solve.call(pos + 1, numPlaced + 1)) return true
removeOrientation.call(orientation, row, col)
placed[i] = false
}
}
}
return false
}
var shuffleShapes = Fn.new {
var n = shapes.count
while (n > 1) {
var r = rand.int(n)
n = n - 1
shapes.swap(r, n)
symbols.swap(r, n)
}
}
var printResult = Fn.new {
for (r in grid) {
for (i in r) System.write("%(symbols[i]) ")
System.print()
}
}
shuffleShapes.call()
for (r in 0...nRows) {
for (c in 0...grid[r].count) grid[r][c] = -1
}
for (i in 0..3) {
var randRow
var randCol
while (true) {
randRow = rand.int(nRows)
randCol = rand.int(nCols)
if (grid[randRow][randCol] != blank) break
}
grid[randRow][randCol] = blank
}
if (solve.call(0, 0)) printResult.call() else System.print("No solution")
- Output:
Sample run:
L L L L V U U U Y Z Z L V U - U Y Y Z - V V V T Y W Z Z X T T T Y W W X X X F T P P W W X F F F P P N N N F - - P N N I I I I I
zkl
fcn printResult
{ foreach row in (grid){ row.apply(symbols.get).concat(" ").println() } }
fcn tryPlaceOrientation(o, R,C, shapeIndex){
foreach ro,co in (o){ r,c:=R+ro, C+co;
if(r<0 or r>=nRows or c<0 or c>=nCols or grid[r][c]!=-1) return(False);
}
grid[R][C]=shapeIndex; foreach ro,co in (o){ grid[R+ro][C+co]=shapeIndex }
True
}
fcn removeOrientation(o, r,c)
{ grid[r][c]=-1; foreach ro,co in (o){ grid[r+ro][c+co]=-1 } }
fcn solve(pos,numPlaced){
if(numPlaced==target) return(True);
row,col:=pos.divr(nCols);
if(grid[row][col]!=-1) return(solve(pos+1,numPlaced));
foreach i in (shapes.len()){
if(not placed[i]){
foreach orientation in (shapes[i]){
if(not tryPlaceOrientation(orientation, row,col, i)) continue;
placed[i]=True;
if(solve(pos+1,numPlaced+1)) return(True);
removeOrientation(orientation, row,col);
placed[i]=False;
}
}
}
False
}
reg [private] // the shapes are made of groups of 4 (r,c) pairs
_F=T(T(1,-1, 1,0, 1,1, 2,1), T(0,1, 1,-1, 1,0, 2,0),
T(1,0 , 1,1, 1,2, 2,1), T(1,0, 1,1, 2,-1, 2,0), T(1,-2, 1,-1, 1,0, 2,-1),
T(0,1, 1,1, 1,2, 2,1), T(1,-1, 1,0, 1,1, 2,-1), T(1,-1, 1,0, 2,0, 2,1)),
_I=T(T(0,1, 0,2, 0,3, 0,4), T(1,0, 2,0, 3,0, 4,0)),
_L=T(T(1,0, 1,1, 1,2, 1,3), T(1,0, 2,0, 3,-1, 3,0),
T(0,1, 0,2, 0,3, 1,3), T(0,1, 1,0, 2,0, 3,0), T(0,1, 1,1, 2,1, 3,1),
T(0,1, 0,2, 0,3, 1,0), T(1,0, 2,0, 3,0, 3,1), T(1,-3, 1,-2, 1,-1, 1,0)),
_N=T(T(0,1, 1,-2, 1,-1, 1,0), T(1,0, 1,1, 2,1, 3,1),
T(0,1, 0,2, 1,-1, 1,0), T(1,0, 2,0, 2,1, 3,1), T(0,1, 1,1, 1,2, 1,3),
T(1,0, 2,-1, 2,0, 3,-1),T(0,1, 0,2, 1,2, 1,3), T(1,-1, 1,0, 2,-1, 3,-1)),
_P=T(T(0,1, 1,0, 1,1, 2,1), T(0,1, 0,2, 1,0, 1,1),
T(1,0, 1,1, 2,0, 2,1), T(0,1, 1,-1, 1,0, 1,1), T(0,1, 1,0, 1,1, 1,2),
T(1,-1, 1,0, 2,-1, 2,0), T(0,1, 0,2, 1,1, 1,2), T(0,1, 1,0, 1,1, 2,0)),
_T=T(T(0,1, 0,2, 1,1, 2,1), T(1,-2, 1,-1, 1,0, 2,0),
T(1,0, 2,-1, 2,0, 2,1), T(1,0, 1,1, 1,2, 2,0)),
_U=T(T(0,1, 0,2, 1,0, 1,2), T(0,1, 1,1, 2,0, 2,1),
T(0,2, 1,0, 1,1, 1,2), T(0,1, 1,0, 2,0, 2,1)),
_V=T(T(1,0, 2,0, 2,1, 2,2), T(0,1, 0,2, 1,0, 2,0),
T(1,0, 2,-2, 2,-1, 2,0), T(0,1, 0,2, 1,2, 2,2)),
_W=T(T(1,0, 1,1, 2,1, 2,2), T(1,-1, 1,0, 2,-2, 2,-1),
T(0,1, 1,1, 1,2, 2,2), T(0,1, 1,-1, 1,0, 2,-1)),
_X=T(T(1,-1, 1,0, 1,1, 2,0)),
_Y=T(T(1,-2, 1,-1, 1,0, 1,1), T(1,-1, 1,0, 2,0, 3,0),
T(0,1, 0,2, 0,3, 1,1), T(1,0, 2,0, 2,1, 3,0), T(0,1, 0,2, 0,3, 1,2),
T(1,0, 1,1, 2,0, 3,0), T(1,-1, 1,0, 1,1, 1,2), T(1,0, 2,-1, 2,0, 3,0)),
_Z=T(T(0,1, 1,0, 2,-1, 2,0), T(1,0, 1,1, 1,2, 2,2),
T(0,1, 1,1, 2,1, 2,2), T(1,-2, 1,-1, 1,0, 2,-2));
const nRows=8, nCols=8, target=12, blank=12;
var [const]
grid = nRows.pump(List(),nCols.pump(List(),-1).copy),
placed = target.pump(List(),False),
symbols="FILNPTUVWXYZ-".split(""),
shapes=T(_F,_I,_L,_N,_P,_T,_U,_V,_W,_X,_Y,_Z) // ((a,b, c,d))-->(((a,b),(c,d)))
.pump(List,List("pump",List,List("pump",List,Void.Read,T.create)));
foreach r,c in ([0..nRows-1].walk().shuffle().zip([0..nCols-1].walk().shuffle())[0,4])
{ grid[r][c]=blank } // make sure 4 unique random spots
if(solve(0,0)) printResult();
else println("No solution");
- Output:
F Y Y Y Y U U U F F F Y - U X U I F W W L X X X I W W N L - X T I W N N L T T T I V N L L Z Z T I V N P P P Z - - V V V P P Z Z