生成循环以产生 4X4 骑士问题网络图的边

Question

我想简化以下代码中的大量边列表，但我不确定如何计算它们或在它们上生成循环。结果应该显示 4X4 棋盘骑士问题的网络图。下面的代码与以下内容一起运行，但不是很干净。请帮我创建一个循环来生成合法骑士移动方块之间的边。

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

Answer 1

由于我最初误读了这个问题，我开始真正地寻找路线，而不是仅仅标记每个方格的所有合法移动，因此下面实现了这两个。宏

\findtour{<x>}{<y>}{<m>}{<n>}

MxN从初始位置 开始在棋盘上寻找骑士巡游(x,y)。它首先尝试使用启发式算法（Warnsdorff）寻找巡游，这可能会失败，但速度相当快。如果启发式算法失败，则使用深度优先搜索算法。宏

\allmoves{<m>}{<n>}

显示MxN棋盘上所有可能的走法。

\allmoves{6}{6}

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

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

对于代码墙，我提前表示歉意。

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

Answer 2

一个稍微手动的有效移动检查器。它依赖于顶点的命名，并且不太灵活，但可以完成工作。以下是 5x5 的情况：

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

Answer 3

游戏有点晚了，不确定是否完全正确，但今天是缓慢的一天，所以......

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

Answer 4

由于最后 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)
}

以下工作：

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

由于列表中存在模式，如果有限，则可以使用以下方法减少数据负载

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