
1. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
BluShadow Jun 5, 2019 7:36 AM (in response to Ranagal)Of course you could use a similar solution with recursive subquery factoring. The trick is going to be modelling in some way a structure to represent the board, which coordinates have been visited, and how the knight moves from one coordinate to another. You could do that using a single string to represent the board, or 8 strings to represent each "row" on the board, or 64 separate values to represent each coordinate... though that would be a lot of parameters to the recursive query.
Have you had a go yourself? How far did you get?

2. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Ranagal Jun 5, 2019 11:12 AM (in response to BluShadow)No. It needs many inputs like you rightly mentioned. That's why I thought of asking experts on this forum. I'm glad to learn it if someone shows how it can be done.
Regards,
Ranagal

3. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
mathguy Jun 5, 2019 12:42 PM (in response to BluShadow)BluShadow wrote:
Of course you could use a similar solution with recursive subquery factoring.
Really? How?

4. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
BluShadow Jun 5, 2019 12:59 PM (in response to Ranagal)1 person found this helpfulPerhaps something along these lines (unoptimized as I don't have much time)...
with t(nowt) as (select '0000000000000000' from dual)
,tour(r1, r2, r3, r4, r5, r6, r7, r8, r, c, mv, strt) as (
select case when r != 1 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r1
,case when r != 2 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r2
,case when r != 3 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r3
,case when r != 4 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r4
,case when r != 5 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r5
,case when r != 6 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r6
,case when r != 7 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r7
,case when r != 8 then nowt else lpad('0',(c1)*2,'0')'01'lpad('0',(8c)*2,'0') end as r8
,r
,c
,1
,strt
from (select nowt
,floor((level1)/8)+1 as r  row
,mod(level1,8)+1 as c  column
,level as strt
from t
connect by level <= 64
)  all the starting positions
union all
select case when tour.r + m.mr = 1 then case when tour.c + m.mc > 1 then substr(tour.r1,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r1,(((tour.c + m.mc)1)*2)+3) else tour.r1 end
,case when tour.r + m.mr = 2 then case when tour.c + m.mc > 1 then substr(tour.r2,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r2,(((tour.c + m.mc)1)*2)+3) else tour.r2 end
,case when tour.r + m.mr = 3 then case when tour.c + m.mc > 1 then substr(tour.r3,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r3,(((tour.c + m.mc)1)*2)+3) else tour.r3 end
,case when tour.r + m.mr = 4 then case when tour.c + m.mc > 1 then substr(tour.r4,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r4,(((tour.c + m.mc)1)*2)+3) else tour.r4 end
,case when tour.r + m.mr = 5 then case when tour.c + m.mc > 1 then substr(tour.r5,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r5,(((tour.c + m.mc)1)*2)+3) else tour.r5 end
,case when tour.r + m.mr = 6 then case when tour.c + m.mc > 1 then substr(tour.r6,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r6,(((tour.c + m.mc)1)*2)+3) else tour.r6 end
,case when tour.r + m.mr = 7 then case when tour.c + m.mc > 1 then substr(tour.r7,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r7,(((tour.c + m.mc)1)*2)+3) else tour.r7 end
,case when tour.r + m.mr = 8 then case when tour.c + m.mc > 1 then substr(tour.r8,1,((tour.c + m.mc)1)*2) else null endto_char(tour.mv+1,'fm00')substr(tour.r8,(((tour.c + m.mc)1)*2)+3) else tour.r8 end
,tour.r + m.mr
,tour.c + m.mc
,tour.mv + 1
,strt
from tour
join
(  8 potential directions of movement
select 2 as mr, 1 as mc from dual union all
select 2, 1 from dual union all
select 1, 2 from dual union all
select 1, 2 from dual union all
select 1, 2 from dual union all
select 1, 2 from dual union all
select 2, 1 from dual union all
select 2, 1 from dual
) m on (
 where the new position would be on the board
tour.r + m.mr between 1 and 8
and tour.c + m.mc between 1 and 8
 and the new position is not already used
and case tour.r + m.mr
when 1 then substr(tour.r1,(((tour.c + m.mc)1)*2)+1,2)
when 2 then substr(tour.r2,(((tour.c + m.mc)1)*2)+1,2)
when 3 then substr(tour.r3,(((tour.c + m.mc)1)*2)+1,2)
when 4 then substr(tour.r4,(((tour.c + m.mc)1)*2)+1,2)
when 5 then substr(tour.r5,(((tour.c + m.mc)1)*2)+1,2)
when 6 then substr(tour.r6,(((tour.c + m.mc)1)*2)+1,2)
when 7 then substr(tour.r7,(((tour.c + m.mc)1)*2)+1,2)
when 8 then substr(tour.r8,(((tour.c + m.mc)1)*2)+1,2)
else null
end = '00'
)
where tour.mv+1 <= 64
)
select tour.*
,r1chr(10)r2chr(10)r3chr(10)r4chr(10)r5chr(10)r6chr(10)r7chr(10)r8chr(10) as soln
from tour
where mv = 64
Each "row" is a row on the board, and that row is made up of 16 digits, with each pair of digits representing a square on the board.
As the tour progresses, each "00" get's given the move number, and all solutions that reach the 64th move are considered as successful.
The only bit missing from this is rule that says the final position should be one move from the starting position (if you want to find closed tours)
Note: I've only run it to generate the first few moves just to test the logic, so not sure if it'll blow Oracle's memory (or indeed if it's completely correct ) having to do all 64 possible moves.
It's a starting point.

5. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
mathguy Jun 5, 2019 1:02 PM (in response to Ranagal)Not possible.
You seem to believe that the Knight's Tour problem is similar to solving a Sudoku. It is not.
In Sudoku, you are not given a blank board and asked to find ALL the correct completed games. Instead, you are given a board that is already filled about 1/3 of the way, and  if the Sudoku is correct  there is only one correct solution you are asked to find. (At least, that's the problem Anton Scheffer's code solves.) The analog in the Knight's Tour would be to have most of a "knight's tour" given, and be asked to complete it, knowing that the solution is unique. Very different (and very likely, a very easy and boring) problem.
In principle, but unfortunately not in practice, Anton's code CAN be used to find all correct sudoku (all correct completed games)  just start with a blank board and look for ALL solutions. Indeed, his code makes no assumption about the uniqueness of the solution; given a game partially filled out, which still has several distinct solution, his code will find ALL of those. So if you start with a blank board, you will find all the correct sudokus. The problem is that the number of such solutions is about 6 * 10^21. The program will crash long before it will get anywhere close to completed games. (And note that Anton's code doesn't have any features to allow it to find "some"  a small number of  solutions; it will, indeed, look for ALL of them at the same time.)
On a chessboard there are about 2.6 * 10^13 knight's CIRCUITS (tours with the additional condition that the knight can jump from the last position to the first in a legal knight's move). And this is just the number of "final answers"; there are 4 * 10^51 move sequences on the board, that must either be accepted or rejected by any code you write.
So: To solve the Knight's Tour problem, unlike Sudoku, you need an ALGORITHM. And finding an algorithm for the Knight's Tour has nothing to do with SQL, or with computer programming in general. The first step is to find an algorithm (by Googling, for example); IMPLEMENTING the algorithm, in SQL or in any other language, is where programming begins. Note, however, that there are no simple algorithms for this. There is a heuristic rule, Warnsdorff's rule, which is just that  a heuristic. (Some dunces online call it "Warnsdorff's ALGORITHM"  they probably don't even understand the difference.) You can, of course, try to implement a heuristic, but keep in mind that  while it may work  it also may not. There is no GUARANTEE that you will find a solution following a heuristic. Still, that's perhaps the best chance you have; and, since your purpose is to practice writing interesting SQL code for learning, that is probably all you need.

6. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
BluShadow Jun 5, 2019 1:30 PM (in response to mathguy)mathguy wrote:
In principle, but unfortunately not in practice, Anton's code CAN be used to find all correct sudoku (all correct completed games)  just start with a blank board and look for ALL solutions. Indeed, his code makes no assumption about the uniqueness of the solution; given a game partially filled out, which still has several distinct solution, his code will find ALL of those. So if you start with a blank board, you will find all the correct sudokus. The problem is that the number of such solutions is about 6 * 10^21. The program will crash long before it will get anywhere close to completed games. (And note that Anton's code doesn't have any features to allow it to find "some"  a small number of  solutions; it will, indeed, look for ALL of them at the same time.)
Well, Anton's solution can't be coded to find ALL or SOME solutions to a Sudoku puzzle, because each puzzle only has 1 solution anyway, so that's somewhat of a difference to the Knights Tour problem where there can be multiple solutions. As you say... it's a lot of solutions/paths to check hence why I didn't run it to the full 64 moves in my own testing.

7. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Paulzip Jun 5, 2019 1:35 PM (in response to Ranagal)Concurring with Mathguy here, I think you are underestimating the complexity and number of sequences involved in finding solutions to this problem. There are many mathematical papers on it and the best approaches I've read about seem to be a divide and rejoin  on an 8 x 8, solve for a 4 x 4 for a set of single visit solutions and for those pick quadrants whose subsequent move is the start of the next quadrant  even that is still an O(n^2) time problem  other approaches tend to involve neural net solution, which is probably outside your capability.
Perhaps try a simpler problem like
 Knight's tour 4 x 4
 8 Queens puzzle.

8. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Frank Kulash Jun 5, 2019 1:57 PM (in response to Ranagal)1 person found this helpfulHi, Ranagal,
I did it this way:
WITH cntr (n) AS
(
SELECT LEVEL
FROM dual
CONNECT BY LEVEL <= 8
)
, board (r, f, r_str, f_str) AS
(
SELECT rnk.n
, fil.n
, TO_CHAR (rnk.n)
, CHR (ASCII ('a') + fil.n  1)
FROM cntr rnk
CROSS JOIN cntr fil
)
SELECT SYS_CONNECT_BY_PATH ( r_str  f_str
, ' '
) AS path
FROM board
WHERE LEVEL = &num_moves
START WITH r = 1
AND f = 2
CONNECT BY NOCYCLE (PRIOR r, PRIOR f) IN ( (r + 1, f + 2)
, (r + 1, f  2)
, (r  1, f + 2)
, (r  1, f  2)
, (r + 2, f + 1)
, (r + 2, f  1)
, (r  2, f + 1)
, (r  2, f  1)
)
AND LEVEL <= &num_moves
AND ROWNUM <= 2  number of paths to display
;
Instead of hardcoding the number of moves, I made it a substitution variable, to make testing and debugging easier. When num_moves was 32, results came back immediately, but when I increased it to 64, this took 5 minutes on my laptop. The results I got were:
PATH

1b 2d 1f 2h 3f 1e 2c 1a 3b 1c 2a 3c 1d 2b 3d 2f
1h 3g 2e 1g 3h 4f 2g 3e 4c 3a 5b 4d 5f 4h 6g 5e
4g 6f 5h 7g 6e 8d 7b 5a 6c 7a 8c 6d 8e 7c 8a 6b
4a 5c 4e 5g 7h 8f 7d 8b 6a 4b 5d 7e 8g 6h 7f 8h1b 2d 1f 2h 3f 1e 2c 1a 3b 1c 2a 3c 1d 2b 3d 2f
1h 3g 2e 1g 3h 4f 2g 3e 4c 3a 5b 4d 5f 4h 6g 5e
4g 6f 5h 7g 8e 6d 4e 5c 4a 6b 8a 7c 5d 4b 6a 8b
7d 8f 7h 5g 6e 8d 7b 5a 6c 7a 8c 7e 8g 6h 7f 8hI just showed 2 of the many possible tours for a knight starting on rank 1, file b.
Originally, I tried this CONNECT BY condition:
CONNECT BY NOCYCLE ABS ( (r  PRIOR r)
* (f  PRIOR f)
) = 2
but it was extremely slow.

9. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
mathguy Jun 5, 2019 2:47 PM (in response to Frank Kulash)Frank Kulash wrote:
Hi, Ranagal,
I did it this way: [............]
Very interesting! This shows that my understanding of the way CONNECT BY queries work internally is fatally flawed.
I modified your query by removing the rowlimiting clause at the end, changing the number of levels to 63 (instead of 64), and wrapping the outer query within SELECT COUNT(*) FROM ....  to see how many 63move sequences are found. Before seeing your solution I thought this should crash out pretty quickly.
Instead, I canceled the query after 15 minutes. It hadn't crashed yet, and I don't know if it would crash eventually, or if it would give an answer after one hour, one week, or a hundred years.
But the query you wrote, exactly as you wrote it, did return the same two completed answers, in a little over three minutes (on a desktop rather than laptop).
So, here is what I don't understand. This seems to demonstrate pretty clearly that some rows at LEVEL = 64 are being generated BEFORE all the rows at LEVEL = 63 have been produced. I thought just the opposite: no row at LEVEL = 64 is ever produced before ALL rows are LEVEL = 63 are generated.
Learning something new every day.

10. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Ranagal Jun 5, 2019 5:05 PM (in response to BluShadow)Quite lengthy. Thanks for the initial thoughts on this.
Regards,
Ranagal

11. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Ranagal Jun 5, 2019 5:06 PM (in response to Frank Kulash)True genius. Thanks for the solution Frank.
Regards,
Ranagal

12. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Stew Ashton Jun 5, 2019 5:22 PM (in response to mathguy)mathguy wrote:
...
This seems to demonstrate pretty clearly that some rows at LEVEL = 64 are being generated BEFORE all the rows at LEVEL = 63 have been produced. I thought just the opposite: no row at LEVEL = 64 is ever produced before ALL rows are LEVEL = 63 are generated.
With recursive subquery factoring, you have the choice (copied/pasted from the documentation):
 Specify BREADTH FIRST BY if you want sibling rows returned before any child rows are returned.
 Specify DEPTH FIRST BY if you want child rows returned before any siblings rows are returned.
As far as I can tell from using it for years, CONNECT BY does "depth first" and we have no choice.
Regards, Stew

13. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
Ranagal Jun 6, 2019 6:21 AM (in response to Frank Kulash)Hey Frank,
I got it in 199.08 seconds for the connect by nocycle abs((rprior r) * (fprior f)) = 2 approach. But it took 488.84 seconds for the other approach which is exactly opposite to what you observed. I am on Oracle Database 12c Enterprise Edition Release 12.1.0.2.0  64bit Production. Dont know how and why it would take different execution times to achieve the same using different approaches.
Regards,
Ranagal

14. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
BluShadow Jun 6, 2019 8:11 AM (in response to Ranagal)Ranagal wrote:
Quite lengthy. Thanks for the initial thoughts on this.
Regards,
Ranagal
Not really that lengthy. It just looks a lot because of the string manipulation to cut and insert values in to each string.