Low-stepper Puzzles.

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

Postby gsf » Tue Jun 13, 2006 10:58 pm

a new 1 stepper improvement and 2 others
Code: Select all
#II,1,40,-,800001905000863700624000300740295080090306050050147092009000841001578000203900006,gsf,2006-06-12:16:04

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

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

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

#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  . . .

#VI,4,24,SM,000080000904000802003402600870000054020903010000000000005000200000746000030000070,gsf,2006-06-13:15:58

. . .  . 8 .  . . .
9 . 4  . . .  8 . 2
. . 3  4 . 2  6 . .

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

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

Postby JPF » Wed Jun 14, 2006 7:43 am

An improvement (2-stepper, 180-degree rotational symmetry)

Code: Select all
Type V , 2 steps, 33 clues


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


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

Postby gsf » Wed Jun 14, 2006 9:30 pm

a low/hi stepper search anecdote

I let fly a background generator/solver/filter that greps for symmetric minimal lo/hi steppers
every once in a while it goes through a dry spell -- nothing sufficiently low or high for the filter
I assumed it randomly hit a sequence of average puzzles
closer inspection showed the minimization code hitting a low clue initial puzzle
merrily dropping the clue count below 17 looking for valid (single solution) minimal puzzles
the long lapse that exposed the problem had it searching a 12 clue candidate puzzle
for this program <<17 is not very productive
I don't know how much this bug affected the ~1/day low stepper improvement rate

moral: unless you are looking for a 16 clue sudoku, adding tests for ~17 may speed up
some sudoku algorithms
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Wed Jun 14, 2006 11:20 pm

improvement of the day...
2-stepper, horizontal reflection

Code: Select all
Type VI, 2 steps, 34 clues

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


I realize that I haven't checked if my posted symmetric puzzles were SM or not.

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

Postby JPF » Thu Jun 15, 2006 7:26 am

improvement of the night...
2-stepper, horizontal reflection
Code: Select all
Type VI, 2 steps, 33 clues

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


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

Postby gsf » Thu Jun 15, 2006 9:40 am

1 stepper improvement
Code: Select all
#III,1,42,-,609501408070000010083702950305409607000203000208107509032605180060000090407908302,gsf,2006-06-15:03:45

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

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

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

Postby Ocean » Thu Jun 15, 2006 11:50 am

Nice improvements again from JPF and gsf.

Here are my contributions for today:
Code: Select all
# 4 steps. 23 clues. No symmetry. 
..7|1..|8..
.62|...|93.
..4|2.7|1..
---+---+---
...|...|...
...|.1.|2..
.3.|456|...
---+---+---
...|538|.6.
..9|.7.|...
...|...|...
#
# 5 steps. 22 clues. Minimal. No symmetry.
...|...|...
...|.1.|2..
.3.|45.|...
---+---+---
..2|..6|7..
.76|...|13.
..8|9.2|6..
---+---+---
...|843|.5.
..1|.2.|...
...|...|...
#
# Type II. 5 steps. 21 clues. Minimal.
1.2|...|..3
...|1.4|...
...|..5|..6
---+---+---
.47|...|.8.
...|.9.|...
.8.|...|41.
---+---+---
3..|6..|...
...|3.1|...
2..|...|5.9
#

Three puzzles with 20 clues. Type IV symmetry (double diagonal). 6-stepper, 7-stepper, 8-stepper. All in the same pattern.
Code: Select all
# Type IV, 6 steps, 20 clues, minimal.
 *-----------*
 |..1|.23|..4|
 |...|..4|...|
 |5..|...|6..|
 |---+---+---|
 |...|...|.71|
 |6..|...|..3|
 |89.|...|...|
 |---+---+---|
 |..4|...|..7|
 |...|3..|...|
 |7..|65.|8..|
 *-----------*
#
# Type IV, 7 steps, 20 clues, minimal.
 *-----------*
 |..1|.23|..4|
 |...|..1|...|
 |5..|...|6..|
 |---+---+---|
 |...|...|.43|
 |6..|...|..1|
 |72.|...|...|
 |---+---+---|
 |..4|...|..5|
 |...|2..|...|
 |8..|69.|7..|
 *-----------*
#
# Type IV, 8 steps, 20 clues, minimal.
 *-----------*
 |..1|.23|..4|
 |...|..1|...|
 |5..|...|6..|
 |---+---+---|
 |...|...|.43|
 |6..|...|..1|
 |72.|...|...|
 |---+---+---|
 |..4|...|..5|
 |...|2..|...|
 |1..|68.|7..|
 *-----------*
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Ocean » Fri Jun 30, 2006 2:21 pm

After a period of frequent submissions, this thread has been quiet for a while. But here is a new improvement:

Code: Select all
#Type II, 5 steps. 20 clues, minimal.
1..|...|2.3
...|...|4..
56.|.7.|...
---+---+---
...|2.5|...
..4|...|8..
...|1.3|...
---+---+---
...|.6.|.71
..8|...|...
2.3|...|..5

Still, the numbers ought to go down in several of the categories...
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Fri Jun 30, 2006 3:10 pm

Ocean wrote:After a period of frequent submissions, this thread has been quiet for a while. ...
Still, the numbers ought to go down in several of the categories...

I just set off two background processes with a new sort that should keep
generated file sizes in the Kb instead of Gb, one for inferior and one for
ulterior (another thread). They are set to reap the entire step range. Will
get back in a week or so.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Fri Jun 30, 2006 5:44 pm

