# Tough Problem 4 (VBA)



## pgc01 (Jan 19, 2009)

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


----------



## yytsunamiyy (Jan 19, 2009)

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)


----------



## yytsunamiyy (Jan 19, 2009)

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


----------



## pgc01 (Jan 19, 2009)

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.


----------



## pablotravel (Jan 19, 2009)

hey can you help me with something


----------



## yytsunamiyy (Jan 19, 2009)

**** 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.


----------



## SydneyGeek (Jan 19, 2009)

Hmmm... running it visually took 64 moves the first time through. Could be fun trying to code the optimal solution.

Denis


----------



## Andrew Fergus (Jan 19, 2009)

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.



```
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


----------



## gardnertoo (Jan 19, 2009)

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.


----------



## Andrew Fergus (Jan 20, 2009)

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.


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


----------



## gardnertoo (Jan 20, 2009)

Thank you for the explanation.  It confirms that I had correctly figured out what you did.  I've learned a lot about multi-dimension arrays by picking apart your macro.  I love the backtracking feature, and the fact that it remembers where it left off at the previous square.  The sequential move generator is a big improvement over my random choice approach.  While dissecting your work I added some lines among yours to make it spit out some numbers: to arrive at the final sequence of moves, the ValidateMove function got called over 67 million times.  This generated almost 40 million legal moves, most of which turn out to be dead ends on the way to a valid 64 move sequence.  My "random move" attempt was iterating only 65,000 times per shot, and I saw the same failed sequences repeating (due to the random move selection); I was afraid to let it run open ended until it found a solution, and seeing what you did, I don't think it would have ever gotten there!


PGC01: As long as we are talking chess, is the Eight Queens puzzle up next?


----------



## Colin Legg (Jan 20, 2009)

This problem really interested me because I played a bit of chess when I was younger and I remember sitting over a board trying to solve the Knight's Tour. The rule of thumb is, when you have a choice of squares, to pick the one which has the fewest number of legal moves. This invariably means that the knight is moved towards the empty edges and corners of the board in this puzzle. It also has relevance to a game of chess because it also tells us that knights are generally more powerful when they are closer to the middle of the board (since they command more squares from there) and, in the endgame, a flank pawn can be a handy tool against an opponent's knight.

This is my solution. To run it, copy into a standard code module and execute the sub called Main(). I've added randomising factors so it will produce a different Knight's Tour each time it is run and you can experiment with changing the dimensions of the board by changing the values of the mlROW_COUNT and mlCOL_COUNT constants. On my PC it produces a Knight's Tour on an 8x8 board at the first attempt in under a second.


```
Option Explicit
 
'grid rows and columns representing dimensions of the chess board
'change dimensions to suit (a traditional board is 8x8):
Const mlROW_COUNT As Long = 8
Const mlCOL_COUNT As Long = 8
 
'the maximum number of permissable attempts to solve the puzzle
'change max number of attempts to suit:
Const mlMAX_ATTEMPTS As Long = 10
 
'we will use C3 as the top left cell so that no moves can
'take us off the worksheet
Const msTOP_LEFT_CELL As String = "C3"
 
'a range representing a chess board
Dim mrngChessBoard As Range
 
 
 
 
'the main sub to run to try to solve the puzzle
Public Sub Main()
 
    Dim lAttempts As Long  'a counter to monitor how many tries the algorithm has had
    Dim sMsg As String        'a report message
 
    'get a reference to a range which represents our chess board
    Set mrngChessBoard = Worksheets.Add.Range(msTOP_LEFT_CELL).Resize(mlROW_COUNT, mlCOL_COUNT)
 
    'try to solve the puzzle
    Do
        'we must start with an empty board
        mrngChessBoard.Clear
        lAttempts = lAttempts + 1
    Loop While KnightMoves <> (mlROW_COUNT * mlCOL_COUNT) And lAttempts < mlMAX_ATTEMPTS
 
    'tidy up the chess board presentation however you need to....
    mrngChessBoard.Columns.AutoFit
 
    'create a report message for the end user
    sMsg = "solved after " & lAttempts & " attempt": If lAttempts > 1 Then sMsg = sMsg & "s"
 
    'did we solve it? if not then adjust the report message....
    If lAttempts = mlMAX_ATTEMPTS Then sMsg = "NOT " & sMsg
 
    MsgBox sMsg
 
    'clean up
    Set mrngChessBoard = Nothing
 
End Sub
 
 
 
 
 
'a function which moves the knight around the board and tracks the number of moves
Private Function KnightMoves() As Double
    Dim rngCurrent As Range     'a range representing the current position of the knight
 
    'let's take a random corner of the board as our starting point
    Set rngCurrent = GetStartingSquare
    KnightMoves = 1
 
    With rngCurrent
        .Value = KnightMoves
        .Interior.Color = vbYellow  'mark the starting square yellow
    End With
 
    'move the knight around the board until we run out of available squares
    Do
 
        Set rngCurrent = GetNextMove(rngCurrent)
 
        If Not rngCurrent Is Nothing Then
            KnightMoves = KnightMoves + 1
            rngCurrent.Value = KnightMoves
        Else
            Exit Do
        End If
 
    Loop
 
