Low-stepper Puzzles.

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

Postby gsf » Sat Jun 10, 2006 5:10 am

still ~1/day
Code: Select all
#V,3,26,SM,080000024050009000014750000008040600000102000002060700000015360000300090590000040,gsf,2006-06-10

. 8 .  . . .  . 2 4
. 5 .  . . 9  . . .
. 1 4  7 5 .  . . .

. . 8  . 4 .  6 . .
. . .  1 . 2  . . .
. . 2  . 6 .  7 . .

. . .  . 1 5  3 6 .
. . .  3 . .  . 9 .
5 9 .  . . .  . 4 .
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Sat Jun 10, 2006 7:25 am

2 Improvements :

Type VI ; 1 step ; 41 clues
Code: Select all

 . . 9 | . 7 3 | 1 . .
 . 1 . | 4 9 . | . . 5
 7 . 4 | 2 . . | 3 . 8
-------+-------+-------
 4 3 . | . . 8 | . 6 1
 6 5 . | 9 3 . | 4 . .
 2 9 . | . . 4 | . 7 3
-------+-------+-------
 3 . 5 | 6 . . | 8 . 9
 . 8 . | 7 5 . | . . 4
 . . 2 | . 8 1 | 6 . .



3 steps ; 26 clues ; no symmetry (Type 0)
Code: Select all

 . 5 4 | . 7 6 | . . .
 1 . . | . . . | 2 . .
 . . 9 | . 4 . | . . .
-------+-------+-------
 . . . | . . 7 | . 6 .
 . . 8 | . . 9 | . . 5
 7 . 1 | . . 8 | . 9 .
-------+-------+-------
 . . . | . 5 1 | . . .
 4 . . | . 9 2 | 3 . .
 2 3 . | . . . | 7 . .



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

Postby JPF » Sat Jun 10, 2006 9:28 am

Type IV ; 1 step ; 43 clues
Code: Select all
 3 2 1 | 6 . 5 | . . 7
 4 . . | . . 8 | . 3 .
 9 . 5 | 2 7 . | 6 . .
-------+-------+-------
 2 . 9 | . 5 . | . 8 1
 . . 6 | 1 9 4 | 2 . .
 1 7 . | . 3 . | 9 . 6
-------+-------+-------
 . . 8 | . 2 1 | 7 . 5
 . 4 . | 5 . . | . . 8
 5 . . | 4 . 7 | 3 6 9

 


2 steps ; 29 clues ; no symmetry (Type 0)
Code: Select all

 . 4 . | 7 . . | 2 . .
 . 8 2 | . . 1 | 6 . 4
 . . . | . 4 . | . . 3
-------+-------+-------
 2 3 . | 4 . . | . 7 .
 . 9 . | 8 6 3 | . 4 .
 . . . | . . . | 1 . .
-------+-------+-------
 . . 1 | 9 7 5 | . . .
 3 . 6 | . . . | . . .
 . . 8 | 2 . . | . 5 .



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

Postby Ocean » Sat Jun 10, 2006 8:16 pm

Lots of contributions lately. Great! The table now has 62 entries (only two holes left). There is still room for improvement for most of the numbers. But not all: Ten entries cannot possibly be beaten unless new 17s (or lower) are found.

Code: Select all
# 1. The current state:
     1  2  3  4  5  6  7  8
  I 44 32 28 28 24 24 24 20
 II -- 32 24 24 24 20 20 20
III -- 34 28 25 22 22 22 22
 IV 43 34 28 26 25 24 24 24
  V 40 35 26 24 20 20 18 18
 VI 41 35 27 25 24 24 22 22
VII 40 34 25 25 23 23 18 18
  0 37 29 26 26 24 19 18 17
#

Entries that cannot possibly be beaten unless new 17s (or lower) are found:
Code: Select all
# 2. Almost lowest possible:
     1  2  3  4  5  6  7  8
  I -- -- -- -- -- -- -- 20
 II -- -- -- -- -- 20 20 20
