Howdy, Stranger!

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

Checkerboard puzzle

dave1707dave1707 Mod
in Code Sharing Posts: 8,505

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

Comments

  • AnatolyAnatoly Mod
    Posts: 889

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

  • Posts: 199
    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 ?
  • dave1707dave1707 Mod
    Posts: 8,505

    @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: 1,769

    @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.

  • dave1707dave1707 Mod
    Posts: 8,505

    @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 20 Posts: 1,769

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

    Do you account for them ?

  • dave1707dave1707 Mod
    Posts: 8,505

    @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.

  • dave1707dave1707 Mod
    Posts: 8,505

    @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: 199
    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...
Sign In or Register to comment.