Knight Moves

[bplus]

AKA Knight's Tour at Rosetta:

Code: QB64: [Select]

1. 'Knight Moves 3 Recurring.txt for JB v2.0 B+ started 2018-10-06
2. OPTION _EXPLICIT
3. _CONTROLCHR OFF
4. DEFINT A-Z
5. 'OK try some recusion
6. DIM SHARED counter&&
7.  
8. DIM SHARED dxa(1 TO 8)
9. DIM SHARED dya(1 TO 8)
10.  
11. DIM i, startx, starty, beenHere
12. DIM board$
13.  
14. DATA 2,1,-1,-2,-2,-1,1,2
15. FOR i = 1 TO 8
16.     READ dxa(i)
17. NEXT
18. DATA 1,2,2,1,-1,-2,-2,-1
19. FOR i = 1 TO 8
20.     READ dya(i)
21. NEXT
22.  
23. FOR i = 1 TO 64
24.     board$ = board$ + CHR$(98) 'using chr$(98) for not visited yet signal
25. NEXT
26. 'PRINT board$
27.  
28. startx = 1: starty = 1: beenHere = 0
29. MoveKnight startx, starty, board$, beenHere
30.  
31. SUB MoveKnight (x, y, board$, beenHere)
32.     'recursive procedure: from this x, y position
33.     'first check if position is OK to move into, if so
34.     '    record the position in the board
35.     '    then see if the board is complete, show soultion if so
36.     '    else find new positions to move to by recursive calls
37.     'else dead end exit
38.     'convert x, y to a position in a string 64 characters long
39.     DIM cy, cx, cBoard$, cBeenHere
40.     cx = x: cy = y: cBoard$ = board$: cBeenHere = beenHere
41.     DIM position, m, dx, dy, wate$
42.     position = (cy - 1) * 8 + cx
43.     IF MID$(cBoard$, position, 1) = CHR$(98) THEN 'OK to move here
44.         'PRINT board$
45.         'add position to board string
46.         cBeenHere = cBeenHere + 1
47.         MID$(cBoard$, position, 1) = CHR$(cBeenHere)
48.  
49.         'check board finished ha!
50.         IF INSTR(cBoard$, CHR$(98)) > 0 THEN 'not done
51.  
52.             'progress report
53.             counter&& = counter&& + 1
54.             IF counter&& MOD 10000 = 0 THEN
55.                 'IF counter&& MOD 1 = 0 THEN
56.                 ShowBoard cBoard$
57.                 '_DELAY .20 'really will bog down processing!
58.             END IF
59.  
60.             FOR m = 1 TO 8
61.                 dx = dxa(m)
62.                 dy = dya(m)
63.                 'check now that the recursive call is in bounds
64.                 IF cx + dx >= 1 AND cx + dx <= 8 THEN
65.                     IF cy + dy >= 1 AND cy + dy <= 8 THEN
66.                         MoveKnight cx + dx, cy + dy, cBoard$, cBeenHere
67.                     END IF
68.                 END IF
69.             NEXT
70.         ELSE 'we are done and have a solution to show!
71.             ShowBoard cBoard$
72.             PRINT
73.             PRINT "    That's All Folks!"
74.             END
75.         END IF
76.     END IF
77. END SUB
78.  
79. SUB ShowBoard (b$)
80.     DIM row, col, visit
81.     CLS
82.     PRINT counter&&
83.     FOR row = 0 TO 7
84.         FOR col = 1 TO 8
85.             LOCATE row + 3, col * 4
86.             visit = ASC(MID$(b$, row * 8 + col, 1))
87.             IF visit = 98 THEN PRINT "    " ELSE PRINT RIGHT$("    " + STR$(visit), 4)
88.         NEXT
89.     NEXT
90. END SUB
91.  

A better version of this can be made by using a recursive function returning 1 if solved and 0 if not, then you would NOT have to carry around a copy of the board.

