#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Checkerboard puzzle

Mod
Posts: 9,260

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
end
end
w1=true
end

function touched(t)
if t.state==BEGAN then
if stop then
stop=false
elseif wait then
wait=false
removepiece()
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

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
``````

• Mod
Posts: 891

Nice Work! Thanks! @dave1707 - Am I the first, whose idea was to comment this good work?

• Posts: 256
This game looks good, but because I have i-phone it starts high along the y axis, is the a line I could change to lower the starting pt along the y axis ? And bring the boxes down along the y axis ?
• Mod
Posts: 9,260

@kendog400 Its not really a game, but just a program to solve a puzzle. It can be scaled down by using the scale command. Try putting scale(.3,.3) at the start of the draw function. Change the .3 to whatever value you need.

• Posts: 2,243

@dave1707 - that’s a very neat example of an approach to solve an old popular puzzle. I need to digest this to see how you have approached orientation of the pieces and placement.

I take it that you will find 4 orientation solutions for one placement solution, as the puzzle itself is a square.

• Mod
Posts: 9,260

@Bri_G For each solution with a specific orientation, there will be three other ones since the square can be rotated in three other positions. This uses a brute force method, so eventually it will find all of the solutions for all the orientations.

• edited July 2020 Posts: 2,243

@dave1707 - just thought, there will be 4 solutions in different square rotations and four mirror image rotations.

Do you account for them ?

• Mod
Posts: 9,260

@Bri_G I’m using the brute force method, so eventually I’ll be trying every combination of all the pieces. So it will find all the solutions in all the different rotations of the board. Every time I try a piece, if it doesn’t fit, I rotate it counter clockwise 90 degrees to see if it fits. If it does fit, then I’ll try other pieces in the next open squares. Eventually I’ll come back to the piece that fit, remove it, rotate it 90 degrees ccw, and see if it fits again. I’m not sure how many combinations there are. There are 12 pieces and 4 rotations of each piece. So I guess that’s equivalent to 48 pieces.

• Mod
Posts: 9,260

@Bri_G I ran my other program of this that just prints solutions and there were about 1,885 solutions and 97,538,378 tries before piece 1 had its first rotation. It immediately did another rotation because piece 1 doesn’t fit in the first square with rotation 2. So it went to it’s 3rd rotation.

• Posts: 256
I haven't figured this out yet, and I havent been able to rotate any of the pieces as of yet, but the PGM looks good. I changed the values in set-up f(x) / show...just so I could see the peices on the screen. Still I'm not able to post PGMs on the fourm so I snapped a screen shot for any one to take a peek..I think it's because I havent waited until the brute force has finished...The i-ph has a different screen resolution than the i-pad, so I'm constantly adjusting x & y axis values...