Su-don't-ku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Su-don't-ku

Postby Smythe Dakota » Thu Jun 12, 2008 2:38 am

Here's an idea. Concoct a puzzle with the following rules:

Each row, column, and box contains 7 of the digits once each, 1 digit twice, and 1 digit no times. (For example there might be two 6's and no 4 in column 2.) Of course you aren't told which digits are double or missing from each row, column, or box. But there still must be a total of 9 of each digit in the entire puzzle.

Can anybody come up with one?

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

Postby tarek » Thu Jun 12, 2008 6:16 pm

deleted: must have been thinking of something else:(
Last edited by tarek on Thu Jun 12, 2008 5:51 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby coloin » Thu Jun 12, 2008 8:16 pm

Code: Select all
+---+---+---+
|972|834|956|
|369|815|478|
|458|679|712|
+---+---+---+
|665|781|293|
|921|346|784|
|783|492|551|
+---+---+---+
|893|123|645|
|534|962|127|
|216|547|831|
+---+---+---+


Does this grid comply ?

If it does - remove some clues !

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Smythe Dakota » Sat Jun 14, 2008 2:42 am

It probably does, but after checking the columns, my head hurt, so I didn't finish checking the rows, boxes, or overall totals.

Right now my gut feeling is that there would have to be an unacceptably large number of initial clues, to ensure a unique solution. So there should probably be an additional constraint:

Each digit must appear twice in exactly one row, and no times in exactly one row. Ditto for columns and boxes.

For example, having three columns with two 1's each, and three other columns with no 1's, would not be acceptable.

Or, by any chance, is this constraint somehow implied by the constraints already stated?

It's possible this additional constraint might reduce the necessary number of initial clues, and also might provide some interesting new solving techniques.

Bill Smythe
Last edited by Smythe Dakota on Tue Jun 17, 2008 7:24 am, edited 1 time in total.
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Postby niallpaterson » Sat Jun 14, 2008 3:55 am

I made this puzzle from the above grid using the simplest possible solver. No doubt it could be vastly improved upon. I think the original idea may be viable.

Code: Select all
+---+---+---+
|9 2|8  |9  |
|  9|815| 7 |
|458|  9|712|
+---+---+---+
|66 | 8 | 93|
|92 | 46|78 |
| 83| 92|551|
+---+---+---+
| 93| 23|  5|
|5 4|9 2|1 7|
| 1 | 47|831|
+---+---+---+
niallpaterson
 
Posts: 2
Joined: 14 July 2007

Postby HATMAN » Sat Jun 14, 2008 3:58 pm

Bill

There is some relation between this and 007 (001234567) and also OverKillers (0 to 9 with nine of one number and eight of each of the rest).
For OverKillers Mel-o-rama came up with a nice solution technique of extending the grid to 10 by 10 to include the missing numbers.

Both of these worked very well as killers but were not succesfull in vanilla format. I would suggest that the same applies with this one. It probably works even better with repeat killers.

I agree with your extra contraints as it brings us back to nine times 1 to 9 in a different layout.

I'll give it a go.

Maurice

PS By the way you should point this idea out to JC.
HATMAN
 
Posts: 310
Joined: 25 February 2006
Location: Saudi Arabia

Postby motris » Sat Jun 14, 2008 9:40 pm

I find this a very interesting discussion, more interesting because the "SuDON'TKu" name was used in a somewhat related context on today's US Puzzle Championship. In that puzzle, which should soon be posted on wpc.puzzles.com when the official test page is made public, you have an 8x8 grid where each row/column/box takes the digits 1-9 except that the digits 1 through 8 have each been dropped exactly once from a row/column/box.

Putting in that extra "a digit repeats only once per row/column/box and is only missing once per row/column/box" constaint should make a valid if very very difficult puzzle.
motris
 
Posts: 71
Joined: 13 March 2006

Postby Smythe Dakota » Mon Jun 16, 2008 10:42 am

Another possibly useful constraint:

For each digit, there must be exactly one cell in the grid where that digit appears twice in the row, twice in the column, and twice in the box containing that cell. (Additional possibility: the duplicate appearance in the box must not be in the same row or column as the original.)

Or, perhaps just the opposite of the above: If a digit is duplicated in a row, that occurrence of the digit cannot also be duplicated in a column or box (and similarly if "row", "column", and "box" are interchanged in any way).

Bill Smythe
Last edited by Smythe Dakota on Tue Jun 17, 2008 7:25 am, edited 1 time in total.
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Postby udosuk » Tue Jun 17, 2008 7:06 am

It's actually quite easy to convert a valid Sudontku solution grid from a valid Sudoku solution grid (and vice versa). We just need to choose 9 cells which don't share any row/column/box and then permute them to other values via a "mapping".

For example, coloin's grid:
972 834 956
369 815 478
458 679 712

665 781 293
921 346 784
783 492 551

893 123 645
534 962 127
216 547 831

We just need to figure out the "mapping of digits". In this case, the mapping and the original Sudoku grid is:
[123456789] -> [987645321]
(Sudoku grid -> Sudontku grid)
172 834 956
369 215 478
458 679 312

645 781 293
921 356 784
783 492 561

897 123 645
534 968 127
216 547 839

But I don't like this mapping because it's not symmetrical (6 digits map pairwise while 3 digits map in a 3-way cycle). I prefer to map all 9 digits in a 9-way cycle.

Say, we use the "most canonical grid" as the Sudoku grid. We can even choose which 9 cells to change in advance, in this case:
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

The "changing cells" are the cells which represent the box number, i.e. 1 in box 1, 2 in box 2, etc.

Now, different mappings can produce different effects. For example, with the following mapping:
[123456789] -> [456789123]
423 456 789
456 789 126
789 153 456

231 864 897
567 897 231
897 231 594

312 645 378
645 972 312
918 312 645

We'll have the duplication in each box overlap with the duplication on each column, while the duplication on each row are independent.

On the other hand, with the following mapping:
[123456789] -> [567891234]
523 456 789
456 789 127
789 163 456

231 964 897
568 897 231
897 231 514

312 645 478
645 973 312
928 312 645

You'll find the row/column/box duplication all independent to each other (although quite a few duplications are between adjacent cells).

In summary, a Sudontku grid is just a partial transformation of a certain part of a Sudoku grid. The mechanism isn't that interesting. But hopefully somebody can produce some interesting puzzles from this concept.:idea:


PS: Something tells me Bill's usage of the word restraint in place of the word constraint is wrong but I can't find any solid evidence. I don't think I can apply for a restraining order to restrain him from doing that.:(

Anyway, according to Maurice it's contraint and according to Thomas it's constaint, so I don't know which spelling is correct anymore.:(
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Smythe Dakota » Tue Jun 17, 2008 11:35 am

You're right, constraint sounds better than restraint. I've edited my two earlier posts accordingly.

I refuse, however, to use either contraint or constaint.:)

udosuk wrote:.... The mechanism isn't that interesting. ....

Hmm, maybe so. Phooey -- you may have debunked the whole idea.

udosuk wrote:.... But hopefully somebody can produce some interesting puzzles from this concept. ....

Or maybe not.

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

Postby udosuk » Tue Jun 17, 2008 7:17 pm

Well, according to Maurice the usage of the word "restrained" to describe a puzzle prototype with a very limited solution space should be credited to Ruud. But I'm not sure if it's relevant here.:)

