New Knight's Tour.

Yuya Kakoi,Naoki Saida,Kazuki Takeshima,Yoshiaki Ohishi, Hiroshi Matsui,Toshiyuki Yamauchi, Takashi Kajimoto, Kanta Yoza, Akihiro Hyogu, Yuta Nakagawa, Naoyuki Totani and Ryohei Miyadera
miyadera1272000@yahoo.co.jp

Traditionally the Knight's Tour consists of moving a knight on a chessboard.The knight is placed on the empty chessboard and,moving by the rules of chess,must visit each square exactly once.

In our new Knight's tour we are going to use the following boards instead of a chessboard.

Problem 1. How can the knight visit each square on this board exactly once?

An answer to Problem 1.

You can make a beautiful graph from this board of the Knight's Tour.

The above board consists of 44 squares. We represents these 44 squares by 44 vertexes. We connect corresponding two vertexes by an edge if and only if the Knight can go from one square to another directly. We color a vertex with yellow and an edge with 
blue. With a background of black color the graph looks quite beautiful.

This problem is equivalent to finding a Hamiltonian path of the graph made by the board. If the final position is a knight's move away from the first position, we call the tour re-entrant. The tour that is re-entrant is a Hamiltonian circuit.

Remark. This kind of graphs are already studied for the traditional Knight's Tour. Please look for Knight's Tour in MathWorld.

http: // 
      mathworld . wolfram . com/KnightsTourGraph . html

You can find beautiful graphs that the authors made in MathArt published by the Mathematical Institute, Belgrade, Yugoslavia.

http: // www . mi . sanu . ac . yu/vismath/
          miyadera2007knight/graph . html

We are the first people who began to look for variants of Knight's tour that present us beautiful graphs.

How we can make board, boardnumbers and the graph using Mathematica.

Once you make a variant of knight's tour by using a paper and a pencil, then you can represent the solution of the problem as a matrix.

For example the above problem can be represented by the following matrix.

ohishi=(({{0, 0, 23, 0, 0, 0, 21, 0, 0}, {0, 0, 0, 19, 22, 17, 0, 0, 0}, {29, 0, 0, 24, 0, 20, 0, 0, 15}, {0, 25, 28, 0, 18, 0, 16, 11, 0}, {0, 30, 0, 26, 0, 10, 0, 14, 0}, {0, 27, 32, 0, 6, 0, 12, 9, 0}, {31, 0, 0, 4, 0, 8, 0, 0, 13}, {0, 0, 0, 7, 2, 5, 0, 0, 0}, {0, 0, 3, 0, 0, 0, 1, 0, 0}}));

<<DiscreteMath`Combinatorica` (*It is essential to load this package before you use the following functions.*)

board[ma_] := 
      Block[{mm = ma, aa}, aa = Transpose[mm]; 
        Show[Graphics[
            Evaluate[
              Table[Table[{RGBColor[If[aa[[y, z]] == 0, 0, 0.9], 
                      If[aa[[y, z]] == 0, 0, 0.9], 
                      If[aa[[y, z]] == 0, 0, 0.9]], 
                    Rectangle[{y, -z}, {y + 0.9, -z + 
                          0.9}]}, 
{y, 1, Length[aa]}], {z, 
                  1, Length[aa[[1]]]}]]], AspectRatio -> Automatic, 
          Background -> RGBColor[0, 0, 0]]]

board[ohishi]

boardnumber[ma_] := 
      Block[{mm = ma, aa}, aa = Transpose[mm]; 
        Show[Graphics[
            Evaluate[{Table[
                  Table[{RGBColor[If[aa[[y, z]] == 0, 0, 0.9], 
                        If[aa[[y, z]] == 0, 0, 0.9], 
                        If[aa[[y, z]] == 0, 0, 0.9]], 
                      Rectangle[{y, -z}, {y + 0.9, -z + 
                            0.9}]}, 
{y, 1, 
                      Length[aa]}], {z, 1, Length[aa[[1]]]}], 
                Table[Table[{If[aa[[y, z]] == 0, RGBColor[0, 0, 0], 
                        RGBColor[0, 0, 0]], 
                      Text[aa[[y, z]], {y + 0.5, -z + 
                            0.5}]}, 
{y, 1, 
                      Length[aa]}], {z, 1, Length[aa[[1]]]}]}]], 
          AspectRatio -> Automatic, 
          Background -> RGBColor[0, 0, 0]]]

boardnumber[ohishi]

