Minimum number of clues

Everything about Sudoku that doesn't fit in one of the other sections

Postby Moschopulus » Wed Oct 26, 2005 8:36 am

kjellfp wrote:But for the 16-clue task: Those who now have experience, what is the apparently fastest algorithm for finding solutions to a clue-set? The setting I'm thinking of is when there are many solutions (thousands, millions), this might be different from the best algorithm for an assumed unique-solution sudoku.


True, but perhaps not important in the 16 clue problem. For each potential 16 clue puzzle generated, we just want to see if there is one solution or more than one solution. Once we find 2 solutions, we can pass to the next candidate. The exact number of solutions is not needed.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby DanO » Wed Oct 26, 2005 3:20 pm

dukuso wrote:When you have a multi-solution puzzle, then "unavoidable" has no meaning at all, it's not defined.


I thought "unavoidable" was a set of cells in a valid grid that can be permuted to form a different valid grid. Having a multi-solution puzzle means that from any solution there is set of cells that can be permuted to form another solution (ie, an unavoidable set that doesn't have a clue).

A question I have is, how does such a permutation affect the other intersecting unavoidable sets?

A puzzle with exactly 2 solutions will have only 1 unfixed unavoidable set with a cycle of 2. The transposition of that set will change several intersecting unavoidable sets but cannot create an unavoidable set that is not already fixed by a clue.

Is there a property of the unavoidable sets that is always preserved by such permutations?
DanO
 
Posts: 40
Joined: 18 October 2005

Postby Wolfgang » Thu Oct 27, 2005 5:45 pm

Please verify if i had a lucky punch (cant find another solver, which does it):
700200080000000100000903000000007046090000000050010000000009500000500000800000000
500200080000000100000903000000007046090000000050010000000000500000500000802000000
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Moschopulus » Thu Oct 27, 2005 6:19 pm

I get 0 solutions for both.:(
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Thu Oct 27, 2005 6:37 pm

Guenter's solver says 0 sol.
Sad man solver gets confused ! - eventually stalls

If your solver solves it ......well it certainly wont have been luck !

I await the experts on Pappacom.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Ocean » Thu Oct 27, 2005 11:26 pm

Wolfgang wrote:Please verify if i had a lucky punch (cant find another solver, which does it):
700200080000000100000903000000007046090000000050010000000009500000500000800000000
500200080000000100000903000000007046090000000050010000000000500000500000802000000

Code: Select all
 *-----------*
 |7..|2..|.8.|
 |...|...|1..|
 |...|9.3|...|
 |---+---+---|
 |...|..7|.46|
 |.9.|...|...|
 |.5.|.1.|...|
 |---+---+---|
 |...|..9|5..|
 |...|5..|...|
 |8..|...|...|
 *-----------*

Interesting puzzle, though invalid.

There is a conflict in R4C5:
1. Only cell in R4 where a 5 can be put.
2. Only cell in C5 where a 9 can be put.


For the second puzzle, try to put in the missing 5's.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Wolfgang » Fri Oct 28, 2005 9:24 am

Thanks, my solver was "optimised" for given grids, where this bug could not occur:(
This 17 clue should be correct now:
600200080000000100000903000000007046090000000050010000000000500000500309800000000
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby coloin » Fri Oct 28, 2005 2:10 pm

A good try.....a de novo non-Gfroyle 17.[Probably]
I dont know why the sadman solver got confused !

dukuso wrote:so our best grids have many unavoidables !


I suppose it is possible to chart all the minimal unavoidables with up to 4 clue numbers..........

But the non-minimal unavoidables...........
Every minimal puzzle will have x number of mostly non-minimal unavoidable sets, where x=the number of clues in the minimal puzzle grid.

No way to chart all of those !

But if we could list a representative sample of the nonminimal unavoidable sets from 100 randomly generated minimal grids........the most common clue in the sample of sets might will be the clue which hits the most sets. [ In the SF could it be the 1 in r3c2 ?]

We could then repeat with this clue always in and pick the 8 "best" clues this way.Then solve it minimaly to 17.......

It seems the unavoidables are no more than a tolerated nuisance....if the grid is completable - they all are covered - ipso facto.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Moschopulus » Sun Oct 30, 2005 10:14 pm

DanO wrote:
dukuso wrote:When you have a multi-solution puzzle, then "unavoidable" has no meaning at all, it's not defined.


I thought "unavoidable" was a set of cells in a valid grid that can be permuted to form a different valid grid. Having a multi-solution puzzle means that from any solution there is set of cells that can be permuted to form another solution (ie, an unavoidable set that doesn't have a clue).


Yes, you are right about the definition. Note that an unavoidable set is a set of cells *and* the digits in those cells. It's hard to word this properly.

What dukuso is referring to (I think) is that an unavoidable set is a property of a completed grid, not a property of a puzzle.
If a puzzle has more than one solution, it doesn't determine any particular grid.

You might then argue that although a puzzle with multiple solutions will determine several completed grids, those grids will all have the same unavoidable set in common. Namely, the one that "caused" multiple solutions.

In that case, yes the *cells* are determined by the puzzle but not the individual *digits* in the cells.
So we don't actually have an unavoidable set unless we specify the digits as well.


DanO wrote:A question I have is, how does such a permutation affect the other intersecting unavoidable sets?


Usually they are destroyed. After the permutation, other intersecting unavoidable sets are no longer unavoidable sets.
You might create new unavoidable sets as well.
For example, in this grid (which I call MG)

937856241
562194387
481273569
823647915
615932478
749581623
378469152
196725834
254318796

there is an unavoidable set in {11,15,21,25} i.e. rows 1 and 2, columns 1 and 5.
9...5....
5...9....

If you switch the 5 and the 9 in this unavoidable set, you destroy the unavoidable set {11,13,61,63}.
But you create a new one at {15,16,75,76}.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

SF

Postby Moschopulus » Sun Oct 30, 2005 10:30 pm

Promises promises....

A friend and I are working on a program to search the SF grid exhaustively for a 16.
We think we are nearly there. Currently it seems to work but the running time is too long. But not by much.
We are adjusting the number of unavoidable sets the program uses and trying to see how this affects the running time.
We think it can be optimized into a 10 day program, which we will divide up into 4 pieces and run on 4 computers. This will hopefully happen soon, although like everybody, we are working in our spare time which is limited.
When the program is suitable for public consumption we will post it.
Thanks to dukuso for providing a solver and other programs, and gfroyle for providing unavoidable sets.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Wolfgang » Wed Nov 02, 2005 11:06 am

[deleted (first have to make a program out of my hacks)]
Wolfgang
 
Posts: 208
Joined: 22 June 2005

no 16 in SF

Postby Moschopulus » Wed Nov 02, 2005 2:32 pm

We have completed an exhaustive search for a 16 clue puzzle in the SF grid.

639241785284765193517983624123857946796432851458619237342178569861594372975326418

No 16 was found.

Total CPU time 9-10 days on linux 2.1Ghz.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby dukuso » Wed Nov 02, 2005 2:43 pm

good !
10 days.
How long would it take to search for all 17s in that grid ? 170days ?
Maybe you'll make this program faster...
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Wed Nov 02, 2005 3:50 pm

dukuso wrote:Maybe you'll make this program faster...


or maybe you will....

The source code will be posted soon. There are several places where it can be made faster.

I'll look at the 17s computation.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Wed Nov 02, 2005 8:04 pm

Well done Mosch
I take it you done it by going through all the unavoidable possibilities.
A very determined effort.

Well which grid next ?

Wolfgang is homing in on 17s which are difficult to solve.......
I took two clues off his 17 clue puzzle but didnt generate any new 17s from the surounding environment.

The grid he is using has the first two horizontal gangsters similar to the SF.

Code: Select all
|639|241|785|
|284|765|193|
|517|983|624|

|321|857|946|
|796|432|851|
|458|619|237|

|963|124|578|
|142|578|369|
|875|396|412|



This grid
Code: Select all
|137|824|596|
|695|371|428|
|248|659|713|

|351|987|642|
|476|213|985|
|982|465|137|

|563|142|879|
|719|538|264|
|824|796|351|


is a grid I have been working on - it only has 3 [4 set unavoidables] - all with a common clue the 2 in r7c6 .[thats a certain clue then]

There are other unavoidables which conjoin. Probably a low MCN.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General