[Qwerkey]

Well, that's got that covered.

[Thunder Cat]

This version would run much faster if a modification was made for corner movements. Specifically, there is only one way into and out of a corner square. So when you get to C2, the next two moves are always A1 and B3. Or, if you approach from B3, the next two moves are always A1 and C2. In the version shown, you are investigating all the possibilities ignoring this fact, so you spend a huge amount of time investigating paths that lead to nowhere, because you have to do the search for each of the four corners

[bplus]

This version would run much faster if a modification was made for corner movements. Specifically, there is only one way into and out of a corner square. So when you get to C2, the next two moves are always A1 and B3. Or, if you approach from B3, the next two moves are always A1 and C2. In the version shown, you are investigating all the possibilities ignoring this fact, so you spend a huge amount of time investigating paths that lead to nowhere, because you have to do the search for each of the four corners

Nope don't think so, you are suggesting more conditional testing which is sure to slow down code.

Of course you could prove me wrong ;-))

For me, this is the right amount of code with a timely solution.

[Cobalt]

What exactly is this doing?

[bplus]

Knight covers chess board starting at #1 spot top left without repeating a spot:
http://rosettacode.org/wiki/Knight%27s_tour

 

Sure probably are smarter ways but this is done in under a minute so really, how much time do you want to spend on this?

[TempodiBasic]

Hi Bplus
Cool

about goal I'm a bit confusing....

you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

my ability to understand gets that I must move the Knight on each of 64 cells of chessboard touching one time the single cell, because I cannot pass 2 times on the same cell.

while the image doesn't show this but a simple tour on the chessboard of 24 steps in which the knight uses one time a cell to travel
http://rosettacode.org/mw/images/c/cd/Knight%27s_tour_7x7.png


PS: I see you follow the main stream of output ... no graphic output or Algebrical output but ASCII rappresentation of chessboard with the number of move in each cell. A good comparison.

If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered according to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.

[bplus]

Thanks TempodiBasic, maybe you are confused by the instruction that the knight does not have to return to where it started like a "closed" loop or circuit would be.

You know, since this topic has been reawakened, I have a thought how it might be done faster. I will update if experiment is successful.

Update: Well I learned something kind of ugly about this code, it won't stop if you put EXIT SUB in place of END in the subroutine. ;-(( yikes it goes Energizer bunny on me, but I have that fixed with an extra shared variable and check at start of SUB, a hack job. Now I can analyse solution and continue with experiment.

[bplus]

Well experiment was dismal failure; guess I had pretty naive idea how this thing worked; see conclusions in code comments. So I guess if I were to pursue this further: study solution for a pattern and yes, use a bunch of IF blocks to test where Knight is on board specially edges and corners.

Code: QB64: [Select]

