Rosetta Code

Pentomino tiling: Difference between revisions

Page Discussion

Pentomino tiling (view source)

Revision as of 11:43, 24 January 2024

10,269 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (syntax highlighting fixup automation)
m (→‎{{header|Wren}}: Minor tidy)
 
(6 intermediate revisions by 5 users not shown)
Line 38:
* [[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#}}==
Line 224 ⟶ 541:
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}}==
Line 1,008 ⟶ 1,499:
 
=={{header|Perl}}==
Generates one tiling at random. To generate more during one run, change the "exit" to "return".
<syntaxhighlight lang="perl">use strict;
change the "exit" to "return".
<syntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # first open space version
use warnings;
use feature 'bitwise';
 
my $size = shift // 8;
Line 1,045 ⟶ 1,534:
find( $grid );
 
# looks for the first open space
sub find
{
Line 1,053 ⟶ 1,543:
my ($pattern, $pentomino, $letter) = @$_;
local $used{$letter} = 1;
$grid =~ /^[^ ]*\K$pattern/s and find( $grid ^. "\0" x $-[0] . $pentomino );
}
}</syntaxhighlight>
Line 1,692 ⟶ 2,182:
V Z Z Z W W Y T
V V V Z Y Y Y Y</pre>
 
=={{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|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-traititerate}}
<syntaxhighlight lang="ecmascriptwren">import "random" for Random
import "./traititerate" for Stepped
 
var F = [
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328102...352956"