Searching the minimum given for a Logic Plum Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Searching the minimum given for a Logic Plum Sudoku

Postby Drjsguo » Sat May 05, 2007 3:34 am

Just wondering if anyone is interested to investigate the minimum given for a Plum Sudoku? There are tens of thousand cases for Standard Sudoku, or Classic Sudoku, with minimum given of 17, but none have found a single case lower. Similar to a Standard Sudoku, the Plum Sudoku also has only three restrictions; i.e. “every row, every column, and every same position on all nine 3X3 boxes contain all nine digits.” In an analogy to the Standard Sudoku, I assume the minimum given for Plum Sudoku might be also 17. Since I have not found one single case with given number even close to that figure, I am not positive about this assumption.

One more thing about the characteristic of Plum Sudoku is that the population of Plum Sudoku is apparently much larger than the Standard Sudoku according to the building power of Super Dieluohan. A lot of studies can be done for this new type of Sudoku.

Drjsguo 5-4-2007
Drjsguo
 
Posts: 24
Joined: 23 October 2006

Postby coloin » Sat May 05, 2007 10:18 am

So in Plum sudoku there is no box constraint ?

Of interest

With an extra constraint you would think less clues are possible.
Minimum number of clues in Sudoku DG:
Courtesy of gsf !

Code: Select all
 .46.....3....71.....3....8.2.........9..4.............1.................5........
746982513825371964913465287271638495698547132354129678167854329489213756532796841
.59....6.......5......1.....4...............4....21...2.....7..............3.....
159873462372649518864215973647598321921736854538421697215984736493167285786352149

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Red Ed » Sat May 05, 2007 11:30 am

Isn't plum sudoku equivalent to ordinary sudoku?

Take any sudoku specified as 81 vectors of the form (b,s,r,c,d) where b = band nr, s = stack nr, r = row nr within the band, c = col nr within the stack and d = digit. If { (b,s,r,c,d) } specify an ordinary sudoku then { (r,c,b,s,d) } specify a plum sudoku, and vice-versa.

As a quick sanity-check, I have confirmed that there are the same number of 2x2 plum sudokus as 2x2 ordinary sudokus (namely, 288).

If I got the transformation right then this should be a 17-clue plum sudoku:
Code: Select all
..4|.5.|...
.3.|...|..6
8..|.4.|2..
---+---+---
...|3..|...
4..|7..|...
...|...|...
---+---+---
...|1.2|...
5.2|...|...
...|..1|.63
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Smythe Dakota » Sat May 05, 2007 3:29 pm

Certainly a plum sudoku is equivalent to an ordinary sudoku, in the manner you suggest. This may be even easier to see if the following transformation (of rows) is used:

r1 ---> r1
r2 ---> r4
r3 ---> r7
r4 ---> r2
r5 ---> r5
r6 ---> r8
r7 ---> r3
r8 ---> r6
r9 ---> r9

-- and similarly for columns.

Red Ed wrote:.... As a quick sanity-check, I have confirmed that there are the same number of 2x2 plum sudokus as 2x2 ordinary sudokus (namely, 288). ....

Obviously there are many more than 288 possible sudokus. Maybe you are referring to the number of equivalent sudokus -- puzzles obtainable from a given puzzle by interchanging rows within a band, interchanging columns within a stack, interchanging complete bands, interchanging complete stacks, flipping the puzzle across a main diagonal, applying a one-to-one mapping of the digit set {1,2,3,4,5,6,7,8,9} to itself, or any combination of these. I wouldn't doubt there are about 288 such transformations.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Red Ed » Sat May 05, 2007 3:46 pm

Smythe Dakota wrote:Obviously there are many more than 288 possible sudokus.
No. My sanity-check was for the 2x2 case ... 16 cells arranged into a 2x2 array of 2x2 boxes, filled with digits 1-4.

However, I agree that your way of describing the row/col permutations for the 3x3 case (which is equivalent to mine) might be easier for people to understand. Nicely put.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Smythe Dakota » Sun May 06, 2007 1:36 am

Oops. I didn't notice you said 2x2. My face is red.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Drjsguo » Sun May 06, 2007 3:22 pm

Thanks for all the replies.

The transformation method is brilliant. Standard Sudoku and Plum Sudoku are really equivalent after the transformation.
Drjsguo
 
Posts: 24
Joined: 23 October 2006

Postby Smythe Dakota » Mon May 07, 2007 2:56 am

Now what if we consider puzzles which are BOTH standard and plum? That is, all digits 1-9 appear exactly once in each row, column, box, and plum.

