#### Howdy, Stranger!

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

# Knights Tour

edited January 12 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.x=sx
tab.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
``````

• 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.x=bx
tab.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.

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

• 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