1. OPTION _EXPLICIT
2. 'Revisit KnightMoves for QB64 started from Knight Moves 3 Recurring.txt for JB v2.0 B+ started 2018-10-06
3. ' 2020-04-21 Overhaul MoveKnight SUB so can analyse solution after found.
4. ' 2020-04-22 Cleanup code in MoveKnight SUB add timer and analyse moves. Try running most used moves first to try
5. ' to speed up and reduce recursive calls, backfired completely!!!  No solution found let alone using less iterations.
6. ' Conclusion:
7. ' The Knights Tour problem is very sentive to move order AND where the Knight starts.
8. ' For instance, starting the Knight at 8, 8 instead of 1, 1 fails to find a solution after running
9. ' millions and millions of calls. There must be a pattern needed to run the Knight to cover the board.
10. ' So yes, might run the Knight according to where it is on board, specially edges and corners.
11.  
12. _CONTROLCHR OFF
13. DEFINT A-Z
14. _TITLE "Knight Moves Extended with Analysis" 'b+ 2020-04-22 looking at moves made on board,
15. DIM SHARED counter&&, soln$, dx(1 TO 8), dy(1 TO 8)
16. DIM i, board$, start!, tTime!, lastx, lasty, x, y, position, dx, dy, j, high, savej
17.  
18. DATA 2,1,-1,-2,-2,-1,1,2
19. FOR i = 1 TO 8
20.     READ dx(i)
21. NEXT
22. DATA 1,2,2,1,-1,-2,-2,-1
23. FOR i = 1 TO 8
24.     READ dy(i)
25. NEXT
26. board$ = STRING$(64, "b") 'using chr$(98) for not visited yet signal
27. start! = TIMER(.001)
28. MoveKnight 1, 1, board$, 0
29. tTime! = TIMER(.001) - start!
30. ShowBoard soln$
31. PRINT tTime!; "secs"
32. '=========================================== end of original code reworked
33.  
34. PRINT "Press any for analysis"
35. SLEEP
36. PRINT: PRINT "Analyzing..."
37. DIM moves(1 TO 8)
38. FOR i = 1 TO 64
39.     'find i find the dx, dy move from last position to current position
40.     position = INSTR(soln$, CHR$(i))
41.     x = position MOD 8: y = INT(position / 8) + 1
42.     IF x = 0 THEN x = 8: y = y - 1
43.     'PRINT i, x, y
44.     'INPUT "ok ..."; wate$   'ok working
45.     IF i > 1 THEN
46.         dx = x - lastx: dy = y - lasty
47.         FOR j = 1 TO 8
48.             IF dx(j) = dx AND dy(j) = dy THEN moves(j) = moves(j) + 1: EXIT FOR
49.         NEXT
50.     END IF
51.     lastx = x: lasty = y
52. NEXT
53. PRINT "Here is listing of how many times a move was made:"
54. FOR i = 1 TO 8
55.     PRINT i, moves(i)
56. NEXT
57. 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."
58. DIM newDX(1 TO 8), newDY(1 TO 8)
59. FOR i = 1 TO 8
60.     'search moves for highest number
61.     high = 0: savej = 0
62.     FOR j = 1 TO 8
63.         IF moves(j) > high THEN high = moves(j): savej = j
64.     NEXT
65.     newDX(i) = dx(savej): newDY(i) = dy(savej): moves(savej) = 0 'remove j from search candidates
66. NEXT
67. PRINT "New dx, dy order:"
68. FOR i = 1 TO 8 'trading places
69.     dx(i) = newDX(i): dy(i) = newDY(i)
70.     PRINT dx(i), dy(i)
71. NEXT
72. PRINT "Press any to run recursive sub again..."
73. SLEEP
74. 'reset and run MoveKnight again to see if save time and recursive calls
75. soln$ = "": counter&& = 0
76. board$ = STRING$(64, "b") 'using chr$(98) for not visited yet signal
77. start! = TIMER(.001)
78. MoveKnight 1, 1, board$, 0
79. tTime! = TIMER(.001) - start!
80. ShowBoard soln$
81. PRINT tTime!; "secs"
82. SLEEP
83.  
84. SUB MoveKnight (x, y, board$, beenHere) ' copy solution of Knight's Tour to SHARED soln$ variable
85.     ' x, y have been prechecked to be in the board, will test to see if been here (x, y) yet.
86.     ' board$ is the current instance of chess board$ with places Knight has been already.
87.     ' beenHere is the current move number the knight is on.
88.  
89.     IF soln$ <> "" THEN EXIT SUB '<<<<<<<<<<<<<<<< stop the solution has been found!
90.     DIM cy, cx, cBoard$, cBeenHere ' copy all incoming
91.     cx = x: cy = y: cBoard$ = board$: cBeenHere = beenHere
92.     DIM position, m
93.     position = (cy - 1) * 8 + cx 'convert x, y to a position in a board string 64 characters long
94.     IF MID$(cBoard$, position, 1) = CHR$(98) THEN '  have not been here yet
95.         cBeenHere = cBeenHere + 1 'add position to board string
96.         MID$(cBoard$, position, 1) = CHR$(cBeenHere)
97.         IF INSTR(cBoard$, CHR$(98)) > 0 THEN ' still empty spots so not done
98.             counter&& = counter&& + 1
99.             IF counter&& MOD 1000 = 0 THEN ShowBoard cBoard$ 'slows down soln by 1-2 secs
100.             FOR m = 1 TO 8
101.                 'check now that the recursive call is in bounds
102.                 IF cx + dx(m) >= 1 AND cx + dx(m) <= 8 THEN
103.                     IF cy + dy(m) >= 1 AND cy + dy(m) <= 8 THEN
104.                         MoveKnight cx + dx(m), cy + dy(m), cBoard$, cBeenHere
105.                     END IF
106.                 END IF
107.             NEXT
108.         ELSE 'we are done and have a solution to show!
109.             soln$ = cBoard$ ' copy soln to shared variable
110.         END IF
111.     END IF
112. END SUB
113.  
114. SUB ShowBoard (b$)
115.     DIM row, col, visit
116.     CLS
117.     PRINT counter&&; "recursive calls"
118.     FOR row = 0 TO 7
119.         FOR col = 1 TO 8
120.             LOCATE row + 3, col * 4
121.             visit = ASC(MID$(b$, row * 8 + col, 1))
122.             IF visit = 98 THEN PRINT "    " ELSE PRINT RIGHT$("    " + STR$(visit), 4)
123.         NEXT
124.     NEXT
125.     PRINT
126. END SUB
127.  
128.  

