On the minimum and maximum minlex minimal sudokus

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

On the minimum and maximum minlex minimal sudokus

Postby Mauricio » Wed Aug 01, 2007 7:53 am

We already know the maximum and minimum min-lex solution grids. Finding the minimum is easier that finding the maximum.

A related question is trying to find the minimum and maximum minimal sudokus. That question is obviously harder than trying to find the minimum and maximum minlex solution grid, as there are a lot more minimal sudokus than solution grids.

My conjectures about that sudokus are the following:
Code: Select all
 Minimum?
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
| . . . | . . 1 | . . 2 |
+-------+-------+-------+
| . . 1 | . . 2 | . . 3 |
| . . 2 | . . . | . 4 . |
| . . 3 | . 4 5 | . . 6 |
+-------+-------+-------+
| . 1 . | . . 3 | . 7 . |
| . 2 5 | . 6 . | . 8 . |
| . 3 6 | 7 . 4 | . 1 9 |
+-------+-------+-------+


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


Finding the minimum minlex sudoku should be easier than finding the maximum, and the minimality of the minimum is a necessity, not a requirement.

Are there more extremal minlex examples?

Of course that question is very technical, as morphing a sudoku to its minlex form is not trivial. Perhaps sudocue 3 can help. Sudocue 3 can't help, gsf program can (-f%#mc).
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby daj95376 » Fri Aug 03, 2007 3:21 pm

Hmmmm! Your post prompted me to combine the minimum and maximum min-lex grids with the basic min-lex grid. While reviewing the results, something bothered me when comparing the basic and maximum grids. Does anyone else see a problem???

Code: Select all
            Base                        Minimum                       Maximum
 *-----------------------*     *-----------------------*     *-----------------------*
 | 1 2 3 | 4 5 6 | 7 8 9 |     | 1 2 3 | 4 5 6 | 7 8 9 |     | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 . | . 8 9 | . . . |     | 4 5 6 | 7 8 9 | 1 2 3 |     | 4 5 7 | 8 9 3 | 6 1 2 |
 | . . . | . . . | . . . |     | 7 8 9 | 1 2 3 | 4 5 6 |     | 9 8 6 | 2 1 7 | 3 5 4 |
 |-------+-------+-------|     |-------+-------+-------|     |-------+-------+-------|
 | 2 . . | . . . | . . . |     | 2 3 1 | 5 6 4 | 8 9 7 |     | 2 7 4 | 5 3 8 | 1 9 6 |
 | . . . | . . . | . . . |     | 5 6 4 | 8 9 7 | 2 3 1 |     | 5 3 1 | 9 6 4 | 8 2 7 |
 | . . . | . . . | . . . |     | 8 9 7 | 2 3 1 | 5 6 4 |     | 6 9 8 | 7 2 1 | 4 3 5 |
 |-------+-------+-------|     |-------+-------+-------|     |-------+-------+-------|
 | . . . | . . . | . . . |     | 3 1 2 | 6 4 5 | 9 7 8 |     | 3 4 2 | 6 8 5 | 9 7 1 |
 | . . . | . . . | . . . |     | 6 4 5 | 9 7 8 | 3 1 2 |     | 7 1 5 | 3 4 9 | 2 6 8 |
 | . . . | . . . | . . . |     | 9 7 8 | 3 1 2 | 6 4 5 |     | 8 6 9 | 1 7 2 | 5 4 3 |
 *-----------------------*     *-----------------------*     *-----------------------*
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Fri Aug 03, 2007 3:43 pm

daj95376 wrote:While reviewing the results, something bothered me when comparing the basic and maximum grids. Does anyone else see a problem???

Min - min and max - min has by head spinning, but I would expect both to agree with the "base." They do not.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby JPF » Fri Aug 03, 2007 4:43 pm

daj95376 wrote:Hmmmm! Your post prompted me to combine the minimum and maximum min-lex grids with the basic min-lex grid. While reviewing the results, something bothered me when comparing the basic and maximum grids. Does anyone else see a problem???


I hope i understood your point.
Red Ed wrote:The maximum min-lex grid is:
Code: Select all
123456789457893612986217354274538196531964827698721435342685971715349268869172543
This is the unique grid (up to isomorphism) in which all 6 chutes have the maximum band index, i.e. 416. The grid is 72-way automorphic. And you'll notice that its minimal form doesn't have r2c5,6 = 8,9 -- so that closes off the question about guaranteed digits in min-lex form, too.

So the base is :
Code: Select all
            Base                        Minimum                       Maximum
 *-----------------------*     *-----------------------*     *-----------------------*
 | 1 2 3 | 4 5 6 | 7 8 9 |     | 1 2 3 | 4 5 6 | 7 8 9 |     | 1 2 3 | 4 5 6 | 7 8 9 |
 | 4 5 . | . . . | . . . |     | 4 5 6 | 7 8 9 | 1 2 3 |     | 4 5 7 | 8 9 3 | 6 1 2 |
 | . . . | . . . | . . . |     | 7 8 9 | 1 2 3 | 4 5 6 |     | 9 8 6 | 2 1 7 | 3 5 4 |
 |-------+-------+-------|     |-------+-------+-------|     |-------+-------+-------|
 | 2 . . | . . . | . . . |     | 2 3 1 | 5 6 4 | 8 9 7 |     | 2 7 4 | 5 3 8 | 1 9 6 |
 | . . . | . . . | . . . |     | 5 6 4 | 8 9 7 | 2 3 1 |     | 5 3 1 | 9 6 4 | 8 2 7 |
 | . . . | . . . | . . . |     | 8 9 7 | 2 3 1 | 5 6 4 |     | 6 9 8 | 7 2 1 | 4 3 5 |
 |-------+-------+-------|     |-------+-------+-------|     |-------+-------+-------|
 | . . . | . . . | . . . |     | 3 1 2 | 6 4 5 | 9 7 8 |     | 3 4 2 | 6 8 5 | 9 7 1 |
 | . . . | . . . | . . . |     | 6 4 5 | 9 7 8 | 3 1 2 |     | 7 1 5 | 3 4 9 | 2 6 8 |
 | . . . | . . . | . . . |     | 9 7 8 | 3 1 2 | 6 4 5 |     | 8 6 9 | 1 7 2 | 5 4 3 |
 *-----------------------*     *-----------------------*     *-----------------------*
JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby daj95376 » Sat Aug 04, 2007 3:14 pm

Okay, <89> have been removed from [r2]. But, are any of the other cells common between the minimum and the maximum forced ??? There's enough to where the magic number 17 might be found.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006


Return to General