Knights On A 5x5 Chessboard

Contributers | The Puzzle | The Program | Analysis | Software Solutions

Introduction

The knights puzzle is an beautiful puzzle. It is a single player game, played on a 5x5 chess board with several knights. The search for an optimal solution turned into a mini project for me and some others around the world. I first saw this puzzle in an old PC game called "The 7th Guest" but it may have originated elsewhere. In that game you only had to solve the puzzle but I was more interested in finding an optimal solution (minimum number of moves) and in enumerating all minimal solutions. A close group of friends and I first tussled with the problem for a week or so in May 2000. I was after an analytical solution but was unable to make many inroads in that direction, so we resorted to looking for software solutions as the next best thing. Surprisingly we ran into snags there as well. I then posed the problem to the Usenet group rec.puzzles and was pleasantly surprised by the response. Presented below is a collation and summary of all the results and discussion of this puzzle. As always, I give credit where due. If I've missed any contributers please let me know so I can rectify the oversight.

To my knowledge, a general solution to this puzzle is still very much an open question. Analysis is still thin and underdeveloped and not enough is known to extend the puzzle to arbitrary odd dimension. If you have insights of any kind into this puzzle please email me. I will be delighted to add your contribution to this page. It would be nice to see the problem wrapped up with an analysis along the lines of Donald Knuth's brilliant paper on Leaper Graphs (generalised knights tours on an mxn chessboard).

Contributers

The following people contributed in some way to understanding this puzzle and its solution. Many of them can be found lurking somewhere around rec.puzzles.

Name or Alias Email Web Site
Gene Wagenbreth genew@netcom.com -
Hugo van der Sanden hv@crypt0.demon.co.uk http://crypt.org/hv/puzzle/index.html
James Dow Allen jamesdowallen@yahoo.com http://freepages.genealogy.rootsweb.com/~jamesdow/
Justin Leck justin_leck@my-deja.com -
Niels L Ellegaard gnalle@dirac.ruc.dk -
Peter Ellis peter_ellis@optusnet.com.au -
QSCGZ qscgz@aol.com -
Rich Grise richgrise@vel.net -
Tim Morrow tmorrow@iinet.net.au http://members.iinet.net.au/~tmorrow/ (you are here now)
Wayne Kerr - -

The Puzzle

Consider a configuration of 12 white and 12 black knights arranged on a 5x5 chessboard. Using only knight moves, you need to interchange the black and white knights. Graphically you need to convert from

Starting Configuration Of Knights Puzzle into Final Configuration Of Knights Puzzle

In the above diagrams you will have to imagine the black disks are black knights and the white disks are white knights (sadly, drawing the horsie is far beyond my artistic talent).

Now it isn't that hard to achieve this feat in say 60 or more moves. However, I want you to achieve this transformation in the minimum number of moves possible. Furthermore I want to know in exactly how many ways a minimal solution can be found. I'll give you a big hint (more details later) that may surprise you:

There are 36 moves in a minimal solution.

The Knights Game Program

Thanks to your truely and to a good friend of mine who goes by the handle Wayne Kerr, we are able to provide a Windows 32 bit program that can be used to play the game. See if you can produce a 36 move minimal solution. The program should comfortably run on any standard Windows or NT Operating System. There are no fancy frills - just the basics. You can move by dragging and dropping or by double clicking. Under options you can select player=computer and watch the computer play back some of the 1200 minimal solutions to this game.

I am ashamed of the source code so won't supply it at this stage, at least not until it is cleaned up significantly. There are several improvements that I would like to make to the code - recording player moves, playback of selected sequences, undo, saving etc. that may not ever get done.

The following Knights Program is provided as is with no guarantees. I have not intentionally placed any viruses / trojans or any other malicious code into the program. You should however thoroughly virus check all of the downloaded software. No registry keys are used. It is largely untested on several hardware / software environments and I can take no responsibility for what may happen when you run it. The worst thing I could image it doing is failing to run. You are on your own in any event. Download KnightGame.zip (29 KB).

Analysis

Most of what follows are my own analytical results about this puzzle. Some of the results were motivated by empirical results obtained by computer aided analysis and solutions provided by others.

Result 1

There are 67603900 states (board configurations) for the 5x5 knight game.

We can derive this by noting that there are 25 distinct locations for the empty square. If you then consider the 12 white pieces then you can place them on the 24 remaining squares in C(24,12) ways, the 12 black knights can only be placed in the remaining 12 squares in 1 way. We therefore have 25*C(24,12)*1 = 67603900 distinguishable states.