[bplus]

OK Thunder Cat, I rewrote the whole program to only move to squares accessible to each square such that (yeah) each corner is only accessible or accesses 2 other squares but guess what, it's no faster, it runs the same amount of recursive SUB calls (and thus time as well).

BUT! I did find a much better place to start AND a much better sequence of moves to try such that, I cut the time and recursive SUB calls by 1/3!

Code: QB64: [Select]

1. _TITLE "Knight IF Here Moves" ' b+ started 2020-04-24
2. ' 2020-04-24 start over the Rosetta Code challenge called Knight's Tour
3. ' try testing moves from a matrix listing possible positions from a given position
4.  
5. DEFINT A-Z
6. CONST sq = 8 'try to work this for any sq size
7. DIM SHARED km(1 TO sq * sq, 1 TO 8), dx(1 TO 8), dy(1 TO 8), counter&&, soln$
8. 'from any of 64, km stands for knight move the first dim indexes the sq position in one variable
9. 'the 2nd dimension lists the positions a move go goto
10. DATA 2,1,-1,-2,-2,-1,1,2
11. FOR i = 1 TO 8
12.     READ dx(i)
13. NEXT
14. DATA 1,2,2,1,-1,-2,-2,-1
15. FOR i = 1 TO 8
16.     READ dy(i)
17. NEXT
18.  
19. 'testLoad = 1    ' << uncomment to check the load of km(sq, moves available)  OK looks good
20. FOR p = 1 TO sq * sq 'load our km(p, m(1) to m(8)) array
21.     xy p, x, y 'get x, y for each square position on board
22.     IF testLoad THEN PRINT RIGHT$("   " + _TRIM$(STR$(p)), 3); ": ";
23.     FOR m = 1 TO 8
24.         'see if the knight move is on the board
25.         IF x + dx(m) >= 1 AND x + dx(m) <= sq THEN
26.             IF y + dy(m) >= 1 AND y + dy(m) <= sq THEN
27.                 km(p, m) = position(x + dx(m), y + dy(m))
28.                 IF testLoad THEN PRINT RIGHT$("   " + _TRIM$(STR$(km(p, m))), 3);
29.             ELSE
30.                 IF testLoad THEN PRINT " 00";
31.             END IF
32.         ELSE
33.             IF testLoad THEN PRINT " 00";
34.         END IF
35.     NEXT
36.     PRINT
37. NEXT
38.  
39. board$ = STRING$(64, "b") 'using chr$(98) for not visited yet signal'PRINT board$
40. start! = TIMER(.001)
41. MoveKnight 64, board$, 0
42. tTime! = TIMER(.001) - start!
43. ShowBoard soln$
44. PRINT: PRINT tTime!; "secs"
45.  
46. SUB MoveKnight (xyPlace, board$, beenHere) ' copy solution of Knight's Tour to SHARED soln$ variable
47.     ' x, y have been prechecked to be in the board, will test to see if been here (x, y) yet.
48.     ' board$ is the current instance of chess board$ with places Knight has been already.
49.     ' beenHere is the current move number the knight is on.
50.  
51.     IF soln$ <> "" THEN EXIT SUB '<<<<<<<<<<<<<<<< stop the solution has been found!
52.     cBoard$ = board$
53.     'place = position(x, y) 'convert x, y to a position in a board string 64 characters long
54.     IF MID$(cBoard$, xyPlace, 1) = "b" THEN '  have not been here yet
55.         MID$(cBoard$, xyPlace, 1) = CHR$(beenHere + 1)
56.         IF INSTR(cBoard$, "b") > 0 THEN ' still empty spots so not done
57.             counter&& = counter&& + 1
58.             IF counter&& MOD 1000 = 0 THEN ShowBoard cBoard$ 'slows down soln by 1-2 secs
59.             FOR m = 8 TO 1 STEP -1
60.                 IF km(xyPlace, m) THEN 'try the place to move to
61.                     MoveKnight km(xyPlace, m), cBoard$, beenHere + 1
62.                 END IF
63.             NEXT
64.         ELSE 'we are done and have a solution to show!
65.             soln$ = cBoard$ ' copy soln to shared variable
66.         END IF
67.     END IF
68. END SUB
69.  
70. SUB ShowBoard (b$)
71.     DIM row, col, visit
72.     CLS
73.     PRINT counter&&
74.     FOR row = 0 TO 7
75.         FOR col = 1 TO 8
76.             LOCATE row + 3, col * 4
77.             visit = ASC(MID$(b$, row * 8 + col, 1))
78.             IF visit = 98 THEN PRINT "    " ELSE PRINT RIGHT$("    " + STR$(visit), 4)
79.         NEXT
80.     NEXT
81. END SUB
82.  
83. ''test position function and xy sub OK good!
84. 'FOR p = 1 TO 64
85. '    xy p, px, py
86. '    PRINT position(px, py); "="; px; ","; py,
87. 'NEXT
88.  
89. SUB xy (place, x, y) 'note sq is const square board side size
90.     y = INT(place / sq) + 1: x = place MOD sq
91.     IF x = 0 THEN x = sq: y = y - 1
92. END SUB
93.  
94. FUNCTION position (x, y) 'note sq is const square board side size
95.     position = (y - 1) * sq + x
96. END FUNCTION
97.  
98.  

 