End Function
 
 
'use Warnsdorff's algorithm to determine the next move:
'--> we move to the next square which itself has the
'least number of possible legal moves
Private Function GetNextMove(ByRef Square As Range) As Range
    Const bytMAXMOVES As Byte = 8 'the largest number of squares a knight can move to is 8
 
    Dim rngMove1 As Range   'looking one move ahead
    Dim rngMove2 As Range   'looking two moves ahead
    Dim rngSquare As Range  'a cell counter
    Dim bytNextMoveCounter As Byte 'track the least number of subsequent legal moves
 
 
    Set rngMove1 = GetLegalMoves(Square)
 
    'if there are no legal first moves then do nothing
    If rngMove1 Is Nothing Then
    'if there is only one legal move then we have to move there
    ElseIf rngMove1.Areas.Count = 1 Then
        Set GetNextMove = rngMove1
 
    'if there are multiple legal moves we have to determine
    'which is the best
    Else
 
        bytNextMoveCounter = bytMAXMOVES
 
        'loop through all the squares which are legal 1st moves
        For Each rngSquare In rngMove1.Areas
 
            'determine all the possible legal 2nd moves from the 1st move
            Set rngMove2 = GetLegalMoves(rngSquare)
 
            If Not rngMove2 Is Nothing Then
                With rngMove2.Areas
 
                    'if there are less 2nd moves from that square than
                    'any others we have checked then we want it
                    If .Count < bytNextMoveCounter Then
                        bytNextMoveCounter = .Count
                        Set GetNextMove = rngSquare
 
                    ElseIf .Count = bytNextMoveCounter Then
 
                        'if two squares are equally viable let's randomly pick one
                        'so that our algorithm produces different results each time
                        Randomize
                        If Rnd >= 0.5 Then Set GetNextMove = rngSquare
 
                    End If
                End With
            End If
        Next rngSquare
 
    End If
 
 
End Function
 
'A function to get all the legal moves the knight can make
Private Function GetLegalMoves(ByRef Square As Range) As Range
    Dim rngCell As Range
 
    For Each rngCell In GetAllMoves(Square)
        If IsMoveLegal(rngCell) Then
 
            If GetLegalMoves Is Nothing Then
                Set GetLegalMoves = rngCell
            Else
                Set GetLegalMoves = Union(GetLegalMoves, rngCell)
            End If
 
        End If
    Next rngCell
 
End Function
 
'A function to determine if a move to a square is allowed
Private Function IsMoveLegal(ByRef Square As Range) As Boolean
    'has the square been visited yet?
    If IsEmpty(Square) Then
 
            'is the square on the chess board?
            If Not Intersect(Square, mrngChessBoard) Is Nothing Then IsMoveLegal = True
 
    End If
 
End Function
 
'A function to determine all the possible moves (legal or not) a knight could make
Private Function GetAllMoves(ByRef Square As Range) As Range
    With Square
        Set GetAllMoves = Union( _
                            .Offset(-2, -1), _
                            .Offset(-2, 1), _
                            .Offset(-1, -2), _
                            .Offset(-1, 2), _
                            .Offset(1, -2), _
                            .Offset(1, 2), _
                            .Offset(2, -1), _
                            .Offset(2, 1) _
                                )
    End With
End Function
 
'a function to determine a corner of the chess board to start from
Private Function GetStartingSquare() As Range
    Dim sngRandomNumber As Single
    Randomize
    sngRandomNumber = Rnd
 
    With mrngChessBoard
        If sngRandomNumber >= 0.75 Then
            Set GetStartingSquare = .Cells(1, 1)
 
        ElseIf sngRandomNumber >= 0.5 Then
            Set GetStartingSquare = .Cells(1, mlCOL_COUNT)
 
        ElseIf sngRandomNumber >= 0.25 Then
            Set GetStartingSquare = .Cells(mlROW_COUNT, 1)
 
        Else
            Set GetStartingSquare = .Cells(mlROW_COUNT, mlCOL_COUNT)
        End If
    End With
