What are the minimum clues for this sudoku?

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

What are the minimum clues for this sudoku?

Postby Addlan » Fri Aug 01, 2008 8:03 pm

The minimum clues for the below sudoku must be more than 18 since it is constructed by 9 independent mini-puzzles, each of which needs at least 2 clues. However, 18 clues might not be enough. What is the minimum clues then?

The sudoku:
*-----------*
|123|456|789|
|456|789|123|
|789|123|456|
|---+---+---|
|231|564|897|
|564|897|231|
|897|231|564|
|---+---+---|
|312|645|978|
|645|978|312|
|978|312|645|
*-----------*

One of the mini-puzzles is:
*-----------*
|...|456|789|
|456|789|123|
|789|123|456|
|---+---+---|
|...|564|897|
|564|897|231|
|897|231|564|
|---+---+---|
|...|645|978|
|645|978|312|
|978|312|645|
*-----------*
which needs at least two hints to solve. There are 9 such independent mini-puzzles, needing at least 2*9 hints.

Another kind of mini-puzzles is in another orientation:
*-----------*
|.23|.56|.89|
|.56|.89|.23|
|.89|.23|.56|
|---+---+---|
|231|564|897|
|564|897|231|
|897|231|564|
|---+---+---|
|312|645|978|
|645|978|312|
|978|312|645|
*-----------*

One possibility will be to create hints shared by these mini-puzzles:
*-----------*
|1..|...|7..|
|.5.|.8.|...|
|...|..3|..6|
|---+---+---|
|...|5..|8..|
|.6.|...|.3.|
|..7|..1|...|
|---+---+---|
|3..|6..|...|
|...|.7.|.1.|
|..8|...|..5|
*-----------*

However, the above configure leads to many solutions. How to reduce this sudoku to its minimum hints:?: B.W.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby wintder » Sat Aug 02, 2008 12:41 am

I used sudoku cue to reduce it to this,

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


It is an easy puzzle with 36 clues, at this point.

Here is another, easy with 26.

Code: Select all
. . .|. . .|. . .
. . .|. 8 .|1 . 3
7 . .|. . 3|. 5 6
-----+-----+-----
. 3 .|. . 4|. . 7
. . 4|. . .|2 . .
. . .|2 . .|5 6 .
-----+-----+-----
. . 2|. 4 5|. 7 8
6 . .|. 7 8|. . .
9 7 .|. . .|6 . .
wintder
 
Posts: 297
Joined: 24 April 2007

Postby udosuk » Sat Aug 02, 2008 1:34 am

This is known as the MC (Most Canonical) grid. The minimum number of clues for this grid is known to be 20. Can't find the original source though. I'm sure Pat can dig it out for you in a flash.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Sat Aug 02, 2008 9:22 pm

Here are 2 minimal puzzles with double symmetry (diagonal and antidiagonal) :

22 clues
Code: Select all
 1 . . | . . . | . . .
 . . 6 | 7 . . | . 2 .
 . 8 . | . 2 3 | . . .
-------+-------+-------
 . 3 . | 5 . . | 8 . .
 . . 4 | . . . | 2 . .
 . . 7 | . . 1 | . 6 .
-------+-------+-------
 . . . | 6 4 . | . 7 .
 . 4 . | . . 8 | 3 . .
 . . . | . . . | . . 5       ER=7.2


26 clues
Code: Select all
 1 2 3 | . 5 . | . . .
 4 . . | 7 . . | . 2 .
 7 . 9 | . . 3 | . . .
-------+-------+-------
 . 3 . | . . . | 8 . .
 5 . . | . . . | . . 1
 . . 7 | . . . | . 6 .
-------+-------+-------
 . . . | 6 . . | 9 . 8
 . 4 . | . . 8 | . . 2
 . . . | . 1 . | 6 4 5       ER=10.4


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

Postby Glyn » Sat Aug 02, 2008 9:58 pm

Glyn
 
Posts: 357
Joined: 26 April 2007

Postby Addlan » Mon Aug 04, 2008 2:27 pm

OK, thanks.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Mon Aug 04, 2008 7:48 pm

See also this thread where it is confirmed that the grid has no 19 clue puzzles, but it can be solved with 20 clues:

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

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006


Return to General