The New Sudoku Players' Forum

[gsf]

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"

[olimpia]

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

[udosuk]

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.

[gsf]

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]

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

[eleven]

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.

[JPF]

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]

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

[olimpia]

Thanks for you analysis eleven. Thats interesting info about the 16 clue puzzles.

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

[ChPicard]

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

[Pat]

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.

[JPF]

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

[ChPicard]

Hi

Congratulations eleven

How do you do that?

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

[Red Ed]

Wow, eleven's using mind control to force JPF into making all those posts? Congratulations indeed.

[eleven]

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 !