End Function
```
 
Because this is proof of concept I haven't added any error handling and I haven't concerned myself with the application object's screenupdating, calculation and enableevents properties.

Colin


----------



## Andrew Fergus (Jan 20, 2009)

Hi Colin
Nice non-brute force method.  Why do you select the option with the least number of possible next moves?  I'm not following the relevance of this.....
Cheers
Andrew

Late Edit : Is this an attempt to fill in the outer squares first?  If so, then has 'Warnsdorff's algorithm' been optimised purely for solving the Knights tour problem?  If so, does it have application elsewhere?


----------



## Andrew Fergus (Jan 20, 2009)

http://www.atarimagazines.com/creative/v11n5/64_The_knights_tour_the_co.php


----------



## Colin Legg (Jan 20, 2009)

Hi Andrew,

It's a rule of thumb I learnt at school; the logic being that we move to a square with the least number of valid exit points (we move to it while it still has some) so we are less likely to come to a dead end before the puzzle is complete. On an 'empty' board a knight in a corner square has only 2 valid moves whereas a knight in the centre has 8 valid moves so, all else being equal, the move will tend to be towards the sides and corners. I didn't know it was called Warnsdorff's rule until I googled it yesterday when I was writing this code. I'm not familiar with the other concepts on that good link you provided such as counting adjacent squares.

Cheers
Colin


----------



## pgc01 (Jan 20, 2009)

yytsunamiyy said:


> 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


 
Stephan, learning is always an ongoing process, if you can't solve it this time, study the solutions posted and you'll be able to post your own solution next time! 

Cheers


----------



## pgc01 (Jan 20, 2009)

SydneyGeek said:


> Hmmm... running it visually took 64 moves the first time through. Could be fun trying to code the optimal solution.
> 
> Denis


 
Denis, we already have 2 good solutions, why not a 3rd one? 

Cheers


----------



## pgc01 (Jan 20, 2009)

Hi Andrew, Colin

Thank you for your great solutions.

Andrew, your solution is similar to mine, using recursion. I think it's worth for anywone that tried to solve this problem to examine this solution to learn about recursion. Recursion comes very handy in this type of problems.

Your link seems also very promising. I didn't have time yet to read it carefully, but I will.


Colin, your solution is great and incredibly fast. You followed another path, your method is not a simple try until succeed, the method you use is very efficient. I didn't know it, I'm sure it's worth understanding and studying, which is what I will do. 

Cheers
Pedro


----------



## pgc01 (Jan 20, 2009)

gardnertoo said:


> PGC01: As long as we are talking chess, is the Eight Queens puzzle up next?


 
Hi gardnertoo

That's a very good idea. I'll not use it right now, I'd like to vary the themes of the  problems, but I'll keep it for future use. Like the Knight Tour that's also a problem that may appeal to many of us. I haven't tried it yet, and it may be a good challenge.

Cheers


----------



## pgc01 (Jan 20, 2009)

I'm happy to announce that next week's Tough Problem (vba) will be posted by Andrew Fergus!


This doesn't mean at all that this problem is closed. I still hope to get other answers, maybe with different approaches.

For ex.: the simplest approach, no recursion, just some loops to try to find the desired path.


----------



## pgc01 (Jan 20, 2009)

One interesting solution (or enhancement to the posted solutions) would be a closed path, the 64th movement would get us back to the starting point.

This solution would be interesting because we could choose any square on the board and visit all the other squares touching them only once, and this with one unique path.


----------



## pgc01 (Jan 23, 2009)

This is an example of a closed path solution.

Notice that after the 63 movements (number 64 in the table) you end up in B3. In the next jump you can go back to A1 and close the path.

With this solution you can start on whatever position you want and you have always 2 solutions to visit all the other squares in 63 movements, just follow the closed path in one of the 2 possible directions.

Since no one posted another solution I'll try to post one myself today or tomorrow. Since my first solution was similar to the one Andrew posted, I'll It try a brute force one but without recursion, using arrays to store the necessary information to do the backtracking.


<TABLE style="BORDER-TOP-WIDTH: 2px; BORDER-LEFT-WIDTH: 2px; FONT-SIZE: 10pt; BORDER-LEFT-COLOR: #cccccc; BACKGROUND: #fff; BORDER-BOTTOM-WIDTH: 2px; BORDER-BOTTOM-COLOR: #cccccc; BORDER-TOP-COLOR: #cccccc; FONT-FAMILY: Arial,Arial; BORDER-COLLAPSE: collapse; BORDER-RIGHT-WIDTH: 2px; BORDER-RIGHT-COLOR: #cccccc" cellPadding=1 border=1><TBODY><TR><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>A</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>B</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>C</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>D</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>E</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>F</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>G</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>H</TH><TH style="BORDER-TOP-WIDTH: 1px; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; BORDER-TOP-COLOR: #888888; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888" width=30>I</TH></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*1*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">1</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">12</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">9</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">6</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">3</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">14</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">17</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">20</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*2*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">10</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">7</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">2</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">13</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">18</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">21</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">4</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">15</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*3*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">33</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">64</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">11</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">8</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">5</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">16</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">19</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">22</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*4*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">28</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">25</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">34</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">63</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">40</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">23</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">56</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">61</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*5*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">35</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">32</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">27</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">24</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">57</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">62</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">39</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">44</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*6*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">26</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">29</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">50</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">41</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">38</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">45</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">60</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">55</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*7*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">51</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">36</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">31</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">48</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">53</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">58</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">43</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">46</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*8*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">30</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">49</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">52</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">37</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">42</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">47</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">54</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888">59</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #000000; BACKGROUND: #9cf; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #000000; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #000000; PADDING-TOP: 0.4em; TEXT-ALIGN: center; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #000000">*9*</TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD><TD style="BORDER-TOP-WIDTH: 1px; PADDING-RIGHT: 0.5em; PADDING-LEFT: 0.5em; BORDER-LEFT-WIDTH: 1px; BORDER-LEFT-COLOR: #888888; BORDER-BOTTOM-WIDTH: 1px; BORDER-BOTTOM-COLOR: #888888; PADDING-BOTTOM: 0.25em; BORDER-TOP-COLOR: #888888; PADDING-TOP: 0.4em; TEXT-ALIGN: right; BORDER-RIGHT-WIDTH: 1px; BORDER-RIGHT-COLOR: #888888"></TD></TR><TR><TD style="PADDING-LEFT: 1em; BACKGROUND: #9cf" colSpan=10>[Chess.xlsb]Closed loop</TD></TR></TBODY></TABLE>


----------



## gardnertoo (Jan 23, 2009)

> One interesting solution (or enhancement to the posted solutions) would be a closed path



I took your challenge, and have succeeded in modifying Colin_L's solution, forcing it to reject open tours, try again until it finds a closed tours, and changed the rules to make the closed tour more likely.  While open tours far outnumber closed tours, there are still millions of such tours.  Colin's randomizing feature remains active, so run after run you get a unique closed tour.  I started by cheating a little: realizing that by starting in the corner, we had only one candidate for "final move" (the possible "move #1" that wasn't taken), I decided to shift the start position to there.  Warnsdorff's algorithm will send you into the corner automatically as move #1 anyway, and this gave me five candidates for "final move".  Then, after much manual trial and error with various rules, I came up with two simple (thank goodness) rules that work almost every time.  #1: In cases where the Warnsdorff algorithm results in a tie, before randomly breaking the tie you reject any candidates which are also "last move" candidates.  If the tie is between two "last move" candidates, you'll have to pick one at random.  (You want to save the "last move" candidates, using them up only when you have no other legal moves.)  #2: Once you have used up all but one "last move" candidate, you avoid that square at all costs, even if it is the move with the lowest second-move score.  Once I got it working, I opened up the random first-square selector to allow a starting square anywhere on the board.

I want to thank both Colin_L and Andrew Fergus for your solutions, I have learned a lot by picking apart what you did and modifying it.


```
Option Explicit
 
'grid rows and columns representing dimensions of the chess board
'change dimensions to suit (a traditional board is 8x8):
Const mlROW_COUNT As Long = 8
Const mlCOL_COUNT As Long = 8
 
'the maximum number of permissable attempts to solve the puzzle
'change max number of attempts to suit:
Const mlMAX_ATTEMPTS As Long = 10

'we will use C3 as the top left cell so that no moves can
'take us off the worksheet
Const msTOP_LEFT_CELL As String = "C3"
 
