top of page

The Sukeima® theory - A knight's tour game variation 

The game starts at the numerical digit 1. 

By applying the knight's tour advancement principle to the board, the player will find the missing numbers to fill in. The puzzle setter provides a partially completed grid, which, on a regular board, has a unique solution for each cell. For example: on a 10x10 grid, there are 100 numbers. Any random number in-between 1 and 100 can potentially be missing. So by tracing the numbered path from 1 to 100, and by applying the knight's tour, the player finds all the missing numbers.

If for example the player finds number 7, and then number 9 on the grid; number 8 will be the missing one, you have to fill in. To check if the placed digit is the correct one, the player can apply "L" figures to the board, in all directions. 1 square ahead and 3 to the side, or 3 to the side and then one ahead in any direction, as if the player would draw an alphabetical "L" letter. The grid is completed, when the are no more empty grid cells.

The game can be played on paper, as a paper-and-pencil game, or as a virtual variation, on electronic devices.

 

History

 

The game "Sukeima", an international registered trademark, is a numerical digit variation of the knight's tour game. Philippe FUNK has been working on the project since 2012. The game is based on Warnsdorf's rule, and has been first published by Philippe FUNK in 2014. Mister FUNK has released an IOS 1.0 application version, as well as game books in 2014, registered at the German National Library[[1]]. The Sukeima game is a number variation, based on the well known keima of the Go game, or the in western countries more known chess game, combined with numbers on a grid, as for the worldwide known Sudoku game.

 

The Knight's Move (桂馬 Keima) is more fast-paced than either the diagonal move or the one-space jump in Go. It is similar to the knight’s tour in chess. It is also useful in Sabaki. Near the edge of the board the small knight's move is used to secure a base or to link up stones. However this shape can easily be cut. Hence, you must consider the surrounding stones and be prepared to sacrifice one of your own stones to make good shape. It is sometimes called the « small knight's tour » in order to differentiate it from the « large knight's tour ».

If you consider the shōgi, in Japanese chess, Sukeima has it's origins in the oldest abstract combinatory known strategy game, the “Go” game, defined by the Warnsdorf's rule.

Even if the Go game is very ancient, it is still enjoyed in China, Korea and Japan. The game Go was invented in China, and is played in Japan since 1200 years. The game Go is a not yet very known game in the western part of the world.

The Turks solved the knight's Tour with a chess-playing machine. This solution was closed and circular, completable from anywhere on the board.

 

The knight's tour as solved by the Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can thus be completed from any point on the board.

In the 9th century AD., the first mention was made of the knight’s tour. In Rudraṭa's Kavyalankara[1] (5.15), the knight's tour pattern on a half-board has been presented in a figure ("citra-alaṅkāra") called the "turagapadabandha" or 'arrangement in the steps of a horse', in a Sanskrit work on elaborative Poetics. Since the Indic syllabic writing systems used for Sanskrit, each syllable can represent a square on a chess board. Rudrata's example is as follows:

से ना ली ली ली ना ना ना ली

ली ना ना ना ना ली ली ली ली

न ली ना ली ली ले ना ली ना

ली ली ली ना ना ना ना ना ली

se nā lī lī lī nā nā lī

lī nā nā nā nā lī lī lī

na lī nā lī le nā lī nā

lī lī lī nā nā nā nā lī

Leonhard Euler was one of the first mathematicians to reserach the knight's tour problem. The Knight's Tour first completing procedure was Warnsdorf's rule, first described in 1823 by H. C. von Warnsdorf.

In 1857, Hamilton, described as his Icosian game at a meeting of the British Association in Dublin. It was one of the first modern inventions on the knight’s tour. Sold to J. Jacques and Sons, makers of high quality chess sets, for £25, it was patented in 1859, in London. The Hamiltonian circuit is related to Euler's Knight's Tour in a certain graph, eventhough it was a comercial failure.

The 20th century Oulipo group of writers used the knight tour among many others, even if the their most important example was the 10 × 10 Knight's Tour, setting the order of the chapters in Georges Perec's novel Life: A User's Manual.

 

Schwenk[2] proved that for any m × n board with m ≤ n, closed knight's tour are always possible unless, if one of these conditions are met:

m and n are both odd

m = 1, 2, or 4

Number of tours

26,534,728,821,064 directed closed tours are possible on an 8 × 8 board (i.e. two tours along the same path travelling in opposite directions are counted separately, as well as rotations and reflections).[3][4][5] The number of undirected closed tours is half this number, considering reversed tours. 9,862 is the number of undirected closed tours on a 6 × 6 board.[6]

On an board for n = 1, 2, … are:

1, 0, 0, 0, 1728, 6637920, 165575218320, 19591828170979904 directed open tours (sequence A165134 in OEIS).

Finding tours with computers

Some computer generated tour methods are algorithms, while others are heuristics.

 

 

 

 