knightgraphtest1[ma_List, cl1_, cl2_] := 
        Block[{}, m = ma[[1]] // Length; 
          n = ma // Length; 
Clear[loca, mmm, ed, ver, 
            ver2, edd, vert]; 
loca[z_] := 
            Block[{x, y, ss, st}, x = z[[1]]; y = z[[2]]; ss = {}; 
              st = {{x - 2, y + 1}, {x - 1, y + 2}, {x + 1, y + 2}, {x + 2, 
                    y + 1}}; 
              Do[If[0 < st[[k, 1]] ≤ n && 
                    0 < st[[k, 2]] ≤ m, 
                  ss = Append[ss, st[[k]]], ], {k, 1, 4}]; 
              Table[{{x, y}, ss[[h]]}, {h, 1, 
                  Length[ss]}]]; 
mmm = 
            Flatten[Table[loca[{x, y}], {x, 1, n}, {y, 1, m}], 
              2]; 
ed = 
            Select[mmm, 
              ma[[#[[1, 1]], #[[1, 2]]]]*
                    ma[[#[[2, 1]], #[[2, 2]]]] > 
                  0 &]; 
ver = 
            Flatten[Table[{p, q}, {p, 1, n}, {q, 1, m}], 
              1]; 
ver2 = 
            Select[ver, 
              ma[[#[[1]], #[[2]]]] > 
                  0 &]; 
edd = 
            Map[{{#[[1, 2]], -#[[1, 1]]}, {#[[2, 
                        2]], -#[[2, 1]]}} &, 
              ed]; 
vert = 
            Flatten[Map[{{#[[2]], -#[[1]]}} &, ver2], 
              1]; 
Show[
            Graphics[
              Evaluate[
                Join[Table[{Hue[cl1], Line[edd[[n]]]}, {n, 1, 
                      Length[edd]}], 
                  Table[{Hue[cl2], Disk[vert[[n]], 0.1]}, {n, 1, 
                      Length[vert]}]]]], AspectRatio -> Automatic, 
            Background -> RGBColor[0, 0, 0]]];

knightgraphtest1[ohishi, 0.6, 0.1]

A gallery of beautiful graphs.

Here we present beautiful graphs with matrixes that produce them.

a=(({{0, 1, 4, 0, 0, 23, 20, 0, 0, 27, 30, 0}, {11, 6, 9, 2, 13, 18, 15, 22, 25, 32, 35, 28}, {8, 3, 12, 5, 16, 21, 24, 19, 34, 29, 26, 31}, {0, 10, 7, 0, 0, 14, 17, 0, 0, 36, 33, 0}, {0, 91, 94, 0, 0, 0, 0, 0, 0, 45, 42, 0}, {89, 96, 87, 92, 0, 0, 0, 0, 47, 40, 37, 44}, {86, 93, 90, 95, 0, 0, 0, 0, 38, 43, 46, 41}, {0, 88, 85, 0, 0, 0, 0, 0, 0, 48, 39, 0}, {0, 79, 82, 0, 0, 65, 68, 0, 0, 53, 56, 0}, {77, 84, 75, 80, 63, 70, 61, 66, 51, 58, 49, 54}, {74, 81, 78, 83, 72, 67, 64, 69, 60, 55, 52, 57}, {0, 76, 73, 0, 0, 62, 71, 0, 0, 50, 59, 0}}));

a=(({{0, 20, 27, 34, 0, 0, 43, 38, 41, 0, 57, 52, 47, 0, 0}, {0, 33, 0, 21, 28, 35, 40, 0, 44, 51, 46, 0, 58, 53, 0}, {19, 26, 0, 0, 0, 22, 37, 42, 39, 56, 0, 0, 0, 48, 0}, {32, 0, 0, 0, 36, 29, 6, 1, 12, 45, 50, 0, 54, 59, 0}, {25, 18, 31, 0, 23, 16, 11, 0, 7, 2, 55, 60, 49, 0, 0}, {0, 0, 24, 17, 30, 5, 0, 0, 0, 13, 68, 75, 62, 0, 0}, {0, 0, 101, 90, 95, 10, 15, 0, 3, 8, 61, 0, 69, 76, 63}, {0, 91, 96, 0, 100, 89, 4, 9, 14, 67, 74, 0, 0, 0, 70}, {0, 102, 0, 0, 0, 94, 85, 82, 87, 80, 0, 0, 0, 64, 77}, {0, 97, 92, 0, 104, 99, 88, 0, 84, 73, 66, 79, 0, 71, 0}, {0, 0, 103, 98, 93, 0, 83, 86, 81, 0, 0, 72, 65, 78, 0}}));

a=(({{0, 0, 0, 0, 0, 31, 0, 37, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 36, 0, 40, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 30, 41, 32, 35, 38, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 34, 39, 42, 0, 0, 0, 0, 0}, {0, 0, 24, 0, 0, 29, 0, 33, 0, 0, 44, 0, 0}, {23, 26, 21, 28, 19, 0, 0, 0, 43, 48, 55, 50, 45}, {0, 0, 18, 25, 0, 0, 0, 0, 0, 53, 46, 0, 0}, {17, 22, 27, 20, 15, 0, 0, 0, 47, 56, 49, 54, 51}, {0, 0, 16, 0, 0, 5, 0, 1, 0, 0, 52, 0, 0}, {0, 0, 0, 0, 0, 14, 11, 6, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 10, 7, 4, 13, 2, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 12, 0, 8, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 9, 0, 3, 0, 0, 0, 0, 0}}));

a=(({{0, 5, 2, 0, 0, 45, 48, 0, 0, 51, 54, 0}, {1, 0, 0, 4, 43, 0, 0, 46, 49, 0, 0, 52}, {0, 3, 6, 0, 0, 47, 44, 0, 0, 53, 50, 0}, {0, 8, 11, 0, 0, 42, 39, 0, 0, 36, 33, 0}, {10, 0, 0, 7, 40, 0, 0, 37, 34, 0, 0, 31}, {0, 12, 9, 0, 0, 38, 41, 0, 0, 32, 35, 0}, {0, 17, 14, 0, 0, 21, 24, 0, 0, 27, 30, 0}, {13, 0, 0, 16, 19, 0, 0, 22, 25, 0, 0, 28}, {0, 15, 18, 0, 0, 23, 20, 0, 0, 29, 26, 0}}));

a=(({{0, 26, 31, 22, 19, 42, 39, 46, 35, 0}, {0, 21, 18, 27, 32, 45, 34, 43, 40, 0}, {25, 30, 0, 20, 23, 38, 41, 0, 47, 36}, {0, 0, 24, 17, 28, 33, 44, 37, 0, 0}, {0, 0, 29, 0, 0, 0, 0, 48, 0, 0}, {0, 0, 16, 0, 0, 0, 0, 53, 0, 0}, {0, 0, 5, 12, 1, 54, 49, 58, 0, 0}, {4, 15, 0, 9, 6, 59, 62, 0, 52, 57}, {0, 8, 11, 2, 13, 50, 55, 64, 61, 0}, {0, 3, 14, 7, 10, 63, 60, 51, 56, 0}}));

a=(({{0, 0, 0, 0, 0, 0, 57, 50, 43, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 58, 51, 44, 0, 56, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 45, 0, 0, 0, 49, 42, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 52, 59, 0, 0, 0, 55, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 46, 0, 54, 41, 48, 0, 32, 25, 38, 0}, {0, 0, 80, 67, 74, 53, 60, 47, 0, 33, 26, 39, 0, 31, 0}, {79, 66, 73, 0, 61, 0, 0, 0, 0, 40, 0, 0, 0, 24, 37}, {72, 0, 0, 0, 68, 75, 0, 0, 0, 27, 34, 0, 0, 0, 30}, {65, 78, 0, 0, 0, 62, 0, 0, 0, 0, 21, 0, 29, 36, 23}, {0, 71, 0, 62, 76, 69, 0, 1, 14, 7, 28, 35, 22, 0, 0}, {0, 64, 77, 70, 0, 2, 15, 8, 0, 20, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 9, 0, 0, 0, 13, 6, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 16, 3, 0, 0, 0, 19, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 10, 0, 18, 5, 12, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 17, 4, 11, 0, 0, 0, 0, 0, 0}}));

a=(({{0, 0, 0, 0, 0, 0, 53, 50, 55, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 56, 0, 52, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 51, 54, 49, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 63, 60, 57, 92, 95, 90, 45, 42, 47, 0, 0, 0}, {0, 0, 0, 58, 0, 62, 89, 0, 93, 48, 0, 44, 0, 0, 0}, {0, 0, 0, 61, 64, 59, 94, 91, 96, 43, 46, 41, 0, 0, 0}, {1, 4, 7, 82, 85, 88, 65, 68, 71, 100, 103, 98, 35, 40, 37}, {6, 0, 2, 87, 0, 83, 70, 0, 66, 97, 0, 101, 38, 0, 34}, {3, 8, 5, 84, 81, 86, 67, 72, 69, 102, 99, 104, 33, 36, 39}, {0, 0, 0, 9, 12, 15, 80, 75, 78, 27, 32, 29, 0, 0, 0}, {0, 0, 0, 14, 0, 10, 77, 0, 73, 30, 0, 26, 0, 0, 0}, {0, 0, 0, 11, 16, 13, 74, 79, 76, 25, 28, 31, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 17, 22, 19, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 20, 0, 24, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 23, 18, 21, 0, 0, 0, 0, 0, 0}}));

The problem itself is interesting, but the graph that can be made from the board is very beautiful.
Perhaps many people can enjoy making graphs like these.