By using an identical argument for the generalised knight game on a (2n-1)x(2n-1) board with 2n(n-1) white and black knights, the number of states is an astonishing, astronomical (2n-1)^2*C(4n(n-1),2n(n-1)).

Taking the 7x7 board with n=4 we have 49*C(48,24) = 1580132580471900 distinguishable states. You can see how quickly the number of states grows with board size.

While the 5x5 knight game may be amenable to a computer exhaustive search, it is clear that there is no hope for exhaustively solving the larger dimension games without some extra tools and analysis at our fingertips. It is known for the 5x5 game that all states are reachable. It is likely but not proved that this result is true in the general case. Some of the following results are specific to the 5x5 knight game and will not generalise to higher dimension.

Result 2

Let T denote the number of moves in any solution to the knights puzzle. T is even for every solution including a minimal solution.

This is a property of knight moves. The empty square changes colour from move to move (white, black, white etc). Every second move places the empty square on the same colour as the starting colour. The empty square must end in the middle (where it started) which can only occur after an even number of moves.

Even a small result like this is useful and helps make the problem more tractable. The next result gives us a lower bound.

Result 3

The minimal number of moves T in a solution is at least 30.

Empirical evidence shows that the correct minimum is T=36. I will demonstrate this weaker minimum through some analysis specific to the 5x5 board and then improve upon it after establishing some other results.

Firstly, I need to introduce some notation. One way to refer to the knights and positions on the 5x5 board is to use coordinates (0,0) for the top left corner through to (4,4) in the bottom right corner. It is often easier to translate this to the numbers 00-24 via the mapping f(x,y) = 5x + y. We can then track the knight moves by following the empty square by a sequence of numbers a-b-c-... meaning the empty square moves from a to b to c to ... See the first diagram below. Note that white squares are even and black squares are odd and that 12 is the centre square.

Now consider the black pieces. They have to all move from top-left half to the bottom-right half of the board. Ignore the white pieces completely for now, pretend they are not on the board. Consider the 4 positions on the board indicated by A, B, C, D in the second diagram below.

00 01 02 03 04          A x x x x 
05 06 07 08 09          B x x x x
10 11 12 13 14          x x   x x
15 16 17 18 19          x x x x C
20 21 22 23 24          x x x x D

Moving the black knight at A to the lower-right half-board requires a minimum of 2 moves, by one of the 6 sequences of moves in the first list of moves below.

Moving the black knight at B to the lower-right half-board requires a minimum of 2 moves, by one of the 8 sequences of moves in the second list of moves below.

Moving a black knight to C requires a minimum of 2 moves, by one of the 8 sequences of moves in the third list of moves below.

Moving a black knight to D requires a minimum of 2 moves, by one of the 6 sequences of moves in the fourth list of moves below.

00-07-04          05-02-09          01-08-19          02-13-24
00-07-14          05-02-13          01-12-19          06-13-24
00-07-18          05-12-09          03-12-19          06-17-24
00-11-08          05-12-19*         05-12-19*         10-17-24
00-11-18          05-12-23          11-08-19          16-13-24
00-11-22          05-12-21          11-22-19          20-17-24
                  05-16-13          15-12-19
                  05-16-23          15-22-19

Note that the sequence marked with * above accomplishes both B and C objectives. Thus at a minimum, 3 black pieces must make at least 2 moves and the remaining 9 pieces must make at least 1 move in their transition to the lower-right half-board. In total at least 3*2+9*1=15 moves are required. The same argument applies to moving the 12 white knights to the upper-left half-board. Thus any solution requires a minimum of 15+15=30 moves.

In the above argument we have ignored any move hampering restrictions due to having the 'other colours pieces' or even the same colour pieces in the way at various stages during the exodus from initial to final state. We will need another result before we can improve our lower bound on T.

Result 4

Define W = sum(w_i) and B = sum(b_i) where w_1 - w_12 denote the number of moves made by the 12 white knights in any solution to the puzzle. The b_i's are defined similarly. W and B are both even.

T = B + W and T is even by Result 2 so B and W are both even or both odd. Now I'll demonstrate that neither B nor W can be odd.

If W is odd then at least one of w_i's is odd (in fact an odd number of the w_i's must be odd). Suppose x of the odd w_i's start on white squares and y of the odd w_i's start on black squares with x+y odd. We also have 6-x even w_i's on white and 6-y even w_i's on black initially. After moving we have