'a range representing a chess board
Dim mrngChessBoard As Range
Dim firstsquare As Range    'JDG: a range representing the knight's starting position
Dim finaleight As Range  'JDG: these are the eight squares to which the last move may go to acheive a closed tour
Dim finaleightcount As Integer  'JDG: how many of those eight squares are still available
Dim i As Integer

 
'the main sub to run to try to solve the puzzle
Public Sub Main()
    
    Dim lAttempts As Long  'a counter to monitor how many tries the algorithm has had
    Dim sMsg As String        'a report message
 
    'get a reference to a range which represents our chess board
        'In a new sheet:
        'Set mrngChessBoard = Worksheets.Add.Range(msTOP_LEFT_CELL).Resize(mlROW_COUNT, mlCOL_COUNT)
    
        'In the existing sheet:
        Set mrngChessBoard = ActiveSheet.Range(msTOP_LEFT_CELL).Resize(mlROW_COUNT, mlCOL_COUNT)
 
    'try to solve the puzzle
    Do
        'we must start with an empty board
        'mrngChessBoard.Clear
        clear_board
        mrngChessBoard.ClearContents
        lAttempts = lAttempts + 1
    Loop While KnightMoves <> (mlROW_COUNT * mlCOL_COUNT) And lAttempts < mlMAX_ATTEMPTS
    
    'tidy up the chess board presentation however you need to....
    mrngChessBoard.Columns.AutoFit
 
    'create a report message for the end user
    sMsg = "solved after " & lAttempts & " attempt": If lAttempts > 1 Then sMsg = sMsg & "s"
 
    'did we solve it? if not then adjust the report message....
    If lAttempts = mlMAX_ATTEMPTS Then sMsg = "NOT " & sMsg
 
    MsgBox sMsg
 
    'clean up
    Set mrngChessBoard = Nothing
    Set firstsquare = Nothing
 
End Sub
Sub clear_board()
'
' Macro4 Macro
' Macro recorded 1/23/2009 by John Gardner
'

'
    Range("C3").Interior.ColorIndex = xlNone
    Range("D3").Interior.ColorIndex = 15
    Range("C3:D3").Copy
    Range("E3:J3").PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range("D3:E3").Copy
    Range("C4:J4").PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range("C3:J4").Copy
    Range("C5:J10").PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range("A1").Select
End Sub

 
'a function which moves the knight around the board and tracks the number of moves
Private Function KnightMoves() As Double
    Dim rngCurrent As Range     'a range representing the current position of the knight
    Dim rngSquare As Range
    
    'If we're repeating from a failed attempt, use the same starting square
    If Not firstsquare Is Nothing Then
        Set rngCurrent = firstsquare
    
    'otherwise let's take any random square on the board as our starting point
    Else
        Set rngCurrent = GetStartingSquare
        Set firstsquare = rngCurrent
    End If
    
    KnightMoves = 1
 
      'mark the starting square yellow
      With rngCurrent
        .Value = KnightMoves
        .Interior.Color = vbYellow
    End With
    
'Determine the cells from which a move to cell #1 is possible
'A closed tour must end on one of these cells.
Set finaleight = GetLegalMoves(rngCurrent)
finaleightcount = finaleight.Areas.Count

    'mark the final eight candidates green
    For Each rngSquare In finaleight.Areas
        With rngSquare
            .Interior.Color = vbGreen
        End With
    Next rngSquare

    'move the knight around the board until we run out of available squares
    Do
    
        Set rngCurrent = GetNextMove(rngCurrent)
    
        If Not rngCurrent Is Nothing Then
            KnightMoves = KnightMoves + 1
            rngCurrent.Value = KnightMoves
            If Not Intersect(rngCurrent, finaleight) Is Nothing Then finaleightcount = finaleightcount - 1
        Else
            Exit Do
        End If
    
    Loop
    
End Function
 
 
'use Warnsdorff's algorithm to determine the next move:
'--> we always move to the next square which itself has the
'least number of possible legal moves, unless it is the final member of the finaleight.
'In that case, we move to the second-least moves square.
'Ties are broken first by artificially inflating the number of legal moves of any
'finaleight candidate by 1/2 move (1/2 chosen to avoid creating a new tie), then by random selection.
'If we have used up all eight of the finaleight before move #64, start over.

Private Function GetNextMove(ByRef Square As Range) As Range
    Const bytMAXMOVES As Byte = 8 'the largest number of squares a knight can move to is 8
 
    Dim rngMove1 As Range   'looking one move ahead
    Dim rngMove2 As Range   'looking two moves ahead
    Dim rngSquare As Range  'a cell counter
    Dim bytNextMoveCounter As Byte 'track the least number of subsequent legal moves
    Dim thatcellmove As Double  'allow 1/2 move penalty for membership in finaleight
    Dim tiebreaker As Double  'to avoid last finaleight cell until no longer possible
 
    Set rngMove1 = GetLegalMoves(Square)
 
    'if there are no legal first moves then do nothing
    If rngMove1 Is Nothing Then
    'if used up all final eight possibilites then do nothing
    ElseIf finaleightcount = 0 Then
    'if there is only one legal move then we have to move there
    ElseIf rngMove1.Areas.Count = 1 Then
        
        Set GetNextMove = rngMove1
 
    'if there are multiple legal moves we have to determine
    'which is the best
    
    Else
 
        bytNextMoveCounter = bytMAXMOVES
 
        'loop through all the squares which are legal 1st moves
        For Each rngSquare In rngMove1.Areas
 
            'determine all the possible legal 2nd moves from the 1st move
            Set rngMove2 = GetLegalMoves(rngSquare)
 
            If Not rngMove2 Is Nothing Then
                With rngMove2.Areas
 
                    'if there are less 2nd moves from that square than
                    'any others we have checked then we want it
                    tiebreaker = 0.5
                    If finaleightcount = 1 Then tiebreaker = 8  'forces avoidance of last finaleight memeber
                    
                    thatcellmove = .Count
                    If Not Intersect(rngSquare, finaleight) Is Nothing Then thatcellmove = thatcellmove + tiebreaker
                    
                    'If .Count < bytNextMoveCounter Then
                    If thatcellmove < bytNextMoveCounter Then
                        bytNextMoveCounter = .Count
                        Set GetNextMove = rngSquare
 
                    'ElseIf .Count = bytNextMoveCounter Then
                    ElseIf thatcellmove = bytNextMoveCounter Then
 
                        'if two squares are equally viable let's randomly pick one
                        'so that our algorithm produces different results each time
                        Randomize
                        If Rnd >= 0.5 Then Set GetNextMove = rngSquare
 
                    End If
                
                End With
            End If
        Next rngSquare
 
    End If
 
 
