Pentomino tiling: Difference between revisions
→{{header|Phix}}
(Added Go) |
|||
Line 745:
P P X X X Y Z -
P P P X Y Y Y Y
</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.
<lang Phix>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 shape = {}
integer letter
for orientation=0 to 7 do
sequence this = {}
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
this &= {r-fr,c-fc}
end if
end if
end for
end for
if not find(this,shape) then
shape = append(shape,this)
end if
end for
res = append(res,{letter&"",shape})
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))
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
grid[r][c] = ch
for i=1 to length(o) by 2 do
grid[r+o[i]][c+o[i+1]] = ch
end for
return true
end function
procedure un_place(sequence o, integer r, c)
grid[r][c] = ' '
for i=1 to length(o) by 2 do
grid[r+o[i]][c+o[i+1]] = ' '
end for
end procedure
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
un_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 = 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()</lang>
{{out}}
<pre>
FFPPPVVV
YFFPPX-V
YFUUXXXV
YYU-ZX-I
YTUUZZZI
-TTTWWZI
LTNNNWWI
LLLLNNWI
</pre>
| |||