This implies that x + y = 2x is even which is the desired contradiction. Therefore B and W are both even. A corollory to this is that any solution of the knight puzzle must contain an even number of odd moves for white pieces and for black pieces. Further, the knights with odd moves must be evenly distributed b/w knights on white squares and knights on black squares.

It turns out that 16 moves are sufficient to transport the knights of one colour to the other half of the board. However it can only be done at the cost of extra moves by the other colour knights.

Result 5

An improved lower bound. The number of moves in a minimal solution to the puzzle T is at least 32.

From Result 3 we know that W is at least 15 and from Result 4 we know that W is even. We therefore conclude that W is at least 16 (even number). Similarly for B. Then T = W + B is at least 32.

Cycles

The following thoughts on cycles are from Hugo van der Sanden. I have been unable to utilise these ideas yet. Hugo's discussion uses computing terms because he was thinking of the problem in the context of software implementation.

I wonder whether this becomes more tractable if you enumerate cycles that leave the gap at the centre, and compose such cycles to find solutions.

Since the 2-move cycle has no effect, no cycle shorter than 4 moves need be considered; that means no more than 9 cycles involved.

Every location must be touched by at least one cycle for it to be a solution, so most compositions can be discarded without even looking at the resulting position - represent each cycle as a 24-bit string of the locations touched, and bitwise-or the strings to check that all locations are reached.

Each cycle is fully represented by a 24-element transition vector, so checking the resulting position is fast.

The symmetries of each cycle - both the location bitstring and the transition vector - are easily calculated, so you can fix the first move of the cycle when evaluating them. You do need to be careful to avoid repeats though: if the second and penultimate locations are the same, you should discard (by ordering) one of the possible cycles.

I think this approach might allow enumeration of the solutions efficiently in both time and memory. The only drawback is that I don't know how many cycles there are: the number of 36-cycles might be very large. In any event, you might need to do some pruning of trivialities during their evaluation. At a quick count there seem to be 2 primitive 4-cycles and 26 6-cycles (of which one pair is symmetrical), so the numbers may well get too large for longer cycles.

More Cycles

I now include a contribution from Niels L Ellegaard that utilises cycles. Neils doesn't quite solve the puzzle but suggests a way you might be able to think about the problem that could help if taken further.

My guess would be examining two cyclic motions Starting from the starting point, 0 we can move 0,a-b .... a,0. Doing this will exchange blacks and whites on the fields b-p. The problem is the original pawn that was placed on the field a. We must find some way of disposing of it in the right way, but somehow this should be possible.

Somewhere in the middle of cycle above (b,f,j or n) you should be able to switch to the following cycle 1-8:

* a f k *          2 * * * 8
g l * p e          * * 1 * *
b * 0 * j          * 3   7 *
m h * d o          * * 5 * *
* c n i *          4 * * * 6

Performing this 8 times will switch the pawns 2-8, but again we must find a way of disposing of the original pawn of field 1. I hope this article can serve as inspiration.

Miscellaneous Observations

I'll finish this analysis section with some miscellaneous observations, speculations and open questions that I haven't yet formalised at this stage. If you have any thoughts please let me know.

  1. In any length 32 solution the 12 white (and 12 black) pieces will be of the following types:
    1. 4 pieces moving 2 and 8 moving 1, which we can denote by (1^8,2^4)
    2. 1 piece moving 3, 2 moving 2, 9 moving 1, i.e. (1^9,2^2,3^1)
    No other combinations are possible. It may be possible to determine more by considering the C(12,4) permutations of (1^8,2^4) and the C(12,1)*C(13,2) permutations of (1^9,2^2,3^1).
  2. If it can be shown analytically that no solutions of order 32 exist, then from the above results it is clear that one of the conditions W at least 16 or B at least 16 must change. i.e. W at least 18 or B at least 18 (but not both).
  3. Since empirically we know that T=36 then all minimal solutions must be of the form:
    1. W=16, B=20 - asymmetric solutions
    2. W=18, B=18 - symmetric & asymmetric solutions
    3. W=20, B=16 - asymmetric solutions
    By symmetry there are as many solutions of type (a) as of type (c). Thus the minimal solutions divide into two classes.
  4. What can we say about the empty square? How often does it have to visit the centre? Justin Leck worked out empirically that the answer is 4. Does the empty square visit both sides of the board equally often (probably not).
  5. Do minimal solutions have the property that the board state at each successive move is either as good or better than the previous state under the criteria of "the number of knights in the correct half of the board"?

