1 2 3 Previous Next 39 Replies Latest reply on Jun 28, 2019 1:27 PM by study_anymore

    Weekend fun with Knight's Tour 8x8 solution in SQL

    Ranagal

      Hello experts,

       

      This is just for fun and learning. Meaning not a serious production problem in my project. I'm interested in knowing an SQL solution for the very famous Knight's Tour for 8x8 board. Please teach me how it can be solved in pure SQL. I'm expecting a solution on 12c.

       

      Note:

      I am aware of a  Recursive SQL solution by Anton Scheffer for Sudoku puzzles. Just don't know how I can use the same idea in here. That doesn't limit the ideas to only Recursive Solutions. Anything that works on 12c is fine.

       

      For reference:

      https://technology.amis.nl/2009/10/13/solving-a-sudoku-with-one-sql-statement/

       

      Thanks in advance.

       

      Regards,

      Ranagal

        • 1. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
          BluShadow

          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 co-ordinates have been visited, and how the knight moves from one co-ordinate 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 co-ordinate... 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

            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

              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

                Perhaps something along these lines (un-optimized 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',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r1

                                ,case when r != 2 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r2

                                ,case when r != 3 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r3

                                ,case when r != 4 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r4

                                ,case when r != 5 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r5

                                ,case when r != 6 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r6

                                ,case when r != 7 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r7

                                ,case when r != 8 then nowt else lpad('0',(c-1)*2,'0')||'01'||lpad('0',(8-c)*2,'0') end as r8

                                ,r

                                ,c

                                ,1

                                ,strt

                          from  (select nowt

                                       ,floor((level-1)/8)+1 as r -- row

                                       ,mod(level-1,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 end||to_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 end||to_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 end||to_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 end||to_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 end||to_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 end||to_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 end||to_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 end||to_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.*

                      ,r1||chr(10)||r2||chr(10)||r3||chr(10)||r4||chr(10)||r5||chr(10)||r6||chr(10)||r7||chr(10)||r8||chr(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. 

                1 person found this helpful
                • 5. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
                  mathguy

                  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

                    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

                      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

                        Hi, 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 hard-coding 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 8h

                         

                        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 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 8h

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

                        1 person found this helpful
                        • 9. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
                          mathguy

                          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 row-limiting 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 63-move 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

                            Quite lengthy. Thanks for the initial thoughts on this.

                             

                            Regards,

                            Ranagal

                            • 11. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
                              Ranagal

                              True genius. Thanks for the solution Frank.

                               

                              Regards,

                              Ranagal

                              • 12. Re: Weekend fun with Knight's Tour 8x8 solution in SQL
                                Stew Ashton

                                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

                                  Hey Frank,

                                   

                                  I got it in 199.08 seconds for the connect by nocycle abs((r-prior r) * (f-prior 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

                                    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.

                                    1 2 3 Previous Next