I hope I haven't debunked the whole idea. Like Thomas said if the US Puzzle Championship adopted a similar concept it mustn't have been bad at all. I've just unveiled some of the mystery in creating such a solution grid. We won't know about the puzzles until a decent one is made.:?:

For example, I don't see how to work out the original Sudoku grid with just a handful of initial clues given. But then it's hard to make progress when you don't know which cells are the duplicated ones. Perhaps if we assign a different colour (e.g. red) to all initial givens which are designated as duplicated cells, or shade empty duplicated cells in pink to let the player fill in the duplicated value?:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby coloin » Wed Jun 18, 2008 3:10 pm

udosuk you figured out exactly how I made the grid !

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby udosuk » Thu Jun 19, 2008 1:51 pm

I'm not saying this has anything to do with the Sudontku idea, but the following puzzle has a unique solution:
Code: Select all
 1 . 8 | . . . | 1 . 5
 . 9 . | . 1 . | . 6 .
 2 . . | 5 . 2 | . . 3
-------+-------+-------
 . . 7 | . 3 . | 4 . .
 . 8 . | 2 . 6 | . 9 .
 . . 6 | . 9 . | 5 . .
-------+-------+-------
 6 . . | 8 . 7 | . . 2
 . 2 . | . 2 . | . 7 .
 5 . 4 | . . . | 3 . 4

Here is a minor hint for those who "don't have a clue":

Triple click to see the minor hint I wrote:The source of this puzzle is a Japanese website.

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


Return to Sudoku variants