Software To The Rescue

An Excellent Undergraduate Programming Problem

The 5x5 knights puzzle was ultimately solved in software. At least half a dozen people developed software solutions of varying degrees of sophistocation, from my humble code that takes a couple of days to run to completion to some highly efficient code written by others that can find solutions in under a minute. Some people were generous enough to provide url's to their code (links provided below). I'm not sure how long those links will last.

The 5x5 knights puzzle implemented in software is not a trivial task. Most first attempts invariably fail due to limited memory or ability to run to completion in reasonable time. Several methods have been used to search out the state space for the problem ranging from depth first, breadth first, depth first with iterative deepening, hashing.

An exhaustive search without removing duplicates is doomed to failure within 10-15 moves due to space restrictions. Removing duplicates without an O(1) algorithm like hashing is hugely inefficient and you are unlikely to get past depth 25 in a breadth first search before the day is out.

Due to memory restrictions most attempts at solution require some form of packing the board state into a bit string in some way. Saving the data out to disk was considered and used by some as a way of managing the large number of states that accumulated during the search.

In short I believe the 5x5 knights puzzle implemented in software to be an ideal undergraduate computer science project, especially in a subject like Algorithms and Data Structures.

The contributions below are roughly chronological. All software is written in C.

My Software Solution

After a week of coding and several aborted searches I was able to come up with a 42 move solution. I had sandwiched the number of moves in a minimal solution to an even number between 34 and 42. My program was taking over a day to run.

I provide a link to my source code but you would be well advised to look the other links to source code instead as mine is a shambles. My source is a mixture of solution attempts within the same source code - some commented out, others not. It was compiled in Visual C++ 5.0 and the current size of the state array requires at least 128Mb ram and 256Mb swap space to run. I honestly don't know in what state I left it. I provide it only because it may furnish some ideas.

You can view my code here or instead, download it here.

Hugo's Software Solution

It was about this time when Hugo stepped in and innocently announced that he had discovered a 36 move solution but hadn't been able to record it yet. His second program produced the solution. I believe this achievement to be the first of three major breakthroughs in the solution of this puzzle. We all now knew the answer and could start tailoring our programs to look for 36 move solutions. Hugo also provided an excellent, informative minimum move table of how many states were reachable after n moves which I will discuss a little later. A few days later I produced the first asymmetric 36 move minimal solution after being armed with some information on how to beef up my program.

Hugo van der Sanden's Contributions (in his words over several posts)

The code I've written for this currently peaks at around 80MB, expected to come down to 72MB in the next iteration. This consists of a packed array of 25*C(24,12) 5-bit locations, representing the location of the gap at the previous move (40.3MB), an array of ints listing the positions still to be tracked from (which peaks around 28MB) and sundries. Unfortunately I only have 64MB here, so the process spends most of its time swapping - it takes well over an hour to run, instead of the 20 minutes or so that I think it would otherwise take.

The program claims a shortest solution in 36 moves, but I haven't yet managed to debug the process of printing the results, so I can't validate the claim.

Bringing the memory requirements down should speed the debugging process; the next step is to store 4 bits instead of 5, by taking advantage of the fact that there is at most a choice of 8 locations we can have moved from to any position, plus the marker value for positions never reached. (It is even possible to reduce the storage requirement to 3 bits, and add some cleverness on backtracking to decide on which choice to go for in the odd pair of cases.)

Here is the solution: label the locations 0 to 24, starting from left to right across the top row. Then the location of the gap in successive positions is:

12-01-08-11-22-19-12-03-14-07-00-11-20-17-06-13-02-09-12-
15-22-11-18-07-04-13-24-17-10-21-12-05-02-13-16-23-12

The current code, now 298 lines, including some explanatory notes, available at http://crypt.org/hv/puzzle/kswap.c

Additional notes: I compiled the code with 'gcc -g -O6 -o ksw4bit kswap.c'; every indent is a tab, which I usually set to 4 spaces.

After processing all positions for move n, the number of entries in the list represents the number of positions that can be reached in n moves _and no fewer_. Here is the number of positions reachable after n moves:

