Howdy, Stranger!

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

Knights Tour

dave1707dave1707 Mod
edited January 12 in Code Sharing Posts: 8,723

Here’s another one of my useless programs. I normally write code while I’m watching TV for something else to do. On Saturday and Sunday I spent both days watching the football playoffs all day. This code tries to solve solutions for the knights tour. That’s the chess piece (knight) moving on a checker board so it makes a valid move and lands on each square without landing on a previously occupied square. There are a lot of solutions and even more paths that aren’t. So here’s a visual of the knights moves. A knight can make 8 valid moves from a square. I try a move and if it’s lands on a square already occupied, I try the next move going in a counter clockwise direction. If after the 8 tries, I’ll backup to the previous square and try the next move. The program will pause when a solution is found or you can tap the screen to pause it. The first one is at 54,482,161 tries. When the program starts, it makes 1 try per draw cycle. Opening up the print pane, you can move the slider to increase it to 1,000,000 moves per draw cycle. I show different counts as the program runs. As I said, I wrote this while watching TV, so it might not display correctly on every device. This only starts at the lower left square. If you have questions, just ask.

viewer.mode=FULLSCREEN

function setup()
    sx,sy=1,1
    parameter.integer("tries",0,6) 
    piecePos=1
    pieceMove={vec2(-1,2),vec2(-2,1),vec2(-2,-1),vec2(-1,-2),
    vec2(1,-2),vec2(2,-1),vec2(2,1),vec2(1,2)}
    rectMode(CENTER)
    tab={}
    board={}
    for x=1,8 do
        board[x]={}
        for y=1,8 do
            board[x][y]=0
        end
    end
    for z=1,64 do
        table.insert(tab,piece(vec2(0,0),z))
    end
    size=80
    tab[1].x=sx
    tab[1].y=sy
    board[sx][sy]=1
    count=0
    high=0
    solutions=0
end

function draw()
    background(0)
    drawBoard()
    for z=1,10^tries do
        tab[piecePos]:next()
    end
    if piecePos>high then
        high=piecePos
    end
    fontSize(20)
    fill(255)
    text("Rotations",WIDTH/2,HEIGHT-20)
    for a,b in pairs(tab) do
        text(string.format("%d",b.rot),a*12+20,HEIGHT-50)
    end
    text("Nbr of Tries  "..count,WIDTH-150,HEIGHT-80)
    text("Current Pos "..piecePos,WIDTH-150,HEIGHT-110)
    text("Highest Pos "..high,WIDTH-150,HEIGHT-140)
    text("Solutions   "..solutions,WIDTH-150,HEIGHT-170)
    text("+ 1 + 8 +",WIDTH-150,HEIGHT-200)
    text("2 + + + 7",WIDTH-150,HEIGHT-220)
    text("+ + O + +",WIDTH-150,HEIGHT-240)
    text("3 + + + 6",WIDTH-150,HEIGHT-260)
    text("+ 4 + 5 +",WIDTH-150,HEIGHT-280)    
    text("Tries per draw-cycle "..10^tries,WIDTH/2,HEIGHT-100)
    if wait then
        text("PAUSED",WIDTH/2,HEIGHT-130)
    end
    text("3 solutions at ",WIDTH-150,HEIGHT-310)
    text("54,482,161",WIDTH-150,HEIGHT-330)
    text("57,053,315",WIDTH-150,HEIGHT-350)
    text("57,059,627",WIDTH-150,HEIGHT-370)  
end

function touched(t)
    if t.state==BEGAN then
        wait=not wait
        if high==64 then
            high=0
        end
    end    
end

function drawBoard()
    strokeWidth(1)
    fill(255)
    if wait then
        fill(0, 201, 255)
    end
    for x=1,8 do
        for y=1,8 do
            rect(x*size,y*size,size,size)
        end
    end
    for z=1,piecePos do
        tab[z]:draw()
    end
end

piece = class()

function piece:init(pos,val)
    self.x=pos.x
    self.y=pos.y
    self.rot=0
    self.val=val