End Function
 
'A function to get all the legal moves the knight can make
Private Function GetLegalMoves(ByRef Square As Range) As Range
    Dim rngCell As Range
    
    For Each rngCell In GetAllMoves(Square)
        If IsMoveLegal(rngCell) Then
 
            If GetLegalMoves Is Nothing Then
                Set GetLegalMoves = rngCell
            Else
                Set GetLegalMoves = Union(GetLegalMoves, rngCell)
            End If
 
        End If
    Next rngCell
    
End Function
 
'A function to determine if a move to a square is allowed
Private Function IsMoveLegal(ByRef Square As Range) As Boolean
    'has the square been visited yet?
    If IsEmpty(Square) Then
 
            'is the square on the chess board?
            If Not Intersect(Square, mrngChessBoard) Is Nothing Then IsMoveLegal = True
 
    End If
 
End Function
 
'A function to determine all the possible moves (legal or not) a knight could make
Private Function GetAllMoves(ByRef Square As Range) As Range
    With Square
        Set GetAllMoves = Union( _
                            .Offset(-2, -1), _
                            .Offset(-2, 1), _
                            .Offset(-1, -2), _
                            .Offset(-1, 2), _
                            .Offset(1, -2), _
                            .Offset(1, 2), _
                            .Offset(2, -1), _
                            .Offset(2, 1) _
                                )
    End With
End Function
 
'a function to determine a square on the chess board to start from
    
Private Function GetStartingSquare() As Range
 
    With mrngChessBoard
        'Full randomizer
        Dim sqrow As Integer
        Dim sqcol As Integer
        Randomize
        sqrow = Int(8 * Rnd) + 1
        Randomize
        sqcol = Int(8 * Rnd) + 1
        Set GetStartingSquare = .Cells(sqrow, sqcol)
        
    End With

End Function
```


----------



## gardnertoo (Jan 23, 2009)

Here are some samples of the closed tours generated.  First, three unique solutions coming out of the same corner:Knights Tour by Colin L, Closed by JDG.xlsATAUAVAWAXAYAZBABBBCBDBEBFBGBHBIBJBKBLBMBNBOBPBQBRBS352411492033167287264330934452275245249285541310534215819322522298354431105146238615425105405112213455617627245342334651621585344275629611226354431831562340213649521132475037625760112675039463562574452055641544750612054859364330418236449584528613039237485760151249235386340151293847225365942741964551417625941964331417423110124374832629601383186358131613431839321316Sheet43

Next, three solutions starting at random places on the board:Knights Tour by Colin L, Closed by JDG.xlsATAUAVAWAXAYAZBABBBCBDBEBFBGBHBIBJBKBLBMBNBOBPBQBRBS1224141964391417330133833201518522395432017561352014015186338124123114173421402542160552191442344614859161329439423732191623659385318571615216475245623758401146144512235264124615851481162443224960511233528435061365752762335237641550177282546533457361047845645560233427426332491247182623309505532112764962255853564382936451031141929827543110355648926754632459283544930134611Sheet43


----------



## Andrew Fergus (Jan 24, 2009)

If you tried to solve the Knights Tour problem manually I suspect that if you applied the logic of selecting the path with the least number of available moves, based on Colin's solution, then you could solve the puzzle at your first or second attempt.....it might be worth a go!


----------



## gardnertoo (Jan 24, 2009)

My rules that work "almost every time" -- well, that's on the standard 8x8 board.  I played with it on higher order boards last night, and while it will generate solutions for boards up to a 32x32, it almost always requires multiple attempts.  The 8x8 almost never does.  On the 32x32 it sometimes takes up to twenty attempts to find a closed tour.  I tried a 64x64, and after an hour and thousands of attempts, no solution.  Here are examples of 16x16 and 24x24 solved by the macro:












I think that for a higher-order board, the avoidance routine needs to look deeper than the "last move" candidates (n-0), maybe as far as n-3 or n-4.  Watching the 64x64 run, what is happening is it fills in seven of the eight "last move" candidates very quickly, then while avoiding the last one it fills in all the squares surrounding it, rendering it unreachable.


----------



## pgc01 (Jan 24, 2009)

Andrew Fergus said:


> If you tried to solve the Knights Tour problem manually I suspect that if you applied the logic of selecting the path with the least number of available moves, based on Colin's solution, then you could solve the puzzle at your first or second attempt.....it might be worth a go!


 
Hi Andrew

You are right. I hadn't tried it manually, I thought it would very difficult.
I've just tried it in the site provided by Stephan in post 3, and using Colin's rule of thumb. I did it at the 3rd attempt. This rule of thumb is really efficient!

Cheers
Pedro


----------



## pgc01 (Jan 24, 2009)

Hi gardnertoo

I can only say: great job!!!

I tried the code several times and got the result in under a second. I haven't been able to study Colin's solution and yours but i'll surely do it in the next days. I really think this is a very interesting method and it's worth understanding exactly how it works, who knows if it won't come in handy in another completely different context.



> I think that for a higher-order board, the avoidance routine needs to look deeper than the "last move" candidates (n-0), maybe as far as n-3 or n-4.


 
I agree with you. This is also what I'd try.

Cheers
Pedro


----------



## pgc01 (Jan 24, 2009)

Well, we've already got great solutions in this thread and it's time to make some comments.

- Andrew's solution is a good example of a brute force solution using recursion and this is the quickest and simplest way to get to the result if you just need to run the code a few times and can't or don't want to spend the time necessary to figure out a non brute force solution. This was also my first solution, recursion really comes in handy for this type of problems.

- Colin's and gardnertoo's solutions using Warnsdorff's algorithm show how studying a problem and figuring out a non brute force method can dramatically improve the response time. This is what you'll do if you need a solution that will be used lots of times by lots of people. In such a case it may be not acceptable to wait 1 minute to get the response and it pays to have someone studying the problem to figure out an efficient method that will reduce the code response time.

I will post a different type of solution. This is a minimalist solution. If you didn't know or understand recursion and didn't know any specific method to solve the problem you still could write code to solve the problem using brute force with just 1 loop.


```
Option Explicit
 
