The New Sudoku Players' Forum

[David P Bird]

It's with some trepidation that I write this as I only program at a shallow level writing customised Excel functions in Visual Basic, however for the possible benefit of tyro programmers if no-one else:

I suspect that many solvers repeatedly run the same algorithms on the same data for unchanged parts of the grid. However memory is cheap nowadays while execution time remains important, and it's relatively simple to save the outcome of each algorithm in a result table along with a check value (a checksum or some intermediate result) for the input range that applied at the time. For example if we maintain a checksum of the candidates in each house, we would only have to recheck for locked sets in a house if the saved checksum doesn't match the current one.

Generally the concept isn't as trivial as that example would suggest though, and some consideration needs to be given as to which check values would pay for their keep.

[JasonLion]

For the simpler techniques, naked/hidden singles and locked candidates, keeping flags is often more work than simply checking everything again. I went back and forth on this in JSolve, and ended up getting the fastest times in 64 bit mode with the flags removed. Running in 32 bit mode the modified flags gave a small advantage, but nothing significant.

As the techniques get more complicated there is more to gain from tracking which parts of the board have changed, but it also gets more complicated to track which things need to be checked again. For example, it isn't nearly as easy to figure out which simple fish need to be checked again when a cell changes as it is to figure out which houses need to be checked for naked/hidden singles.

In my solver, 90+% of the time is spent on difficult things, ALS, chains, and mutant fish mostly, so that is the place where the most gain could be made by tracking which things need to be checked again. Of course it is rather complicated to figure out which mutant fish need to be re-examined after changing a single cell. Still, there could be some benefit here. Now that you have mentioned it, I can think of ways to narrow the ALS searches given a list of cells that have changed since last time.

[David P Bird]

Jason Thanks for sharing your results, although I must admit they surprise me.

My views are strongly influenced by my work on a spreadsheet assistant for investigating shortest path solutions. I'm thinking of extending it so it will automatically maintain a map of ALS trigger candidates – ie those that would allow an AIC to be extended though an ALS inference. Currently I do this manually aided by a colouring scheme, but they slowly get out of date. A trigger flag doesn't identify what the inference is, but simply that one exists. It's the sort of approach that could be useful to you too.

[hobiwan]

I am currently in the process of rewriting HoDoKu's search engine (at least I was till three months ago, when my second son was born) so I can post some actual timings. I currently use the 17s as benchmark. They very seldom need hard techniques which means that they allow a fairly good view on the simple ones.

Here is the list (the timing is done via System.nanoTime(); since the times are so short there will probably be a significant absolut error):

Code: Select all

49151 puzzles in 86879ms (0:01:26.879)
1,768 ms per puzzle
0 puzzles require guessing!
0 puzzles require templates!
0 puzzles unsolved!
0 puzzles not solved logically!

   Easy:    19481
   Medium:  21534
   Hard:     6430
   Unfair:   1667
   Extreme:    39

Timing (number of searches - time per search - total time):
     3277590/        0,40us/     1294,74ms: Full House
     2333179/        0,35us/      816,52ms: Naked Single
     1454811/        0,53us/      776,01ms: Hidden Single
      131954/        2,90us/      382,44ms: Locked Pair
      128123/        2,89us/      370,34ms: Locked Triple
      125798/        4,71us/      592,37ms: Locked Candidates
       30057/        6,49us/      195,11ms: Naked Pair
       23182/        6,56us/      151,96ms: Naked Triple
       20206/        7,37us/      148,96ms: Hidden Pair
       17622/        6,78us/      119,56ms: Hidden Triple
       17468/        6,79us/      118,57ms: Naked Quadruple
       17451/        5,44us/       94,94ms: Hidden Quadruple
       17451/       34,90us/      609,02ms: X-Wing
       16885/      187,06us/     3158,52ms: Swordfish
       16560/      607,74us/    10064,19ms: Jellyfish
       16527/       42,32us/      699,50ms: Remote Pair
       14224/        0,60us/        8,60ms: Bivalue Universal Grave + 1
       13366/        5,96us/       79,61ms: Skyscraper
       10634/        6,17us/       65,59ms: 2-String Kite
        9645/       67,44us/      650,43ms: Turbot Fish
        9341/       18,77us/      175,31ms: Empty Rectangle
        8679/       14,82us/      128,65ms: W-Wing
        6227/       11,00us/       68,51ms: XY-Wing
        5313/       10,73us/       56,99ms: XYZ-Wing
        4980/       20,41us/      101,64ms: Uniqueness Test 1
        4719/        5,80us/       27,37ms: Uniqueness Test 2
        4683/        4,75us/       22,26ms: Uniqueness Test 3
        4575/        4,40us/       20,13ms: Uniqueness Test 4
        4364/        4,52us/       19,72ms: Uniqueness Test 5
        4363/        4,53us/       19,74ms: Uniqueness Test 6
        4340/        4,04us/       17,55ms: Hidden Rectangle
        3911/       24,99us/       97,76ms: Avoidable Rectangle Type 1
        3905/       22,09us/       86,25ms: Avoidable Rectangle Type 2
        3905/      343,78us/     1342,46ms: Finned X-Wing
        3787/      340,20us/     1288,33ms: Sashimi X-Wing
        3763/     1034,84us/     3894,09ms: Finned Swordfish
        3283/     1069,77us/     3512,06ms: Sashimi Swordfish
        3176/     1982,41us/     6296,13ms: Finned Jellyfish
        3123/     1989,79us/     6214,11ms: Sashimi Jellyfish
        3114/      621,01us/     1933,83ms: Sue de Coq
        2907/       36,08us/      104,87ms: Simple Colors
        2851/       13,77us/       39,26ms: Multi Colors
        2796/      121,08us/      338,53ms: X-Chain
        2776/      272,28us/      755,86ms: XY-Chain
        1801/     9875,41us/    17785,61ms: Nice Loop/AIC
         343/    10264,02us/     3520,56ms: Grouped Nice Loop/AIC
         208/    11348,01us/     2360,39ms: Almost Locked Set XZ-Rule
         164/    12150,06us/     1992,61ms: Almost Locked Set XY-Wing
         133/    10379,67us/     1380,50ms: Almost Locked Set Chain
         118/      116,97us/       13,80ms: Franken X-Wing
         118/     3823,10us/      451,13ms: Franken Swordfish
         118/     2915,43us/      344,02ms: Finned Franken X-Wing
         118/    39439,85us/     4653,90ms: Finned Franken Swordfish
          99/    12111,17us/     1199,01ms: Forcing Chain
           6/    70142,30us/      420,85ms: Forcing Net