n      #states    Cumulative
00           1             1
01           8             9
02          14            23
03          38            61
04         148           209
05         368           577
06        1001          1578
07        2440          4018
08        6468         10486
09       14116         24602
10       32825         57427
11       64782        122209
12      137262        259471
13      240404        499875
14      455522        955397
15      716458       1671855
16     1224370       2896225
17     1720894       4617119
18     2645274       7262393
19     3327210      10589603
20     4594399      15184002
21     5148132      20332134
22     6372557      26704691
23     6345924      33050615
24     6997217      40047832
25     6160052      46207884
26     6002337      52210221
27     4635014      56845235
28     3942462      60787697
29     2634392      63422089
30     1921476      65343565
31     1086234      66429799
32      658300      67088099
33      300838      67388937
34      144842      67533779
35       49078      67582857
36       17065      67599922
37        3428      67603350
38         488      67603838
39          62      67603900 = 25*C(24,12)

I was very impressed with Hugo's reachable state table. It shows that there are some states that aren't reachable until 39 moves. It also shows that the most states added occurs at depth 24.

Gene Wagenbreth's Break Through

What follows is what in my opinion is the second most important break through in solving this puzzle. This observation is a huge simplification and is big time and space saver for any software solution. I believe Gene Wagenbreth first offered the raw idea and it was first implemented in some brilliant code by James Dow Allen that utilised dynamic hash tables and other speedups. I present a link to James' website below where he presents his code and implementation notes. My first thought on the '1/2 moves trick' was that it would be a shortcut for finding some minimal solutions to the puzzle but would miss some of the asymmetric solutions. In fact this gem of an idea can be extended and utilised to find all solutions.

I have been following this thread with some interest. Unfortunately I have not had the spare time to code a program yet, so you guys beat me to it.

One question. The final position is symetrical with respect to the initial position. That means that in a 36 move solution, after the 18th move you must reach a position that is 18 moves from the finish. The finish position is just the start position with W and B switched. So if you take all the moves reachable in 18 moves and compare them with the same positions with W and B switched, you should get a match. So you only have to do 18 moves to find a 36 move solution.

Does this make sense and would it speed things up?

James Dow Allen's Software Solution

I also wrote a program to solve this problem, and posted it on my website. My program discovers the 36-move solution on my 32-megabyte PC in just 15 seconds!! I've posted the source code and a discussion at http://freepages.genealogy.rootsweb.com/~jamesdow/progex1.htm

My interpretation of the 1/2 moves trick

I've given some thought to the trick of only considering half the moves and its implications.

Generate all states from initial position s out to depth 18. Using Hugo's email of cumulative totals this means you will generate 7262393 states in your minimal move array. Call this set of states S. Let the subset of states at depth 18 be denoted S18. There are 2645274 states in S18 (again from Hugo's totals). S\S18 contains 4617119 states.

Now at the same time, generate all states from the final position f out to depth 18. By symmetry you will generate 7262393 states when you do this. Call this set of states F. Let the subset of states at depth 18 be denoted F18. There are 2645274 states in F18. F\F18 contains 4617119 states.

Now the only solutions will be obtained from connecting S18 and F18 i.e. S18 intersect F18. Now the interesting result is that there is at most 4617119 + 4617119 + 2645274 = 11879512 states that could be part of any minimal solution to the puzzle. In fact the number will be much, much less but I can't simplify it any further at this level of analysis. i.e. 82.4% of the states could never be part of any minimal solution. The memory requirements for the problem come down considerably don't they?

Justin Leck's Software Solution

At about the same time Justin Leck produced the third most important breakthrough. He wrote an awesome program and was able to completely enumerate all minimal solutions. Justin discovered all 1200 minimal solutions to the puzzle. Justin then went on to establish several properties of the solutions that helped give a deeper insight into the puzzle. I too have knocked together a solver for this problem and confirm the minimum to be 36 moves. It won't break any speed records, but it seems to do the job (took about 2 hours to find the solutions). The program also only requires about 68Mb of RAM. Assuming program correctness, the results were: 1200 solutions with 36 moves. Here's the first (squares numbered 0-24, 0 being top right, 24 bottom left):

(09->12) (02->09) (13->02) (06->13) (17->06) (24->17) (13->24) (16->13) (05->16)
(12->05) (01->12) (08->01) (11->08) (22->11) (19->22) (12->19) (03->12) (14->03)
(07->14) (00->07) (11->00) (20->11) (17->20) (10->17) (21->10) (12->21) (15->12)
(22->15) (11->22) (18->11) (07->18) (04->07) (13->04) (16->13) (23->16) (12->23)

