# Generating loops to produce edges for network graph of 4X4 knights problem

I want to simplify the huge list of edges in the following code, but I'm not sure how to calculate them or produce the loop over them. The result should show the network graph of the 4X4 chess board knight problem. The below code functions with the following includes, but it's not very clean. Please help me to create a loop to produce the edges between legal knight move squares.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{arrows, shapes, backgrounds,fit}
\usepackage{tkz-graph}
\begin{document}
\begin{tikzpicture}
\SetVertexNormal[Shape = rectangle, FillColor  = lightgray, LineWidth = 2pt]
\SetUpEdge[lw = 1.5pt, color = black]
\foreach \y in {1,2,3,4}
\foreach \x / \a in {1/a,2/b,3/c,4/d}
{\Vertex[L=\y \a,x=2*\x,y=2*\y]{\x\y}}

\Edge(11)(23)
\Edge(11)(32)
\Edge(14)(33)
\Edge(14)(22)
\Edge(41)(33)
\Edge(41)(22)
\Edge(44)(32)
\Edge(44)(23)
\Edge(21)(33)
\Edge(21)(42)
\Edge(21)(13)
\Edge(24)(12)
\Edge(24)(32)
\Edge(24)(43)
\Edge(31)(12)
\Edge(31)(23)
\Edge(31)(43)
\Edge(34)(13)
\Edge(34)(22)
\Edge(34)(42)
\Edge(12)(33)
\Edge(22)(43)
\Edge(32)(13)
\Edge(42)(23)
\end{tikzpicture}
\end{document}

-
It is always useful to provide a minimal working or non-working example, with \begin and \end{document}. –  Ahmed Musa Feb 11 '13 at 1:41
Thanks @AhmedMusa! I'll keep that in mind. –  ruya Feb 11 '13 at 2:26

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

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
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}

-
Now I know how percuße felt when he responded to my answer. Outstanding. –  Mark Wibrow Feb 12 '13 at 7:02
Yes. Very impressive. –  ruya Feb 14 '13 at 4:26

A slightly manual valid move checker. It relies on the naming of the vertices and also not so flexible as it is but does the job. Here is the 5x5 case:

