6x6 su dokus - how hard can they be?

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

6x6 su dokus - how hard can they be?

Postby Guru » Thu Oct 27, 2005 11:50 am

I'm just curious, i've seen a lot of 6x6 su dokus; but none so far has required any solving method more complicated than naked/hidden singles.

How hard do you think 6x6 su dokus can be?

And how few clues do you think a 6x6 su doku can have, while still having a single solution?
Guru
 
Posts: 5
Joined: 25 October 2005

re: 6-squared SuDoku - how hard can they be?

Postby Pat » Thu Oct 27, 2005 1:03 pm

Guru wrote:How hard do you think 6x6 su dokus can be?


very tough! see r.e.s. (2005.Oct.4) :

r.e.s. (2005.Oct.4) wrote:
tso wrote:SOLO, from Simon Tatham's Portable Puzzle Collection - especially interesting is the ability to make 6x6 puzzles that can be solved only with Forcing Chains -- a great way to learn the technique.


Indeed, the Unreasonable 6x6s are great for learning to use Forcing Chains.

Of the couple dozen or so Unreasonable 6x6s (with "2-way" rotational symmetry) that I tried, one of them is apparently unsolvable by FC:
Code: Select all
 . . . | . 4 .
 . 1 . | 3 . 5
-------+------
 . . . | 2 . .
 . . 3 | . . .
-------+------
 6 . 2 | . 5 .
 . 5 . | . . .
User avatar
Pat
 
Posts: 3449
Joined: 18 July 2005

Postby Guru » Thu Oct 27, 2005 1:20 pm

Amazing!:D i would never have thought that 6x6 su dokus could be that tough!

I notice that the puzzle has 10 clues, is it possible too create 6x6s with less clues?
Guru
 
Posts: 5
Joined: 25 October 2005

Postby Sue De Coq » Thu Oct 27, 2005 4:32 pm

I would like to add my praise to this amazing puzzle - however, it does submit to Tabled Chains, but only after a protracted fight.:)

Code: Select all
1. The cell r4c4 is the only candidate for the value 5 in Column 4.
2. The value 1 in Box 6 must lie in Row 5.
- The moves r6c4:=1, r6c5:=1 and r6c6:=1 have been eliminated.
The value 1 in Box 4 must lie in Column 5.
- The moves r3c6:=1 and r4c6:=1 have been eliminated.
The value 4 in Box 6 must lie in Column 4.
- The moves r5c6:=4 and r6c6:=4 have been eliminated.
Consider the chains r1c4-6-r6c4~6~r6c6 and r1c4-1-r1c6-2-r6c6.
When the cell r6c6 contains the value 6, one chain states that the cell r1c4 contains the value 6 while the other says it doesn't - a contradiction.
Therefore, the cell r6c6 cannot contain the value 6.
- The move r6c6:=6 has been eliminated.
Consider the chains r1c6-1-r5c6-3-r5c2~4~r4c2, r1c6~2~r1c2-2-r4c2 and r1c6~6~r4c6~4~r4c2.
Whichever of the 3 candidate values fills the cell r1c6, the cell r4c2 does not contain the value 4.
- The move r4c2:=4 has been eliminated.
Consider the chains r1c1-3-r6c1~3~r6c6-2-r1c6, r1c1-5-r1c3~6~r1c4-1-r1c6 and r1c1-5-r1c3~6~r1c6.
Whichever of the 3 candidate values fills the cell r1c6, the cell r1c1 does not contain the value 5.
- The move r1c1:=5 has been eliminated.
The cell r1c3 is the only candidate for the value 5 in Row 1.
3. The cell r3c1 is the only candidate for the value 5 in Row 3.
4. Consider the chains r2c5~6~r4c5-1-r3c5-1-r3c3 and r2c5-6-r2c3-6-r3c3.
When the cell r2c5 contains the value 6, one chain states that the cell r3c3 contains the value 1 while the other says it doesn't - a contradiction.
Therefore, the cell r2c5 cannot contain the value 6.
- The move r2c5:=6 has been eliminated.
The value 2 is the only candidate for the cell r2c5.
5. The value 4 is the only candidate for the cell r2c1.
6. The value 6 is the only candidate for the cell r2c3.
7. The cell r4c6 is the only candidate for the value 4 in Row 4.
8. The cell r6c6 is the only candidate for the value 2 in Row 6.
9. Consider the chains r6c3-1-r6c1-3-r6c5 and r3c3-1-r3c5-3-r6c5.
When the cell r6c5 doesn't contain the value 3, one chain states that the value 1 in Column 3 belongs in the cell r6c3 while the other says it doesn't - a contradiction.
Therefore, the cell r6c5 must contain the value 3.
- The move r6c5:=6 has been eliminated.
The value 3 is the only candidate for the cell r6c5.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby tso » Fri Oct 28, 2005 6:01 pm

