The New Sudoku Players' Forum

[Mathimagics]

Ok, I think I can guarantee that every LS I test gives a trusted outcome, but my setup for multiple LS-gen + testing seems to have had a hiccup, which gave an exaggerated count of Unique Solutions. I'll have to rerun those stats.

[Mathimagics]

After some adjustments, I believe the probabilities are:

Random LS's, no restriction:

• grid size 4: pU ~= 60%
• grid size 5: pU ~= 49%
• grid size 6: pU ~= 23%
• grid size 7: pU ~= 3%
• grid size 8: pu ~= 0.3%

It's interesting to see what happens if we only consider LS's with at least 1 chain of maximum length:

• grid size 4: pU ~= 63%
• grid size 5: pU ~= 67%
• grid size 6: pU ~= 40%
• grid size 7: pU ~= 17%
• grid size 8: pU ~= 2.4%

That's quite dramatic, in fact. An increase by a factor 6 (size 7) and 8 (size 8).

[denis_berthier]

The revised probabilities are:

• grid size 4: pU ~= 42%
• grid size 5: pU ~= 12%
• grid size 6: pU ~= 1%
• grid size 7: pU ~= ? (tba)

The trend still seems to be evident.
I'm guessing a grid size 7 will be hard to pin down!

Hi Jim,
I had missed your last post page 4.
I'm very surprised by the results. I expected a much larger pU.

They suggest a complementary question: once uniqueness is granted, how long is it preserved when one starts deleting clues?

[Mathimagics]

I'm very surprised by the results. I expected a much larger pU.