Everything below "Nice Loop/AIC" has not been optimized yet. As you can see most easy techniques only need a few microseconds on a Intel i5 2.67GHz. I doubt additional flags would significantly improve the result.

[David P Bird]

hobiwan congratulations on your family addition! (And I've just become a great-great uncle!)

I can see why using the 17s as a benchmark is good idea. Your timings interested me though as it's clear that you have different procedures for naked and hidden tuples of various sizes, whereas I'm heading for a single routine which will log them all simultaneously. If there aren't any in a house it will log the Almost Locked and Hidden Sets. The same function will then be re-used for locating simple fish (finned and un-finned) where I note your Jellyfish procedure is comparatively quite time consuming.

In contrast your ALS chain routine is very quick. Is this because each chain is limited to one ALS or just as a result of the nature of the 17's?

By way of a bit of background: my first spreadsheet helper ran checks on demand using VBA methods and was tediously slow. I then switched to using customised VBA functions entered in spreadsheet cell formulae as these are only re-calculated when one of their inputs changes, and got a good speed improvement.

[hobiwan]

hobiwan congratulations on your family addition! (And I've just become a great-great uncle!)

Congratulations to you too!

I note your Jellyfish procedure is comparatively quite time consuming.

I have not yet found a really fast way to code a general fish finder, although I have already spent some time with it. The large increase from 34.9us (X-Wing) to 607.74us (Jellyfish) has two reasons: firstly in every search for unfinned n-fish units are only tried if they have at most n candidates (works good for small fish, but does only very little for larger fish); secondly the search stops if a step is found which also works better for small fish because more are actually found.

In contrast your ALS chain routine is very quick. Is this because each chain is limited to one ALS or just as a result of the nature of the 17's?

The nature of the 17's (only a few RCCs per search). ALS chains in HoDoKu are at least three ALS long.

[ronk]

I note your Jellyfish procedure is comparatively quite time consuming.

I have not yet found a really fast way to code a general fish finder, although I have already spent some time with it. The large increase from 34.9us (X-Wing) to 607.74us (Jellyfish) has two reasons: firstly in every search for unfinned n-fish units are only tried if they have at most n candidates (works good for small fish, but does only very little for larger fish); secondly the search stops if a step is found which also works better for small fish because more are actually found.

Sudoku Explainer rating time for this ...

007000900030907060100000003070809020000000000060102090900000007020603010005000800

... is unusually long relative to other puzzles with a jellyfish, even when ERs are greater than its 6.5. I'd like to know the time you see (relative to jellyfish time posted above). TIA

[hobiwan]

ronk (22100 times the same puzzle):

Code: Select all

22100 puzzles in 127583ms (0:02:07.583)
5,773 ms per puzzle
0 puzzles require guessing!
0 puzzles require templates!
0 puzzles unsolved!
0 puzzles not solved logically!

   Leicht: 0
   Mittel: 0
   Schwer: 22100
   Unfair: 0
   Extrem: 0


Statistics total:
        419900 -   419900/       0: Full House
        574600 -   574600/       0: Hidden Single
        265200 -   265200/       0: Naked Single
         44200 -        0/  198900: Naked Pair
         88400 -        0/  265200: Locked Candidates Type 2 (Claiming)
         22100 -        0/   44200: Bivalue Universal Grave + 1
         22100 -        0/   22100: W-Wing
         22100 -        0/   22100: X-Wing
         22100 -        0/   44200: Jellyfish
      ---------------------------------------------------
       1480700 -  1259700/  596700
Timing:
     1480700/        0,44us/      645,70ms: Full House
     1060800/        0,33us/      348,37ms: Naked Single
      795600/        0,50us/      397,93ms: Hidden Single
      221000/        2,25us/      497,89ms: Locked Pair
      221000/        4,08us/      901,43ms: Locked Triple
      221000/        9,71us/     2145,58ms: Locked Candidates
      132600/        6,50us/      862,49ms: Naked Pair
       88400/        8,82us/      780,13ms: Naked Triple
       88400/        5,14us/      454,69ms: Hidden Pair
       88400/        1,87us/      165,27ms: Hidden Triple
       88400/        3,76us/      332,18ms: Naked Quadruple
       88400/        0,75us/       65,93ms: Hidden Quadruple
       88400/       39,68us/     3507,88ms: X-Wing
       66300/      478,08us/    31696,71ms: Swordfish
       66300/     1172,09us/    77709,90ms: Jellyfish
       44200/       37,05us/     1637,81ms: Remote Pair
       44200/        1,44us/       63,48ms: Bivalue Universal Grave + 1
       22100/        6,47us/      143,03ms: Skyscraper
       22100/        5,70us/      125,95ms: 2-String Kite
       22100/       65,81us/     1454,48ms: Turbot Fish
       22100/       12,55us/      277,38ms: Empty Rectangle
       22100/       12,32us/      272,31ms: W-Wing