Const lRows As Long = 6       ' board number of rows
Const lColumns As Long = 6   ' board number of columns
Const lTotal As Long = lRows * lColumns
 
Sub Knight()
Dim lMov As Long
Dim lR As Long, lC As Long
Dim lMovArr(1 To lRows, 1 To lColumns) As Long         ' number of the move when visiting square
Dim lPos(1 To lTotal, 1 To 2) As Long                       ' position on the board in move n
Dim lOff(1 To lTotal) As Long                                  ' offset index in move
Dim vNext                                                           ' offsets to the next positions
 
lMovArr(1, 1) = 1
lPos(1, 1) = 1                                                      ' starts from top left
lPos(1, 2) = 1                                                      ' starts from top left
lMov = 2
 
vNext = [{-2,-1;-2,1;-1,-2;-1,2;1,-2;1,2;2,-1;2,1}]
 
Do
    If lOff(lMov) < 8 Then
        lOff(lMov) = lOff(lMov) + 1                                   ' try next offsets
        lR = lPos(lMov - 1, 1) + vNext(lOff(lMov), 1)            ' row in next move
        lC = lPos(lMov - 1, 2) + vNext(lOff(lMov), 2)            ' column in next move
 
        If (lR >= 1 And lR <= lRows) And (lC >= 1 And lC <= lColumns) Then ' inside the board
            If lMovArr(lR, lC) = 0 Then                                                    ' if square is free
                lMovArr(lR, lC) = lMov
                lPos(lMov, 1) = lR
                lPos(lMov, 2) = lC
                If lMov = lTotal Then Range("A1").Resize(lRows, lColumns).Value = lMovArr ' success
                lMov = lMov + 1
            End If
        End If
    Else                                                                                ' no moves possible
        lOff(lMov) = 0
        lMov = lMov - 1
        lMovArr(lPos(lMov, 1), lPos(lMov, 2)) = 0
    End If
Loop While (lMov <> 1) And (lMov <= lTotal)
If lMov = 1 Then MsgBox "Failed"
End Sub
```
 
I thank everyone that contributed to this thread. I really think we have very good solutions here.

Cheers
Pedro


----------



## gardnertoo (Feb 7, 2009)

It turns out that on a 64x64 board, I had to project backwards to move n-16 to reliably find a solution in fewer than ten attempts.  On the 32x32 board, n-8 will get there in five or fewer attempts, with n-12 usually requiring only one or two tries.  Here's the code, and I promise I'm done:


```
Option Explicit
 
'grid rows and columns representing dimensions of the chess board
'change dimensions to suit (a traditional board is 8x8):
Const mlROW_COUNT As Long = 32
Const mlCOL_COUNT As Long = 32
 
'the maximum number of permissable attempts to solve the puzzle
'change max number of attempts to suit:
Const mlMAX_ATTEMPTS As Long = 10

'the number of moves to look ahead
'change to suit:
Const levels As Integer = 12

'we will use C3 as the top left cell so that no moves can
'take us off the worksheet
Const msTOP_LEFT_CELL As String = "C3"
 
'a range representing a chess board
Dim mrngChessBoard As Range
Dim firstsquare As Range    'JDG: a range representing the knight's starting position
Dim finalsquares(levels) As Range  'JDG: these are the squares to which move n-x may go to acheive a closed tour
Dim finalsquarescount(levels) As Integer  'JDG: how many of those squares are still available
Dim finalsquarestemp(levels) As Range  'JDG: finalsquares set before removing overlap with lower levels
Dim i As Integer

 
'the main sub to run to try to solve the puzzle
Public Sub Main()
    
    Dim lAttempts As Long  'a counter to monitor how many tries the algorithm has had
    Dim sMsg As String        'a report message
    Dim exitMsg As String   'alert user to board size
    
    exitMsg = "Board size " & mlROW_COUNT & " x " & mlCOL_COUNT & ", looking ahead " & levels & " moves."
    If MsgBox(exitMsg, vbOKCancel, "WARNING") = vbCancel Then Exit Sub
    
 
    'get a reference to a range which represents our chess board
        'In a new sheet:
        'Set mrngChessBoard = Worksheets.Add.Range(msTOP_LEFT_CELL).Resize(mlROW_COUNT, mlCOL_COUNT)
    
        'In the existing sheet:
        Set mrngChessBoard = ActiveSheet.Range(msTOP_LEFT_CELL).Resize(mlROW_COUNT, mlCOL_COUNT)
 
    'try to solve the puzzle
    Do
        'we must start with an empty board
        'mrngChessBoard.Clear
        clear_board
        mrngChessBoard.ClearContents
        'Application.ScreenUpdating = False
        Range(Cells(101, 2), Cells((mlROW_COUNT * mlCOL_COUNT) + 101, 3)).Value = Range(Cells(101, 12), Cells((mlROW_COUNT * mlCOL_COUNT) + 101, 13)).Value
        Range(Cells(101, 12), Cells((mlROW_COUNT * mlCOL_COUNT) + 101, 13)).ClearContents
        lAttempts = lAttempts + 1
        
    Loop While KnightMoves <> (mlROW_COUNT * mlCOL_COUNT) And lAttempts < mlMAX_ATTEMPTS
        'Application.ScreenUpdating = True
    'tidy up the chess board presentation however you need to....
    'mrngChessBoard.Columns.AutoFit
    Range(Cells(101, 2), Cells((mlROW_COUNT * mlCOL_COUNT) + 101, 3)).Value = Range(Cells(101, 12), Cells((mlROW_COUNT * mlCOL_COUNT) + 101, 13)).Value
    'create a report message for the end user
    sMsg = "solved after " & lAttempts & " attempt": If lAttempts > 1 Then sMsg = sMsg & "s"
 
    'did we solve it? if not then adjust the report message....
    If lAttempts = mlMAX_ATTEMPTS Then sMsg = "NOT " & sMsg
 
    MsgBox sMsg
 
    'clean up
    Set mrngChessBoard = Nothing
    Set firstsquare = Nothing
    For i = 0 To levels
        Set finalsquares(i) = Nothing
        Set finalsquarestemp(i) = Nothing
    Next i
       
 