end

function piece:draw()
    stroke(0)
    strokeWidth(4)
    for z=2,piecePos do
        line(tab[z].x*size,tab[z].y*size,tab[z-1].x*size,tab[z-1].y*size)
    end
    fontSize(60)
    fill(255,0,0)
    if self.x>0 then
        text(self.val,self.x*size,self.y*size)
    end
end

function piece:next()
    if wait then
        return
    end
    count=count+1
    while true do
        self.rot=self.rot+1
        if self.rot>8 then
            self.rot=0
            board[self.x][self.y]=0
            piecePos=piecePos-1
            return
        else
            tx=tab[piecePos].x+pieceMove[self.rot].x
            ty=tab[piecePos].y+pieceMove[self.rot].y
            if tx<1 or ty<1 or tx>8 or ty>8 or board[tx][ty]~=0 then
                --
            else
                tab[piecePos+1].x=tx
                tab[piecePos+1].y=ty
                board[tx][ty]=piecePos+1
                piecePos=piecePos+1
                if piecePos==64 then
                    wait=true
                    solutions=solutions+1
                end
                return
            end
        end
    end    
end

Comments

  • dave1707dave1707 Mod
    edited January 14 Posts: 8,723

    Here’s an updated version. This version lets you select a starting square. Just tap any square and tap outside the board to un-pause the screen. There is also a Boolean selector in the print panel to allow the program to update the found solutions count without pausing. The slider is still there to allow you to select up to 1,000,000 iterations per draw cycle. The higher the iterations, the lower the frames per second. I show the average FPS to see what’s happening. You can still pause/unpause the screen at anytime by tapping outside the board area. If you select the upper right square, that has a lot of solutions. 230 solutions below 30,000,000 tries and it increases a lot after that.

    PS. Added a single step option. Slide the Boolean switch to on and then tap outside of the board for each single step move.

    viewer.mode=FULLSCREEN
    
    function setup()
        wait=true
        bx,by=1,1
        pieceMove={vec2(-1,2),vec2(-2,1),vec2(-2,-1),vec2(-1,-2),
                    vec2(1,-2),vec2(2,-1),vec2(2,1),vec2(1,2)}
        rectMode(CENTER)
        setup1()
    end
    
    function setup1()
        parameter.integer("tries",0,6,setZero)
        parameter.boolean("pause",true)
        parameter.boolean("singlestep")
        tab={}
        board={}
        piecePos=1
        for x=1,8 do
            board[x]={}
            for y=1,8 do
                board[x][y]=0
            end
        end
        for z=1,64 do
            table.insert(tab,piece(vec2(0,0),z))
        end
        size=80
        tab[1].x=bx
        tab[1].y=by
        board[bx][by]=1
        count=0
        high=0
        low=64
        solutions=0
        tot=0
        cnt=0
        avgFPS=0
    end
    
    function draw()
        background(0)
        process()
        drawBoard()
        showText()
    end
    
    function touched(t)
        if t.state==BEGAN then
            wait=not wait
            if high==64 then
                high=0
            end
            bx=(t.x-size/2)//size+1
            by=(t.y-size/2)//size+1
            if bx>0 and bx<9 and by>0 and by<9 then
                setup1()
                wait=true             
            end
        end    
    end
    
    function process()
        if not wait then
            cnt=cnt+1
            tot=tot+DeltaTime
            avgFPS=cnt/tot
            for z=1,10^tries do
                tab[piecePos]:next()
            end
            if piecePos>high then
                high=piecePos
            end
        end
    end
    
    function setZero()
        cnt,tot=0,0
    end
    
    function drawBoard()
        strokeWidth(1)
        fill(255)
        if wait or singlestep then
            fill(131, 176, 225)
        end
        for x=1,8 do
            for y=1,8 do
                rect(x*size,y*size,size,size)
            end
        end
        for z=1,piecePos do
            tab[z]:draw(z)
        end
    end
    
    function showText()
        fill(255)
        fontSize(17)
        text("Rotations",WIDTH/2,HEIGHT*.98)
        for a,b in pairs(tab) do
            text(string.format("%d",b.rot),a*12+20,HEIGHT*.96)
        end
        text("Average FPS   "..avgFPS//1,WIDTH*.2,HEIGHT*.93)
        text("Current Pos "..piecePos,WIDTH*.2,HEIGHT*.9)
        text("Highest Pos "..high,WIDTH*.2,HEIGHT*.87)
        text("Lowest Pos  "..low,WIDTH*.2,HEIGHT*.84)
        text("Tries per draw-cycle   "..10^tries,WIDTH*.6,HEIGHT*.93)
        text("Number of Tries  "..count,WIDTH*.6,HEIGHT*.9)
        text("Solutions found   "..solutions,WIDTH*.6,HEIGHT*.87)
        if singlestep then
            text("SINGLE STEP",WIDTH*.6,HEIGHT*.84)
        elseif wait then
            text("PAUSED",WIDTH*.6,HEIGHT*.84)
        end
    end
    
    piece = class()
    
    function piece:init(pos,val)
        self.x=pos.x
        self.y=pos.y
        self.rot=0
        self.val=val
    end
    
    function piece:draw(z)
        stroke(0)
        strokeWidth(2)
        if z>1 then
            line(tab[z].x*size,tab[z].y*size,tab[z-1].x*size,tab[z-1].y*size)
        end
        fontSize(30)
        fill(255,0,0)
        text(self.val,self.x*size,self.y*size)
    end
    
    function piece:next()
        if wait then
            return
        end
        count=count+1
        while true do
            self.rot=self.rot+1
            if self.rot>8 then
                self.rot=0
                board[self.x][self.y]=0
                piecePos=piecePos-1
                if piecePos<low then
                    low=piecePos
                end
                if singlestep then
                    wait=true
                end
                return
            else
                local tx=tab[piecePos].x+pieceMove[self.rot].x
                local ty=tab[piecePos].y+pieceMove[self.rot].y
                if tx<1 or ty<1 or tx>8 or ty>8 or board[tx][ty]~=0 then
                    --
                else
                    tab[piecePos+1].x=tx
                    tab[piecePos+1].y=ty
                    board[tx][ty]=piecePos+1
                    piecePos=piecePos+1
                    if piecePos==64 then
                        if pause then
                            wait=true
                        end
                        solutions=solutions+1
                    end
                    if singlestep then
                        wait=true
                    end
                    return
                end
            end
        end    
    end
    
    
  • Posts: 1,898

    @dave1707 - sorry for the delay in posting very busy at moment. Thanks for posting this, I like to see logical meticulous approaches to problems - mainly because I’m personally not very organised. These are good examples of approach to a problem.

    Might have an interesting issue for you to try, when I get round to finishing my current fixations. Not sure it’s something Lua can deal with. Don’t hold your breath though.

  • dave1707dave1707 Mod
    Posts: 8,723

    @Bri_G I like writing programs that give a visual while solving an ongoing problem. It’s a useless program other than giving me something to write. Even after writing some programs, I like to go back and see if there’s anyway to make it faster, smaller, or add other options to make it more interesting. I enjoyed the Beermat problem you posted back in Nov 2019. That was a fun problem to solve.

  • Posts: 787

    there is a heuristic in knight's tour: try moves in order of fewest next options to most.

  • dave1707dave1707 Mod
    Posts: 8,723

    @RonJeffries I looked at a lot of the Knights Tour info on Google, and saw various ways that solutions were found. I wasn’t trying to do anything like that, just to write something that would eventually find a solution. It was really just something to code. There are so many combinations of solutions, that even the fastest computers would take a long time to find them. I find it interesting to just watch as different paths are drawn and then backed out because of dead ends. It almost like watching a mouse trying to find a piece of cheese in a maze.

  • Posts: 787

    yes

Sign In or Register to comment.