The New Sudoku Players' Forum

[Mathimagics]

.
Here is a collection of 2000 x Sudoku 16x16 Minimal Puzzles.

They mostly have 90-96 clues (puzzle format is "." + "0" - "F").

If those in a position to, can verify any or all of these, that would be appreciated … they look kosher to me so far

[m_b_metcalf]

I converted your first puzzle from its, for me, highly inconvenient format by hand into a numerical form, and agree that it has a unique solution and is minimal. Is it possible for you to generate, say, a format using 2 columns per value, as in

Code: Select all

 . . . .10 . . .15 . 8 . 9 5 . .

? then I could run a longer test. Twice as long but no work.

Regards,

Mike

[Mathimagics]

.
No problem. This has 2 cols per value: " .", " 1" … "16", so lots of clues get joined up, but presumably that's ok for you.

[m_b_metcalf]

I've run about 50 through my program. Like many minimal 16x16s, they tend to be very hard. Over 20% would be rated at SE > 10. This means also that my crummy program is very slow in processing them, but I found them thus far to be kosher.

HTH

Mike

[tarek]

Started the process. Kettle is on … It looks it will be a while

[tarek]

Confirmed:

2000 puzzles all with Unique solution and minimal.

The whole process took around 29 minutes

tarek

[Mathimagics]

Thanks tarek!

These were produced by my new toy, an fsss2 solver for 16x16 puzzles, using 256-bit operands.

The 2000 puzzle batch generation took 85s, solving them takes 15s.

Now that I have the fidelity of the solver established I can add support for variants …

[tarek]

The 2000 puzzle batch generation took 85s, solving them takes 15s.

Amazing ... at x120 what I have that is extremely superior … well done

[Mathimagics]

It's pretty fast, and the credit is mostly due to dobrichev, who produced the original fsss2.

But it is still "dumb", in the sense that it is still at heart a DFS ("brute-force") solver.

And strange things happen in 16x16 mode that you just don't see with 9x9, or at least don't really notice. At the individual puzzle level, if your solver is smarter than "hidden singles, naked singles", as it surely must be, it is entirely possible that I could find some examples where this speed differential is much more modest.

If it is really smart, I could probably find a pathological case for my solver where it is your solver that will be faster!

Actually, such a demonstration would be very useful - I will find some examples for you to try.

[tarek]

The Vanilla 9x9 sudoku puzzle is extremely rarely a singles backdoor size 3 puzzle. This obviously changes with more constraints &/or bigger puzzles.

the need to guess & how the solver guesses is what makes a difference in these bigger puzzles. The need to guess is reduced with intersections & locked sets. there will a trade off between Reduced guessing & Reduced performance with an unpredictable influence on speed.

The how is down to how clever your BF algorithm is designed to attack the puzzle space.


I don't think there is much to do with more complex & bigger puzzles except through the "How". We found that SAT is beginning to be applied more & more and appears promising. It needs to be compared with what you've developed on a benchmark sample with High backdoor size & few singles to start with similar to my Pearly6000 list


tarek

[m_b_metcalf]

Like many minimal 16x16s, they tend to be very hard. Over 20% would be rated at SE > 10.

Curious, I instrumented my program to provide information on 11 different levels of difficulty, and ran it on all 2000 puzzles. The result confirms the above. In detail:

Code: Select all

