CHESMAYNE

Midi: Want  When I need U

Knights Tours

 

 

The KT puzzle where the KT lands on every cell only once are called “The KTs Tour”.   At the following link you will find an animated Tour and another link to a website with several different Tours.  

On the Road

 

http://www.chess-poster.com/english/chesmayne/the_knight.htm

Puzzle.   The KT is moved on 64 occasions, entering each cell only once during this tour.  The solution is called ‘re-entrant’ if the KT finishes in a cell which is a KTs move away from the starting cell.   The other knights of Chesmayne may be used in the same manner (KN, SB, KM etc).   The number of possible KT tours is 122+ million.  

Could you do the ‘KTs Tour’ in three minutes in front an audience of millions?   That is exactly what Paul Broad from Cardiff, Wales did on the ITV show ‘The Moment of Truth’ hosted by Cilla Black.   Paul had a week in which to memorise the KTs tour across the board before testing out his memory in front of millions of views in the UK.    Paul completed the Tour successfully! 

In a KTs Tour the Knight must travel to every square/cell on the board without entering any cell more than once while moving in an L-shape as it normally would in a game of chess  There are many ways of achieving this.   The example which follows shows one variation.   The KT starts on the cell numbered one and travels to each cell in numerical order, finishing on cell 64.

 

A Knights Tour

 

“Knight’s Tour” is a puzzle which has amused chess players throughout the ages. The goal of the KT is to traverse around the board, landing on each cell but once.   There are numerous solutions.   Here’s one – with an animation…….

 

 

 

Here’s another one:

 

 

The above two paths are known as ‘closed’ or ‘re-entrant’ paths.   The KT, after completing its journey, lands on the 64th cell, which is also the cell that it started on.   Thus, it can complete the journey again. 

 

This is considered much more of an elegant solution than the many “open” paths, one of which is shown here:

 

 

 

As you can see, the KT still lands on each of the 64 cells.   However, he isn’t able to complete the journey a second time.   In this tour, the KT starts out here on the h8 cell, but ends up on c6... more than a KTs move away. 

 

Not only is this next example a ‘re-entrant’ path, but it’s considered a somewhat semi  magic square.   Each of the columns, add up to 260!

 


However, this one must be considered a “SUPER” magic square which may have been created by the mathematician Leonhard Euler. 

 

01 Each column adds up to 260!

   02 Each row also adds up to 260!

 

 

HOW MANY SOLUTIONS ARE THERE?

I.A. Horowitz and P. L. Rothenberg have stated:

“The number of possible ‘KTs Tours’ lies somewhere between 122,802,512 and 168! / (105!)(63!)”  

chess knight

The KTs Tour
by Dan Thomasson
Dedicated to the memory of GM George Koltanowski (“Kolty”)

chess knight


The “KTs Tour” is an ancient puzzle in which the object is to move a KT, starting from any cell on a chessboard, to every other cell, landing on each cell only once.   This is usually considered to be a very challenging puzzle, so the discovery of the solution described below came as quite a surprise!   To learn more about KT Tours, explore the links below (and watch for new additions to this site in the near future).  

This site is sponsored by Borders Chess Club

KTs Tour Art

The following Knight’s Tour reflects simplicity, beauty, and semi-symmetry in which the two left quadrants show the same path of the KT, while the two right quadrants mirror the path.   Please contact me if you have created interesting KT tours.   I will pick the best ones and add them to this section of the webpage. 

artmpv2.gif


Click on the image above for a static view

Another interesting tour gem, a mini-KT tour of only 16 moves, can be used to create the most amazing geometric pattern called a 4th dimensional hypercube.   The path of the KT could be: d8, b7, a5, b3, d2, f3, g5, f7, d6, c4, e5, c6, d4, e6, c5, e4.  By placing a dot in the center of each cell that the KT moves to, then connecting each dot with a line that represents a legal KT move, the end result is a perfect 4th dimensional hypercube.  Notice that there are 16 different cubes, all of which have the same exact dimensions, inside the hypercube.  Can you find them? 

hypercube.jpg

Below you will find an interesting pattern that can be repeated over and over again to make larger and larger closed KT tours.  The pattern comes from my ‘Closed KTs Solution Key’.   Ceramic tiles, wood, or plastic can be cut into these basic shapes to make the secret closed KTs tour pattern.   The cut pieces could then be put on floors, walls, or table-tops.   For simplicity, create the pattern for an 8 x 8 square board.   Do not put numbers on the top of the pieces.   If you want to make it into a puzzle, cut out the pieces and put the corresponding numbers on the back of the pieces in a very light shade or impression.  

When I practice creating KT tours on paper with checkerboard squares, I can quickly complete an 8 x 8 square closed KTs tour in 15 seconds by marking off each KT move on the squares with the following symbols: /, -, \, |. I first use ‘/’ for all diamond shape patterns leaning in the same direction as ‘/’ in all four quadrants.   I then use ‘-‘ for square shape patterns in all four quadrants, then ‘\’ for the opposite diamond patterns, and finally ‘|’ for the opposite square patterns.  

The Knight's Tour, by Dan Thomasson
After doing hundreds, possibly thousands of KT tours, using those four simple marks (which by the way are much easier to jot down with a pencil than numbers - especially if the tour is 10,816 squares), I realized that they made a neat pattern on the chessboard which could be reproduced with tiles.   I just follow the path pattern that I use for the ‘Closed KTs Tour Solution Key’ and other tours that are displayed on the KT Tours web page.  

