Tough Problem 4 (VBA)

P

pgc01

MrExcel MVP
Joined
Apr 25, 2006
Messages
19,897
Hi all

This week's vba problem is a classic. We've all heard of it sometime and it may not be so simple as one would think.

Problem:

Place a knight on a corner of a chess board. Can you move the knight over all the other squares visiting each one just once?

- If yes, display one possible path.


MVPs and experienced users, please wait 24 hours before posting a solution.

Suggestion: it takes a while for the code to find a solution (at least with my algorithm). You may want to try it first on a board 5 * 5 where it takes less than a second.

It would be interesting to have some discussion about this. Don't wait till you have a top notch solution to post. Possible themes for discussion: how to move the knight, how to represent the board, how to check if all the squares have been visited, etc.

Have fun.

Cheers
 

Excel Facts

How to total the visible cells?
From the first blank cell below a filtered data set, press Alt+=. Instead of SUM, you will get SUBTOTAL(9,)
Can I propose a slight modification to the challenge?

Same task, but instead of visiting each sqare just once the task is to show a path that moves the knight to all sqares in the least number of steps. Record and show the number of steps necessary. Hint: The optimal solution will have 64 steps (number of sqares on a chessboard)
 
oops, slight correction - 63 moves is the optimal number, since 1 square is already taken as the starting position.

if somebody wants to try the moves for themselves prior to launching into the task go and check out this fun site :)
 
Hi Stephan

Thank you for the suggestion. That can be a variant, if you cannot visit the other 63 squares in 63 moves, you can try to find the minimum number of moves that will let you touch all the other squares.

I'm not sure, however, that it will be easier. One good thing about visiting each square only once is that you have one very simple criterium to decide whether to move to a square: if already visited, don't go there. In the variant you suggest that criterium doesn't hold.

And thank you for the link, great for testing and get ideas about the algorithms. :)
 
**** you PCG!

as if I didnt have anything else to do - like finishing my bachelor thesis...

I can solve the problem on the website, in 63 steps, but my vba skills don't seem to be sufficient to translate what I am doing by hand into code :-(
The best I can come up with is a maximum of 53 steps before i run out of cells to jump to. I think i'll give up for know and maybe (if I am not too embarassed by then) post my sorry try once everyone else has shown me how to do it.
 
Hmmm... running it visually took 64 moves the first time through. Could be fun trying to code the optimal solution.

Denis
 
Interesting challenge! I think the 24 hours is up so here goes.....

This didn't seem to take too long to run (a few minutes).

Set the board size (i.e. the number of squares) at the top line where it says Const MaxSq As Long = 64.


Rich (BB code): 
Option Explicit
 
Const MaxSq As Long = 64 'ASSUMED TO BE A PERFECT SQUARE NUMBER (e.g. 64, 49 etc.)
 
Dim Board(MaxSq, 4) As Long
'Dimensions:
'   0 = moved from this square
'   1 = row ref
'   2 = col ref
'   3 = movement sequence number (0 = not used)
'   4 = move attempt number
 
Dim SqSide As Long
Dim FoundSol As Boolean
Dim CPos As Long
Dim MovesMade As Long
 
 
Sub MoveKnight()
 
Dim L1 As Long, L2 As Long, L3 As Long
 
SqSide = CLng(Sqr(MaxSq))
FoundSol = False
ThisWorkbook.Sheets(1).UsedRange.ClearContents
 
For L1 = 1 To SqSide
    For L2 = 1 To SqSide
        L3 = L3 + 1
        Board(L3, 0) = 0
        Board(L3, 1) = L1
        Board(L3, 2) = L2
        Board(L3, 3) = 0
        Board(L3, 4) = 1
    Next L2
Next L1
 
Board(1, 3) = 1
CPos = 1
MovesMade = 1
 
Do While FoundSol = False
    Call TestMove(1)
Loop
 
For L1 = 1 To MaxSq
    ThisWorkbook.Sheets(1).Cells(Board(L1, 1), Board(L1, 2)) = Board(L1, 3)
Next L1
 
MsgBox "Finished", vbInformation, "Done!"
 
