What is most solved cells with "n" clues?

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

Postby gsf » Fri Mar 06, 2009 11:22 am

here's an improvement on the 16
Code: Select all
....4.2...36............1.....6.....2.....4.....7...8........375...1.......8...6. # 16 49 8
...6..74.8...5..........1......3...5.7........1.......3.2.........7..4..5..1..... # 16 51 8

found by searching all derived 16's from the 17 catalog |G|=48010
took 36h wall time
using these options with the just posted sudoku.exe version 2009-03-06
Code: Select all
-go-1 -q- -e "max(determined()+9-(%#vX))" -f"%v # %G %2(determined())x %#vX"
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby olimpia » Fri Mar 06, 2009 8:48 pm

Why so sparse with the information? You just did a 36 hour experiment and then didn't even tell us how many positions they solve.

So I checked the first and it solves to fill 65 cells total. Impressive!

Do I understand you that you took every 16 clue combination from the 17 clues puzzles and checked how many they solve? I would have thought that would take more than 36 hours. I guess that would not be as bad as checking every 15 clue combination, which would produce 17*16 = 272 combinations for each 17 (if my math is correct).

Good work:!:
olimpia
 
Posts: 35
Joined: 14 November 2008
Location: USA

Postby udosuk » Fri Mar 06, 2009 9:35 pm

olimpia wrote:Why so sparse with the information? You just did a 36 hour experiment and then didn't even tell us how many positions they solve.

So I checked the first and it solves to fill 65 cells total. Impressive!

olimpia, perhaps you should have been more observant. gsf already specified the number of solved cells at the end of his 2 lines ("# 16 49 8" and "# 16 51 8"). So in the 1st puzzle 16+49=65 cells are filled, leaving 16 cells unsolved. In the 2nd one 16+51=67 cells are filled, leaving 14 cells unsolved. (The "8" should refer to the number of different symbols appearing among the given clues, I guess.)

Also, knowing gsf's programming prowess, 36h isn't such an surprising time for such a task.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Fri Mar 06, 2009 10:33 pm

udosuk wrote:
olimpia wrote:Why so sparse with the information? You just did a 36 hour experiment and then didn't even tell us how many positions they solve.

So I checked the first and it solves to fill 65 cells total. Impressive!

olimpia, perhaps you should have been more observant. gsf already specified the number of solved cells at the end of his 2 lines ("# 16 49 8" and "# 16 51 8"). So in the 1st puzzle 16+49=65 cells are filled, leaving 16 cells unsolved. In the 2nd one 16+51=67 cells are filled, leaving 14 cells unsolved. (The "8" should refer to the number of different symbols appearing among the given clues, I guess.)

Also, knowing gsf's programming prowess, 36h isn't such an surprising time for such a task.:)

thanks and thanks
the solver evolves with the best ideas posted on the player's and programmer's forums

I'm not pleased with the 36 hours because it makes the search over derived 15's and 14's etc untenable

here's a breakdown of all the options used to show the work being done

Code: Select all
-go-1 -q- -e "max(determined()+9-(%#vX))" -f"%v # %G %2(determined())x %#vX"


-go-1 for each input puzzle generate all subpuzzles with one (-1) clue deleted
since the input puzzles were 17's in this experiment, all 16's are generated
for all 15's use -go-2

-q- don't solve the generated puzzles (because they are subpuzzles)

-e "max(determined()+9-(%#vX))" -e is a filter expression
this expression contains two functions:

determined() for each pencilmark candidate assert the candidate,
run a singles only backtrack solver, and eliminate the candidate if it produces a contradiction
for this experiment determined() will run on 16's, so the absence of a contradiction doesn't necessarily imply valid solution
the return value of determined() is the number of determined clues, e.g., 49 in the first puzzle above

