Since I misread the question initially, I got going on actually finding the tour rather than just marking all legal moves from each square so the following implements both. The macro
\findtour{<x>}{<y>}{<m>}{<n>}
Finds a Knight's Tour on an MxN
board from initial position (x,y)
. It first attempts to find the tour using a heuristic (Warnsdorff) that may fail but is quite fast. If the heuristic fails, then a depth first search algorithm is used. The macro
\allmoves{<m>}{<n>}
Shows all possible moves on an MxN
board.
\allmoves{6}{6}
\findtour{3}{3}{6}{6}
\findtour{1}{1}{6}{4}
Sorry in advance for the wall of code.
\documentclass{article}
\usepackage{luacode}
\usepackage{tikz}
\usetikzlibrary{arrows, shapes, backgrounds,fit}
\usepackage{tkz-graph}
\begin{luacode*}
-- legal moves from a square
local moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,-2},{-2,-1},{-2,1},{-1,2} }
-- table to hold moves list
local lst = {}
-- table for the 2x2 array
local board = {}
-- boolean to switch methods if the heuristic fails
warnsdorffFail = false
-- generates a new board
local function newboard(M,N)
for i = 1, M do
board[i]={}
for j = 1, N do
board[i][j]=0
end
end
end
--[[ Warnsdorff heuristic functions --]]
-- check if move is within bounds of board and to an unvisited square
local function checkmove(xpos,ypos,M,N)
if xpos<=M and xpos>0 and ypos<=N and ypos>0 and board[xpos][ypos]==0 then
return true
end
end
-- determine how many valid moves are available from given square
local function accessible(xpos,ypos,M,N)
local accessible = 0
for i = 1,8 do
if checkmove(xpos+moves[i][1],ypos+moves[i][2],M,N) then
accessible = accessible + 1
end
end
return accessible
end
-- move to the square that results in the fewest available moves
-- this is the "Warnsdorff heuristic"
local function getmove(move,M,N)
xposition = move[1]
yposition = move[2]
local access = 8
for i = 1, 8 do
local newx = xposition + moves[i][1]
local newy = yposition + moves[i][2]
newaccess = accessible(newx,newy,M,N)
if checkmove(newx,newy,M,N) and newaccess < access then
move[1] = newx
move[2] = newy
access = newaccess
end
end
end
--[[ DFS + Backtracing method functions (cribbed from http://rosettacode.org/wiki/Knight's_tour#Lua --]]
--[[
board[x][y] counts number (8 possible) of moves that have been attempted
board[x][y]>=8 --> all moves have been tried
board[x][y]==0 --> fresh square
--]]
local function goodmove( board, x, y, M, N )
if board[x][y] >= 8 then return false end
local new_x, new_y = x + moves[board[x][y]+1][1], y + moves[board[x][y]+1][2]
if new_x >= 1 and new_x <= M and new_y >= 1 and new_y <= N and board[new_x][new_y] == 0 then return true end
return false
end
-- builds list of moves
local function dfsBuildList(initx,inity,M,N)
lst[1] = {initx,inity}
local x = initx
local y = inity
repeat
if goodmove( board, x, y, M, N ) then
-- if goodmove, then mark as tried
board[x][y] = board[x][y] + 1
-- move to new position
x, y = x+moves[board[x][y]][1], y+moves[board[x][y]][2]
-- and add new position to list of squares
lst[#lst+1] = { x, y }
else
-- if the move is bad, check whether it is last possible move from square
if board[x][y] >= 8 then
-- if so, then reset moves tries from square
board[x][y] = 0
-- last square added to list of moves leads to no solution so delete
lst[#lst] = nil
-- if we've backtracked to the start then there's no solution
if #lst == 0 then
print("****The dfs algorithm resulted in no solution****")
break
end
-- if not, then move to previous position and repeat
x, y = lst[#lst][1], lst[#lst][2]
end
-- if we haven't used all moves then try the next
board[x][y] = board[x][y] + 1
end
until #lst == N*M
end
local function printtour(M,N)
tex.print("\\begin{tikzpicture}")
tex.print("\\SetVertexNormal[Shape = circle, FillColor = lightgray, LineWidth = 2pt]")
tex.print("\\SetUpEdge[style={->},lw = 1.5pt, color = black]")
for i = 1, M do
for j = 1, N do
tex.sprint("\\Vertex[L="..i.."-"..j..",x=1.5*"..i..",y=1.5*"..j.."]{"..i..j.."}")
end
end
tex.sprint("\\AddVertexColor{green}{"..lst[1][1]..lst[1][2].."}")
tex.sprint("\\AddVertexColor{red}{"..lst[#lst][1]..lst[#lst][2].."}")
for i = 1,#lst-1 do
tex.print("\\Edge("..lst[i][1]..lst[i][2]..")("..lst[i+1][1]..lst[i+1][2]..")")
end
tex.print("\\end{tikzpicture}")
end
function findtour(initx,inity,M,N)
lst = {}
local move = {}
M = M or 8
N = N or 8
newboard(M,N)
-- add initial pos to list of moves and mark as visited
lst[1]={initx,inity}
local xposition = initx
local yposition = inity
board[xposition][yposition] = 1
-- each iteration should produce a legal move,
-- so produce M*N-1 of them to complete the tour
for i = 1, M*N-1 do
move[1] = xposition
move[2] = yposition
-- get next position according to heuristic
getmove(move,M,N)
-- update coords and mark as visited
xposition = move[1]
yposition = move[2]
board[xposition][yposition] = 1
-- add to list
lst[i+1]={move[1],move[2]}
-- if sam pos appears consecutively, then the heuristic has failed
if lst[i][1]==move[1] and lst[i][2]==move[2] then
print("****The Warnsdorff heuristic resulted in no solution****")
warnsdorffFail = true
break
end
end
if warnsdorffFail then
lst = {}
newboard(M,N)
dfsBuildList(initx,inity,M,N)
end
printtour(M,N)
end
function allmoves(M,N)
for i = 1, M do
board[i]={}
for j = 1, N do
board[i][j]=moves
end
end
tex.print("\\begin{tikzpicture}")
tex.print("\\SetVertexNormal[Shape = circle, FillColor = lightgray, LineWidth = 2pt]")
tex.print("\\SetUpEdge[lw = 1.5pt, color = black]")
for i = 1, M do
for j = 1, N do
tex.sprint("\\Vertex[L="..i.."-"..j..",x=1.5*"..i..",y=1.5*"..j.."]{"..i..j.."}")
end
end
for i = 1, M do
for j = 1, N do
for k,v in pairs(board[i][j]) do
if i+v[1]<=M and i+v[1]>0 and j+v[2]<=N and j+v[2]>0 then
tex.print("\\Edge("..i..j..")("..i+v[1]..j+v[2]..")")
board[i+v[1]][j+v[2]][9-k]=nil
end
end
end
end
tex.print("\\end{tikzpicture}")
moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,-2},{-2,-1},{-2,1},{-1,2} }
end
\end{luacode*}
\def\allmoves#1#2{\directlua{allmoves(#1,#2)}}
\def\findtour#1#2#3#4{\directlua{findtour(#1,#2,#3,#4)}}
\begin{document}
\allmoves{6}{6}
\findtour{3}{3}{6}{6}
\findtour{1}{1}{6}{4}
\end{document}
\begin
and\end{document}
.