13

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.

enter image description here

\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}
1
  • 3
    It is always useful to provide a minimal working or non-working example, with \begin and \end{document}.
    – Ahmed Musa
    Feb 11, 2013 at 1:41

5 Answers 5

12

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}

enter image description here

\findtour{3}{3}{6}{6}

enter image description here

\findtour{1}{1}{6}{4}

enter image description here

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}
2
  • Now I know how percuße felt when he responded to my answer. Outstanding. Feb 12, 2013 at 7:02
  • Yes. Very impressive.
    – ruya
    Feb 14, 2013 at 4:26
10

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}

enter image description here

9

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}

enter image description here

1
  • I feel a sudden urge to delete my answer. Very nice.
    – percusse
    Feb 11, 2013 at 16:51
6

How about

\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)}
3
  • 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, 2013 at 1:45
  • Yes, @cmhughes, I was looking for the moves to be calculated. Though, this cleans things up considerably.
    – ruya
    Feb 11, 2013 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, 2013 at 2:28
6

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}

enter image description here

7
  • Is loops included in CTAN?
    – user11232
    Feb 11, 2013 at 2:21
  • 3
    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, 2013 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, 2013 at 12:43
  • @HarishKumar: Yes. tex.ac.uk/tex-archive/help/Catalogue/entries/loops.html.
    – Ahmed Musa
    Feb 11, 2013 at 13:27
  • Just add a simple % after the last 23 and all works. Feb 11, 2013 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .