'Revisit KnightMoves for QB64 started from Knight Moves 3 Recurring.txt for JB v2.0 B+ started 2018-10-06
' 2020-04-21 Overhaul MoveKnight SUB so can analyse solution after found.
' 2020-04-22 Cleanup code in MoveKnight SUB add timer and analyse moves. Try running most used moves first to try
' to speed up and reduce recursive calls, backfired completely!!! No solution found let alone using less iterations.
' Conclusion:
' The Knights Tour problem is very sentive to move order AND where the Knight starts.
' For instance, starting the Knight at 8, 8 instead of 1, 1 fails to find a solution after running
' millions and millions of calls. There must be a pattern needed to run the Knight to cover the board.
' So yes, might run the Knight according to where it is on board, specially edges and corners.
_TITLE "Knight Moves Extended with Analysis" 'b+ 2020-04-22 looking at moves made on board, DIM i
, board$
, start!
, tTime!
, lastx
, lasty
, x
, y
, position
, dx
, dy
, j
, high
, savej
board$
= STRING$(64, "b") 'using chr$(98) for not visited yet signalMoveKnight 1, 1, board$, 0
tTime!
= TIMER(.001) - start!
ShowBoard soln$
'=========================================== end of original code reworked
PRINT "Press any for analysis" 'find i find the dx, dy move from last position to current position
x
= position
MOD 8: y
= INT(position
/ 8) + 1 IF x
= 0 THEN x
= 8: y
= y
- 1 'PRINT i, x, y
'INPUT "ok ..."; wate$ 'ok working
dx = x - lastx: dy = y - lasty
lastx = x: lasty = y
PRINT "Here is listing of how many times a move was made:" PRINT "Lets sort this list so most used move is first and least is last and rerun the soln to see if we saved time and interations." 'search moves for highest number
high = 0: savej = 0
IF moves
(j
) > high
THEN high
= moves
(j
): savej
= j
newDX(i) = dx(savej): newDY(i) = dy(savej): moves(savej) = 0 'remove j from search candidates
PRINT "New dx, dy order:" FOR i
= 1 TO 8 'trading places dx(i) = newDX(i): dy(i) = newDY(i)
PRINT "Press any to run recursive sub again..." 'reset and run MoveKnight again to see if save time and recursive calls
soln$ = "": counter&& = 0
board$
= STRING$(64, "b") 'using chr$(98) for not visited yet signalMoveKnight 1, 1, board$, 0
tTime!
= TIMER(.001) - start!
ShowBoard soln$
SUB MoveKnight
(x
, y
, board$
, beenHere
) ' copy solution of Knight's Tour to SHARED soln$ variable ' x, y have been prechecked to be in the board, will test to see if been here (x, y) yet.
' board$ is the current instance of chess board$ with places Knight has been already.
' beenHere is the current move number the knight is on.
IF soln$
<> "" THEN EXIT SUB '<<<<<<<<<<<<<<<< stop the solution has been found! DIM cy
, cx
, cBoard$
, cBeenHere
' copy all incoming cx = x: cy = y: cBoard$ = board$: cBeenHere = beenHere
position = (cy - 1) * 8 + cx 'convert x, y to a position in a board string 64 characters long
IF MID$(cBoard$
, position
, 1) = CHR$(98) THEN ' have not been here yet cBeenHere = cBeenHere + 1 'add position to board string
MID$(cBoard$
, position
, 1) = CHR$(cBeenHere
) counter&& = counter&& + 1
IF counter&&
MOD 1000 = 0 THEN ShowBoard cBoard$
'slows down soln by 1-2 secs 'check now that the recursive call is in bounds
MoveKnight cx + dx(m), cy + dy(m), cBoard$, cBeenHere
ELSE 'we are done and have a solution to show! soln$ = cBoard$ ' copy soln to shared variable
PRINT counter&&;
"recursive calls" visit
= ASC(MID$(b$
, row
* 8 + col
, 1))