Brute force algorithms

 

A brute-force search for a knight's tour is impractical on all but the smallest boards;[7] On an 8x8 board, approximately 4×1051 possible move sequences exist,[8] and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However the size of this number gives a misleading impression of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty."[7]

 

Divide and conquer algorithms

 

By constructing the pieces together, and dividing the board into smaller pieces, tours on most rectangular boards can be constructed in polynomial time.[9][10]

 

 

Neural network solutions

 

By a neural network implementation, the knight’s tour can be solved.[11] Every legal knight's move is represented in the network by a neuron, and each neuron active or inactive neuron is initialized randomly (output of 1 or 0), including the neuron 1 being part of the final solution. Each neuronal state function (described below) is initialized to 0.

In the running network, each neuron can change its state and output based on the states and outputs of its neighbors (those exactly one knight's move away) if the following transition rules are met, as follows:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

otherwise, where t represents discrete intervals of time, U (N i,j,) is the state of the neuron connecting i square to square j, V (N i,j) is the output of the neuron from i to j, and G (Ni,j) is the set of neighbors of the neuron.

The network should potentially converge, even in divergent cases, occuring when no neuronal changes state from time t to t+1. During network convergence, it encodes a knight's tour or a series of two or more independent circuits within the same board.

 

Warnsdorf's rule

 

On the graphical representation of Warnsdorf's Rule, each square contains an integer giving the number of moves, the knight could make from that square to the one with the smallest integer in it, namely 2.

 

 

24×37 board (888 cells)

 

 

 

 

 

 

 

 

 

 

 

 

Warnsdorf's heuristic rule for knight's tour proceeds the knight’s move to the square from which the knight will have the fewest onward moves. When calculating onward moves for each potential square, already visited squares are not considered. Various methods for breaking ties exist, including one devised by Pohl[12] and another by Squirrel and Cull.[13]

 

Any graph can apply this rule. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Even if the Hamiltonian path problem is NP-hard in general, this heuristic is able to successfully locate a solution in linear time.[12] The knight's tour is a special case.[14]

 

The first heuristic was described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorf in 1823.[14] The book 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally (ISBN 071260541X) provides a computer program, that finds any starting position for Warnsdorf’s rule.

Sukeima uses this algorithm to generate it's puzzles and solutions. There are three kinds of tie breakers used in the puzzle generation: clockwise, random, and calculating from the center.

 

Variations of grid size

 

Creating a program to find a knight's tour is a common problem given to computer science students.[15] Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 × 8, as well as irregular (non-rectangular) boards.

The developed software generates square and rectangular puzzles of different sizes. The smallest possible open knight tour is a 3x4 solution, that can be generated.

The classic Sukeima board can be generalized into NxN grids, where each of the N rows, columns, and regions have N cells and each of the knight move numbers occur once in a board.

This will produce more variations by size and shape. Sukeima is not always square in shape, so the combination can be huge enough. This generation problem is a recent one, and can be solved by using any computer software that can solve Knight's Tour problem. When the knight move is replaced by numbers, any grid size can satisfy single visit knight moves, can be implemented into the Sukeima game, by deleting some of its numbers.

The Sukeima generator is based on the Warnsdorff algorithm. This software is made, so that the user can input any desired board size preferably above 3x4 or 4x3, and so the algorithm can solve it well. User can also pinpoint the first position of the knight, so the generation can be more specified.

The number of grids that can be generated in one run, also customizable by the user. The program will search for any combination that can be integrated into a Sukeima grid. However, when user puts too much requirements, the software will sometimes fail in generating satisfying board solutions, so the number of grids generated will be decreased as well.

The algorithm used in this software, as stated before, is the Warnsdorff algorithm. There is no further explanation about different algorithms such as Warnsdorff+, Random Tie Breaker, or Backtrack so the unfamiliar user will not have sufficient information. But using the default setting such as board size, knight position, levels, and missing grid percentage, the user can make a huge combination of Sukeima grids easily.

 

The variant of the Sukeima, as in Sudoku, is also depending on size, type, and the creativity of the creator. Some of them are:

 

Sukeima: "Go Keima"

Sukeima board that consists of 3x4.Because Sukeima grids can be any size even non-squared in size. A grid consisting of 3x4 (Wide) or 4x3 (high) is known as the smallest possible non-squared combination based on the Sukeima Puzzle Creator. This combination is known to be the smallest possible square sized Sukeima board based on the Sukeima software.

 

Sukeima: "Tall or wide Keima"

A rectangular keima, with a difference of at least four grid cells, side to side.

 

Sukeima: "Prime Keima"

Sukeima board having prime number rows and columns. "Go Keima" is also a part of this variant.

 

Sukeima: "Blind Keima"

This combination is defined by more than 90% of missing grids. This variation is one of the most difficult ones.

 

Sukeima: "Giant Keima"

Any board above 20x20 will be considered as a "giant keima". This variant is very interesting when combined with the "blind keima" variation.

 

Sukeima: "Base-n Keima"

This kind of Sukeima is made using 0–9 base numbers to represent values zero to nine. Any board using different base numbers can be made up, so the game will be more satisfying. This variant example is a "binary keima" or "hexadecimal keima".

 

Sukeima: "Regional Keima"

Sukeima can be also made up as a sudoku that has regions inside a grid. The rule of the sudoku game can also be applied to sukeima, when the sudoku number game position condition of the number not appearing in the same row or same column is respected.

 

Sukeima: "Fibonacci Keima"

Instead of using sequence numbers, Sukeimas also can be made by using Fibonacci numbers.

 

Sukeima: "Sukeima-zilla"

A board that is made of 100 regions, each region will be bigger than a 8x8 grid, and the "regional keima" will be applied in here.

 

Sukeima: "Double keima"

Sukeimas that only have 2 missing grids, but each grid can be occupied by more than one different number.

 

Sukeima: "3D keima"

The game on a cube, where all sides of the shape are playable.

 

Game editions

 

Software

Release name: Sukeima, category: Games, released: Mar 21, 2014, version: 1.0, size: 13.5 MB, language: English, seller: F Services, © 2013 Philippe Funk, rated 4+ https://itunes.apple.com/us/app/sukeima/id647293412?mt=8

 

Books

Sukeima Eco Edition : Yellow Belt Book- Bonsai N°2 - Beginner / Philippe Funk, Norderstedt : Books on Demand, July 2014, http://d-nb.info/1053347502

SUKEIMA ORIGINAL EDITION : YELLOW BELT BOOK- BONSAI N°2 - BEGINNER / Philippe FUNK, Norderstedt : Books on Demand, July 2014, http://d-nb.info/1054034338

SUKEIMA ORIGINAL EDITION: GOLD BELT BOOK- BONSAI N°3 – BEGINNER / Philippe Funk, Norderstedt: Books on Demand, July 2014, http://www.bod.de/index.php?id=296&objk_id=1289428

Sukeima Original Edition : GRASS GREEN BELT BOOK- SAMOURAI N°4 - INTERMEDIATE / Philippe Funk, Norderstedt : Books on Demand, 2014, http://d-nb.info/1054348731

 

See also

  • Abu-Bakr Muhammad ben Yahya as-Suli

  • George Koltanowski

  • Longest uncrossed knight's path

  • Eight queens puzzle

  •  

Notes

  • Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.

  • Allen J. Schwenk (1991). "Which Rectangular Chessboards Have a Knight’s Tour?". Mathematics Magazine: 325–332.

  • Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3 (1): R5. Remark: The authors later admitted that the announced number is incorrect. Considering McKay's report, the correct number is 13,267,364,410,532 and is repeated in Wegener's 2000 book.

  • Brendan McKay (1997). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University).

  • Wegener, I. (2000). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3.

  • Weisstein, Eric W., "Knight's Tour", MathWorld.

  • Simon, Dan (2013), Evolutionary Optimization Algorithms, John Wiley & Sons, pp. 449–450, ISBN 9781118659502, The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality Nx of x (the size of the search space) is over 3.3×1013 (Löbbing and Wegener, 1995). We don’t ry to solve this problem using brute force, but by using human insight and ingenuity. The cardinality of a combinatorial optimization problem is not necessarily indicative of its difficulty.

  • "Enumerating the Knight's Tour".

  • Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited" (PDF). Fibonacci Quarterly 16: 276–285.

  • Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics 73: 251–260. doi:10.1016/S0166-218X(96)00010-8.

  • Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

  • Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM 10 (7): 446–449. doi:10.1145/363427.363463.

  • Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Retrieved 2011-08-21.

  • Alwan, Karla; Waters, K. (1992). Finding Re-entrant Knight's Tours on N-by-M Boards (PDF). ACM Southeast Regional Conference. New York, New York: ACM. pp. 377–382. doi:10.1145/503720.503806. Retrieved 2008-10-28

  • H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326–328. 2003.

External links

Wikimedia Commons has media related to Knight's Tours.

  • (sequence A001230 in OEIS)

H. C. von Warnsdorf 1823 in Google Books Category:Graph algorithms Category:Mathematical chess problems Category:Chess problems Category:Hamiltonian paths and cycles Category:Mathematical problems

 

 

This article was published on the internet site sukeima.com the 6th of May 2015.

 

  •  

Ut+1(Ni,j)=Ut(Ni,j)+2-∑ Vt(N)

                           N Є G(Ni,j)

                        1  if Ut+1(Ni,j)>3

Vt+1(Ni,j)=         0  if Ut+1(Ni,j)<0

                        Vt(Ni,j)                    

bottom of page