Notes: After 36 moves you can reach 67599922 out of the 67603900 possible states.

First moves (5->12), (19->12) can't yield a solution in 36 moves. The other 6 can.

[QSCGZ] what's Solns ? How does your program work?

Solns is the number of solutions that each program displayed. I assumed that James's program produced half a solution, because it outputs the state of the board at move 18 (That's what the asterisk was for). I now realise that he has in fact considered all 36 moves. Displaying the full solution requires his program to be run 34 times, with the execution time differing, depending on how many moves the program has to consider. Even so, his is still the quickest solver.

I took the easy approach in writing a solver and used two stages. There are 67603900 possible board states, so I have an array of this this size. The first stage involves filling in the array with the minimum number of moves to reach a specific state from the initial board state. If I understand Hugo's definitions correctly, I used a breadth first approach to fill in the array.

Stage two involves using a depth first search to walk through the minimum move array, starting from the end position to the start position. While searching through the array, the various moves are collected and the set of moves is displayed when the intial position is found. It also backtracks so that all possible solutions are displayed.

I have implemented these two stages as two different programs, with the first stage dumping a 67Mb file to the hard disk. The second stage is fairly quick (about 1 minute), and has the advantage that it can dump the set of minimum move solutions from _any_ ending position to the starting position, without the need to perform the first stage again.

The 16Mb space reduction comes from the fact that I use a byte to represent the move number. A 6 bit number could be used instead, so saving (67603900 / 4) bytes, at the expense of greater complexity and slower execution speed. Writing the program in assembler would probably halve the execution time as well.

Not writing out the state array to the hard disk will save about a minute. The programs do an awful lot of conversions from a state number (long word) to a 5x5 array representing the board and vice-versa. The various permissible moves for each gap position could also be precalculated. Implementing these would probably halve the execution time.

I've been waiting for someone else to enumerate all the solutions and verify my findings.

The 1200 solutions my program has found should be all the solutions. I've thought about posting 600 solutions (the 600 can be recreated by playing the other solutions backwards), but the size is still about 59Kb. Here are some stats on the solutions:

1200 solutions in total, 56 of which are totally symmetrical.

Number of times the gap is on a specific square:

Solns Once Twice Thrice Fourfold
1200  18   4     2      1

1 1 * 1 1
1 1 2 * 1
1 3 4 3 1
1 * 2 1 1
1 1 * 1 1

* = These squares either have the gap once or twice

Number of moves for white / black knights

Solns White Black
360   16    20
480   18    18
360   20    16

Number of times a specific knight is moved:

Solns Once Twice Thrice
864   12   12    -
320   13   10    1
16    14    8    2

12 knights move once, 12 knights move twice (Here's a symmetrical one. There
are also many non-symmetrical solutions)

13-02-09-12-21-18-07-14-25-18-11-22-13-10-03-14-17-06-13-
20-09-12-23-16-13-04-15-08-01-12-19-08-05-14-17-24-13

13 knights move once, 10 knights move twice, 1 knight moves three times

13-10-03-14-07-18-25-14-17-06-13-02-09-12-23-20-13-22-11-
18-21-12-23-16-13-04-15-08-01-12-19-08-05-14-17-24-13

14 knights move once, 8 knights move twice, 2 knights move three times
(Symmetrical)

13-02-09-12-23-20-13-22-11-18-07-14-05-08-01-12-23-16-13-
10-03-14-25-18-21-12-19-08-15-04-13-06-03-14-17-24-13

14:8:2 (Not symmetrical)

13-16-23-12-09-20-13-22-11-18-07-14-05-08-01-12-09-02-13-
10-03-14-25-18-21-12-19-08-15-04-13-06-03-14-17-24-13

The above solutions show the position of the gap with the board numbered 1
(top left) to 25 (bottom right)

You can view Justin's code, or instead, download Justin's code. I'm grateful to Justin for allowing me to host his work on my site.

Here are Justin's 1200 minimal solutions. Note that the viewing page is 140Kb of HTML while the zipped up download is only 12Kb. View the 1200 solutions or download the 1200 solutions.

Wayne Kerr's Software Solution

Wayne Kerr was able to duplicate Justin's results and produce the same 1200 solutions using an independently developed program. I am fortunate to be able to present the source code for Wayne's excellent software solution to this puzzle. As with all the source code on this page, it is a "use at your own risk" download. I include Wayne's email on how to use his program.