here is a table of the progress for min # clues for each step count
it includes posts to this list
the search is on symmetric puzzles only
Code: Select all
|||||1||2||3||4||5||6||7||8||9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27
||O|36|29|26|23|22|19|18|17|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--
||I|44|32|28|28|24|24|24|20|28|24|28|28|28|28|28|28|--|29|--|--|28|--|--|--|--|--|--
|II|40|32|24|24|21|20|20|20|24|24|24|24|25|24|28|24|28|28|--|24|28|--|--|--|--|--|--
III|42|32|28|25|22|22|22|22|24|24|24|24|25|26|26|26|28|--|28|--|24|--|--|--|--|--|--
|IV|41|32|28|26|24|20|20|20|25|24|25|24|24|24|24|25|27|28|--|--|28|--|--|28|26|--|--
||V|40|33|26|24|20|20|18|18|22|22|22|23|22|22|23|22|23|24|24|24|23|22|23|26|24|--|--
|VI|41|33|27|24|23|23|22|22|23|23|22|22|23|22|22|23|22|23|23|24|24|24|24|24|27|--|--
VII|40|34|25|25|22|22|18|18|22|22|22|21|21|22|22|22|23|23|23|23|23|23|23|22|25|23|24
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ab » Sun Jul 02, 2006 4:31 pm

just stumbled across the first sudoku printed in the Times:
http://www.timesonline.co.uk/article/0,,18209-2249082,00.html
it's a 3 stepper:
Code: Select all
 . 2 . | 8 1 . | 7 4 .
 7 . . | . . 3 | 1 . .
 . 9 . | . . 2 | 8 . 5
 ------+-------+------
 . . 9 | . 4 . | . 8 7
 4 . . | 2 . 8 | . . 3
 1 6 . | . 3 . | 2 . .
 ------+-------+------
 3 . 2 | 7 . . | . 6 .
 . . 5 | 6 . . | . . 8
 . 7 6 | . 5 1 | . 9 .

ab
 
Posts: 451
Joined: 06 September 2005

Postby Ocean » Mon Jul 03, 2006 11:34 pm

ab wrote:just stumbled across the first sudoku printed in the Times: [...]
it's a 3 stepper:


Thanks for the pointer. Don't know what is the average stepcount for newspaper puzzles nowadays. They should preferably both be challenging and be solved in reasonable time...

gsf wrote:I just set off two background processes with a new sort that should keep
generated file sizes in the Kb instead of Gb, one for inferior and one for
ulterior (another thread). They are set to reap the entire step range. Will
get back in a week or so.


Looking forward to see the results from these runs.

gsf wrote:here is a table of the progress for min # clues for each step count
it includes posts to this list
the search is on symmetric puzzles only
Code: Select all
|||||1||2||3||4||5||6||7||8||9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27
||O|36|29|26|23|22|19|18|17|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--
||I|44|32|28|28|24|24|24|20|28|24|28|28|28|28|28|28|--|29|--|--|28|--|--|--|--|--|--
|II|40|32|24|24|21|20|20|20|24|24|24|24|25|24|28|24|28|28|--|24|28|--|--|--|--|--|--
III|42|32|28|25|22|22|22|22|24|24|24|24|25|26|26|26|28|--|28|--|24|--|--|--|--|--|--
|IV|41|32|28|26|24|20|20|20|25|24|25|24|24|24|24|25|27|28|--|--|28|--|--|28|26|--|--
||V|40|33|26|24|20|20|18|18|22|22|22|23|22|22|23|22|23|24|24|24|23|22|23|26|24|--|--
|VI|41|33|27|24|23|23|22|22|23|23|22|22|23|22|22|23|22|23|23|24|24|24|24|24|27|--|--
VII|40|34|25|25|22|22|18|18|22|22|22|21|21|22|22|22|23|23|23|23|23|23|23|22|25|23|24



Interesting statistics. Also noticed the jump between 8 and 9, indicating that <=8 has been attacked specifically, while >=9 follows a more uniform statistical pattern. When special collections are investigated, the general statistics is disturbed.
For instance, these two from gfroyle's 17s would lead to new anomalies:

Code: Select all
VII,13,17,M,000000001000000023004005000000100000000040600006000405000076000010000000320008000,gfroyle/Red_Ed
VII,16,17,M,000000001000000023004005000000100000000040600006000405000076000010000000820009000,gfroyle/Red_Ed

How long time would it take to find those two by ordinary search?
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby ab » Tue Jul 04, 2006 11:09 pm

You missed out the 28 step puzzles from Ruud and vidarino. Ruud's has 21 clues and the symmetry is 180 rotation.
ab
 
Posts: 451
Joined: 06 September 2005

Postby Ocean » Tue Jul 11, 2006 8:32 pm

ab wrote:You missed out the 28 step puzzles from Ruud and vidarino. Ruud's has 21 clues and the symmetry is 180 rotation.

Yea.. but they actually belong to the inferior thread...

Here is an 8-stepper.
Code: Select all
# Type VI. 8 Steps. 20 clues. Minimal.
 *-----------*
 |...|...|...|
 |...|..1|2..|
 |13.|.4.|.5.|
 |---+---+---|
 |..2|..6|7..|
 |.53|...|...|
 |..8|..2|9..|
 |---+---+---|
 |98.|.5.|.3.|
 |...|..7|6..|
 |...|...|...|
 *-----------*
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby JPF » Thu Jul 13, 2006 2:11 pm

New improvement :

1-stepper, 35 clues, no symmetry.

Code: Select all
 9 4 7 | . . 8 | 1 . .
 1 . 3 | . . 6 | 8 2 .
 . . . | . . . | . 5 7
-------+-------+-------
 . 9 . | 3 4 . | . . 8
 6 3 . | . 9 . | . . .
 2 1 . | . . . | . 7 9
-------+-------+-------
 . . 6 | 8 3 1 | . . .
 . . . | 7 . 4 | 2 6 .
 5 . 1 | 2 . . | 4 . .


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

PreviousNext

Return to General