I might consider making a cool poster out of it or some of the other tours I’ve created.  There is a definite symmetrical pattern.   Just think, by creating that one quadrant, it can be used as computer wallpaper, web page background, watermarks, or quilts by tiling it.   Experiment by changing the line colour and thickness, and the tile colour.   By combining these four shapes in various ways, alphabets, number systems, and ciphers can be easily created.   Who knows, maybe there could be a fictional story written that centers its plot around the patterns in the ‘Secret Closed KTs Tour’.  

scktp.gif.gif
[Intro]   [Simple Solution]   [Semi-Magic Square Knight Tours]
[Closed Knight Tours]   [Solving with Number Pairs]
[Knight Tour Cube]   [Knight Tour Tessellations]   [Links to Knight Tours]

www.BordersChess.org/KTart.htm   modified 2002.03.06

 

The KTs Tour

 An Extremely Simple Solution

I would like to share a KTs Tour I created by using a very simple rule I devised that requires no memorization:  Start at any corner and continuously rotate in the same direction around the board moving on the outermost squares.   The moves create a semi-symmetrical pattern around the board.   The tour is completed with only four trips around the board.   Feel free to post this solution on your web-pages, other publications, or with other KT Tour enthusiasts.   Please reference my name and e-mail address when posting my design and KTs Tour solution.  

simplempv1.gif

simplespv2.gif

 

I originally created the chessboard in Excel which I could also use to automatically sum the rows, columns, and diagonals.  My KTs Tour does not reflect a ‘Magic Square’ but does provide an extremely simple solution.   I recreated the board in Visio and added the red lines to show the symmetry.   Connecting the sequential moves is fun to do with other KT Tours, Magic Squares, and Magic Cubes to come up with different designs. 

In addition to being fun, the KTs Tour puzzle also helps chess students to develop their ability to visualize tricky KT move sequences.   The Greater Knoxville Chess Club’s director wrote: “Thanks for the brainwork!   I just started using the KTs tour as an instructional device two weeks ago with my students.  Lev Alburt gives a solution in ‘Comprehensive Chess Course’ starting with a KT on d3.  Your solution with the KT starting from a corner is what I told my students that I would develop a methodology for.   Now I don’t have to do nothing but present your work!   Thanks for the assist - you must have read my mind!” 

Reader Feedback on Thomasson's Knight's Tour Solution