You might notice I have provided up-to-date results (see post above beginning "After some adjustments ...", this supercedes the post following, which I can't seem to be able to delete {OK now deleted by Moderator}).

They suggest a complementary question: once uniqueness is granted, how long is it preserved when one starts deleting clues?

An interesting question, which I'll look into in due course.

[Mathimagics]

They suggest a complementary question: once uniqueness is granted, how long is it preserved when one starts deleting clues?

An interesting question, which I'll look into in due course.

That will be sooner rather than later, now that I've been able to exploit the "maximal chain" (MC) effect to advantage.

The problem I had was that, while it took less generations to find U's, it required many more random LS generations before an LS with MC's was found. The roundabout was thus no faster than the swing, possibly slower.

But now I have a direct construction method, which allows fast generation of LS's of the desired properties. It's turning up N=9 solutions as I write this. The observed probabilities (bearing in mind these are not truly random) are:

• grid size 9: (MC >= 1) 12000 tested, nU = 6, pU ~= 0.05%
• grid size 9: (MC >= 2) 1500 tested, nU = 10, pU ~= 0.67%

Having suitable exemplars to work with, I am now quite keen on reducing them to minimal form, with a view to feeding that info back into the direct generator.

I have already observed that some non-U cases are almost U, having 2 solutions which vary only by 4 cells having 2 interchangable values. With Kakuro I can automatically correct these, but not so here, where perturbations have to preserve order or the whole structure is altered. When I have better solutions (ie. with no MC's) it just might be possible to do value-swaps which preserve order.

[denis_berthier]

I don't know why, but I think once you have uniqueness, you may delete many inequality clues without loosing it.
When you have a few full N=9 Futoshikis with uniqueness, I'd like to rate them, in order to see how they compare with those of atk and other websites, whose densities of clues are much lower. (I prefer N=9 because I've solved hundreds of this size.)

[Mathimagics]

I have 83 9x9 U's. The raw grid data is just the grid content. I've attached it just in case, if that's suitable for your purpose. From that you can generate the fully-specified hints.
A sample:

Code: Select all

   9  4  6  2  3  8  7  1  5
   8  2  5  1  4  6  9  7  3
   2  6  4  3  5  7  8  9  1
   1  7  3  4  8  9  2  5  6
   4  1  2  5  9  3  6  8  7
   3  9  1  6  7  4  5  2  8
   6  5  8  7  1  2  4  3  9
   7  3  9  8  2  5  1  6  4
   5  8  7  9  6  1  3  4  2


I suspect you'd rather just have the hints, and only for the reduced (minimal) forms? That will be a day or two away.

[denis_berthier]

I have 83 9x9 U's. The raw grid data is just the grid content. I've attached it just in case, if that's suitable for your purpose. From that you can generate the fully-specified hints.

I wrote a function to map each solved puzzle to my input format.
I was surprised to find that 2 of the 83 puzzles are significantly harder than the rest. After the surprise that there were so few Us, this is a lesser one, but still...
Before I tell you what the 2 puzzles are, could you check if your solver can find them?

I suspect you'd rather just have the hints, and only for the reduced (minimal) forms? That will be a day or two away.

It will be interesting also.

[Mathimagics]

I was surprised to find that 2 of the 83 puzzles are significantly harder than the rest. After the surprise that there were so few Us, this is a lesser one, but still...
Before I tell you what the 2 puzzles are, could you check if your solver can find them?

My current Solver is not particularly efficient, being a non-standard model, but as best I can tell from these solve times, one probable candidate is #79, and the other one of these

Code: Select all

Begin solve #45 21:19:14   NFS = 1, et =26.31 *
Begin solve #51 21:20:18   NFS = 1, et =27.12 *
Begin solve #66 21:22:33   NFS = 1, et =29.60 *
Begin solve #71 21:23:28   NFS = 1, et =29.02 *
Begin solve #79 21:25:15   NFS = 1, et =33.87 *


It could be any of these I guess!

[denis_berthier]

My current Solver is not particularly efficient, being a non-standard model, but as best I can tell from these solve times, one probable candidate is #79, and the other one of these

Code: Select all

Begin solve #45 21:19:14   NFS = 1, et =26.31 *
Begin solve #51 21:20:18   NFS = 1, et =27.12 *
Begin solve #66 21:22:33   NFS = 1, et =29.60 *
Begin solve #71 21:23:28   NFS = 1, et =29.02 *
Begin solve #79 21:25:15   NFS = 1, et =33.87 *

Bad draw!
All the puzzles, except 11 and 67, can be solved using only singles and ascending chains.
11 and 67 require whips[3] - which is not very much harder, but harder nevertheless.

Is your solver based on some form of DFS?

[Mathimagics]

I can see that my guesses were pretty atrocious!

But my solver was not DFS, it was an interim hack designed to get the bugs out of my DFS solver. It proceeded chain by chain, at each step enumerating all possible chain settings for the next chain, then intersecting these with the current set, eventually producing a reduced list of possibilities.

But it has done its job, my DFS solver is now working.

I'll run it against the batch of 83 and see if will correctly identify those two.

[denis_berthier]

my solver was not DFS, it was an interim hack designed to get the bugs out of my DFS solver. It proceeded chain by chain, at each step enumerating all possible chain settings for the next chain, then intersecting these with the current set, eventually producing a reduced list of possibilities.

Our resolution models are very different. It's not too surprising that we don't find the same "hardest".

[Mathimagics]

Ok, my DFS solver appears to be fully operational.

I have verified the batch of 83, and now solve them in an average of 0.0025s, which is a great improvement (cf: my pathetic timings above).

All the puzzles, except 11 and 67, can be solved using only singles and ascending chains.
11 and 67 require whips[3] - which is not very much harder, but harder nevertheless.

I assume your "singles" are cells which can only take one value, and "ascending chains" are the same as my chains, ie. a sequence of n cells C(k) with C(1) < C2 ... < C(n).

My "pre-shave" routine (which is only applied at the beginning) presets any chains of maximum length, then passes through the chain list looking for any chains that can be completed. Only if this fails to complete the grid does it go into DFS mode.

I log both the DFS iteration count (total number of search tree "visit"s) and the number of passes taken in the pre-shave routine.

It's interesting, then, that in that batch it solved 82 of them without any DFS, the only exception being #49. The pre-shave only required a second pass in 2 cases, #66 and #78.

Pre-shave for #49 left 15 cells with apparent value choices.

So I'd never have identified #11 and #67 in any case.

Anyway, now that I have an easy way to detect reduced forms - they should be precisely those puzzles that require any DFS - I can get on with the reduction process.

[Mathimagics]

Here are a couple of test items for you - I've reduced #1 and #2 to a reasonable degree (not guaranteed minimal but I will develop the process further). They do require 15-16K node visits in the DFS, so they are "tough" in my model!

Can you work with this format? (I can add sugar to taste for later batches)

Batch #1:

Code: Select all

 9
 . . . < . . . < .
 . < . . < . . . .
 < . . . < < < . .
 . . < . < . < . .
 > < . < > < < . .
 . . < < . < . < .
 > . > . < . > . .
 > < > > . . . . .
 . . < . . < < > .
 > . > . < > . . .
 . . . < < < . < >
 > . . . < < . . <
 < . > < . > < < <
 > . . < > . > . <
 < > . < . > . . <
 . > . < < < . < .
 > . . < . . . > .
 . . . . . . . . .


Batch #2

Code: Select all

 9
 > > > > . > . > .
 . > > . > . . . .
 . > . . < < . < .
 . . < . > . < . .
 < < . > < > > < .
 < < > > > > > < .
 . . < . < > > . .
 > < . > > > . . .
 . . > . . > > < .
 > < > . > < . . .
 < . < < > . . > .
 < < . . < > > < .
 . . . . > < < > .
 > < . < . . . < >
 . > > > < . . . .
 . > . . < > . < .
 > > . > . . < > .
 . . . . . . . . .


[Mathimagics]

I've worked on those two examples, and have reduced them to an extremely reduced form. These take DFS = 100K (egad!) visits. I'm not sure I'd like to tackle them by hand!

They still retain a maximal chain, however. You'd think, oh boy, I've got 9 givens straight away, but you'd quickly run out of "must be"'s. Assuming I'm right in assessing the complexity anyway. We'll see what your system makes of them.

I've anticipated a 1 line format like Kakuro:

Code: Select all

 9 . . . < . . . < . / . < . . . . . . . / . . . . . < < . . / . . < . . . . . . / . < . . . . < . . / . . . < . < . . . / > . > . < . > . . / . . > . . . . . . / . . . . . < < > . // . . > . < . . . . / . . . . < < . . > / . . . . < . . . < / < . > < . . < . < / > . . < > . > . < / < . . < . > . . < / . > . < . . . . . / > . . . . . . > . / . . . . . . . . . //
 9 > > > > . > . > . / . . > . > . . . . / . > . . . . . < . / . . < . . . . . . / < < . . < > . . . / . . . . > > > < . / . . . . . > > . . / . < . > . > . . . / . . > . . > . < . // . < . . > < . . . / < . < . . . . . . / < < . . . . . . . / . . . . . . < . . / . . . . . . . < > / . > . > < . . . . / . > . . < . . < . / > > . . . . < . . / . . . . . . . . . //


Of course, this is just one particular reduced form for each case. Because I started with a maximal chain that happened to be retained at the first iteration (coarse shave), it then persisted through the subsequent iterations (fine shave).

I will next try and deliberately disturb the maximal chains, and see what happens.