Singles/pairs/pointing:   0
Hidden triplet:           1 (#1302)
Wing + naked quad:        1 (#1285)
SE range 5 to ~8.5:      25 (e.g. #14)   
SE range ~8.5 to ~9.9: 1720 (e.g. #1)
SE >  9.9:              253 (e.g. #2)

Hope that's of interest.

Mike

[Mathimagics]

The need to guess & how the solver guesses is what makes a difference in these bigger puzzles. The need to guess is reduced with intersections & locked sets. there will a trade off between Reduced guessing & Reduced performance with an unpredictable influence on speed.

The how is down to how clever your BF algorithm is designed to attack the puzzle space.

Well, the BF algorithm is in fact not very sophisticated, it attacks the puzzle space with all the subtlety of a sledgehammer, but there is a very good reason for this.

It's worth reviewing the architecture of this solver, which I call dSolver16, as I think this will explain much, and it won't take long because it's really quite simple!

• dSolver16 is essentially Mladen dobrichev's fsss2 solver, as used in GridChecker.

• ST's are elementary - Singles only - so it really is very much like a DLX solver, and in fact typically makes the same number of guesses for a given puzzle. But 20 times faster!

• It gets a massive speed advantage over DLX by using bit-mask operations to process these singles. This aspect is highly optimisable, particularly with modern CPU's that have very fast instructions for doing operations on 128-bit and 256-bit variables. For standard Sudoku the entire puzzle state can be packed into 9 x 128-bit variables (144 bytes!). For 16x16 we need 32 x 256-bit variables, but that is still only 1024 bytes. When represented this way, the most heavily performed "tasks", such as eliminating candidates when a digit is placed in a cell, are achieved with a handful of logical bit-mask operations.

• when no singles are available, it goes into guess mode, and the NCS (next candidate selection) is essentially the same as for DLX, namely pick a cell with the least number of possible values, then pick the first of these values to make the guess.

I have done extensive experiments with alternate strategies, and have come to the conclusion that it is pointless trying to find a better one. For simple strategies (where no analysis of the puzzle state is done), it really is a case of "your guess is as good as mine", the solution space below is unknown, and we can't know which guesses will turn out to be good or bad until we make them.

Any attempt to introduce analysis (other ST's) is pointless here because it will always take far longer to perform than the time it will save. That is certainly true for 9x9 Sudoku, and probably true also for 16x16. Another possibility is "look-ahead" - if there are several cells with the least possible values, and generally this is always the case, we can sneak-preview each one to see which choice eliminates the most candidates. This reduces the guess count, but on avarage doubles the actual time!

So tarek's point about reduced guessing and reduced performance is bang on the money here.

On the other hand, this solver model is very flexible - it can solve in any variant mode that is based on additional/modified houses, we simply change the bit tables that tell the solver which cells are affected when we make set a value in any cell.

For larger puzzles, 25x25, etc, the BF solver becomes pretty useless, as the solution space explodes super-exponentially, and the number of "registers" we need to use in our data model becomes unwieldy. I tend to agree that SAT and similar approaches will become more attractive/effective for these.

Fortunately I have no interest whatsoever in anything beyond 16x16 - if it doesn't fit on a piece of A4 paper it's quite useless to me. I only do P&P puzzles, it's one way to get me off this computer!

[m_b_metcalf]

Fortunately I have no interest whatsoever in anything beyond 16x16 - if it doesn't fit on a piece of A4 paper it's quite useless to me. I only do P&P puzzles, it's one way to get me off this computer!

Dear Mathimagics (or may I call you Euler?),
That raises the question as to what is the purpose of generating puzzles at astonishingly impressive lightning speeds if only 0.1% of them can be solved by humans (see my previous post), and one doesn't know which ones, to boot? Maybe someone can devise a fine-grained rating system so that a 16x16 Patterns Game can be started

Regards,

Mike

P.S. I'm sure you know about blue's 16x16 nightmares.

P.P.S. Your post on the General thread about the Sudoku Survey vanished before I could read it. What did you write?

[dobrichev]

Few notes from me.
1) fsss2 has never been part of gridchecker.
2) Essentially SAT is a brute force approach to a problem so it shouldn't be viewed as an alternative of brute force.
3) In fsss2 there is conditional compilation code that uses locked candidates eliminations at early stages. Its usage for 17-clue puzzles results in better performance, but in general it drops performance for about 5 - 10% and this is probably due to the inappropriate data model. On the other hand, isn't the core of Zhou's solver based on locked candidates eliminations? So that the effectiveness of combining singles + locked candidates + informed guessing remains an open question, even for 9x9 puzzles.

[Mathimagics]

• Mike, it wasn't me, the whole "Sudoku Survey" thread has gone (a sure sign that Jason is back! Yay!)

• Mladen, I apologise, I don't know where I got that notion (about GridChecker) from, but it kind of stuck.

• SAT is still "brute force", I agree