Pentomino tiling: Difference between revisions

=={{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>