[bplus]

Just to show, it wasn't new code technique that improved the time and number of calls, here is original method with the new start point (8, 8) opposite diagonally from (1, 1) and new move order (reverse of original):

Code: QB64: [Select]

1. _TITLE "Knight Moves" 'b+ updated version with soln$ passed to main program 2020-04-23
2. ' 2020-04-24 cut some variable assignments from main sub to save time
3. DEFINT A-Z
4. DIM SHARED counter&&, soln$, dx(1 TO 8), dy(1 TO 8)
5. DATA 2,1,-1,-2,-2,-1,1,2
6. FOR i = 1 TO 8
7.     READ dx(i)
8. NEXT
9. DATA 1,2,2,1,-1,-2,-2,-1
10. FOR i = 1 TO 8
11.     READ dy(i)
12. NEXT
13. board$ = STRING$(64, "b") 'using chr$(98) for not visited yet signal'PRINT board$
14. start! = TIMER(.001)
15. MoveKnight 8, 8, board$, 0
16. ttime! = TIMER(.001) - start!
17. ShowBoard soln$
18. PRINT: PRINT ttime!; "sec"
19.  
20. SUB MoveKnight (x, y, board$, beenHere) ' copy solution of Knight's Tour to SHARED soln$ variable
21.     ' x, y have been prechecked to be in the board, will test to see if been here (x, y) yet.
22.     ' board$ is the current instance of chess board$ with places Knight has been already.
23.     ' beenHere is the current move number the knight is on.
24.  
25.     IF soln$ <> "" THEN EXIT SUB '<<<<<<<<<<<<<<<< stop the solution has been found!
26.     cBoard$ = board$
27.     position = (y - 1) * 8 + x 'convert x, y to a position in a board string 64 characters long
28.     IF MID$(cBoard$, position, 1) = "b" THEN '  have not been here yet
29.         MID$(cBoard$, position, 1) = CHR$(beenHere + 1)
30.         IF INSTR(cBoard$, "b") > 0 THEN ' still empty spots so not done
31.             counter&& = counter&& + 1
32.             IF counter&& MOD 1000 = 0 THEN ShowBoard cBoard$ 'slows down soln .25-.5 secs
33.             FOR m = 8 TO 1 STEP -1
34.                 'check now that the recursive call is in bounds
35.                 IF x + dx(m) >= 1 AND x + dx(m) <= 8 THEN
36.                     IF y + dy(m) >= 1 AND y + dy(m) <= 8 THEN
37.                         MoveKnight x + dx(m), y + dy(m), cBoard$, beenHere + 1
38.                     END IF
39.                 END IF
40.             NEXT
41.         ELSE 'we are done and have a solution to show!
42.             soln$ = cBoard$ ' copy soln to shared variable
43.         END IF
44.     END IF
45. END SUB
46.  
47. SUB ShowBoard (b$)
48.     DIM row, col, visit
49.     CLS
50.     PRINT counter&&
51.     FOR row = 0 TO 7
52.         FOR col = 1 TO 8
53.             LOCATE row + 3, col * 4
54.             visit = ASC(MID$(b$, row * 8 + col, 1))
55.             IF visit = 98 THEN PRINT "    " ELSE PRINT RIGHT$("    " + STR$(visit), 4)
56.         NEXT
57.     NEXT
58. END SUB
59.  