End Sub
 
 
Sub TestMove(Attempt As Long)
 
Dim TV As Long
 
If FoundSol = True Then Exit Sub
 
TV = ValidateMove(Board(CPos, 1), Board(CPos, 2), Attempt)
 
If TV > 0 And Board(TV, 3) = 0 Then
    Board(TV, 0) = CPos
    MovesMade = MovesMade + 1
    CPos = TV
    Board(CPos, 3) = MovesMade
    Board(CPos, 4) = Attempt
    If MovesMade >= MaxSq Then FoundSol = True
ElseIf Attempt < 8 Then
    Call TestMove(Attempt + 1)
Else
    MovesMade = MovesMade - 1
    TV = CPos
    CPos = Board(CPos, 0)
    Board(TV, 3) = 0
    Board(TV, 0) = 0
    Call TestMove(Board(TV, 4) + 1)
End If
 
End Sub
 
 
Function ValidateMove(RowRef As Long, ColRef As Long, MoveNum As Long) As Long
 
ValidateMove = 0
 
Select Case MoveNum
    Case 1
        If RowRef < SqSide And ColRef < SqSide - 1 Then ValidateMove = CPos + SqSide + 2
    Case 2
        If RowRef < SqSide - 1 And ColRef < SqSide Then ValidateMove = CPos + (2 * SqSide) + 1
    Case 3
        If RowRef < SqSide - 1 And ColRef > 1 Then ValidateMove = CPos + (2 * SqSide) - 1
    Case 4
        If RowRef < SqSide And ColRef > 2 Then ValidateMove = CPos + SqSide - 2
    Case 5
        If RowRef > 1 And ColRef > 2 Then ValidateMove = CPos - SqSide - 2
    Case 6
        If RowRef > 2 And ColRef > 1 Then ValidateMove = CPos - (2 * SqSide) - 1
    Case 7
        If RowRef > 2 And ColRef < SqSide Then ValidateMove = CPos - (2 * SqSide) + 1
    Case 8
        If RowRef > 1 And ColRef < SqSide - 1 Then ValidateMove = CPos - SqSide + 2
End Select
 
End Function

And no stack error this time!! I might have to revist the other thread.....

Cheers
Andrew
 
Last edited:
Very nice! Your code generated a good knight's tour on my machine (Excel 2003, Win XP) in only a few minutes. Gonna have to spend some time dissecting what you did; I got as far as a very ugly, completely random, valid-moves-sequence generator that tested hundreds of failed attempts.
 
gardnertoo said:
Very nice! Your code generated a good knight's tour on my machine (Excel 2003, Win XP) in only a few minutes. Gonna have to spend some time dissecting what you did; I got as far as a very ugly, completely random, valid-moves-sequence generator that tested hundreds of failed attempts.
Click to expand...
Thanks for that. To save you a bit of time, it might help if I explain what it is doing from a conceptual angle - please don't read on if you would rather work it out yourself! :)

The assumes the Knight starts in the top left corner and then tries to make 1 of 8 possible legal or non-legal moves. A number of these moves might take it off the board - this is being checked by the ValidateMove function. If it is a valid move then the function returns the square number - the board squares are numbered 1 to 64 starting from the top left and moving to the right, then down. Provided this square is not occupied then it remembers that move and then tries another from that starting position, and so on.

The key (for my solution) is the global array which represents the 64 squares on the board. This has a number of dimensions, which includes the row and column reference of the square, the (valid) move sequence, the valid move attempt number (1-8) and which square the move came from. This last bit is crucial for undoing a move. If it cannot make a legal move, it back-tracks one move at a time, but it only then goes on to check the valid moves numbered 1-8 that it hasn't already tried, and so on.

Once again the key is a recursive sub that calls itself - this is a useful technique when you don't know how many times you want to run a loop. However, if not coded correctly (as I did in the other thread) then you can get a 'stack full' error.

Also, keep in mind this is a 'brute force' method - what would be nice is an elegant solution that doesn't use brute force.

Andrew
 
You must log in or register to reply here.

Forum statistics

Threads
1,222,646
Messages
6,167,301
Members
452,109
Latest member
nathanle89

Share this page

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top