Chess Algorithm Optimization

I was asked by a friend if it was possible to have a horse start in any spot on a standard chess board and jump on every square.

I have constructed an algorthim to do the crunching for me. However, it takes more than 2 hours ( I gave up waiting after 2 hours) to go through all the permutations.

Anyone have any suggestions on how to optimise the algorithm so that it takes less time?

For a start I have string concatenation in there which is slow.

If it is not possible with VB, perhaps with c++ or are there simply too many permutations?

Here is the algorithm:

VB Code:

Private Sub Command1_Click()
Dim timeit As Date
timeit = Time
Call KnightMoves(4, 1, ",41,")
Debug.Print FormatDateTime(Time - timeit, vbLongTime)
MsgBox "Finished"
End Sub
 
Function KnightMoves(ByVal x, ByVal y, ByVal PrevMoves$)
 Dim newx&, newy&, b1 As Boolean, b2 As Boolean, b3 As Boolean, b4 As Boolean
 Dim b5 As Boolean, b6 As Boolean, b7 As Boolean
 
 newx = x + 2
 newy = y + 1
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b1 = True
 End If
 
 newy = newy - 2
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b2 = True
 End If
    
 newx = newx - 4
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b3 = True
 End If
 
 newy = newy + 2
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b4 = True
 End If
 
 newx = newx + 1
 newy = newy + 1
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b5 = True
 End If
 
 newx = newx + 2
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b6 = True
 End If
 
 newy = newy - 4
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    b7 = True
 End If
 
 newx = newx - 2
 If CBool(newx > 0 And newx < 9 And newy > 0 And newy < 9) And InStr(1, PrevMoves, "," & newx & newy & ",", vbBinaryCompare) = 0 Then
    Call KnightMoves(newx, newy, PrevMoves & newx & newy & ",")
 Else
    If b1 And b2 And b3 And b5 And b6 And b7 Then
        If Len(PrevMoves) = 193 Then Debug.Print PrevMoves
    End If
    
 End If
 
End Function

There is a relevant puzzle called "8-queens". In simple terms: arrange 8 queens on a chessboard so that no queen attacks any other queen.

To my knowledge there is only 1 configuration that solves this puzzle (ignoring symmetrical equivalents).

There are many links to this puzzle, and they often have others of similar ilk.

By my reckoning, it is possible to jump to any square with a knight (horsey!)...

Take 2 white knights and 2 blacks ones, arrange them at the corners of a 3 by 3 grid of squares. Blacks at the top left and right and white at the bottom left and right. In as few moves as possible, swap the positions of the colours. The only square that never gets used is the center one. and on a normal board this can be reached by leaving the 3 by 3 grid.

Just my theory. Look up the queens thing though, quite interesting, and a tricky programming challenge!

Solutions to this problem have been known for well over 100 years. There is a book called Mathematical Recreations and Essays by W. W. Rouse Ball, originally published in 1892, which discusses the problem. There is a currently available 13th edition of that book, which has been updated by H. S. M. Coxeter (Dover Publications). This book has all sorts of interesting articles. I like it for the Magic Squares chapter.

One approach to the Knight problem (called a Knight tour) mentioned in this book starts by imagining the chess board as an inner 4X4 square ringed by a border two squares wide.

• Start in the upper right corner, making moves that stay in the border until you must move into the inner 4X4 square.
  
• When you are forced to move into the inner square, move immediately back to the border.
  
• Keep using the above process until every square in the border has been visited, which takes 50 moves.
  
• When every square in the border has been visited as described above, it is not hard to figure out how to finish the job.

It is best to use coins to mark visited squares on a chess board. I would use a spread sheet and put move numbers into each square visited, providing a record of the solution.

Another method mentioned by the book is as follows.

• Move the knight randomly, recording each move. The record must include the move number for each square visited. A spread sheet is an easy way to do this.
  
• When you can no longer make a move, study the unvisited squares on the board.
  
• Study each visited square which can be reached from an unvisited square.
  
• You are likely to be able to find a way to incorporate unvisited squares into the tour by making slight detours from the original unsuccessful tour.