I can't recall for certain but I think these where the events:

  1. Run knights.cpp with one set of START1 and START2 defines and fopen out set to outputa.txt
  2. Run knights.cpp with the other set of START1 and START2 defines and fopen out set to outputb.txt
  3. Run compare.cpp which will create outputc.txt
  4. Run knightsa.cpp with one set of START1 and START2 defines and fopen out set to outputd.txt
  5. Run knightsa.cpp with the other set of START1 and START2 defines and fopen out set to outpute.txt
  6. Run match.cpp which will create outputf.txt - the set of all 1200 solutions.

Note the two sets of START1 and START2 defines are the starting board state and the ending board state. START1 is the bit state of the board pieces whilst STATE2 is the space position. Outputa.txt and outputb.txt are all the enumerated board states at depth 18. The files will be about 25Mb each. Outputc.txt are the common enumerated board states between outputa.txt and outputb.txt. Outputd.txt and outpute.txt are the two half list of all the moves (I think). Outputf.txt is the final list of all the moves. I suggest you might want to compile and run the above steps to make sure that the above steps are correct. In particular you will probably want to change my hard coded directory paths.

You can view Wayne's code or instead, download Wayne's code.

QSCGZ's Contribution

QSCGZ contributed much to the discussion on this problem. What follows are some of his thoughts and insights into the puzzle. QSCGZ also posed an interesting related puzzle that I haven't had a chance to look at yet.

[Hugo]
(It is even possible to reduce the storage requirement to 3 bits, and add some cleverness on backtracking to decide on which choice to go for in the odd pair of cases.)

[QSCGZ]
You could always calculate all possibilies of -say- 5 continous moves and mark the reached positions with the new iteration number. Whenever during this process , you reach a position marked with an old iteration number, you can backtrack immediately. Or when you find an unexact (e.g. 20-24) iteration number, you can just calculate the exact one (e.g.23) by doing some moves on the fly. So you only need 36/5 = 3 bits for the iteration-numbers but at the cost of speed.

Follow-Up-Puzzles: If we play the position as in chess, who wins? Does white end up with more knights than black? Can he capture all black knights? How many moves are required? What about using other start-positions, other (fairy) chess-pieces?

Rich Grise's Contribution

Rich Grise was generous enough to offer me some tips on how to save the state of my program to disk that could be retrieved later. His ideas were based on a program he wrote to solve Hi-Q.

Well, actually, it's been awhile since I've done any actual programming, but I'd think, depending on how fast it goes, every hundred or 1000 iterations, check the keyboard. If there's a keystroke waiting, check to see if it's the "stop and save" command, then if so, just dump the whole array to a file. Then, depending on OS, load up the next run from the command line, or (in for example VB or probably VC) give a menu option to load the latest pattern.

In my Hi-Q program, I knew that at any level there are only a certain number of moves, and I wrote it recursive / reentrant. So it wasn't hard to pick up where it left off - at any given level, there are a finite number of moves, and all the higher-level moves are in the array. So you'd go to the next move, record it, call the iterator, it'd check all its moves, calling the iterator each time, and when you get to one peg, announce a win. Then, of course, return back up the iteration chain to try the rest of the possibilities. And of course, each iteration or level has its own stack, where it keeps a record of its previous moves. Local variables, actually, but they're stored in the stack frame, at least in 8086 C.

The knight move thing would be a challenge because one would have to figure out a convenient way to order possible moves. Almost makes me wish I had some ambition. Maybe something like,

iteration() { 
  for each piece,
    check available moves. 
    if move is available, 
      do the move.
      check next iteration
    end if
    check if done, etc
  end for
  if (iteration count mod 1000 == 0)
    print progress report
    check for keystrokes;
    if keystroke is waiting,
      if it's the "save and exit" key, then
        save the whole array
        (presumably you'd need a static variable somewhere for this one)
        exit the program;
      }
    }
  }
}

Wrapping It Up

Some people may like to read the posts on this puzzle in their entirety. I provide a zip file of the entire Usenet thread of 44 posts here. The posts are in *.nws format viewable in most news readers and have the numbers 01-44 at the end of the filenames so you can read them in order.

Alternatively you can browse your favourite news archive site like deja-news and search for the thread "Swapping Knights Puzzle On a 5X5 Chess Board". Enjoy!

Contributers | The Puzzle | The Program | Analysis | Software Solutions