Knight's Tour on a Chessboard

Simulate a knight's tour in a recursive manner

Open in Cloud
Download Notebook

Here we use recursion coupled with a heuristic (Warnsdorff's rule) to determine a possible path for a knight on the chessboard with the constraint that it can visit all 8 x 8 positions only once during its journey.

Set up the chessboard and the associated configuration:

In[1]:=

knight=Rasterize[Style["♞",100],BackgroundNone];

In[2]:=

chessboard=Boole@NestList[RotateLeft,EvenQ@Range[8],7];grid=Array[List,{8,8}];gridindices=Flatten[grid,1];edges=Union[grid〚1〛,grid〚All,1〛,grid〚-1〛,grid〚All,8〛];step=Select[Permutations[{2,-1,-2,1},{2}],Total@#≠0&];nearestEdge=Nearest[edges];

Define a function to draw the chessboard and the knight:

In[3]:=

drawboard[pos_]:=ArrayPlot[chessboard,ColorRules{0White,1XYZColor[0,0,1,0.7]},Epilog(Inset[knight,pos-1,pos-1,1])];

Show the board with a knight at {3,4}:

In[4]:=

drawboard[{3,4}]

Out[4]=

Define the moveset of the knight on the chessboard:

In[5]:=

knightsMove[{row_,col_}]:=Intersection[gridindices,({row,col}+#)&/@step];

In[6]:=

breakTies[{pat:{_Integer,_Integer}}]:=pat;breakTies[{pat:Repeated[{_Integer,_Integer},{2,∞}]}]:=Part[{pat},RandomChoice@Flatten@Position[#,Min@#]&@(EuclideanDistance[First@nearestEdge[#],#]&/@{pat})];

In[7]:=

knightsTour[visited_,row_,col_]:=Module[{availableMoves,move},availableMoves=Complement[knightsMove[{row,col}],visited];move=breakTies[availableMoves];If[Length@visited<64,knightsTour[Join[visited,{{row,col}}],First@move,Last@move],visited]];

Simulate until a possible tour is found, i.e., the knight visits each position only once:

In[8]:=

path={};While[path==={},path=Cases[Table[knightsTour[{},i,j],{i,8},{j,8}],{patt:{_Integer,_Integer}..}{patt},∞]];path=RandomChoice@path;

In[9]:=

linepath=#-

&/@path;

Create a video of the tour:

In[10]:=

MapThread[Show[drawboard[#1],Graphics[{Red,#2}],ImageSizeSmall]&,{path,Table[Line@linepath〚1;;i〛,{i,Length@path}]}]//FrameListVideo[#,FrameRate15]&

Out[10]=

Related Symbols

Permutations

Publisher Information

Contributed by: Ali Hashmi, Wolfram Research