Looking for really hard sudoku puzzles

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • JosAH
    Recognized Expert MVP
    • Mar 2007
    • 11453

    #16
    Originally posted by NeoPa
    I have an Excel spreadsheet that handles solving and allowing user entry (with checking and optional assistance). It implements some of the techniques I use when solving, but is otherwise brute-force / iterative.
    I didn't know Excel has an ILP solver; cute. Can it solve sudokus? A pure ILP doesn't need any brute force at the surface, i.e. the branch and bound strategy handles that below the surface but even my cplex solver takes a few seconds to come up with a solution. My brute force silly solver in the Java articles section is much, much faster.

    kind regards,

    Jos

    edit. I happen to have a 2007 version of excel and it explicitly mentions a sudoku solver in its help files; here it is. I tried it; it is pure crap.

    Comment

    • NeoPa
      Recognized Expert Moderator MVP
      • Oct 2006
      • 32636

      #17
      I make no claims to an ILP solution Jos. My education didn't get that far if I remember accurately enough. I always loved Maths, but missed out on university due to various complications at the time.

      I was able to code in a solver of sorts into Excel using VBA. In truth, it was never meant as a solver per se. Rather it was a teacher and something to provide the puzzles (for my children). It offered some assistance, but I'm not even sure now if it could necessarily solve all solvable puzzles, though I think it did. I must dig it up. I stopped using it a while back when I got into the (for me more interesting) Killer puzzles.

      PS. Just checked and "No". It doesn't handle all - just the basic slog of the simple checks. I guess that means the intelligent checks never got as far as implementation (:embarrassment :).

      Comment

      • JosAH
        Recognized Expert MVP
        • Mar 2007
        • 11453

        #18
        Originally posted by NeoPa
        PS. Just checked and "No". It doesn't handle all - just the basic slog of the simple checks. I guess that means the intelligent checks never got as far as implementation (:embarrassment :).
        No need to be ashamed; my solver doesn't make any 'intelligent' decisions either; it just tries them all and it tries to do that as efficient as possible. The recursion in it is just an artifact: basically speaking it runs as follows: if the solving succeeded this far try to solve the rest of it otherwise crawl back and try another possibiliy.

        IMHO there's not much intelligence in the sudoku puzzle to apply or I am just too stupid too see it ;-) The ILP approach has just too much overhead in every step to make it fast. The math in it isn't much more than 101 either. OTOH I haven't seen any 'killer' puzzles either; a brute force approach can solve the difficult puzzles just as easy if not easier ...

        kind regards,

        Jos

        Comment

        • NeoPa
          Recognized Expert Moderator MVP
          • Oct 2006
          • 32636

          #19
          I didn't even get that far Jos. The (Excel) interface is able to handle the display layout for Killers, but only with great difficulty. Realising that I would need to insert extra, ultra-thin columns and rows, and that these would further complicate the workings out of what's where, I decided not to invest the time ;)

          Comment

          • jkmyoung
            Recognized Expert Top Contributor
            • Mar 2006
            • 2057

            #20
            Took a look at the excel method. Didn't know Excel had an iterative method.

            Looking back at my notes, the one thing I failed to code was as such:

            Given n cells in any row, column, or nonet, if there are n values which are not possible any of the 9-n other cells of the group of 9, eliminate all of the 9-n other possibilities for each of the original n cells.

            Am uncertain how to code this.
            1. How do I find these n-cells? OR
            2. How do I find these n-values?
            (efficiently, of course).

            Will probably code in pairs, and/or if I can figure it out, triplets in a line/nonet.

            Does anyone know of any better rules that they've used in their own solvers?

            Comment

            • NeoPa
              Recognized Expert Moderator MVP
              • Oct 2006
              • 32636

              #21
              That's pretty well how I do it JKM. Let me see if I can specify that more clearly in English.

              Given n cells, where the only possible values for any (all) of those n cells make up a group of only n values, none of those values is available to any other cell in the section (line, column or nonet).

              EG. You have a row of nine cells with the following values (possibilities) :
              A=3; B=5; C=8; D=4 or 7; E=9; F=4 or 2; G=1; H=6; I=4 or 7
              As both D & I have the possibilities of 4 or 7, then neither 4 nor 7 is available to any other cell. ==> F=2.

              The more basic and obvious rules are that a value is not available to any other cell once it has been used within that section.

              Slightly less obvious is that if a cell is the only one within any section that has a particular value available to it, regardless of how many other values are still available to it, that cell has the value of that particular value.
              Last edited by NeoPa; Jan 6 '09, 09:50 PM. Reason: Added extra 'n' to 2nd para & changed "are" to "is" after "none".

              Comment

              • NeoPa
                Recognized Expert Moderator MVP
                • Oct 2006
                • 32636

                #22
                Originally posted by jkmyoung
                Took a look at the excel method. Didn't know Excel had an iterative method.
                Frankly I don't follow this statement at all :S What is "the Excel method" (What are you referring to when you say it)?

                Anyway, in case it helps I'll attach what I have. As I say, it was never principally for solving the puzzles, it was more as an application to use to see and interface to them. I should also point out that it was developed a while ago so, while I'm happy to field any questions, I may not know the answers.

                PS. I'm not suggesting anyone should be interested in my version, simply that it's there to look at should you feel you may want to. It was always a personal project so please excuse any untidiness in the code (and, of course you're free to use it as it was intended - simply to allow you to solve sudoku puzzles on screen. It does provide an interface for adding new puzzles if that helps).

                PS. It seems I must lose some of the current stored puzzles to fit the size limit. Give me a short while.

                Comment

                • NeoPa
                  Recognized Expert Moderator MVP
                  • Oct 2006
                  • 32636

                  #23
                  Originally posted by NeoPa
                  PS. It seems I must lose some of the current stored puzzles to fit the size limit. Give me a short while.
                  Sorry. It seems that a claimed ZIP file attachment size of 50 MB is not supported (by about 49.999 MB).

                  Staff can hit me up on IM of course (or email or whatever) where I can get it transferred without fuss.

                  Comment

                  • jkmyoung
                    Recognized Expert Top Contributor
                    • Mar 2006
                    • 2057

                    #24
                    I was referring to the Excel Sudoku solver link posted by Jos.

                    I think the example works if you note not only that "both D & I have the possibilities of 4 or 7" but also "both D & I ONLY have the possibilities of 4 or 7"

                    Another example to clear what I said up earlier.
                    a = 1,2,3,4,5,6,7,8 ,
                    b = 1,2,3,4,5,6,7,9
                    c = 1,2,3,4,5,6,8,9
                    d = 1,2,3,4,5,7,8,9
                    e = 1,2,3,6,7,8,9
                    f = 1,2,3,5,6,7,8,9
                    g = 2,3
                    h = 1,3
                    i = 1,2

                    g-i are limited to 1-3, and do not have 4-9. So, cells a-f are limited to 4-9. Remove 1-3 from a-f.

                    a = 4,5,6,7,8
                    b = 4,5,6,7,9
                    c = 4,5,6,8,9
                    d = 4,5,7,8,9
                    e = 6,7,8,9
                    f = 5,6,7,8,9
                    g = 2,3
                    h = 1,3
                    i = 1,2

                    Comment

                    • NeoPa
                      Recognized Expert Moderator MVP
                      • Oct 2006
                      • 32636

                      #25
                      Originally posted by jkmyoung
                      I was referring to the Excel Sudoku solver link posted by Jos.
                      Ah yes of course. Makes perfect sense.
                      Originally posted by jkmyoung
                      I think the example works if you note not only that "both D & I have the possibilities of 4 or 7" but also "both D & I ONLY have the possibilities of 4 or 7"
                      I think if you read my second paragraph you'll find that is covered.
                      Originally posted by NeoPa
                      Given n cells, where the only possible values for any (all) of those n cells make up a group of only n values, none of those values is available to any other cell in the section (line, column or nonet).
                      I've edited the quote here (and the original) in case that helps to make it clearer (the bolded n), but it's essentially the same (I also changed "none ARE" to the more correct "none IS").

                      Your example though, is a better illustration of the point we were both making. Well expressed.

                      Comment

                      • NeoPa
                        Recognized Expert Moderator MVP
                        • Oct 2006
                        • 32636

                        #26
                        The logic to test for this is not trivial, even for the human brain, but I suspect that the brain has many advantages in a problem of this kind over a computer.

                        Mathematicians may find shortcut ways to cancel out some of the work of this, but the tests for determining this, as far as I can see easily at this point, would have to include some of the following logic.
                        1. Start with a single section (Row; Column or Nonet).
                        2. Get to a position where each element (cell) has a list of possible values left to it (as in your example).
                        3. This must be done in memory (tables / arrays should be used). Excell cells are probably too clumsy to work fast enough. Many events get triggered every time a cell is updated. For proper programming, ignore this line.
                        4. Start with a depth level (DLvl) of 2. This means that pairs of cells are being checked first time through the loop. The depth level only needs to go to 4. Once you are checking more than half of the available cells you can only find a result if there is also a result for the remaining cells. Clearly this should already have been found as they must, of necessity, have a depth of 9-DLvl ==> must be less than DLvl when DLvl > 9/2.
                        5. Start from a. If/when a is fully exhausted proceed onto b through h in similar manner.
                        6. Starting from the current letter +1 (b for the first iteration, then c etc) check each grouping (pairs to start with then groups of 3 & 4) and find each unique possible value for the grouping.
                        7. Check each possible grouping (for whatever the current DLvl is) available. For pairs the sequence would be - ab; ac; ad; ...; bc; bd; be; ...; cd; ce; ...; hi. Threes are more complicated and fours even more so, but if you start from one end (a) and proceed only towards the other, all situation can be covered. Threes would start - abc; abd; ...; acd; ace; ...; bcd; bce; ...; bde; bdf; ...ghi.
                        8. If, at any time, the number of unique values found for a grouping exceeds 8, then abort the test on that particular grouping. To illustrate take an example of DLvl=4 and testing the first grouping (abcd). If a has 9 possible values then abort the grouping. If ab together have 9 then again, abort. The same for abc.
                        9. If however, the number of unique values found matches (there should never be less unless an earlier process has failed) DLvl, then all those unique values may be removed from all cells within the section except for those within the current grouping.

                        Hopefully, that is a workable outline of how to process this algorithm in a logical way. The numbers of tests here will actually be quite large and may even strain a modern computer. I don't know.

                        Comment

                        • jkmyoung
                          Recognized Expert Top Contributor
                          • Mar 2006
                          • 2057

                          #27
                          maximum
                          pairs: 36
                          triplets: 84
                          quadruplets: 126

                          There's probably a way to test the triplets from pairs, quadruplets from pairs or triplets, to avoid repeating work.

                          I'm trying to figure out if the reverse is as easily doable also. Swap cells and values in your previous statement and you get the following:
                          Given n values, where the only possible cells for any (all) of those n values make up a group of only n cells, none of those cells is available to any other value in the section (line, column or nonet).
                          eg, a-g can take any values but 8 or 9. 8 or 9 is therefore restricted to h-i regardless of h and i's earlier possibilities, eg even if they were unrestricted.
                          The algorithm seems to be slightly different here.

                          Due to the current layout of my program, the reverse method does not seem as reasonable (in terms of computation time). Will have to have a go at it this week and see what happens.

                          Will definitely program the 54 triplets sharing a row/nonet or col/nonet, and hope for results.

                          Comment

                          • NeoPa
                            Recognized Expert Moderator MVP
                            • Oct 2006
                            • 32636

                            #28
                            Originally posted by jkmyoung
                            maximum
                            pairs: 36
                            triplets: 84
                            quadruplets: 126
                            Possibly less mindless crunching than I anticipated then. This is a good thing :)
                            Originally posted by jkmyoung
                            There's probably a way to test the triplets from pairs, quadruplets from pairs or triplets, to avoid repeating work.
                            I started from this point, but it's a ba***rd to express in clear English. The order of processing would need to be different (build triplets only on valid pairs and quads only on valid triplets etc. Doable, but I'm guessing a bit more complicated in the design.
                            Originally posted by jkmyoung
                            I'm trying to figure out if the reverse is as easily doable also. Swap cells and values in your previous statement and you get the following:

                            eg, a-g can take any values but 8 or 9. 8 or 9 is therefore restricted to h-i regardless of h and i's earlier possibilities, eg even if they were unrestricted.
                            The algorithm seems to be slightly different here.

                            Due to the current layout of my program, the reverse method does not seem as reasonable (in terms of computation time). Will have to have a go at it this week and see what happens.
                            Perfectly reasonable, but doesn't this just leave you at your starting point (unless you're not considering starting from the same position I am). You already know which values are possible in each individual cell. There doesn't appear to be any further restriction (info) from this.
                            Originally posted by jkmyoung
                            Will definitely program the 54 triplets sharing a row/nonet or col/nonet, and hope for results.
                            I was considering treating each section (Row; Column or Nonet) separately. Cross referencing separate sections doesn't accrue any benefit that I can perceive (and adds an order of magnitude of complexity). Maybe I'm simply not following you clearly enough.

                            Comment

                            • jkmyoung
                              Recognized Expert Top Contributor
                              • Mar 2006
                              • 2057

                              #29
                              The cross-referencing was to take advantage of particular computations that I was already using in my solving algorithm. Actually, why don't I just post it? This tries to determine if there is any number which can only fit within one cell in the row:
                              Code:
                                      int parityRow = C[row][0]^C[row][1]^C[row][2]^C[row][3]^C[row][4]^
                                                      C[row][5]^C[row][6]^C[row][7]^C[row][8];
                                      int t1or      = C[row][0]|C[row][1]|C[row][2];
                                      int t2or      = C[row][3]|C[row][4]|C[row][5];
                                      int t3or      = C[row][6]|C[row][7]|C[row][8];
                                      int t1and     = C[row][0]&C[row][1]&C[row][2];
                                      int t2and     = C[row][3]&C[row][4]&C[row][5];
                                      int t3and     = C[row][6]&C[row][7]&C[row][8];
                                      int share     = (t1or & t2or) | (t1or & t3or) | (t2or & t3or);
                                      
                                      long solveRow  = parityRow & (~share) & (~t1and) & (~t2and) & (~t3and) 
                                          & solve & (~Row[row]);
                              Explanation:
                              The or's: find the possibilities in each of the triplets.
                              The and's: find the numbers which can be placed in any square of the triplet.
                              share: Find the numbers which can only be in more than one of the triplets.
                              parityRow: find parity of row.

                              If the number is set in share, then there's clearly more than one possibility.
                              If not, then the number is only in one triplet.
                              Break it down to the 3 cases:
                              possible in 3 cells. Then it appears in one of the ands.
                              possible in 2 cells. Then parity is even.
                              possible in 1 cells. Parity is odd.

                              So we can find all numbers which are possible in 1 cell this way.

                              Coded in the check for the 27 triplets for the rows, and the reverse cases (eg check the other 6 cells), but it has given me nothing so far. OH! Just realized that I forgot to call the new functions in the Column and Nonet methods. Will implement it and see what happens.

                              Comment

                              • NeoPa
                                Recognized Expert Moderator MVP
                                • Oct 2006
                                • 32636

                                #30
                                What type of value do you have in the elements of C (presumably a 9 x 9 array)?

                                Haven't done c for a while, are :
                                Code:
                                ^ ==> EOR
                                & ==> AND
                                | ==> OR

                                Comment

                                Working...