[Intro]   [Semi-Magic Square Knight Tours]
[Knight's Tour Art]   [Closed Knight Tours]   [Solving with Number Pairs]
[Knight Tour Cube]   [Knight Tour Tessellations]   [Links to Knight Tours]

www.BordersChess.org/KTsimple.htm   modified 2002.03.06

 

Closed (Reentrant) KT Tours

In the early 1940s, GM George Koltanowski toured the countryside providing KTs tour demonstrations at various chess clubs and tournament events.

kolty2.jpg


Grandmaster George Koltanowski, 1903-2000
copyright(C) 2000, San Francisco Chronicle

He used a closed (re-entrant) KTs Tour for his solutions.   “Closed” means that the KT moves to all cells on the chessboard making legal KT moves and covering every cell only once in which the last move can connect back to the starting position (64 connects back to 1).  This is also known as “reentrant”.  A member of the audience would ask him to block out a cell on an 8 x 8 chessboard.   He would begin making his KT moves from that cell and then return to that cell with his last move. 

Here is my thought process for creating a closed KT tour. 

When I create a tour, I think of diamond and square patterns and the letters U and C. 

ds.gif

I divide the board into four quadrants, start with the top left quadrant, then place the diamonds and squares in their respective quadrants following the directional patterns of the letters U and C. 

diasqua.gif

Check out the following steps:

Step 1: I create the same diamond pattern in all four quadrants using the directional pattern of the letter U.

Step 2: I repeat step 1, but instead of diamonds, I create the same square pattern in all four quadrants.

Step 3: I create the same diamond pattern in all four quadrants using the directional pattern of the letter C.

Step 4: I repeat step 3, but instead of diamonds, I create the same square pattern in all four quadrants.

closedmcv2.gif 


click on the image above to see an elaborated version

Look at the closed KTs Tour below where I alternate the diamond and square pattern for each quadrant.   The result is the same - a completed closed KT tour.   What once seemed impossible to do without the aid of a computer is now possible and extremely simple.  

closedscv2.gif 


click on the image above to see an elaborated version

The figure below shows a closed KTs Tour on a 16 x 16 cell board.   The pattern used in this example is the same pattern or solution that I use on boards with 1024, 4096, or even 10816 cells.   For speed and ease of completing such large tours, it is best to use the same closed tour in the 16 x 16 board that I’ve provided, but begin the tour from the top left cell.   In other words, make square 190 = 1, 191 = 2, 192 = 3, ... etc., all the way around the board until the tour is completed.   You will see just how easy it really is!  

ckt256.gif

I created the pattern in this solution key which I used to solve the 16 x 16 board KTs Tour, and it can be used on larger boards such as 32 x 32 cells, 64 x 64 cells, 104 x 104 cells, along with other board sizes.  

cktkey.gif

Closed Knight's Tour Solution Key

[Intro]   [Simple Solution]   [Semi-Magic Square Knight Tours]
[Knight's Tour Art]   [Solving with Number Pairs]
[Knight Tour Cube]   [Knight Tour Tessellations]   [Links to Knight Tours]

www.BordersChess.org/KTclosed.htm   modified 2002.03.06

 

 

Link to: KTs tour program

This WWW page is for a shareware MS-DOS program that solves the KTs Tour puzzle (visit all 64 cells/squares with one KT).  The small program (50k) can be downloaded from this site.   While the author of this site doesn’t mention it, it is nice to know that the KTs tour puzzle is more than 1,000 years old.

§         http://www.gfcs.demon.co.uk/tour/ KTs tour program.

§         From: ‘Chess Variants’ web page. 

 

Worse than Worthless

By Ralph Betza

Something that is worthless has zero value.   What could be worse?

Negative Money

My dentist told me the fee for today’s visit was zero, and he hoped I had that amount with me.   Ha ha.

I immediately went into an uncommunicative reverie, thinking about negative-valued money.   If I owe you ten dollars, you can give me a minus-ten dollar bill.

There would need to be severe penalties against destroying or discarding or even hiding negative money, to prevent its abuse.   Imagine the anti-miser, who lives well beyond his apparent means and after death is discovered to have a huge stash of negative money hidden in a mattress.

Strangely enough, negative money has some positive value.   If you have a debt, you pay interest on it, but if you have negative cash, it is like having an interest-free loan. Therefore negative money would be somewhat sought after, as people would try to keep all their liabilities in uncash. 

Counterfeit negative money would not be a problem.

The Negative Relay Knight

In the mid 1970s, I did an article for NOST-algia in which I explored “all possible” variants of Relay Chess.   One such variant allows only your opponent to benefit from the relay powers.

Consider a piece that moves as a KT but has no capturing powers; instead, any enemy piece a KTs move away from it gains temporarily the power of moving or capturing as a KT.   This is a piece of negative value!  

Following Mannis Charosh’s rules, the enemy KI cannot benefit from the relay power, and the enemy PAs cannot use this power to move to their first or eighth ranks.   However, I will break from the Charosh tradition and allow the Negative Relay KT to give an enemy Negative Relay KT the temporary power to move or capture as KT, and my reason for doing so is that I have seen that the resulting tactics are piquant and charming.  

Using the above rules, and replacing each side’s KTs with Negative Relay KTs, we get a simple game called Negative Relay Chess.   Here is a sample opening: 

1. NegRelayNb1-c3 d7-d5 2. NegRelayNc3-e4 e7-e5 3. NegRelayN e4-f6+ NegRelayNg8-h6 4. NegRelayNf6-g8; and White has succeeded in burying his negative-valued piece deep in enemy territory where it blocks enemy moves and where the benefits the foe gains from it are less dangerous (but where the opponent is more likely to be able to get pieces in range of it).   This is a strategy that might be worthless or worse, and to achieve it W has lost several tempi.  

Meanwhile, the pieces at h6 and g8 temporarily give each other the ability to capture. Notice that the Negative Relay KT can be captured, but can be used as though it were uncapturable because, due to its negative value, capturing it is usually undesirable.  

The move 3.Ne4-f6+ tries to force the capture of the liability.   Instead, Black’s reply 3...Ng8-h6 provides an illustration of the temporary nature of the relay power.  The sample game is very short, but provides insight into the rules, the strategy, and the tactics; I think it’s a pretty good sample game!  

There is absolutely no doubt that one can play Negative KT Relay Chess with Different Armies.  Beware confusion and danger of illegal moves when negative KT and negative Fibnif mutually attack. 

What’s it Worth?

The Negative Relay KT has some small potential positive value, because it could be used to blockade a passed PA or to make tempo moves in the late endgame.   In fact, in the late endgame, because there are so few enemy pieces to be helped by it, it might even have a very small positive value overall.

Its whole-game value can be estimated as the amount of average mobility it gives to the enemy times the chance that it does so, and the chance that it does so is its own average mobility times half the probability that a random CELL is occupied.   That’s -4.59375, and since the KTs positive average mobility is 5.25, replacing a KT with a Negative Relay KT makes your army weaker by 9.8, or one and seven-eighths of a KT; in other words, replacing a pair of KTs with Negative Relay KTs should theoretically make your army 11.25 PAs weaker!   

Because the KT starts at g1 and b1, where its friendly PAs shield it from undesired contact with enemy pieces, an army that has 3.75 KTs’ worth of power distributed among its other pieces might be able to simply win with its other pieces while leaving its negative-valued KTs at home, right?   The positive value of having a worse than worthless piece in your army is that you get to have so much power added to your other pieces!  

Maybe not.   With the funny material balance, the levelling effect will hurt the pieces that have added powers - for example if you have Cardinals instead of BSs, the enemy BSs gain the ability to chase your Cardinals away.  

In order to keep the strategy of keeping the negatives at home from being too strong, I’m going to avoid giving jumping moves as enhancements to any of the pieces.   This means that the negative pieces, if left at home, will have the added liability of being in the way of smooth development.   Also, because the army with negative pieces has to move PAs to develop, it must break up the PA formation that shields the liabilities from contact with the foe.  

Let’s let the RO have the additional power of moving as a three-cell limited BS (that is, as a BS3 that can’t move farther than from a1 to d4), and the BS also move as RO2 (making normal BS moves or short RO moves, for example f1 to f3 but no further). 

I haven’t worked out the exact arithmetic of that, but it’s close enough to be worth a try.   It feels right, too.   But omigosh, what an experimental army, how exotic it is, and oh, so great a chance that it is too weak or too strong!   My brain is tired and I can’t playtest it blindfold; but it’s such an exciting idea, and such a crazy army, I can’t resist publishing it as is, just eight hours after the dentist’s joke, with apologies if it needs to be corrected later.  

The Nattering Nabobs of Negativity

The Nattering Nabobs of Negativity[1] are a highly experimantal and untested army intended to fit into the framework of Chess with Different Armies.

The QU, KI, and PAs are the normal FIDE Q, K, and P.

The R is the FIDE Rook plus short bishop of length 3 - RB3 - and because it ought to have a name I’ll call it a Rhubarb.

The B is the FIDE Bishop plus short Rook of length 2 - R2B -- Rutabaga is its name.

The KT is a Negative Relay KT, as described previously in this document.   It’s called the Ruthven, named after the Murgatroyd whose family curse made his title of nobility worse than worthless. 

Strangenesses

I don’t have the energy to discuss the following ideas in complete detail.

Asymmetrical Relay

Its whole-game value can be estimated as the amount of average mobility it gives to the enemy times the chance that it does so, and the chance that it does so is its own average mobility times half the probability that a random cell is occupied”.  Perhaps you can detect that my particular way of phrasing that statement encompasses the possibility of a piece moving as KT, and granting any piece a KIs move away from it the right to move as a RO or to capture as a BS? 

Promiscuous Negative Relay

Notice that friendly pieces are not affected by the relay power of a friendly piece. Unfortunately, the opening position is so crowded that if a friendly PA a KTs move away from a friendly KT gained the liability of being used by the enemy to move or capture as a KT, chaos might ensue.   However, since PAs may not move to their own first rank, the game might be playable?   But if Pd2 captures Bf1 and Bf1 is also a liability, then the capture would be undesirable.  

Therefore a game in which all pieces (except perhaps KI) are negative relay pieces both to friend and foe might be playable after all! 

Huge Negative Values

Its whole-game value can be estimated as the amount of average mobility it gives to the enemy times the chance that it does so, and the chance that it does so is its own average mobility times half the probability that a random cell is occupied”.   For a symmetrical relay piece, that is, in the natural case where the power of movement is the same as the power granted, the negative value varies as the square of the average mobility of the power.   In other words, the negative relay Amazon would have in theory sixteen times the negative value of the negative relay KT!   Sixteen times! 

That’s more negative value in one piece than the positive value of an entire normal army of pieces! 

 [1] Phrase coined by William Safire for a speech by Spiro T. Agnew.

Written by Ralph Betza.

 

The Distribution of the KT


The Knight’s Tour problem can be stated as follows……. 

·         Given a chessboard with n x m cells, find a path for the KT that visits every cell exactly once. 

For example, here is a solution to the KTs tour problem on a 3 x 10 chess board.   In this example, the KT starts out in the lower left corner and ends in the bottom right corner: 


If we started on the second square on the first row, would it still be possible to find a solution?   More generally, what does the distribution of solutions across the chessboard look like?   That is, for every given starting point, how many solutions exist?

This problem can be solved by computer: for every given starting point, evaluate every possible path that visits each square exactly once, and then count how many solutions exist.   We used Mathematica to do this hunt……. 

We present here the distribution of solutions across a chessboard, for all chess boards with 32 or less cells. 

Select a chessboard from the menu on the left.

Related Links

·         Java Game

·         Arnd Roth's page - an improvement to Warnsdorff’s algorithm.

·         Combinatorial Object Server - the KTs tour and sequences.

·         References and more

·         Schröer and Wegener's paper - (a GZipped postscript file): section 7 derives the (currently) smallest known upper bound on the number of solutions on a 8 x 8 board: the bound is 2.544 * 1017.

·         Chess on Stamps - KTs, chess, and more.

 

 

Leapers

Chess KTs and the like  

 

I intend to place a leaper-tour solving applet at this location.  For now, here is a small article I wrote.  I intended to expand this into my Master’s Thesis, but Donald Knuth wrote an excellent article about leapers that made any expansion a moot point.  In February 1956, M Apsimon posed the question: how many cyclically symmetric KT tours on a board 10 x 10?    In the 1970’s, W H Cozens reiterated the question in ‘The Mathematical Gazette’, and published the tours below.    More recently, Donald Knuth found that exactly 2,432,932 KTs tours are unchanged by 180-degree rotation of the chessboard.    It seems the problem from 1956 might now be answerable. 

 

 


1956 question - how many of these are there?

 

Patent 694038 (1902) by W E Stubbs patented a KTs tour on a 6 x 6 board.   See GP Jelliss's page for the history of this problem.   The Stubbs puzzle used a pegboard and pegs joined with cord.   To solve the puzzle, all the lengths of cord between the pegs had to be taut.    Suppose that you had a 5 x 5 grid of pegs.   Some holes are already filled, perhaps.   With 15-25 pegs, is there a series of lengths so that the pegs can only be put away tautly in a unique way?  

In the March 1973 issue of Games and Puzzles, Robin Merson found a non-crossing KTs tour on an 11 x 11 board with a length of 74 moves.    He found a longer non-crossing tour on a board with a smaller area.   Can you find it?  

 

Roger Phillips has found a smaller board with a longer uncrossing tour.  A 10 x 12 board allows for a length 75 tour.    I’ve moved the material from a few weeks ago to the Leapers page.  

 

 

 

Juha Saukkola wondered what the longest possible Knightrider tour might be.  A knightrider moves like a KT, by may keep going in a straight line.   Here is his answer.   What is the fewest number of moves for a knightrider to tour the chessboard?

 

 

 

Advanced Computing Technology has a program that solves large Leaper problems.

Keyed Tours.  Each path starts at the top left corner, and starts cycling through the KEY over and over again.    It will always take the direction suggested by the key IF a complete closed tour would still be possible.   There are three parts to the key.

1.  A direction key.  Below, a simple 1=N 2=E 3=S 4=W is used.   The eight paths of a knight could be labelled, or something more complicated. 


2.  A grid.  Below, a 6 x 6 grid is used.  The grid could be multidimensional, or hexagonal, or even a grid of chaos tiles. 

 
3.  A code.  Each code will produce a unique path.  On a 50 x 50 grid, what path would result from a 12345678 code from a KT? 

CONSTANT LENGTH TOURS  by Ed Pegg Jr.

Leonhard Euler was the first to find a closed tour of a chessboard by a KT.  Other pieces, more exotic, exist in the realm of Fairy Chess.   Until now, their tour potential hasn’t been studied.   I’ll start with definitions, most of them standard Graph Theory terms. 

Point (vertex, node, junction, cell)

Line (edge, arc, branch)

Two points are adjacent (linked) if they are joined by a line.

A loop links a point to itself.  [None of the graphs in this paper contain loops.]


A line is incident to the points it joins.


The degree of a point is the number of lines incident to it.

Lattice - a graph where all points are midpoints of tiles in a regular tiling.   [I’ll deal with square tilings.] 

A graph is connected if there exists a sequence of points and lines from any point to any other point.

A Hamiltonian cycle is a loopless, connected graph where every point of the graph has degree 2.


A Hamiltonian path is a connected graph of N points with N-2 points of degree 2 and 2 points of degree 1.

A Re-entrant knights tour is a Hamiltonian cycle on an 8 x 8 lattice where each line has length.

Board:  m x n lattice of squares.

(Closed) Tour:  A Hamiltonian cycle on a lattice.

Open Tour:  A Hamiltonian path on a lattice.

Leaper:  A KT is a (1,2) leaper.  In the same fashion, (2,3) leapers and (1,4) leapers exist.

Constant Length Tour:  A tour where every line has a constant length, c.

   For c= sqrt(5), we get KT moves.  Question: What c’s allow a tour of the 8 x 8 board?  Answer: The only c’s that work are c=1, c= sqrt(5), and c=5.   No tour exists on the 9 x 9 board, due to parity.   For the 10 x 10 board, c=1, c= sqrt(5), c= sqrt(13), c= sqrt(17), and c=5 are the only c’s that allow a constant length tour. 

C = 1 corresponds to the (0,1) leaper and is called a Prince.

C = sqrt(5) corresponds to the (1,2) leaper and is called a KT.

C = sqrt(13) corresponds to the (2,3) leaper and is called a Zebra [traditional Fairy Chess].  C = sqrt(17) corresponds to the (1,4) leaper and is called a Giraffe.
   Note that C =  sqrt(a^2 + b^2) corresponds to a (a,b) leaper.

The standard puzzle seen in puzzle books involves the idea of parity.   An example of a parity argument: Prove that a KT cannot make a closed tour of an n x n chessboard, where n is odd.    Proof: fill in the board with a checkerboard colouring.  The KT will start on one of the two colours, let it be white.   After an even number of moves, the KT will be on a white cell.   The closed tour has an odd number of cells.   Since a closed tour would require the KT to land on its starting cell after an odd number of moves, the tour is impossible.  

   We will now prove:

   1.  There is no closed tour for a (1,2) leaper [KT] on a 4 x n board.
   2.  There is no open tour for a (1,2) leaper on a 4 x 4 board.
   3.  There is no open tour for a (1,4) leaper on an 8 x 8 board.
   4.  There is no open tour for a (2,3) leaper on an 8 x 8 board.
   5.  There is no open tour for a (2,3) leaper on a 9 x 9 board.
   6.  There is no open tour for a (2,3) leaper on an 11 x 11 board.
   7.  There is no open tour for a (2,3) leaper on a 12 x 12 board.
 

   Note that the nonexistence of an open tour implies the nonexistence of a closed tour.

1.          There is no closed tour for the (1,2) leaper [KT] on a 4 x n board.  Proof by contradiction:  Suppose such a tour existed.  As can be seen in diagram 1, every grey point (cell) is adjacent to two clear points.  A grey point is not adjacent to a grey  point.   Since half the tour consists of grey points, the tour must look something like  grey white grey white .... white grey, where the first and last grey cells are the same cell.   Thus, every other move is a clear point.   As can be seen in diagram 2, grey  points are adjacent only to clear  points.  Every other move must be a clear point.  By combining these two results, we get a contradiction; namely, that one fourth of the points support one half of the total moves.   The idea of this proof is used several times in the course of this paper. 

 

2.          There is no open tour for a (1,2) leaper on a 4 x 4 board.

Proof A: Examine the black  points and grey  points of diagram 3.  The corner grey  points are adjacent only to the interior grey  points, the same applies to the black  corner points.  A closed tour is thus impossible, since these two colours are closed to the rest of the board.   However, we have the leeway of a spare move at the beginning and end of an open tour.  We can start with a black corner, eventually make a move from a black  interior point to the dot  points and clear  points, move to a grey interior point, and finish the tour.  Unfortunately, it is impossible to move directly from a dot point to a clear  point.   So an open tour is impossible. 

Proof B:  This proof exploits the idea of Proof 1.  Colour the outer columns as shown in diagram 4.   A closed tour is impossible, as described in Proof 1.   However, an open tour is possible on a 4 x n board, provided the move sequence looks something like the following: grey white grey...white grey grey-white ... grey white grey.   If we colour the top and bottom rows, we reach the same conclusion.  Combining these, a tour is possible as long as we move from a white point in diagram 5 to another white  point.   This is impossible.

3.          There is no open tour for a (1,4) leaper on an 8 x 8 board.  Proof A: Examine diagram 6.  Borrowing a term from Cartesian coordinants, examine the eight black points in the first and third quadrants.  They are adjacent only to black points in the second and fourth quadrants.   Similarly, the grey points in the second and fourth quadrants are adjacently only to grey  points in the first and third quadrants.  From here on, the proof is identical to the proof in 2A.

Proof B: Colour the board as shown in diagram 7.   The grey points are adjacent only to clear and dot  points.   The closed tour is impossible, see proof 1.   An open tour might be possible if we move from a non-grey point to a non-grey point midway through the tour.  Rotate the diagram 90 degrees, and make the same observations.   A tour is possible if two dot points are tour-adjacent.  But they aren’t, so there isn’t an open tour. 

4.  There is no open tour for a (2,3) leaper on an 8 x 8 board.
Proof: In diagram 8, each grey point has degree 2, unless it marks the beginning or end of a tour, in which case it can have degree 1.  The grey points are adjacent only to dot points.  The grey points require at least (14*2 +  2*1 = 30) lines, but the dot  points can only accept (12*2 = 24) of these lines.  An open tour is thus impossible.  

4.          There is no open tour for a (2,3) leaper on a 9 x 9 board.
Proof:  In diagram 9, each black point is adjacent to two dot points.  Each grey point is adjacent to at least one dot point.  The black and grey points require at least ( (16*2 + 16*1)/2 = 24)  dot points, but there are only 21 dot  points, so the open tour is impossible.

   A similar colouring scheme is useful for showing the impossibility of (a,b) leapers on small boards.

6.  There is no open tour for a (2,3) leaper on an 11 x 11 board.
Proof:  First, note that this is an odd board.  Due to parity, the grey points and X points can neither begin nor end the open tour.    Next, note that the X points are adjacent only to dot points and squiggle points.   During the course of the tour, we must have the sequence squiggle X dot X squiggle four times.   Now look at the grey points.   As far as the tour is concerned, the grey points cannot be adjacent to dot points, so they must be adjacent to the greydot  points.   Since each grey point has degree two, we have a closed loop: grey greydot grey greydot grey greydot grey greydot.    The tour is impossible.

   This problem was first solved by Dan Cass.

7.              There is no open tour for a (2,3) leaper on a 12 x 12 board.  Proof: First, note that a closed tour is impossible.  Each greysquiggle point has degree 2 and is only adjacent to dot  points.  There are 36 greysquiggle points and 36 dot  points, and thus we have a closed system.

   Now then, using the methodology in Proof 1, note that the gray-shaded points are adjacent only to the white-shaded points.   Turn the diagram 90 degrees and note the same thing.   Combining, an open tour is possible only if we can move from a dot point to a dot point midway through the tour.   We can!   But this use of the only free move leads to the same closed system described above.   Thus the open tour is impossible.  

 

 

Warnsdorff’s rule

In the beginning of the 19th century a practical method for solving the KTs tour emerged.    In “Des Rösselsprungs einfachste und allgemeinste Lösung”

 (Schmalkalden, 1823) H. C. Warnsdorff presented his method of constructing KTs tours.

The aim is to avoid creating dead ends - cells from which the KT cannot get further without getting to an already visited cell.   For that reason the possible cellss to be chosen next are examined before every move.   One counts the number of free new choices - entrances - every one of them has, and then moves to the square with the lowest number of new choices. (Example see [1] ). 

Warnsdorff’s rule is heuristic.   Theoretically there are objections [2], but on a normal 8*8 cell board the rule works just fine.  

The Java applet on this page demonstrates the efficiency of Warnsdorff’s rule:

1.    Click on any starting cell of your choice (mouse left).  The numbers of free entrances to the cellss of the next legal move will be displayed.   Click on the one with the lowest number, and continue this way until the whole board is covered and the KTs tour completed.   In many cases there are equal choices and sometimes one might spare a cell with the lowest number (in order to have it as the end cell of a re-entrant tour).   There is a certain limited freedom of choice, but cellss with one entrance are due to be visited at once - otherwise they will turn into dead ends.   One such cell can serve as ending cell for the whole tour, two means trouble.  

2.    Back: Click with mouse right on an already visited cel, and the tour will be shortened so that the move from that cell can be redone.  

Try it and discover how easy it is to solve the KTs tour with the help of Warnsdorff’s rule! 


1. Example: Take a look at a cell in a corner of the board.   From such a cell a KT can jump to only two other cells.   And the cell in the corner can be reached only from these two other cells - the cell in the corner has two “entrances”.   When a KT during a tour happens to visit any of these entrances, it is almost bound to visit the corner cell next.   If the KT doesn’t do that, it has used up one of the two free entrances of the corner cell - and thus turned that cell into a dead end; the corner cell can still be reached later, but there will no longer be any unused way out.  During a KTs tour the number of free entrances to all cells of the board are gradually used up.   Warnsdorff’s rule serves to direct the KT to the cells with the least numbers of free entrances left - before these cells have turned into dead ends.  

2. Warnsdorff’s rule gives solutions, but not all possible solutions (One can make moves opposing the rule and yet get a complete tour).   The rule possesses a trait of arbitrariness; there is often a choice between equal alternatives.   And on really big boards the rule runs into trouble.   Warnsdorff scarcely had the possibilities to explore this, but Arnd Roth at the Max-Planck-institut für Medizinische Forschung presents an investigation of this in "The Problem of the Knight" 

© 1999 Gunno Törnberg


 

[Magnus Ludus][visit our sponsor]

[Knights' Tourney]

A strategy game for you and your computer

Take the Challenge

A chessboard is set with two KTs: one black, one white.   Yours is the white KT and you take the first move.   You alternate turns with the computer, but you lose if it’s your turn and you can’t move.   Sounds easy, right?  

The pieces move just like knights in ordinary chess, but the trick is that cells disappear from the board when pieces pass through them.   Once you’ve been to a cell, neither you nor the computer can go there again.  

One strategy is to try and stay free so that you’ll never be caught without a possible move.   Another is to try and head off the computer KT so that it will be left without anywhere to go.   The computer does a little of each and plays a decent game.  

Click Here to Play On-line

Once the game is loaded, you simply point and click on the board to move.   After the game ends, click the red button to play again.  

KTs’ Tourney requires version 5 of Macromedia’s Flash Player.   If you don’t have the plug-in, you can download it for free. 

About this Game

The KTs Tour is a classic logic puzzle in the form of a chess problem: Is it possible for a chess KT to move through every cell on the board without revisiting any? The answer for the usual 8 x 8 chessboard is yes, but the general question for arbitrary board sizes has interested mathematicians working in the area of graph theory.   See, for instance, Mark Keen's paper on the subject. There are several on-line implementations of the original problem.  

KT’ Tourney is a two-player generalization of the KTs Tour which has been suggested by enough people that it’s hard to name one inventor.   This implementation of it is ©2001 by P.D. Magnus.  

[Magnus Ludus][Email me!] 

8 Queens Chess Puzzle

Active Chess Web

Banchi

Caissa's Web

CChess

Chess for Internet

        Chess Player

ChessLive!

DeepFrozen

Duchess

Ex-Chess!

Futuretouch Java Chess

Gentle Bishops Puzzle

Grand Chess

iChess

InternetChess

Java Chess server with sounds

Java Network Chess

JavaChess-01  JavaChess-02

JavaChess version 2

Knights Tour Chess Puzzle

NetChess

Solving the 8-queen problem

The Chess

Virtual Chinese Chess

WebChess (Gnuchess)

Xiang Qi - Elephant Chess

 

CoffeeHouse - Java interface to Internet Chess Club
 
Grandmaster Java Chess Viewer

If you can’t see the frames at the left please click here

This page was designed and is maintained by David Roberts, d@dial.pipex.com
©1997, 1998 David Roberts.

 

 

Links to More Knight Tours

www.BordersChess.org/KnightTour.htm

http://www.ktn.freeuk.com/

homepages.stayfree.co.uk/gpj/ktn.htm

www.velucchi.it/mathchess/knight.htm

enchantedmind.com/puzzles/knights/knight.htm

www.helsinki.fi/~vahaaho/KnightsTour/tour.html

www.helsinki.fi/~vahaaho/KnightsTour/doc/doc.html

student.lssu.edu/~gbharadw/java/knight.html

www.tcp-ip.or.jp/~toshio-t/K_tour.html

w1.859.telia.com/~u85905224/knight/knight.htm

w1.859.telia.com/~u85905224/knight/knight.htm

w1.859.telia.com/~u85905224/knight/eknight.htm

home.earthlink.net/~tfiller/knight.htm#

www.worle.com/chess/solution.htm

www.worle.com/chess/knight.htm#top

www.tri.org.au/knightframe.html

members.attcanada.ca/~ptah/knights.htm

www.inficad.com/~ecollins/knights-tour.htm

 

www.npac.syr.edu/projects/tutorials/Java/examples/KnightTour/Knight.html

www.mactech.com/articles/mactech/Vol.14/14.11/TheKnight'sTour/

www.delphiforfun.org/Programs/knight's_tour.htm

www.uweb.ucsb.edu/~rjr/KnightsTour.html

mail.stuy.edu/pipermail/csteam/2000-October/000001.html

hercule.csci.unt.edu/~ian/papers/knight2.html

hercule.csci.unt.edu/~ian/papers/knight3.html

www.wordways.com/knights.htm

www.theory.csc.uvic.ca/~cos/inf/misc/Knight.html

ourworld.compuserve.com/homepages/John_Katrin_Sharp/Articles.htm

www.mathpuzzle.com/leapers.htm

www.reflexive.net/james/OldSoftware/

www.hctc.com/~dtriplet/link.htm#Puzzles

mathworld.wolfram.com/KnightsTour.html

mathworld.wolfram.com/KnightsTourGraph.html

www.math.niu.edu/~rusin/known-math/99/knights

www.markkeen.com/knight.html

www.singaren.net.sg/DAC/projects/magic.html

www.behnel.de/knight.html

www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html

www.combinatorics.org/Volume_3/Comments/v3i1r5.html

cs.anu.edu.au/~bdm/papers/knights.ps.gz

www.ex.ac.uk/~dregis/DR/tour2.html

 

Hi, You asked if I could give you a link.  I would like to share http://www.borderschess.org/KnightTour.htm (The Knight's Tour).  KnightTour.htm  is in English and in German in order to reach a larger audience.  It describes how to solve open and closed knight tours along with other interesting knight tour puzzles such as closed knight's tour cube, magic/semi-magic squares, tessellations, and knight's tour art.  You will find many new items and updates on my web page that will enhance your Chesmayne Chess Dictionary.  Please feel free to make the necessary changes and updates to your section of Knight - Tour in your dictionary.  You may want to change the reference of Knight - Tour on http://chesmayn.valuehost.co.uk/K.htm to "Knight - Tours". Also, on http://chesmayn.valuehost.co.uk/Knights-Tour.htm, please change the title of "Knights Tour" to "Knight Tours".  I have a new title banner and home-made navigation buttons for each page on KnightTour.htm.  Feel free to copy them for your use.  I've made several corrections to many of my web pages.  Please update your site with the new changes.  Nice Site you have at  http://chesmayn.valuehost.co.uk.  I think it will become very successful on the Internet.  Cordially, Dan. 

 

If you get a chance, take a fresh look at my Knight Tours web site:  www.borderschess.org/KnightTour.htm to see many new items.  I am applying for a patent on Springer Geometry.  Springer is the German word for "Knight" in English.  Springer Geometry is the geometry of polygons created by closed knight tours.  I hope you enjoy my new additions.  A patent search has already been completed, so now the patent attorney is ready to send my ideas in for a Utility Patent.  I am currently preparing information to send to Springer-Verlag, a math & science book publishing company, to see if they would be interested in publishing a book about my Knight Tours and Springer Geometry.  Their logo is the chess knight.

 

I've also finally decided to let my computer solve additional knight tours using Mathematica and code written by Dr. Colin Rose and modified by Michael Taktikos from Germany, and from myself.  The code has solved all unique 6x6 closed knight tours (9862 total).  I have included printouts on my web site of various other closed and symmetrical tours for smaller size boards.  Anyway, check it out and see if you like the new stuff.  Let me know if you have any ideas, comments, or criticisms.

 

Keep in touch.  Cheers,

 

Dan  

Links to More Knight Tours

www.BordersChess.org/KnightTour.htm

www.ktn.freeuk.com

homepages.stayfree.co.uk/gpj/ktn.htm

www.velucchi.it/mathchess/knight.htm

enchantedmind.com/puzzles/knights/knight.htm

www.helsinki.fi/~vahaaho/KnightsTour/tour.html

www.helsinki.fi/~vahaaho/KnightsTour/doc/doc.html

student.lssu.edu/~gbharadw/java/knight.html

www.tcp-ip.or.jp/~toshio-t/K_tour.html

www.npac.syr.edu/projects/tutorials/Java/examples/KnightTour/Knight.html

w1.859.telia.com/~u85905224/knight/knight.htm

w1.859.telia.com/~u85905224/knight/eknight.htm

home.earthlink.net/~tfiller/knight.htm#

www.mactech.com/articles/mactech/Vol.14/14.11/TheKnight'sTour/

www.worle.com/chess/solution.htm

www.worle.com/chess/knight.htm#top

www.tri.org.au/knightframe.html

members.attcanada.ca/~ptah/knights.htm

www.inficad.com/~ecollins/knights-tour.htm

www.delphiforfun.org/Programs/knight's_tour.htm

www.uweb.ucsb.edu/~rjr/KnightsTour.html

mail.stuy.edu/pipermail/csteam/2000-October/000001.html

hercule.csci.unt.edu/~ian/papers/knight2.html

hercule.csci.unt.edu/~ian/papers/knight3.html

www.wordways.com/knights.htm

www.theory.csc.uvic.ca/~cos/inf/misc/Knight.html

ourworld.compuserve.com/homepages/John_Katrin_Sharp/Articles.htm

www.mathpuzzle.com/leapers.htm

www.reflexive.net/james/OldSoftware/

www.hctc.com/~dtriplet/link.htm#Puzzles

mathworld.wolfram.com/KnightsTour.html

mathworld.wolfram.com/KnightsTourGraph.html

www.math.niu.edu/~rusin/known-math/99/knights

www.markkeen.com/knight.html

www.singaren.net.sg/DAC/projects/magic.html

www.behnel.de/knight.html

www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html

www.combinatorics.org/Volume_3/Comments/v3i1r5.html

cs.anu.edu.au/~bdm/papers/knights.ps.gz

www.ex.ac.uk/~dregis/DR/tour2.html