III -- -- -- -- -- -- -- --
 IV -- -- -- -- -- -- -- --
  V -- -- -- -- -- -- 18 18
 VI -- -- -- -- -- -- -- --
VII -- -- -- -- -- -- 18 18
  0 -- -- -- -- -- -- 18 17
#

Entries that match the 'accumulated list' in some way or another:
Code: Select all
# 3. Matching accumulated lowest:
     1  2  3  4  5  6  7  8
  I 44 32 -- -- -- -- -- --
 II -- 32 24 24 -- 20 -- --
III -- -- -- -- -- -- -- --
 IV -- -- -- -- -- -- -- --
  V 40 -- -- 24 20 20 18 18
 VI -- -- -- -- -- -- -- --
VII 40 -- -- -- -- -- 18 18
  0 37 29 -- -- -- 19 18 17
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Sun Jun 11, 2006 5:39 am

another
Code: Select all
#IV,2,32,SM,002806030000004809600095070800000354006000700591000006010670008309100000040209600,gsf,2006-06-10:21:56

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

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

. 1 .  6 7 .  . . 8
3 . 9  1 . .  . . .
. 4 .  2 . 9  6 . .
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Sun Jun 11, 2006 2:13 pm

an improvement
Code: Select all
#VI,6,23,SM,000008000000035810067000000002060503000040000005080907049000000000051280000009000,gsf,2006-06-11:02:09

. . .  . . 8  . . .
. . .  . 3 5  8 1 .
. 6 7  . . .  . . .

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

. 4 9  . . .  . . .
. . .  . 5 1  2 8 .
. . .  . . 9  . . .

and a type II 1 stepper
Code: Select all
#II,1,41,-,100900873806005000200781050098040207003526900604090310060278009000300601352009004,gsf,2006-06-11:02:0
1 . .  9 . .  8 7 3
8 . 6  . . 5  . . .
2 . .  7 8 1  . 5 .

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

. 6 .  2 7 8  . . 9
. . .  3 . .  6 . 1
3 5 2  . . 9  . . 4
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Sun Jun 11, 2006 7:33 pm

Two puzzles with double diagonal symmetry.
Code: Select all
# Type IV. 8 steps. 20 clues. SM
 *-----------*
 |...|..1|.23|
 |..1|...|..4|
 |.5.|.2.|...|
 |---+---+---|
 |...|6..|..7|
 |..8|...|5..|
 |3..|..8|...|
 |---+---+---|
 |...|.5.|.8.|
 |5..|...|9..|
 |26.|7..|...|
 *-----------*
#
# Type IV. 7 steps. 20 clues. SM
 *-----------*
 |...|..1|.23|
 |..2|...|..4|
 |.5.|.6.|...|
 |---+---+---|
 |...|3..|..7|
 |..8|...|2..|
 |6..|..7|...|
 |---+---+---|
 |...|.2.|.5.|
 |1..|...|6..|
 |74.|8..|...|
 *-----------*
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby JPF » Sun Jun 11, 2006 11:36 pm

1 step ; 36 clues ; no symmetry (type 0)

this one :

Code: Select all

 3 . . | . . 7 | 1 9 .
 2 . . | 8 . 6 | . . .
 4 5 9 | . . . | . 6 .
-------+-------+-------
 9 . 6 | . . 1 | . 5 4
 . . . | . 3 . | 2 . .
 . . 7 | 2 . 4 | 8 1 9
-------+-------+-------
 . 4 . | 1 5 . | . . 3
 . 8 5 | . 2 . | 9 . 7
 6 . . | 4 . 8 | . . .



or this one :
Code: Select all

 2 3 . | 7 . . | 8 . .
 . . . | 6 . 9 | . 5 1
 1 . . | . . . | 4 3 .
-------+-------+-------
 . 7 8 | . 1 5 | . 4 3
 9 . . | . 8 . | 1 . 6
 . 4 . | . . . | . . 2