Result:

[TempodiBasic]

Hi Bplus
I'm having a strange experience with latest code posted if I try the task starting from a natural position of black knight Kd7 that translated into cohordinates for your code are 4,2.
I have taken a screenshot, and I have written this post, but it is still running to solve the task....now is at 75405000
screenshot has been taken before this
 

Do you think that some start positions have no solution for a complete tour of chessboard with one passing on each cell?

[bplus]

Do you think that some start positions have no solution for a complete tour of chessboard with one passing on each cell?

@TempodiBasic,
As noted already, the Knight's Tour as coded here is extremely sensitive to the starting position and the ordering of the way you test moves. I think, eventually, if you don't burn out the CPU you will get a solution but who wants to wait for (6.xxx or 7.xxx?)^64 recursive calls if you happen to start wrong near the beginning?

As you can see in the fast soln, 3 corners are covered in 21 moves, so definitely think starting at corner is really good one corner done free of charge! As Thunder Cat implied, the corners seem to be the bottle neck of the Tour, you got to go in and out just right 4 times if you don't start in one.

[TempodiBasic]

Thanks Bplus,
so the combinations are very massive and  if we start not from a corner we increase very much the work to do to get the solution. Well.
But apart the language of programming and the algorythm, it is cleared if there is a solution for any position of starting?

[TempodiBasic]

Just now I have controlled your Knight application that was running while I was writing in QB64.org/forum..
well it has done the work also for that position...