Pentomino tiling: Difference between revisions
Added 11l
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Alextretyak (talk | contribs) (Added 11l) |
||
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|C sharp|C#}}==
| |||