-------+-------+-------
 . . 3 | . 6 2 | . 9 4
 8 2 7 | 3 . . | . . .
 4 6 . | 1 5 . | . . .




Some 1 steppers, 37 clues , type 0 :
Code: Select all
702600019503007000000823060900031850054080670017040020201000007000309482090205000
860305009005074002009008300002000840638009070070600005904850763100230500700400100
054300007700100043610900502300820470001060809570000200809503000200090051100047600
020600000001080540300921780064700000900250003850006209400193820080000634500004010
410000052300420069000068000000907208047200003005310796060540000100003670859001300
740001300012000680000729050060500740308090005090102000480000030007630920620950401
367000910080090406005081000070562030003000647091003080800400071500900302026105000
002634000008001570490058302003900681007310020065000009320047010070000000506803900
286009400009510800000000670635900000090000732100084000002468050500273901470100008
681004090003080500004003128048710630050940080060000057890001000000539072700002004
600000450591080070824003900042090106000076090005408020073500002080140600100030709
032590007050080962080700050490063000021000800605004100009208074067050003203010008
390000065050190024060200080004003000020871009805640013087054600006000790109008400
640050091703008054800092000010000739000670002530210008020000687008705900409030100
000045006007830501830090002903100648060580000020000730076209010382006000001070064
080600000000002950040185270010728090829003600350000400102076000690530001004009803
090076000006380071000100240704900513200704009800035000040291705001040680523000000
060090704201040069009370051983000100006002030700005800430600000502814600010700902


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

Postby JPF » Mon Jun 12, 2006 12:21 am

4 steps ; 25 clues ; no symmetry (type 0)
Code: Select all
 . . . | 8 . . | . . .
 7 . . | . . 5 | 1 8 .
 . 6 4 | . . . | . 3 .
-------+-------+-------
 . . . | . 1 4 | . . .
 . . 6 | . . . | . 7 9
 . 5 . | . 9 2 | . . .
-------+-------+-------
 1 7 8 | . . . | . . 2
 2 . . | 9 3 . | . . 6
 . . . | 1 . . | . . .



Type IV ; 1 step ; 41 clues
Code: Select all
 . . 7 | . 2 . | 9 5 4
 . 1 . | . 5 9 | . 3 7
 4 . . | 8 . 3 | . . 2
-------+-------+-------
 . . 2 | 3 . . | 1 8 .
 1 4 . | . 8 . | . 9 6
 . 6 5 | . . 7 | 4 . .
-------+-------+-------
 5 . . | 2 . 6 | . . 8
 6 2 . | 1 3 . | . 7 .
 9 3 8 | . 4 . | 2 . .



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

Postby JPF » Mon Jun 12, 2006 12:30 am

Ocean, you wrote:Entries that match the 'accumulated list' in some way or another...

What does that mean ?
JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Mon Jun 12, 2006 7:32 am

a new entry ; the last one ?

type III ; 1 step ; 44 clues

Code: Select all

 2 . 8 | 5 3 7 | 4 . 6
 . . . | 8 1 9 | . . .
 5 3 . | . 4 . | . 7 8
-------+-------+-------
 1 . 6 | . 8 . | 2 . 4
 . . 3 | 2 . 1 | 6 . .
 8 . 7 | . 6 . | 9 . 5
-------+-------+-------
 7 4 . | . 5 . | . 6 9
 . . . | 9 2 6 | . . .
 9 . 1 | 4 7 8 | 5 . 3


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

Postby Ocean » Tue Jun 13, 2006 10:01 am

JPF wrote:a new entry ; the last one ?
Nice to have all entries in the table! The table in is also updated with new improvements.
JPF wrote:
Ocean, you wrote:Entries that match the 'accumulated list' in some way or another...