Guru wrote:Amazing!:D i would never have thought that 6x6 su dokus could be that tough!

I notice that the puzzle has 10 clues, is it possible too create 6x6s with less clues?


That depends how you define a 6x6 Sudoku. If you allow the boxes to be irregularly shaped, the minimum number of clues is only 6. (Maybe 5, though I couldn't find an example.) Since using a 2x3 box is somewhat arbitrary anyway, why not?

See: http://www.latinsquares.com/LSQ.html

Though the minimum number of clues for a standard 9x9 Sudoku is believed to be 17, again, if irregular boxes are used, the minimum drops to 8.

See:http://www.bumblebeagle.org/dusumoh/9x9/index.html


http://home.flash.net/~markthom/html/latin_square_puzzles.html
http://homepages.tesco.net/~stephen.bennett/latinsquare/latinsquare.html
tso
 
Posts: 798
Joined: 22 June 2005

Postby r.e.s. » Fri Oct 28, 2005 10:52 pm

tso wrote:
Guru wrote:I notice that the puzzle has 10 clues, is it possible too create 6x6s with less clues?

That depends how you define a 6x6 Sudoku. If you allow the boxes to be irregularly shaped, the minimum number of clues is only 6. (Maybe 5, though I couldn't find an example.)

According to this post by Bob Harris, there might be a "0-clue" 6x6 (!):
me13013 wrote:The holy grail would be a puzzle with no clues and 9! solutions. In other words, the layout allows only one possibility for the latin square. The player could just write 1-9 along the top row and start solving. I believe Mark Thompson found one of these for 5x5 or 6x6.

That would be neat!


6x6 sudokus with irregular boxes are my favorite -- there's a great variety of levels of difficulty, from not-so-hard to unreasonably hard -- and solving strategies include all the various methods of "standard sudoku", plus some additional methods (e.g., Bob H's little & big laws of leftovers described in the Tutorials at http://www.bumblebeagle.org/dusumoh ). For 6x6's not necessarily of Bob H's "dusumoh" type, don't miss Eric Anderson's collection at the first link listed above.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby Pat » Sun Oct 30, 2005 11:17 am

Guru wrote:I notice that the puzzle has 10 clues, is it possible too create 6x6s with less clues?


for a box-size of 2x3,
menneske.No offers plenty of 8-clue puzzles

so, i wonder if a 7-clue puzzle may be possible?

- Pat
User avatar
Pat
 
Posts: 3449
Joined: 18 July 2005

Postby r.e.s. » Tue Nov 01, 2005 11:14 pm

Sue De Coq wrote:I would like to add my praise to this amazing puzzle - however, it does submit to Tabled Chains, but only after a protracted fight.:) [...]

Hey, that looks like a nice program -- will you be putting it online?:D
I wonder how well it does with this pretty outrageous 6x6, which I stumbled across recently ...
Code: Select all
 . . . | 5 . 6
 . . . | . 4 .
 ------+------
 1 . . | 3 . .
 . . 3 | . . 5
 ------+------
 . 4 . | . . .
 2 . 1 | . . .
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby rubylips » Wed Nov 02, 2005 3:10 am

Here's the solution to the tricky first two moves:

Code: Select all
1. Consider the chain r1c5-3-r2c6~3~r6c6-4-r6c4-4-r4c4-1-r4c5.
When the cell r1c5 contains the value 1, so does the cell r4c5 - a contradiction.
Therefore, the cell r1c5 cannot contain the value 1.
- The move r1c5:=1 has been eliminated.
The cell r1c2 is the only candidate for the value 1 in Row 1.
2. Consider the chain r1c5-3-r1c1~3~r5c1-3-r6c2~3~r6c5.
When the cell r6c5 contains the value 3, so does the cell r1c5 - a contradiction.
Therefore, the cell r6c5 cannot contain the value 3.
- The move r6c5:=3 has been eliminated.
Consider the chain r5c5-3-r1c5-2-r1c3-4-r3c3-4-r3c6-4-r6c6.
When the cell r6c6 contains the value 3, some other value must occupy the cell r5c5, which means that the value 4 must occupy the cell r6c6 - a contradiction.
Therefore, the cell r6c6 cannot contain the value 3.
- The move r6c6:=3 has been eliminated.
The value 4 is the only candidate for the cell r6c6.


The solver has been online for a long time - however, the output above is from a late beta of the next release, which I intend to bring out later this week.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby r.e.s. » Wed Nov 02, 2005 7:51 pm

rubylips wrote:The solver has been online for a long time - however, the output above is from a late beta of the next release, which I intend to bring out later this week.

Great! Of course I've appreciated your online solver for months, but for a while now I've noticed some postings that quote results which the current version, R1_21, does not produce (e.g., it finds no chains at all for either of the above 6x6's) -- so I figured something was brewing.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby rubylips » Thu Nov 03, 2005 12:24 am

r.e.s. wrote:Great! Of course I've appreciated your online solver for months.

Thanks. I've just uploaded 22 beta because it's been too long since the last release. There are plenty of new features, accompanied by a couple of minor bugs but no documentation. I'll release formally as soon as these omissions have been rectified.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby me13013 » Wed Apr 26, 2006 3:38 am

I've just come across the discussion from way back on Oct/29/2005 (I don't read this group often, someone else pointed me at this thread), regarding the minimum number of clues needed for a 6x6 sudoku's with irregular regions.

The answer is 5, and I have plenty of examples of that at
www.bumblebeagle.org/dusumoh
But the answer as to the minimum number of clues necesary depends on the particular layout (i.e. the shapes). For any N there exists an NxN layout with an N-1 clue puzzle. See proof on the site above but note that the puzzle shown in the proof is not very interesting as a puzzle.

There was also mention of my previous post (from who knows when):
In other words, the layout allows only one possibility for the
latin square. The player could just write 1-9 along the top row
and start solving. I believe Mark Thompson found one of these
for 5x5 or 6x6.

I was unable to find the one Mark did, and may have been mistaken, but I recently searched for those myself and found five 6x6's pretty quickly (there may be more) and one 7x7 after a much longer search. There are probably others, but as N gets larger the layouts with low clue puzzles become much much much sparser. Actually the proof mentioned two paragraphs above shows how to create such a "no-clue" layout for any N>=4 (but again, not interesting as a puzzle).

Bob H
me13013
 
Posts: 3
Joined: 14 October 2005

re: 2x3 - minimum number of clues

Postby Pat » Thu Aug 31, 2006 8:27 am

Pat (2005.Oct.30) wrote:for a box-size of 2x3,
menneske.No offers plenty of 8-clue puzzles

so, i wonder if a 7-clue puzzle may be possible?


i now see that this has been answered elsewhere:

Red Ed (2006.Mar.11) wrote:Unless my coding let me down,
the minimum number of clues for the 3x2 case (M=6) is 8.
User avatar
Pat
 
Posts: 3449
Joined: 18 July 2005


Return to General