Solving Sudoku with SQL



  • Discovered via digg (and I'm posting with no real review of the page, sorry):



  • Hehe, that's quite painful in theory but in practice - I love it! It takes a special kind of mind to think up something like that though. And it's probably the kind of mind that could do real harm with a little less knowledge...



  • I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



  • I can't even solve a Sudoku myself.

    Though I must say I only tried once, using brute-force, which will always put you into a numerical lock-down and forcing you backtrack over earlier umbers whish is a dumb idea of course.



  • @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Such a single SQL-statement is not difficult to construct, though execution time might be sluggish ;-)
    I'll show how for a 4x4 sudoku, changing that to 9x9 is left as an exercise to the students.

    First I create a table NUMS with a column N and insert the values 1..4 in this table. If you think this violates the "single SQL statement" requirement, replace every occurance of NUMS with "(select 1 as N from dual union all select 2 from dual union all select 3 from dual union all select 4 from dual)".

    create table NUMS (N number);
    insert into NUMS values (1);
    insert into NUMS values (2);
    insert into NUMS values (3);
    insert into NUMS values (4);

    select n11.n, n12.n, n13.n, n14.n,
    n21.n, n22.n, n23.n, n24.n,
    n31.n, n32.n, n33.n, n34.n,
    n41.n, n42.n, n43.n, n44.n
    from NUMS n11, NUMS n12, NUMS n13, NUMS n14,
    NUMS n21, NUMS n22, NUMS n23, NUMS n24,
    NUMS n31, NUMS n32, NUMS n33, NUMS n34,
    NUMS n41, NUMS n42, NUMS n43, NUMS n44
    where n11.n <> n12.n
    and n11.n <> n13.n
    and n11.n <> n14.n
    and n11.n <> n21.n
    and n11.n <> n31.n
    and n11.n <> n41.n
    and n11.n <> n22.n
    /* snipped few dozends of lines */
    and n43.n <> n44.n
    /* ... target numbers ... */
    and n11.n = 3
    and n32.n = 1
    /* ... */
    and n43.n = 2;

    Easy, isn't it? Just create a big cross product of all possible sudokus and eliminate all that isn't the right solution.

    (Untested, since I don't have a big machine at my disposal)



  • I think that's just about the brutest of all brute force methods.

    Applause.



  • @ammoQ said:

    Easy, isn't it? Just create a big cross product of all possible sudokus and eliminate all that isn't the right solution.

    (Untested, since I don't have a big machine at my disposal)

    This was the only way I could think of, mainly because I could never properly define all the rules I use to solve them.  I was hoping to discover something more elgant and that would finish running before the universe ends.



  • Algorithms like that exist.



  • Most Sudokus (especially the easy and medium difficult ones) can be solved without backtracking.



  • @ammoQ said:

    Most Sudokus (especially the easy and medium difficult ones) can be solved without backtracking.


    All sudoku should be solvable without backtracking. With enough intelligence the solution should be entirely deterministic. However, in some instances there is no unique solution. I've done some that get down to four squares which are all mutually dependent. For each square the only option was to choose one at random because they all worked. Hence no unique solution and thus the last step just has to be a leap of faith.

    But I understand that "proper" sudoku should only have one solution.



  • @LoztInSpace said:

    @ammoQ said:

    Easy, isn't it? Just create a big cross product of all possible sudokus and eliminate all that isn't the right solution.

    (Untested, since I don't have a big machine at my disposal)

    This was the only way I could think of, mainly because I could never properly define all the rules I use to solve them.  I was hoping to discover something more elgant and that would finish running before the universe ends.

    Try reading The Mathematics of Sudoku. The paper probably isn't complete but is an interresting read nonetheless and thinking of how you'd implement XY-Wing and XYZ-Wing is a nice way to pass time.



  • @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Yeah, his just happens to use SQL, but isn't really a set-based sql solution.

    I threw one together the other day that uses SQL, but still of course needs to do *some* looping, but the logic is truly set-based.


  • @Jeff S said:

    @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Yeah, his just happens to use SQL, but isn't really a set-based sql solution.

    I threw one together the other day that uses SQL, but still of course needs to do *some* looping, but the logic is truly set-based.

    Let's have a look then!



  • @Jeff S said:

    @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Yeah, his just happens to use SQL, but isn't really a set-based sql solution.

    I threw one together the other day that uses SQL, but still of course needs to do *some* looping, but the logic is truly set-based.

    Let's have a look then!



  • @Jeff S said:

    @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Yeah, his just happens to use SQL, but isn't really a set-based sql solution.

    I threw one together the other day that uses SQL, but still of course needs to do *some* looping, but the logic is truly set-based.


    Let's have a look then!


  • @dhromed said:

    @Jeff S said:
    @LoztInSpace said:

    I posted to Oracle's Ask Tom website a while ago hoping to get the SQL guru to solve it in one select statement.  He didn't respond [:(]

    This is ok but still pretty procedural.  I wonder if you can do it reasonably using sets rather than like this.  Any takers?  Maybe one for the coding challenge.



    Yeah, his just happens to use SQL, but isn't really a set-based sql solution.

    I threw one together the other day that uses SQL, but still of course needs to do *some* looping, but the logic is truly set-based.


    Let's have a look then!


    There is one last scenerio I need to code in .. I should be able to do this tomorrow.  Even if I don't finish it completely, I will post it up.  It currently solves most puzzles, but gets stuck on a few.  Stay tuned .... : )



  • Until I post mine, here is a thread that you may find interesting regarding this topic :

    http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=50372




  • As promised, here is my solution:

    http://weblogs.sqlteam.com/jeffs/archive/2006/04/06/9545.aspx

    Still some puzzles it cannot solve, but it can handle most of them. And it's definitely set-based. I may need to add 1 more "elimination" INSERT statement in there, but right now it is giving me a headache to try to visualize it!


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.