Here a program that solves a checkerboard puzzle. There are 12 pieces that can be rotated, and when placed correctly would fit on an 8x8 checkerboard. I show the 12 pieces on the right of the 8x8 board. When the program is started (tap the screen) I place the pieces on the board. If a piece fits on the board, it’s matching piece on the right is colored white. If it’s not on the board, it shows its current color. If it’s color is flashing, it’s being moved on and off the board. The values below the board show how the pieces are placed on the board and their rotation position. If you really want to know their use, ask and I’ll post the answer. The try count
increments each time I try to place a piece on the board. The fit count
increments each time a piece fits in the next open spot and solutions
increments each time all 12 pieces fit. The program stops at a solution, just tap the screen to continue to the next solution. The list below are some of the solutions. I only did the first 2 solutions with this program. For the other solution values, I used a stripped down version that ran faster and just printed out the solutions. This program is too slow to find a lot of solutions, but I wrote it just for something to do.
Solutions at try count.
77566
77568
341780
359584
405551
407979
688578
displayMode(FULLSCREEN)
function setup()
fitcount,trycount,solution,nextopen=0,0,0,0
pieceoffset,size=1,40
col={color(255,0,0),color(0,255,0),color(0,0,255),color(255,255,0),
color(0,255,255),color(255,0,255),color(255,128,0),color(255,128,128),
color(128,128,255),color(128,128,128),color(128,64,64),color(255,0,128)}
show={vec2(500,900),vec2(500,780),vec2(500,700),vec2(500,580),
vec2(530,480),vec2(530,380),vec2(650,900),vec2(650,800),
vec2(650,700),vec2(650,600),vec2(650,500),vec2(650,380)}
used={0,0,0,0,0,0,0,0,0,0,0,0}
rot={0,0,0,0,0,0,0,0,0,0,0,0}
here={0,0,0,0,0,0,0,0,0,0,0,0}
board={88,88,88,88,88,88,88,88,88,88,88,00,00,00,00,00,00,00,00,88,
88,00,00,00,00,00,00,00,00,88,88,00,00,00,00,00,00,00,00,88,
88,00,00,00,00,00,00,00,00,88,88,00,00,00,00,00,00,00,00,88,
88,00,00,00,00,00,00,00,00,88,88,00,00,00,00,00,00,00,00,88,
88,00,00,00,00,00,00,00,00,88,88,88,88,88,88,88,88,88,88,88}
piece={
{{0,10,20,30,31,40,41},{0,1,7,8,9,10,11},{0,1,10,11,21,31,41},{0,1,2,3,4,10,11}},
{{0,1,10,11,12,13},{0,10,19,20,29,30},{0,1,2,3,12,13}, {0,1,10,11,20,30}},
{{0,10,20,30,31,32},{0,10,17,18,19,20},{0,1,2,12,22,32},{0,1,2,3,10,20}},
{{0,1,11,12,13,14},{0,10,20,29,30,39},{0,1,2,3,13,14},{0,9,10,19,29,39}},
{{0,10,20},{0,1,2},{0,10,20},{0,1,2}},
{{0,1,11},{0,1,10},{0,10,11},{0,9,10}},
{{0,1,2,3,4,14},{0,1,10,20,30,40},{0,10,11,12,13,14},{0,10,20,30,39,40}},
{{0,10,20,21,22},{0,10,18,19,20},{0,1,2,12,22},{0,1,2,10,20}},
{{0,1,2,10,11},{0,10,11,20,21},{0,1,9,10,11},{0,1,10,11,21}},
{{0,10,20,30,31,32},{0,10,17,18,19,20},{0,1,2,12,22,32},{0,1,2,3,10,20}},
{{0,10,20,30,40,41},{0,6,7,8,9,10},{0,1,11,21,31,41},{0,1,2,3,4,10}},
{{0,10,11,21,22},{0,9,10,18,19},{0,1,11,12,22},{0,1,9,10,19}}}
w1,stop=true,true
fill(255)
end
function draw()
background(33, 89, 104, 255)
drawboard()
printTotals()
showPieces()
solve()
end
function solve()
if stop or wait then
return
end
if w1 then
nextopen=nextboard()
nextpiece(pieceoffset,1)
w1,yy=false,true
end
while yy==true do
nextopen=nextboard()
if checkfit()==1 then
pieceoffset=pieceoffset+1
if pieceoffset>12 then
pieceoffset=12
solution=solution+1
wait=true
return
else
yy=false
end
else
addone()
end
end
w1=true
end
function touched(t)
if t.state==BEGAN then
if stop then
stop=false
elseif wait then
wait=false
removepiece()
addone()
end
end
end
function drawboard()
pushStyle()
local z,c=0,0
for y=10,1,-1 do
for x=1,10 do
z=z+1
c=board[z]
if c==0 then
fill(0)
elseif c==88 then
fill(64,64,64)
else
fill(col[c])
end
rect(30+x*size,360+y*size,size,size)
fill(0)
if c>0 and c<13 then
text(c,30+x*size+size/2,360+y*size+size/3)
end
end
end
popStyle()
end
function showPieces()
pushStyle()
rectMode(CENTER)
fontSize(10)
local rr=rect local tt=text local pp=piece local v=0
local tab={0,0,0,0,0,0,0,0,0,0,0,0}
for z=1,12 do
v=used[z]
if v>0 then
tab[v]=1
else
tab[v]=0
end
end
for z=1,#show do
for w=1,#pp[z][1] do
fill(col[z])
if tab[z]>0 then
fill(255)
end
v=pp[z][1][w]
rr(show[z].x+(v%10)*20,show[z].y-(v//10)*20,20,20)
fill(0)
tt(z,show[z].x+(v%10)*20,show[z].y-(v//10)*20)
end
end
popStyle()
end
function printTotals()
pushStyle()
textMode(CORNER)
font("Courier-Bold")
text("used ",50,300)
text("rotate ",50,270)
for z=1,12 do
text(used[z],100+z*30,300)
text(rot[z],100+z*30,270)
end
text("try count "..trycount,125,210)
text("fit count "..fitcount,125,180)
text("solutions "..solution,125,150)
popStyle()
end
function nextboard()
for z=1,100 do
if board[z]==0 then
return(z)
end
end
return(0)
end
function nextpiece(curr,val)
local loop,dup=true,0
used[curr]=val rot[curr]=1
while loop do
dup=0
for z=1,(curr-1) do
if used[curr]==used[z] then
dup=1
used[curr]=used[curr]+1
break
end
end
if dup==0 then
loop=false
end
end
return(0)
end
function checkfit()
local pp=piece local b1=nextopen local p1=used[pieceoffset]
local p2=rot[pieceoffset] local offset
trycount=trycount+1
for z=1,#pp[p1][p2] do
offset=b1+pp[p1][p2][z]
if board[offset] ~= 0 then
return(0) -- wont fit
end
end
for z=1,#pp[p1][p2] do
offset=b1+pp[p1][p2][z]
board[offset]=p1
end
here[pieceoffset]=b1
fitcount=fitcount+1
return(1) -- fit ok
end
function pieceused(val)
for z=1,12 do
if used[z]==val then
return(1)
end
end
return(0)
end
function removepiece()
local pp=piece local b1=here[pieceoffset]
local p1=used[pieceoffset] local p2=rot[pieceoffset]
for z=1,#pp[p1][p2] do
offset=b1+pp[p1][p2][z]
board[offset]=0
end
end
function addone()
local r,lp,u
while 1 do
r=rot[pieceoffset]+1
if r<5 then
rot[pieceoffset]=r
return
end
lp=true
while lp do
u=used[pieceoffset]+1
if u<13 then
if pieceused(u)==0 then
used[pieceoffset]=u
rot[pieceoffset]=1
return
else
used[pieceoffset]=u
end
else
used[pieceoffset]=0
rot[pieceoffset]=0
pieceoffset=pieceoffset-1
removepiece()
lp=false
if pieceoffset==0 then
exit()
end
end
end
end
end