End Sub
Private Sub clear_board()
'
' Macro4 Macro
' Macro recorded 1/23/2009 by John Gardner
'

'
    Range("C3").Interior.ColorIndex = xlNone
    Range("D3").Interior.ColorIndex = 15
    Range("C3:D3").Copy
    Range(Cells(3, 5), Cells(3, mlCOL_COUNT + 2)).PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range("D3:E3").Copy
    Range(Cells(4, 3), Cells(4, mlCOL_COUNT + 2)).PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range(Cells(3, 2), Cells(4, mlCOL_COUNT + 2)).Copy
    Range(Cells(5, 2), Cells(mlROW_COUNT + 2, mlCOL_COUNT + 2)).PasteSpecial Paste:=xlPasteFormats, Operation:=xlNone, _
        SkipBlanks:=False, Transpose:=False
    Application.CutCopyMode = False
    Range("A1").Select
End Sub

 
'a function which moves the knight around the board and tracks the number of moves
Private Function KnightMoves() As Double
    Dim rngCurrent As Range     'a range representing the current position of the knight
    Dim rngSquare As Range
    
    'If we're repeating from a failed attempt, use the same starting square
    'If Not firstsquare Is Nothing Then
        'Set rngCurrent = firstsquare
    
    'otherwise let's take any random square on the board as our starting point
    'Else
        Set rngCurrent = GetStartingSquare
        Set firstsquare = rngCurrent
    'End If
    
    KnightMoves = 1
 
      'mark the starting square red
      With rngCurrent
        .Value = KnightMoves
        '.Interior.Color = vbRed
      End With
    
'Determine the cells from which a move to cell #1 is possible
'A closed tour must end on one of these cells.
For i = 0 To levels
    Set finalsquares(i) = Nothing
    Set finalsquarestemp(i) = Nothing
Next i
Set finalsquares(0) = firstsquare
Set finalsquarestemp(0) = finalsquares(0)
finalsquarescount(0) = 1
Set finalsquares(1) = GetLegalMoves(rngCurrent)
Set finalsquarestemp(1) = finalsquares(1)
finalsquarescount(1) = finalsquares(1).Areas.Count

'********************Lookahead*******************************
    For i = 1 To levels
    For Each rngSquare In finalsquarestemp(i - 1).Areas
        If finalsquarestemp(i) Is Nothing Then
            Set finalsquarestemp(i) = GetLegalMoves(rngSquare)
        Else
            Set finalsquarestemp(i) = Union(finalsquarestemp(i), GetLegalMoves(rngSquare))
        End If
    Next rngSquare
    
    For Each rngSquare In finalsquarestemp(i)
        If i > 1 Then
            If Intersect(finalsquarestemp(i - 2), rngSquare) Is Nothing Then
                If finalsquares(i) Is Nothing Then
                    Set finalsquares(i) = rngSquare
                Else
                    Set finalsquares(i) = Union(finalsquares(i), rngSquare)
                End If
            End If
        End If
    Next rngSquare
    'audit
    Cells(100 + i, 5).Value = finalsquares(i).Areas.Count
    
Next i
Dim colortouse As Integer
'color code the levels of lastmove(x) in the display
For i = 1 To levels
    colortouse = GetSquareColor(i)
    For Each rngSquare In finalsquares(i).Areas
    rngSquare.Interior.ColorIndex = colortouse
    Next rngSquare
Next i

        'color code the inner three, and outermost, levels of lastmove(x)
        'For i = 1 To 3
            'colortouse = GetSquareColor(i)
            'For Each rngSquare In finalsquares(i).Areas
            'rngSquare.Interior.ColorIndex = colortouse
            'Next rngSquare
        'Next i
        'For Each rngSquare In finalsquares(levels).Areas
            'rngSquare.Interior.ColorIndex = 9
        'Next rngSquare
        
'******************************************************************


    'move the knight around the board until we run out of available squares
    Do
        'data table for graphical move display
        Cells(KnightMoves + 100, 12) = rngCurrent.Column - 2
        Cells(KnightMoves + 100, 13) = rngCurrent.Row - 2
    
        'Set rngCurrent = GetNextMove(rngCurrent, levels)
        Set rngCurrent = GetNextMove(rngCurrent)
        
        If Not rngCurrent Is Nothing Then
            KnightMoves = KnightMoves + 1
            rngCurrent.Value = KnightMoves
            For i = 1 To levels
                If Not Intersect(rngCurrent, finalsquares(i)) Is Nothing Then finalsquarescount(i) = finalsquarescount(i) - 1
            Next i
        Else
            Exit Do
        End If
    Loop
    
End Function
 
 
'use Warnsdorff's algorithm to determine the next move:
'--> we always move to the next square which itself has the
'least number of possible legal moves, unless it is the final member of any finalsquares(x).
'In that case, we move to the second-least moves square.
'Ties are broken first by artificially inflating the number of legal moves of any
'finalsquares(x) candidate by larger amounts as the (x) decreases, then by random selection.
'If we have used up all eight of the finalsquares(1) before move #64, start over.

