The New Sudoku Players' Forum

[Moschopulus]

We were wondering about puzzles with two completions.
Call a sudoku puzzle with exactly two completions a pseudo-puzzle, or pseudo for short.

We all think that a 16 clue sudoku does not exist.
The next best thing is a 16 clue pseudo, and what is interesting is that these do exist.
As far as I know, there is only one example known of a 16 clue pseudo, found by Gordon.
5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........
So 16 clue pseudos could be much rarer than 17s (although we haven't been looking very hard for them).

The two completions of this pseudo are
562389471849716253137425896358194627974263185216857349691542738725638914483971562
562398471948716253137425986359184627874263195216957348681542739725639814493871562
and the set of cells where they differ is (by definition) an unavoidable set.
In this case the unavoidable set consists of all cells containing 8 and 9.
Either one of these grids is the SF grid.

We were wondering about an exhaustive search of a grid for a pseudo, and the connection to unavoidable sets.

Here is one way to proceed, but there may be better ways.

Recall the method checker uses to search a grid exhaustively for an n clue puzzle.
(The key point is that a puzzle with one completion will have to intersect all unavoidable sets.)

1. Find a decent collection C of unavoidable sets.
2. Enumerate all hitting sets (sets of size n that intersect all unavoidables in C).
3. Run a solver on each hitting set to see if there is a unique solution.

For a pseudo-puzzle, it is no longer true that there has to be one clue in each unavoidable.
However, any pseudo with n clues will arise from removing a clue from a hitting set with n+1 clues (*proof below).
Therefore, to enumerate all candidate pseudos with 16 clues, we need to enumerate all hitting sets with 17 clues and remove one clue in all possible ways.

This is not terribly efficient. Is there a better way?


[*Proof: let G be a completed grid and let X be the set of clues in a pseudo-puzzle in G. Say X has n clues. Let U be any unavoidable set in G that does not intersect X. Then removing U from G leaves a pseudo-puzzle with 2 solutions, the 2 solutions of X. So the 2 solutions of X differ only in cells that are in U. This is true for any U that does not intersect X, so the 2 solutions of X differ only in cells that are in all such U's. Choose a cell in the intersection of all such U's, add it to X, and we have a hitting set with n+1 clues.]

[Red Ed]

This is not terribly efficient. Is there a better way?

I may have missed the point entirely, but isn't this exactly what Gordon's done already -- I mean, enumerate "all" (or 95%+) 17s and reduce those by one?

As a side note: an alternative to your proof would be to note that any pseudo puzzle on n clues must have its solutions differing by a unique minimal unavoidable set, from which you can borrow any clue to make a uniquely-solvable puzzle on n+1 clues.

[Ocean]

We were wondering about puzzles with two completions.
Call a sudoku puzzle with exactly two completions a pseudo-puzzle, or pseudo for short.

...

... 16 clue pseudos could be much rarer than 17s (although we haven't been looking very hard for them).

...

We were wondering about an exhaustive search of a grid for a pseudo, and the connection to unavoidable sets.

It's a bit unclear to me whether you plan to do a complete search on one specific grid for finding the smallest pseudos in that grid (which I think is hard), or finding one pseudo (which is trivial), or finding/counting all.


Here are two alternative (slightly different and easier) approaches:

1.
To search for pseudos with N clues, a simple way is to start with a list of 'N+1'-sudokus, and for each of them remove one clue (in all N possible ways), and count the number of solutions for each candidate. The fast solvers take less than a millisecond per candidate, so the whole search should be pretty fast.

For instance, checking all known 17-sudokus should take less than 10 minutes to run. - [Edit:] My version of the pseudo-finder (which I wrote after posting the previous sentence) is a bit slower, and I tried it on Gordon's list of 17s. A bit surprising (to me, because I had not thought about it), 18 of the 17s generated a 16-pseudo-puzzle with 2 completions (I naively expected only two, while everybody else apparantly knew there had to be between four and eighteen). These 16-pseudos are all isomorph. Instead of listing the parent 17s, here are the isomorph 16-pseudos, generated from Gordon's list of 17s by removing one clue in every possible way:

Code: Select all

the isomorph 16-pseudos (with 2 completions), generated from Gordon's list of 17s.

000010004700000020300000000080000200000700030010000000000004801602300000000000000
000607300201000005000000000030000800700020000000010000005000010070800000000300000
000005081604700000000000000000200700080000040010000000000010005200000400700000000
010000070000800002000500000007000410500302000000000000800000005000010000000040200
010070000000003200000000500200005000000300080000000010500000403007810000000000000
030025000000000710060000000000060005700000600100400000400000000050000002000100000
060000052000301000040000000000000100020050000800000000100000800300400000000020040
060000705000401000030000000050070000000000010200000000000050300100000020400300000
060053000000000801020000000000020030800000200100700000030000050700000000000100000
060503000000000201040000000100070000200000400000400030700000000030000050000010000
075600000000000081000300000000500700000040000100000000400010000000080030030000500
200000030000010700030040000000600082000300000041000000800200000000000100000070000
300000206000071000400000000010000080070040000000600400600200000000000010080000000
309000500000071004000000000000500200070090000010000000000004010200900000500000000
300000007000010800400000000000300004050000070010000000207400000000008150000000000
500000700000100000060000000300075000000000081200000000010600000080000020000020500
600500000000000010030000000700000506000081000200000000000600200080020000010000030
800000040300700000000040200010062000000000083040000000020000600700000000000300000

2.
With reference to

"The only other example I know of a pseudo-puzzle with two completions is the one found by Gordon with 16 clues."

... I think most grids (possibly all) have pseudo-puzzles with two completions (that is, the grid is one of two grids constituting the solution set to some 'pseudo puzzles'). Start with a full grid, locate a small unavoidable set and remove those clues, and the resulting subgrid will probably be a pseudo-puzzle with exactly two completions. (To make it 'minimal', try to remove more clues one by one as long as the count is still two).

Here is one with 77 clues (and I am too lazy to make it minimal by hand):

Code: Select all

Pseudo-puzzle (two solutions):
 *-----------*
 |159|286|473|
 |237|154|896|
 |486|397|521|
 |---+---+---|
 |912|843|765|
 |345|..9|182|
 |678|521|349|
 |---+---+---|
 |861|432|957|
 |593|..8|214|
 |724|915|638|
 *-----------*

[Moschopulus]

I may have missed the point entirely, but isn't this exactly what Gordon's done already -- I mean, enumerate "all" (or 95%+) 17s and reduce those by one?

Yep, you're right, thanks. To be clear, this is a consequence of the following fact.

Fact: Any pseudo-puzzle with n clues arises from deleting a clue in a proper puzzle with n+1 clues.

Proof: (thanks for your simplification) Let X be the set of n clues for the pseudo. There is a unique minimal unavoidable set that does not intersect X. Add any clue from this set to X and we obtain a puzzle with n+1 clues that has one solution.

Two other comments: I'm not sure if you are assuming every 17-hitting set is a valid puzzle, which is not true in general, but is true here. Also, is the 95% figure proved or a heuristic guess?

This raises a question for Gordon, also raised by Ocean's first point.

To Gordon: for each 17 you find, do you check whether removing each clue leaves a 16 with two completions? I would assume you check this and a lot more besides.

I guess I was thinking of puzzles with 16 clues and a small number (<=10) of completions. I asked Gordon earlier it they all arose from deleting a clue in a 17, and he said no. So, this *is* true for puzzles with two completions. Must it be true for puzzles with three completions?

I get the impression that people feel that there is only one pseudo-puzzle with 16 clues. I'm amazed by this, how can there be only one? If so, what is so special about the SF grid?

It's a bit unclear to me whether you plan to do a complete search on one specific grid for finding the smallest pseudos in that grid (which I think is hard), or finding one pseudo (which is trivial), or finding/counting all.

We aren't sure at this point. Just thinking out loud. It would be nice to find more pseudos with 16 clues, so one thing to do is look for them. I guess the idea is to look by doing an exhaustive search through one grid (as checker does for ordinary puzzles). Now we can easily modify checker to do this.

Thanks for the observation about pseudos with arbitrary numbers of clues. I think most grids have an unavoidable of size 4, so they will all have a pseudo as you said. And those grids that don't have a size 4 will have a size 6 (I conjecture) and the same thing will work there, probably.

Conjecture: every grid has either a size 4 unavoidable set or a size 6 unavoidable set. (Most grids have both sizes)

[Ocean]

For comparision and statistics I run the pseudo-search program on random generated minimal sudokus with N clues. The result is in the table below (number of pseudo-puzzles found per 1000 minimal sudokus as a function of N).

Code: Select all

N   # found
27: 800/1000
26: 727/1000
25: 557/1000
24: 447/1000
23: 294/1000
22: 155/1000
21:  54/1000
20:  18/1000

None of these minimal sudokus generated more than one pseudo-puzzle! (When running on a full grid or non-minimal sudokus, several pseudo-puzzles will often be generated.)

Code: Select all

Sample set:

17-P: 000050062038000000000000000000307400200000070000800000070000300600020009000100000
18-P: 000020800610000400080000000302060000000400108000000000005000032004100000000000010
19-P: 120600000000000790000000300004900000007000100000400082000003540000081000005000000
20-P: 120000008000370000000009000004050002603000000000006000007040500000800031400000009
21-P: 120000050060300000000067000004010070500009020300004600080000000000040003000050001
22-P: 100050000000300002709000600904100007000009000500000400030420500000701003800000000
23-P: 020687430000000000000049070004100000002000090000006005078000501000000080009003600
24-P: 100007050900300040000005029054080000000500006000610000700000060041000003003400070
25-P: 120000040080300000000948300060509007008700400500800000300000500002090700070000010
26-P: 123090000000307000080046009054600010010000000060001053000000594006072000000000060

[Red Ed]

I'm not sure if you are assuming every 17-hitting set is a valid puzzle, which is not true in general, but is true here.

I was assuming you had not just a "decent collection" of unavoidables, but all of them. In which case, a 17-hitting set is a 17-clue puzzle.

Also, is the 95% figure proved or a heuristic guess?

Heuristic. Gordon received a list of 700 17s from some Japanese chap, only 33 of which were genuinely new. Pretending for a moment that Gordon and his correspondent drew their 17s at random from the universe of all 17s, the max likelihood estimator for the size of the universe is ~34550. But of course the search methods are biased towards what humans [conjecture: Gordon is human] can think up and be bothered to code, so that MLE will be probably be an underestimate. Maybe 90% is closer than 95% is. Either way, the probability of missing all 65 17s that are a 1-off extension of any given 16 is practically nil, and the probability of missing all 4+ 17s that are a 1-off extension of any given pseudo-16 is not much better.

Conjecture: every grid has either a size 4 unavoidable set or a size 6 unavoidable set. (Most grids have both sizes)

I believe this. I had a quick go a while back at generating a grid free of 4-sets and 6-sets, but ran out of patience before my program finished. It wasn't looking promising.

Update 27 Aug 2006: I have now verified that conjecture by computer search.

[coloin]

Yes it would be nearly as unlikly to find anothe pseudo with 18 clue completions - ie another very fertile grid containing 17s

It is slightly confusing when one speaks of "solutions"

......................grid completions [solutions]
......................clue completions [to make a different puzzle]

16-clue pseudos in the SF have :
2 grid completions [The two grid completions are essentially the same however!]
18 clue completions.[there are 18 clues - each one of which gives a unique 17 clue puzzle]

Code: Select all

+---+---+---+
|5.2|...|4..|
|...|71.|..3|
|...|...|...|
+---+---+---+
|...|..4|6..|
|.7.|2..|...|
|.1.|...|...|
+---+---+---+
|6..|..2|...|
|...|.3.|.1.|
|4..|...|...|
+---+---+---+ 16 clue "pseudo"

+---+---+---+
|562|3..|471|
|.4.|716|253|
|137|425|..6|
+---+---+---+
|35.|1.4|627|
|.74|263|1.5|
|216|.57|34.|
+---+---+---+

|6.1|542|73.|
|725|63.|.14|
|4.3|.71|562|
+---+---+---+  18 clue completion per each of 2 grid solutions.


At the 16 clue stage there is an unavoidable set with all these missing clues.
{15,16,21,23,37,38,43,45,51,58,64,69,72,79,86,87,92,94}
[Actually in all grids - each set of 2 clues has one of these unavoidable sets.] *

So all 2 grid solution pseudos have one unavoidable set of "x" number of clues - giving "x" unique clue completions.

Purists might argue that these 16 clue pseudos from the SF grid were doomed in the first place as they had no chance of a unique solution on their own [Only seven clue numbers] *

I consider the 16 clue pseudo which has 4 grid solutions - one of which has 19 clue completions as perhaps the more "fertile" example of how close 16 clues come to nearly giving a valid puzzle.

Code: Select all

5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..8........


[Moschopulus]

I was assuming you had not just a "decent collection" of unavoidables, but all of them. In which case, a 17-hitting set is a 17-clue puzzle.

Aha. No, we don't have *all* unavoidables, just a decent collection which includes all of size 4 and 6, and almost all (perhaps all) of size up to 14.

These are computed using "unavoid" which incorporates dukuso's program "unav36".

I would like to have an efficient way to compute *all* minimal unavoidables in a grid. There will be thousands. Ideas and suggestions are very welcome!

[Red Ed]

I would like to have an efficient way to compute *all* minimal unavoidables in a grid. There will be thousands. Ideas and suggestions are very welcome!

How about this. You spend a few weeks calculating representative minimal unavoidables from thousands of random grids. Then for each new grid of interest, you search for instances of those representative unavoidables. This'll get you nearly all unavoidables, but not every single one. (Do you really want every last unavoidable for a given grid?)

Some more detail. By representative (minimal) unavoidable, I mean some form of the unavoidable that is representative of all its friends generated by the 9! x 2 x 6^8 sudoku symmetries: I'm specifically thinking of a matrix that specifies for each clue in the unavoidable its relationship to all the other clues in the unavoidable (e.g. as per DanO's post).

When generating the big list of "all" representatives, you generate random unavoidables in the usual way (generate random grid, generate random clue set, solve, compare pairs of distinct solutions). For each unavoidable, you check (a) it's minimal and (b) it's not already in your big list (up to isomorphism). Checking (a) is done by enumerating partial grids that have the same row/col/box memberships as does your unavoidable and rejecting the unavoidable if any (position,value) pair appears in more than one partial grid. Checking (b) is just a matter of grinding through isomorphism checks against every other same-sized unavoidable. (I suppose you could also use subgraph isomorphism checks to do (a), but I think this is slower than the enumerating-partial-grids method.)

Checking a new grid for all instances of some representative unavoidable comes down to another subgraph isomorphism, I think. That is, find the ordered subset S of {0,...,80} such that the relationship matrix of your grid, restricted to rows/cols in S, is equal to the relationship matrix of the unavoidable being considered. I don't have a good feel for how fast or slow this might be, however.

I've actually got the big list generator mostly coded already. If there's interest, I can patch up the gaps and post some stats in the next few days. When I first did this work, I found there was essentially only one 4-set (unavoidable of size 4), four 6-sets (AFAIR), and no k-sets above k=35. In between that, I'd have to re-run to find out.

[Moschopulus]

Thanks, I am certainly very interested to see some stats.

This was our original plan for the programs "unavoid" and "checker". We had got the one representative of size 4 and the four of size 6, but we figured size >=8 would be harder so we didn't try to obtain a full set of representatives. Certainly this would be interesting to resolve. Unavoid computes all sets of sizes 4 and 6 using this representative idea. We then use dukuso's program to find some more sets, but this doesn't find all sets. We get enough sets to form a decent collection and make the program viable.

This is one way that checker could be speeded up, perhaps by quite a bit. The small unavoidables are more useful, so it would be really interesting to know that we had all the small ones (small meaning up to size 14 maybe). Size 8 would probably be the most important, so even to resolve that would be great.

[Ocean]

Here are 15 nonisomorph minimal 17-clue pseudo-puzzles (with 2 solutions) in the SF-grid:

500000400000710003000020000000004600070000000210000000600002000000030010400000002
500000400000710003000020000000004607070000000210000000600002000000030010400000000
500000400000710003000020000000004620070000000210000000600002000000030010400000000
500000400000710003000020000000004620070200000010000000600002000000030010400000000
500000400000710003007020000000004600070000000210000000600002000000030010400000000
500000470000710003000020000000004600070000000210000000600002000000030010400000000
500009400000710003000020000000004620070000000010000000600002000000030010400000000
502000400000710003000000000000004600070000000210000000600042000000030010400000000
502000400000710003000020000000004600070000000210000000600002000000030010400000000
502000400000710003000400000000004600070000000210000000600002000000030010400000000
502009400000710003000000000000004600070000000010000000600042000000030010400000000
502009400000710003000020000000004600070000000010000000600002000000030010400000000
502009400000710003000400000000004600070000000010000000600002000000030010400000000
502080400000710003000000000000004600070003000010000000600042000000000010400000000
502300400000710003000000000000004600070000000010000000600042000000008010400000000

All have 2 solutions (grid completions).
There are nine with 18 clue completions and six with 12 clue completions.
Two of them expand into 18 minimal 18s:
(17p/18c:) 500000400000710003000020000000004607070000000210000000600002000000030010400000000
(17p/18c:) 500000400000710003000020000000004600070000000210000000600002000000030010400000002
11 of the minimal 17-pseudos expand also into non-minimal 18-sudokus, which is the same as finding a 17-sudoku. In total 9 different 17s are found this way.
3 of the non-minimal 18s have each 3 different subgrids being minimal 17-pseudos.
11 of the 18s (5 minimal and 6 non-minimal) have each 2 different subgrids being minimal 17-pseudos.

In addition to these there is of course all 47 trivial extensions of the 16-clue pseudo:
502000400000710003000000000000004600070200000010000000600002000000030010400000000
(these 47 maybe could be called non-minimal 17-pseudos).
[In fact, it is possible to insert any combination of these 47 clues, giving rise to a total of 2^47-1, or 1e14, new different non-minimal pseudo-puzzles, having between 17 and 63 clues, all with 2 solutions.]
The 63-pseudo-puzzle (has also 2 solutions, and the same 18 clue completions):
562300471040716253137425006350104627074263105216057340601542730725630014403071562

Some more stats for the SF-grid: [Edit: These numbers are 'the best I know so far', and will be updated from time to time.]

Code: Select all

Number of sudokus
#17s:     29
#18s:    748 minimals
#19s: >60000 minimals
#20s:>570000 minimals

Number of pseudo-puzzles with 2 solutions
#16-p:      1
#17-p:     15 minimals
#18-p:   1185 minimals
#19-p: >27000 minimals

The two most fertile 18-clue pseudos found (with 2 solutions) have 29 clue-completions:
18p/29c 500000400000710003000000000000004600070000080210000000600002000000030010480000060
18p/29c 500000400000710003000000006000004600070000080210000000600002000000030010480000000


The most fertile 19-clue pseudo found (with 2 solutions) has 39 clue-completions:
19p/39c 502009400000710003000000000000004600070000000010050000600002000000030014400000500

[Red Ed]

Thanks, I am certainly very interested to see some stats.

... it would be really interesting to know that we had all the small ones (small meaning up to size 14 maybe). Size 8 would probably be the most important, so even to resolve that would be great.

OK, I think I've got the code running now. I'll post some stats below for the number of [isomorphism classes of minimal] unavoidables of various sizes, and will edit it from time to time as I get more results.

Code: Select all

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|    4|    5|    6|    7|    8|    9|   10|   11|   12|
|Nr Unavoidables|    1|    0|    4|    0|    9|    3|   47|   44|  416|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   13|   14|   15|   16|   17|   18|   19|   20|   21|
|Nr Unavoidables|  849| 5182| 9834|20021|16753|18461|13362|12552| 9486|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   22|   23|   24|   25|   26|   27|   28|   29|   30|
|Nr Unavoidables| 7912| 6252| 4818| 3556| 2615| 1836| 1320|  830|  516|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   31|   32|   33|   34|   35|   36|   37|  38+|
|Nr Unavoidables|  334|  217|  120|   63|   32|   14|    7|    0|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+

The number of unavoidables for 4-12 clues is looking quite stable, but there are still lots more to find among the larger sets.

Update: I have found lots of large minimal unavoidables now, not listed above, including a 47-set. Several of these large unavoidables are very rare in the sense that they are present in only one sudoku grid each (that is, they can be regarded as valid -- if rather uninteresting -- puzzles in their own right).

[Ocean]

OK, I think I've got the code running now. I'll post some stats below and edit this message from time to time as I get more results.

Interesting stats. I wonder if the numbers are 'calculated theoretical values', or if they are based on occurence in random grids, or in carefully selected representative grids - or possibly a combination?

[The case "4 clues: 1" is obviously (also) a theoretical result, but how many others are...]

[gfroyle]

To Gordon: for each 17 you find, do you check whether removing each clue leaves a 16 with two completions? I would assume you check this and a lot more besides.

Yep.. actually I keep a list of all 16s with up to 200 completions... again based on the "local search" principle that something with few completions is hopefully close to something with a unique completion.

Then I do a sort of "up and down" procedure as follows:

- start with some 17s, delete clues to find 16s with few (ie up to 200) completions

- perturb the 16s, keeping all those new ones with up to 200 completions

- add clues in all possible ways to create 17s

- perturb the 17s to get new ones

- repeat until fed up with lack of success


I have also implemented a new program which finds the "closest" uniquely completable puzzle to a 17 with any (moderate) number of completions. I perturb the starting puzzle and put all the perturbed ones into a queue in order of number of completions. Then I work through the queue, each time perturbing the next puzzle, adding the perturbed ones to the queue in the correct position if new, and so on, stopping only when I get to a puzzle with a unique solution. This gives me a "path" through a number of 17-clue pseudo-puzzles starting with the original pseudo-puzzle and ending with the CLOSEST valid puzzle, in the sense that there is no other valid puzzle that can be reached by using only intermediate pseudo-puzzles with fewer completions.

For those of you with CS or AI backgrounds, this is known as the A* search algorithm...

In general, I usually start it off with something with no more than a few hundred completions, say 500 at most, because otherwise it is very slow.

Interestingly it almost always ends up with a puzzle ALREADY in my collection, rather than a new one, adding weight to the suspicion that the existing list contains "most" 17-clue valid puzzles.

Cheers

gordon

[Moschopulus]

Some more stats for the SF-grid:

Code: Select all

Number of sudokus
#17s:     29
#18s:    724 minimals
#19s: >25000 minimals

Number of pseudo-puzzles with 2 solutions
#16-p:     1
#17-p:    15 minimals
#18-p: >1100 minimals

Thanks for those puzzles. How do you know these numbers are complete?

( i.e., how do you know there are *exactly* 29 17s in SF. I would bet there aren't any more, but how did you prove it?)

Earlier

18 of the 17s generated a 16-pseudo-puzzle with 2 completions (I naively expected only two, while everybody else apparantly knew there had to be between four and eighteen). These 16-pseudos are all isomorph.

So you found isomorph 16-clue pseudos with non-isomorph solutions? When are two puzzles isomorph? I'm missing something here.