\documentclass{article}
\usepackage{tkz-graph}
\newif\ifLmovevalid
\Lmovevalidfalse
\makeatletter
\newcommand{\Lmove}[1]{\pgfutil@ifundefined{pgf@sh@ns@#1}{\Lmovevalidfalse}{\Lmovevalidtrue}}
\makeatother
\begin{document}
\begin{tikzpicture}
\SetVertexNormal[Shape = rectangle, FillColor  = lightgray, LineWidth = 2pt]
\SetUpEdge[lw = 1.5pt, color = black]
\foreach \y in {1,2,3,4,5}
\foreach \x / \a in {1/a,2/b,3/c,4/d,5/e}
{\Vertex[L=\y \a,x=2*\x,y=2*\y]{\x\y}}

\foreach \x in {1,...,5}{
\foreach \y in {1,...,5}{
\edef\vertnamea{\number\numexpr\x+2\relax\number\numexpr\y+1\relax}
\edef\vertnameb{\number\numexpr\x-2\relax\number\numexpr\y+1\relax}
\edef\vertnamec{\number\numexpr\x+1\relax\number\numexpr\y+2\relax}
\edef\vertnamed{\number\numexpr\x-1\relax\number\numexpr\y+2\relax}
\foreach \i in {a,...,d}{
\Lmove{\csname vertname\i\endcsname}
\ifLmovevalid
\Edge(\x\y)(\csname vertname\i\endcsname)
\Lmovevalidfalse
\fi
}
}
}
\end{tikzpicture}
\end{document}


-

A little late to the game, and not sure if it's exactly right, but it's a slow day so...

\documentclass{standalone}
\usepackage{tikz}
\makeatletter
\let\pgfforalpha=\pgffor@alpha
\makeatother
\begin{document}
\pgfdeclarelayer{background}%
\pgfsetlayers{background,main}%

\newcount\size
\size=4

\tikzset{
declare function={
inrange(\v,\l,\h)=(\v >= \l) && (\v <= \h);
},
knights moves/.style={
insert path={ ++(-#1/2,-#1/2) rectangle ++(#1,#1) },
path picture={
\tikzset{shift=(path picture bounding box.south west)}
\size=#1%
\foreach \x [count=\j from 0] in {a,...,\pgfforalpha{\size}}
\foreach \y  [count=\i from 0] in {1,...,\size}
\node [vertex/.try] at (\j+0.5, \i+0.5) (\y\x) {\y\x};
%
\begin{pgfonlayer}{background}
\foreach \x [count=\j from 1] in {a,...,\pgfforalpha{\size}}
\foreach \y  [count=\i from 1] in {1,...,\size}
\foreach \mx/\my [evaluate={
\jj=int(\j+\mx);
\ii=int(\i+\my);
\v=inrange(\jj, 1, \size) && inrange(\ii, 1, \size);}
] in  {1/2,2/1,1/-2,-2/1}
{
\ifnum\v=1
\draw [edge/.try] (\y\x) -- (\ii\pgfforalpha{\jj});
\fi
}
\end{pgfonlayer}
}
}
}

\begin{tikzpicture}[
x=1.25cm,
y=1.25cm,
vertex/.style={
draw=black,
very thick,
fill=gray!25,
font=\footnotesize,
minimum size=0.5cm,
},
edge/.style={
draw=black,
very thick
},
]

\path (0,0) [knights moves=3];

\path (6, 0) [knights moves=4];

\path (6,-6) [knights moves=5];

\path (0,-6) [knights moves=6];

\end{tikzpicture}

\end{document}


-
I feel a sudden urge to delete my answer. Very nice. –  percusse Feb 11 '13 at 16:51

\foreach \x/\y in {11/23,11/32,14/33,14/22,
41/33,41/22,44/32,44/23,
21/33,21/42,21/13,24/12,
24/32,24/43,31/12,31/23,
31/43,34/13,34/22,34/42,
12/33,22/43,32/13,42/23}
{\Edge(\x)(\y)}

-
or do you mean something that calculates the legal moves for you? That could surely be done, but at higher computational expense... –  cmhughes Feb 11 '13 at 1:45
Yes, @cmhughes, I was looking for the moves to be calculated. Though, this cleans things up considerably. –  ruya Feb 11 '13 at 2:27
@ruya I'll look into a way to compute the moves- should be possible using a few loops and ifs... –  cmhughes Feb 11 '13 at 2:28

The following fails because of the spurious space after the last 23:

\foreach \x/\y in {
11/23,11/32,14/33,14/22,
41/33,41/22,44/32,44/23,
21/33,21/42,21/13,24/12,
24/32,24/43,31/12,31/23,
31/43,34/13,34/22,34/42,
12/33,22/43,32/13,42/23
}{
\Edge(\x)(\y)
}


The following works:

\usepackage{loops}

\newforeach \x/\y in {
11/23,11/32,14/33,14/22,
41/33,41/22,44/32,44/23,
21/33,21/42,21/13,24/12,
24/32,24/43,31/12,31/23,
31/43,34/13,34/22,34/42,
12/33,22/43,32/13,42/23
}{
\Edge(\x)(\y)
}


Since there is a pattern in your list, if limited, you can reduce the data payload by using

\documentclass{article}
\usepackage{tikz,loops}
\usetikzlibrary{arrows,shapes,backgrounds,fit}
\usepackage{tkz-graph}

\begin{document}
\begin{tikzpicture}
\SetVertexNormal[Shape=rectangle,FillColor=lightgray,LineWidth=2pt]
\SetUpEdge[lw=1.5pt,color=black]
\foreach \y in {1,2,3,4} {
\foreach \x / \a in {1/a,2/b,3/c,4/d} {
\Vertex[L=\y \a,x=2*\x,y=2*\y]{\x\y}
}
}
% \foreach will not work in the following because, for an empty component of a list
% item, it enforces inheritance from the preceding component. If you want
% \newforeach to enforce such inheritance, you should call the option 'inherit'.
\newforeach \x/\y/\z/\s in {
11/23/32,14/33/22,41/33/22,44/32/23,21/33/42/13,
24/12/32/43,31/12/23/43,34/13/22/42,12/33,22/43,
32/13,42/23
}{
\Edge(\x)(\y)
\ifx\z\empty\else\Edge(\x)(\z)\fi
\ifx\s\empty\else\Edge(\x)(\s)\fi
}
\end{tikzpicture}
\end{document}


-
Is loops included in CTAN? –  Harish Kumar Feb 11 '13 at 2:21
In my opinion, this is a low-quality answer and should rather be a comment to cmhughes' answer. Why? It doesn't really add value, and somehow seems to promote your loops package more than anything else... –  Werner Feb 11 '13 at 3:03
@Werner: If you believe your comment is fair and unbiased, I am OK with it. Some of us are too old for pranks. No one pays a package author. I added a comment to cmhughes' answer but he quickly deleted it. –  Ahmed Musa Feb 11 '13 at 12:43
@HarishKumar: Yes. tex.ac.uk/tex-archive/help/Catalogue/entries/loops.html. –  Ahmed Musa Feb 11 '13 at 13:27
Just add a simple % after the last 23 and all works. –  Qrrbrbirlbel Feb 11 '13 at 15:04