'Private Function GetNextMove(ByRef Square As Range, levels As Integer) As Range
Private Function GetNextMove(ByRef Square As Range) As Range

    Const bytMAXMOVES As Integer = 1000 'the largest number of squares a knight can move to is 8
 
    Dim rngMove1 As Range   'looking one move ahead
    Dim rngMove2 As Range   'looking two moves ahead
    Dim rngSquare As Range  'a cell counter
    Dim bytNextMoveCounter As Double 'track the least number of subsequent legal moves
    Dim thatcellmove As Double  'allow penalty for membership in finalsquares(x)
    Dim tiebreaker(levels) As Double  'to avoid last finalsquares(x) cell until no longer possible
 
    Set rngMove1 = GetLegalMoves(Square)
 
    'if there are no legal first moves then do nothing
    If rngMove1 Is Nothing Then
        Range("AB68").Value = "No legal moves"
    'if used up all final eight possibilites then do nothing
    ElseIf finalsquarescount(1) = 0 Then
        Range("AB68").Value = "All used up"
    'if there is only one legal move then we have to move there
    ElseIf rngMove1.Areas.Count = 1 Then
        Range("AB68").Value = "One legal move"
        Set GetNextMove = rngMove1
 
    'if there are multiple legal moves we have to determine
    'which is the best
    
    Else
        Range("AB68").Value = "Multiple legal moves"
        bytNextMoveCounter = bytMAXMOVES
 
        'loop through all the squares which are legal 1st moves
        For Each rngSquare In rngMove1.Areas
 
            'determine all the possible legal 2nd moves from the 1st move
            Set rngMove2 = GetLegalMoves(rngSquare)
 
            If Not rngMove2 Is Nothing Then
                With rngMove2.Areas
 
                    'if there are less 2nd moves from that square than
                    'any others we have checked then we want it
                    tiebreaker(1) = 0.5
                    If finalsquarescount(1) = 1 Then tiebreaker(1) = 6.5  'forces avoidance of last finalsquares(1) memeber
                    If Not Intersect(rngSquare, finalsquares(1)) Is Nothing Then thatcellmove = thatcellmove + tiebreaker(1)
                    
                    thatcellmove = .Count
                    'For i = 1 To levels
                    For i = levels To 1 Step -1
                        tiebreaker(i) = (0 + levels - i) / levels
                        If finalsquarescount(1) = 1 Then tiebreaker(i) = 6.5 + ((0 + levels - i) / levels)
                        If Not Intersect(rngSquare, finalsquares(i)) Is Nothing Then thatcellmove = .Count + tiebreaker(i)
                    Next i
                    
                    
                    If thatcellmove < bytNextMoveCounter Then
                        bytNextMoveCounter = thatcellmove
                        Set GetNextMove = rngSquare
 
                    ElseIf thatcellmove = bytNextMoveCounter Then
 
                        'if two squares are equally viable let's randomly pick one
                        'so that our algorithm produces different results each time
                        Randomize
                        If Rnd >= 0.5 Then Set GetNextMove = rngSquare
 
                    End If
                
                End With
            End If
        Range("AB68").Value = "Legal moves: " & rngMove1.Areas.Count
        Next rngSquare
        
    End If
 
End Function
 
'A function to get all the legal moves the knight can make
Private Function GetLegalMoves(ByRef Square As Range) As Range
    Dim rngCell As Range
    
    For Each rngCell In GetAllMoves(Square)
        If IsMoveLegal(rngCell) Then
 
            If GetLegalMoves Is Nothing Then
                Set GetLegalMoves = rngCell
            Else
                Set GetLegalMoves = Union(GetLegalMoves, rngCell)
            End If
 
        End If
    Next rngCell
    
End Function
 
'A function to determine if a move to a square is allowed
Private Function IsMoveLegal(ByRef Square As Range) As Boolean
    'has the square been visited yet?
    If IsEmpty(Square) Then
 
            'is the square on the chess board?
            If Not Intersect(Square, mrngChessBoard) Is Nothing Then IsMoveLegal = True
 
    End If
 
End Function
 
'A function to determine all the possible moves (legal or not) a knight could make
Private Function GetAllMoves(ByRef Square As Range) As Range
    With Square
        Set GetAllMoves = Union( _
                            .Offset(-2, -1), _
                            .Offset(-2, 1), _
                            .Offset(-1, -2), _
                            .Offset(-1, 2), _
                            .Offset(1, -2), _
                            .Offset(1, 2), _
                            .Offset(2, -1), _
                            .Offset(2, 1) _
                                )
    End With
End Function
 
'a function to determine a square on the chess board to start from
    
Private Function GetStartingSquare() As Range
 
    With mrngChessBoard
        'Full randomizer
        Dim sqrow As Integer
        Dim sqcol As Integer
        Randomize
        sqrow = Int(mlROW_COUNT * Rnd) + 1
        Randomize
        sqcol = Int(mlCOL_COUNT * Rnd) + 1
        Set GetStartingSquare = .Cells(sqrow, sqcol)
        'non random
        'Set GetStartingSquare = .Cells(mlROW_COUNT / 2, mlCOL_COUNT / 2)
        
    End With

End Function


Private Function GetSquareColor(ByRef level As Integer) As Integer
Dim x As Integer

    Select Case level
        Case 17
            x = 13
        Case 16
            x = 54
        Case 15
            x = 39
        Case 14
            x = 34
        Case 13
            x = 8
        Case 12
            x = 42
        Case 11
            x = 5
        Case 10
            x = 14
        Case 9
            x = 4
        Case 8
            x = 12
        Case 7
            x = 43
        Case 6
            x = 6
        Case 5
            x = 40
        Case 4
            x = 44
        Case 3
            x = 45
        Case 2
            x = 46
        Case 1
            x = 3
    End Select
GetSquareColor = x

End Function
```


----------

