Knights Tour

dave1707

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

dave1707

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

Bri_G

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

dave1707

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

RonJeffries

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

dave1707

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

RonJeffries

yes