Then it should be possible to devise puzzles that require far fewer than 17 givens.

Also, the following transformations would then become possible, for generating equivalent puzzles:

A. Boxes become plums, and vice versa. (We've already seen how to do this.)

B. Rows become columns, and vice versa. (This is easy, and works with vanilla puzzles too.)

C. Rows become boxes, columns become plums, and vice versa to both.

D. Rows become plums, columns become boxes, and vice versa to both.

The last two are new, and are made possible because the relationship between rows and columns is the same as that between boxes and plums. That is, each row intersects each column in exactly one cell, and each box intersects each plum in exactly one cell.

On the other hand, each row intersects each box in either 3 or 0 cells. Similarly for columns and boxes, rows and plums, and columns and plums. Therefore, for example, rows cannot be interchanged with boxes, unless columns are also interchanged with plums, etc.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Drjsguo » Mon May 07, 2007 2:21 pm

Your idea is great. Two new kinds of Sudokus have born. I would like to name them 川 (pronounced Chuan, River) and 三 (pronounced San, Three) due to the shape of these two new rules.

After a Row to Plum transformation, the Column automatically transforms to Block. Meanwhile the old Block transforms to Chuan (川) as shown below:

x . . x . . x . .
x . . x . . x . .
x . . x . . x . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Where x contains all digits from 1 to 9, each appears only once. They form a new group or a new rule among themselves.

Similarly, a process of Column transform to Plum generates a San (三) shaped new Sudoku.

x x x . . . . . .
. . . . . . . . .
. . . . . . . . .
x x x . . . . . .
. . . . . . . . .
. . . . . . . . .
x x x . . . . . .
. . . . . . . . .
. . . . . . . . .

Drjsguo 5-7-2007
Drjsguo
 
Posts: 24
Joined: 23 October 2006

Postby RW » Mon May 07, 2007 3:25 pm

Smythe Dakota wrote:Now what if we consider puzzles which are BOTH standard and plum?

Then you get the standard disjoint group sudoku. Coloin already gave you a link to the thread that discusses minimum number of clues in sudoku DG and a couple of 12-clue puzzles by gsf.

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

Postby udosuk » Mon May 07, 2007 3:47 pm

Drjsguo wrote:Your idea is great. Two new kinds of Sudokus have born. I would like to name them 川 (pronounced Chuan, River) and 三 (pronounced San, Three) due to the shape of these two new rules...

Of course, all these concepts (including the Sudoku-DG) have been discussed for numerous times at least since 1-2 years ago.

Here is a Sudopedia article about Sudoku-DG:
http://www.sudopedia.org/wiki/Sudoku-DG

Here is another page where a random Sudoku-DG puzzle will be generated for you to solve:
http://www.menneske.no/sudoku/dg/3/eng/

On the Chuan/San puzzles, back in Oct 2005 dukuso already studied these concepts in the following thread:
http://forum.enjoysudoku.com/viewtopic.php?t=30

... where you can find the following link in the bottom post:
http://magictour.free.fr/sudoku6

... where you can find 100 such puzzles, many of them having as few as 8 clues (the minimum you can have on 9 unrelated symbols).

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Drjsguo » Mon May 07, 2007 5:34 pm

The San and Chuan Sudokus I posted earlier are not having more than three restrictions. They each have only three rules. E.g. San Sudoku: each block, Plum positions, and San (三) shaped three-line groups are limited to have nine different digits. There is no row or column restriction for San Sudoku at all. Here is an example:

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

Row and column constraints are no longer required here. Same is for Chuan Sudoku. I do not think they are not new types of Sudoku. I also believe 17 could be the lowest given to solve them logically.

BTW, it seems that Row and Column are also transformable to San (三) and Chuan (川). For example, if Row transformed into San, the Column would be transformed to Chuan. Meanwhile the Blocks (Boxes) remain the same but move to different locations. With constraints included only San, Chuan, Block and nothing else, it is also another new type of Sudoku.

Drjsguo 5-7-2007
Drjsguo
 
Posts: 24
Joined: 23 October 2006

Postby udosuk » Mon May 07, 2007 6:58 pm

Drjsguo wrote:The San and Chuan Sudokus I posted earlier are not having more than three restrictions. They each have only three rules. E.g. San Sudoku: each block, Plum positions, and San (三) shaped three-line groups are limited to have nine different digits. There is no row or column restriction for San Sudoku at all. Here is an example:

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

Row and column constraints are no longer required here.

I think what you describe here is just another representation of our plain Vanilla Sudoku. Try to transform boxes 1,2,3,4,5,6,7,8,9 to rows 1,4,7,2,5,8,3,6,9. Your example then becomes this grid:
Code: Select all
4 5 7 6 1 8 9 3 2
6 9 8 2 5 3 7 4 1
1 2 3 7 4 9 5 6 8
3 4 9 5 7 1 8 2 6
5 8 1 9 2 6 3 7 4
7 6 2 3 8 4 1 5 9
9 3 4 8 6 5 2 1 7
2 1 5 4 9 7 6 8 3
8 7 6 1 3 2 4 9 5

Which is just a simple Vanilla Sudoku grid.

Drjsguo wrote:Same is for Chuan Sudoku. I do not think they are not new types of Sudoku. I also believe 17 could be the lowest given to solve them logically.

Similarly, the "Chuan Sudoku" is just another representation of a normal Vanilla Sudoku grid if you do the transformation boxes 1,2,3,4,5,6,7,8,9 to columns 1,2,3,4,5,6,7,8,9. Also, if you simply transpose the grid a "Chuan Sudoku" is essentially the same as a "San Sudoku". That's why 17 is the (conjectured) minimum number of givens to these puzzles. They're essentially the same as Vanilla Sudoku puzzles.

Drjsguo wrote:BTW, it seems that Row and Column are also transformable to San (三) and Chuan (川). For example, if Row transformed into San, the Column would be transformed to Chuan. Meanwhile the Blocks (Boxes) remain the same but move to different locations. With constraints included only San, Chuan, Block and nothing else, it is also another new type of Sudoku.

This transformation is essentially boxes 1,2,3,4,5,6,7,8,9 to boxes 1,4,7,2,5,8,3,6,9. Again I wouldn't call it "a new type of Sudoku", but just "a different representation of an existing Vanilla Sudoku grid".
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Smythe Dakota » Tue May 08, 2007 1:28 am

Anyway, getting back to the concept of a box-plus-plum Sudoku (where you have row, column, box, and plum restraints) --

How many essentially different (non-isomorphic) such puzzles are there? Obviously, far fewer than vanilla sudokus, for two reasons:

1. There are far fewer valid sudoku grids, and

2. There are more isomorphisms!

For example, the box-to-plum transformation would not be an isomorphism in the world of vanilla sudokus.

I hope there is at least one valid box-plus-plum puzzle! But of course there is:

Code: Select all
1  2  3     4  5  6     7  8  9
4  5  6     7  8  9     1  2  3
7  8  9     1  2  3     4  5  6

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

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

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Smythe Dakota » Tue May 08, 2007 2:56 am

Now, can we go even further, and not only interchange rows, columns, boxes, and plums, but also digits?

To get a glimpse, let's take a step backwards, and remove both plums and boxes. This leaves us with a 9x9 latin square, otherwise thought of as a vanilla sudoko without boxes. The only constraints are that every row and every column contains every digit 1 to 9.

A 9x9 latin square can be viewed in another way, as well -- as a subset L of the set T of all ordered triples (x,y,z) where x,y,z are all in the range 1 through 9. To translate the standard view of a latin square to this ordered-triple view, just consider the triple (x,y,z) to be in L if and only if, in the traditional view, the cell at row x, column y contains the digit z.

Viewed this way, the set L consists of at most 81 elements -- 81 exactly if the grid is complete (i.e. the puzzle has been solved), fewer than 81 if there are still blank cells (the puzzle has not yet been filled in completely).

The only constraints on (x,y,z) are:

A. No two distinct elements of L can have the same first and second coordinates. (This translates to: No cell can contain more than one digit.)

B. No two distinct elements of L can have the same first and third coordinates. (Translation: No digit can appear twice in the same row.)

C. No two distinct elements of L can have the same second and third coordinates. (Translation: No digit can appear twice in the same column.)

Viewed this way, there is an obvious 3-way symmetry among rows, columns, and digits.

For example, rows and digits can be interchanged, to produce an equivalent latin square grid. In grid A, the digit z appears in row x, column y if and only if, in grid B, the digit x appears in row z, column y.

Likewise, columns and digits can be interchanged. And, of course, rows and columns can be interchanged. There can also be three-way interchanges, e.g. where rows become columns, columns become digits, and digits become rows. In a three-way interchange, in grid A, the digit z appears in row x, column y if and only if, in grid B, the digit x appears appears in row y, column z.

Now, can this idea somehow be used when box and/or plum restraints are added? Stay tuned.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Next

Return to Sudoku variants