This is the sort of problem that a human can solve faster than a computer if you consider the programming time required to get a debugged program to do it. While a programmed solution is probably possible, this is a type of problem for which you might never get a programmed solution.

I am too lazy to post a solution from the book. For money or sexual favors I could be coaxed into providing a solution.

Money or sexual favours eh?

I have no money and I get the feeling it wouldn't be much of a favour from me! lol

Here are two solutions to the queens challenge that are not symmetrical:

x0000000
0000x000
0000000x
00000x00
00x00000
000000x0
0x000000
000x0000

x0000000
00000x00
0000000x
00x00000
000000x0
000x0000
0x000000
0000x000


Modifying the above algorithm I can say that I am 100% sure that a knight tour can't be done with 4x4 chessboard.

With a 6x6 board there are many solutions including
(where each set of 2 numbers represents x,y co-ordinates):
11,32,53,34,55,36,15,23,35,16,24,12,31,52,64,56,44,65,46,25,13,21,33,54,66,45,26,14,22,41,62,43,51,6 3,42,61

Can the algorithm be tweaked to get it to work for a 8x8 board so that it doesn't take hours/days?

Well I have the algorithm running on my P-III650.
I'll be out most of the morning so that should give it a good stab at it.

Its compiled, for fast code, with all the optimizations.
I am however also running the protien analysis dooda yokie, and also the UD Cancer agent. But your app is getting good mileage still :)

Reentrant Knight Tours end on a square from which the knight can move to the starting square. Such a tour can obviously start on any square.

Divide the chess board into 4 sub squares. Label the 16 squares in each quarter as follows.

L E A P
A P L E
E L P A
P A E L

Note that in each quarter of the board there are 4 reentrant Knight Tours, each indicated by a different letter. Furthermore, you can readily determine 4 Knight Tours, each visiting 16 squares on the 64X64 board, and each indicated by a different letter.

The above can be used to construct Tours of the entire board, some reentrant and others not reentrant. It is claimed that the above can be used to construct a Tour which starts on any square and ends on any other specified square.

The book also shows a Knight Tour with a remarkable property. If you put 1 in the starting square, 2 in the next square visited, et cetera, the result is a Magic Square. The numbers in each row and in each column add up to 260. The sum of the numbers in the diagonals also add up to 260.

I wonder how long it took to create that Knight Tour.

Some time ago I ran a knights walk program to completion on a 5x5 grid, taking every possible path from every square.

Numbering the squares 1 to 5 across the top row, 6 to 10 second row etc.
Links are the legal moves from each square.
An analysis of the results of 5x5 grid.

Number of possible paths from:
Square links paths
1 2 304
2 3 0
3 4 56
4 3 0
5 2 304
6 3 0
7 4 56
8 6 0
9 4 56
10 3 0
11 4 56
12 6 0
13 8 64
14 6 0
15 4 56
16 3 0
17 4 56
18 6 0
19 4 56
20 3 0
21 2 304
22 3 0
23 4 56
24 2 0
25 2 304

Total paths 1728.
There are no possible paths from any even numbered square.
From the four corners, there are 12 possible end squares (all the other odd numbers)
All paths from the remaining odd numbered squares end at one of the four corners.

Actually it is only necessary to check 6 squares, 1, 2, 3, 7, 8, and 13 as any paths from any other squares are either mirror images or rotations of these.

I ran this program on an 8x8 grid for a few days and found 7823 paths from 1 before I crashed the pc doing something else and had to reboot.

The end squares of these paths were: 18,25,27,29,31,34,38,40,43,45,50,52,54,56,57,59,or 61.

Assuming that you only have to find paths from 1,2,3,4,10,11,12,19,20 and 28 (or paths terminating in these) then:
1 – start point – all paths started here
2 – equivalent to 56
3 – equivalent to 59
4 – equivalent to 40
10 – equivalent to 50
11 – equivalent to 18
12 – equivalent to 31
19 – equivalent to 43
20 – equivalent to 27
28 – equivalent to 29
I would conclude that it is indeed possible to complete the knights walk, starting at any square on the chessboard.

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

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

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

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

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

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

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

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

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