What does that mean ?
JPF
With 'accumulated list' I meant this upper/summary part of the table:
Code: Select all
#------------------------------+----+----+----+----+----+----+----+----+
Number of steps:               |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
#------------------------------+----+----+----+----+----+----+----+----+
Symmetric + absolute minimal:  | -- | -- | -- | 24 | 20 | 20 | 18 | 18 |
Symmetric + minimal symmetric: | 44 | 32 | 24 | 24 | 20 | 20 | 18 | 18 |
Symmetric:                     | 40 | 32 | 24 | 24 | 20 | 20 | 18 | 18 |
Minimal:                       | -- | -- | -- | 24 | 20 | 19 | 18 | 17 |
Any sudoku:                    | 36 | 29 | 24 | 24 | 20 | 19 | 18 | 17 |
#------------------------------+----+----+----+----+----+----+----+----+
... and picked those entries for each symmetry type that match the current 'accumulated'. Which now is:
Code: Select all
# 3. Matching accumulated lowest:
     1  2  3  4  5  6  7  8
  I 44 32 -- -- -- -- -- --
 II -- 32 24 24 -- 20 -- --
III -- -- -- -- -- -- -- --
 IV -- 32 -- -- -- -- -- --
  V 40 -- -- 24 20 20 18 18
 VI -- -- -- -- -- -- -- --
VII 40 -- -- -- -- -- 18 18
  0 36 29 -- -- -- 19 18 17
#

If we take the 1-steppers as an example: Lowest number of clues for any sudoku is 36 clues, which is found for puzzles with no symmetry. For a symmetric sudoku, the lowest number of clues found is 40. This is found for symmetry types V and VII, but not (yet) for the other symmetries. 44 clues is the lowest number for SM (found for type I symmetry), while no absolute minimal 1-stepper is found.

My assumption is that symmetry groups with 'lower symmetry' will (with high probability) contain puzzles with at least as few clues as puzzles with higher symmetry (for a given step count). (Any other opinions?) For instance: Since a 3-stepper with 24 clues is found with symmetry type II, it is expected that this (or lower) should exist also for symmetry types III-VII + 0.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Tue Jun 13, 2006 12:52 pm

another improvement
Code: Select all
#VII,6,22,M,000000030000305809006001070700000240430900000000020060200000500000090000005014000,gsf,2006-06-12:18:16

. . .  . . .  . 3 .
. . .  3 . 5  8 . 9
. . 6  . . 1  . 7 .

7 . .  . . .  2 4 .
4 3 .  9 . .  . . .
. . .  . 2 .  . 6 .

2 . .  . . .  5 . .
. . .  . 9 .  . . .
. . 5  . 1 4  . . .
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Tue Jun 13, 2006 4:53 pm

An improvement (5-stepper, diagonal symmetry):
Code: Select all
# Type VII, 5 steps. 22 clues. Minimal.
1 2 .|. 3 4|. . .
5 . .|. . .|6 . .
. . 3|. . .|7 . .
-----+-----+-----
. . .|. . 8|. 1 .
3 . .|. . .|. 2 8
2 . .|7 . .|. . .
-----+-----+-----
. 8 9|. . .|. . 3
. . .|4 5 .|. . .
. . .|. 1 .|9 . .
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby JPF » Tue Jun 13, 2006 9:59 pm

Ocean wrote:My assumption is that symmetry groups with 'lower symmetry' will (with high probability) contain puzzles with at least as few clues as puzzles with higher symmetry (for a given step count). (Any other opinions?) For instance: Since a 3-stepper with 24 clues is found with symmetry type II, it is expected that this (or lower) should exist also for symmetry types III-VII + 0.

I agree.
There are actually 4 "classes" of symmetries :
Order 8 : Type I (F)
Order 4 : Type II,III,IV (L,P,X)
Order 2 : Type V,VI,VII (R,H,D)
Order 1 : Type 0 (A)

with the following notations :

st : symmetry type (A<D;H;R<X;P;L<F)
s : number of steps
m : minimality (NM<SM<M)
N(st,s,m) = Min of clues

we can assume that :
st<st’ => N>=N’ (other parameters being equal)
s<s’ => N>=N’
m<m’ => N>=N’

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

PreviousNext

Return to General