max(expr) if the arithmethic expression expr is greater than
the previous expr evaluated then max(expr) returns true, otherwise false
the effect in this experiment is to only list puzzles that improve on the metric
the metric in this case is to maximize determined()+9-(%#vX)
(%...) is a term that expands the value of the -f format %...
in this case its %#vX, which is the number of clue values used by the puzzle, not counting dups
so 9-(%#vX) minimizes the number of clue values
and the entire expression maximizes the number of determined clues and minimizes the number of clue values

finally
-f"%v # %G %2(determined())x %#vX" is the output format for each puzzle meeting the filter criteria
each %... represents a puzzle property
%v the 81 char grid
%G the number of clues in the original grid
%2(determined())x the number of determined clues, print field width 2
%#vX the number of clue values

the determined() results are cached for each puzzle, so multiple calls
for a single puzzle only do the computations once

so the hot spot for this example is determined()
on the hobby todo list is to plug in briturner's original backtrack solver to see if it improves runtime

the --man option should describe all of this (tersely)
if it doesn't let me know
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Fri Mar 06, 2009 10:40 pm

I forgot to mention that -go... keeps a minlex dictionary of all generated subpuzzles
this eliminates dups, a big win, especially as the subgrid size decreases
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby eleven » Sat Mar 07, 2009 6:40 pm

Well done, gsf.

This astonishing result again shows, how near the puzzles came to a 16 clue. We had G.Royles 16 clue with 2 solutions and 18 unsolved cells - but ok, with two missing numbers you cant get a unique puzzle.
Here are no digits missing and they end up with only 16 and 14 unsolved cells, leaving 7 and 6 solutions. This is nearly nothing, when you keep in mind, how many solutions have been excluded by the 16 clues.

To compare: If in the second puzzle you take the 17 clue you get by adding 2 in r2c7 and then remove the 7 in r5c2, you have a 16 clue with 131251 solutions and only 4 solved cells. So in this case a single clue can exclude more than 100000 solutions and solve the last 61 cells.
eleven
 
Posts: 1537
Joined: 10 February 2008

Postby JPF » Sun Mar 08, 2009 1:54 pm

Here is an improvement :
9/7
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|..1|
 |..2|..3|...|
 |---+---+---|
 |...|...|.1.|
 |...|..2|...|
 |.1.|...|...|
 |---+---+---|
 |...|...|2..|
 |...|.1.|...|
 |2..|...|...|
 *-----------*

solved to
 *-----------*
 |...|..1|...|
 |...|...|..1|
 |1.2|..3|...|
 |---+---+---|
 |.2.|...|.1.|
 |...|1.2|...|
 |.1.|...|...|
 |---+---+---|
 |..1|...|2..|
 |...|21.|...|
 |2..|...|1..|
 *-----------*
JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Sun Mar 08, 2009 2:40 pm

Here's an improvement :
14/25
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|.12|
 |..3|..4|...|
 |---+---+---|
 |...|...|3..|
 |...|.1.|...|
 |...|25.|...|
 |---+---+---|
 |...|..3|4..|
 |.1.|...|...|
 |25.|...|..1|
 *-----------*

solved to
 *-----------*
 |5.2|..1|.43|
 |...|.35|.12|
 |1.3|.24|5..|
 |---+---+---|
 |.21|...|35.|
 |..5|31.|2..|
 |.3.|25.|1..|
 |---+---+---|
 |...|1.3|425|
 |31.|5.2|...|
 |25.|...|.31|
 *-----------*
JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby olimpia » Sat Mar 14, 2009 7:38 pm

Thanks for you analysis eleven. Thats interesting info about the 16 clue puzzles.
eleven wrote:This astonishing result again shows, how near the puzzles came to a 16 clue.

Maybe a 16 clue puzzle can still be discovered. I'm not going to give up hope until I see that some mathematician or programmer has done a thorough search of every grid. This probably deserves its own thread but I read about some programmer who spent more than 10 years using many PCs to play every game of checkers (and found out the game is a draw if there's no mistakes in play). I wonder if anyone has started something like that for sudoku:?:

BTW, here's an update for our "n" clue search:
Code: Select all
givens   qty solved  total  values   source
------   ----------  -----   ------  ------
4         1           5       1
5         1           6       1
6         3           9       1     (Coloin)
7         4           11      2     (JPF)
8         5           13      2     (JPF)
9         7           16      3     (JPF)
10        10          20      3     (eleven)
11        11          22      3     (JPF)
12        14          26      6     (JPF)
13        17          30      6     (JPF)
14        25          39      5     (JPF)
15        33          48      8     (JPF)
16        51          67      8     (gsf)
17        64          81      8or9  (many)


It looks like 10 clues is the first point where you can get a 1:1 payback (10 clues can solve 10 positions).

The best 14 needs only 5 values, but the 13 needs 6, and the 15 needs 8. An interesting bump down:?:

Also, the 15 is the first point where we get "bounceback". The 8 values are enough to introduce a 9th value. Its like a party and when the door is opened to let the 9 in, a bunch of others come and the party gets fun:!:
olimpia
 
Posts: 35
Joined: 14 November 2008
Location: USA

12 or 13 givens, which solve more than 14 and 17

Postby ChPicard » Wed Mar 18, 2009 2:42 pm

olimpia wrote:
BTW, here's an update for our "n" clue search:
Code: Select all
givens   qty solved  total  values   source
------   ----------  -----   ------  ------
4         1           5       1
5         1           6       1
6         3           9       1     (Coloin)
7         4           11      2     (JPF)
8         5           13      2     (JPF)
9         7           16      3     (JPF)
10        10          20      3     (eleven)
11        11          22      3     (JPF)
12        14          26      6     (JPF)
13        17          30      6     (JPF)
14        25          39      5     (JPF)
15        33          48      8     (JPF)
16        51          67      8     (gsf)
17        64          81      8or9  (many)


The best 14 needs only 5 values, but the 13 needs 6, and the 15 needs 8. An interesting bump down:?:



Then we can hope than JPF will find a 12 or 13 givens, which solve respectively more than 14 and 17 with only 4 values.


Very interesting thread Olimpia

ChPicard , modest discoverer of # 47742, 47743, 47782 and 48014 in the Royle's database.

Maybe a 16 clue puzzle can still be discovered.


Thank you for encouragements


:D
ChPicard
 
Posts: 16
Joined: 02 March 2008

Postby Pat » Wed Mar 18, 2009 2:54 pm

ChPicard wrote:Then we can hope that JPF will find
a 12 or 13 givens
which solve respectively more than 14 and 17
with only 4 values.


yes i do hope
    needn't be more than 14 and 17

    12 or 13 clues solving just 14 and 17 cells (same quantity as before)
    would be an improvement
    where the clues use fewer than 6 different digits.
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Postby JPF » Fri Mar 20, 2009 1:40 pm

For ChPicard and Pat :

Here is a 12/14 with only 4 digits :
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|..1|
 |..2|..3|...|
 |---+---+---|
 |...|...|...|
 |...|..2|...|
 |.1.|...|..4|
 |---+---+---|
 |...|.4.|.3.|
 |..3|...|.2.|
 |.4.|.1.|...|
 *-----------*

solved to
 *-----------*
 |..1|...|..2|
 |...|.2.|..1|
 |..2|1.3|...|
 |---+---+---|
 |.2.|..1|...|
 |...|..2|.1.|
 |.1.|...|2.4|
 |---+---+---|
 |...|24.|13.|
 |1.3|...|42.|
 |24.|31.|...|
 *-----------*

Here is an improvement 13/18 and only 4 digits :
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|.12|
 |...|.34|...|
 |---+---+---|
 |...|...|..3|
 |...|...|4..|
 |..2|1..|...|
 |---+---+---|
 |...|2..|...|
 |.3.|...|...|
 |41.|...|3..|
 *-----------*

solved to
 *-----------*
 |...|...|.34|
 |.43|...|.12|
 |.21|.34|...|
 |---+---+---|
 |1.4|...|2.3|
 |...|3..|4.1|
 |3.2|14.|...|
 |---+---+---|
 |...|2.3|.4.|
 |23.|4..|...|
 |41.|...|32.|
 *-----------*

Edit : 13/19 - 4 digits
Code: Select all
 *-----------*
 |...|...|...|
 |...|...|..1|
 |...|..2|...|
 |---+---+---|
 |...|..3|.2.|
 |..1|...|...|
 |..4|...|3..|
 |---+---+---|
 |...|.1.|..4|
 |.2.|...|.3.|
 |.3.|.4.|...|
 *-----------*

solved to
 *-----------*
 |..3|..1|..2|
 |..2|.3.|..1|
 |.1.|..2|..3|
 |---+---+---|
 |...|1.3|42.|
 |3.1|.2.|...|
 |2.4|...|31.|
 |---+---+---|
 |...|31.|2.4|
 |42.|...|13.|
 |13.|24.|...|
 *-----------*

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Hi eleven! Two new Royles in a week

Postby ChPicard » Fri Mar 20, 2009 7:50 pm

Hi

Congratulations eleven

How do you do that?

ChPicard , modest discoverer of # 47742, 47743, 47782 and 48014 in the Royle's database.
ChPicard
 
Posts: 16
Joined: 02 March 2008

Postby Red Ed » Sat Mar 21, 2009 2:05 pm

Wow, eleven's using mind control to force JPF into making all those posts? Congratulations indeed.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Hi eleven! Two new Royles in a week

Postby eleven » Sat Mar 21, 2009 5:11 pm

ChPicard wrote:Congratulations eleven

How do you do that?
Thanks, but the congrats have to go to gsf. I am just playing around with his excellent program on a 2GH notebook since 2 weeks. The first new 17 seems to be pure luck, the second one i found starting with "isolated" 18's, i.e no other 18 within {-1+1}. But it took the same time (about 5 days running):(

I think, JPF and gsf were doing a better job here, congratulations !
eleven
 
Posts: 1537
Joined: 10 February 2008

PreviousNext

Return to General