The most elegant Sudoku variant puzzle

For fans of Killer Sudoku, Samurai Sudoku and other variants

The most elegant Sudoku variant puzzle

Postby udosuk » Mon Sep 22, 2008 8:58 am

I've been thinking, what factors constitute the most elegant Sudoku variant puzzle?

As far as I know there are 2 basic "flavours" for a standard (vanilla) Sudoku puzzle:

1. Symmetry: the pattern of given clues are rotationally or reflectionally symmetrical.

2. Minimality: no given clue is redundant (i.e. if any given clue is removed the puzzle no longer has a unique solution).

Also, certain people like to have the puzzle stays "purely logical", i.e. no arithmetical ingredient is allowed. In particular, the digit symbols (1-9) can be replaced by any other set of 9 incomparable symbols. Thus consecutive/non-consecutive, greater-than/less-than, odd/even, magic squares or killer cages shouldn't be used.

And, most importantly, the additional variant constraint(s) should be as simple and short as possible. Nothing is more inattractive than a puzzle with 7 or 8 complex rules which take several minutes to read, let alone to understand.

For example, here is an example of such a simple constraint:

Code: Select all
Big square

. . . . . . . . .
. . . . . . . . .
. . x x x x x . .
. . x . . . x . .
. . x . o . x . .
. . x . . . x . .
. . x x x x x . .
. . . . . . . . .
. . . . . . . . .

All the x cells can't have the same value as the o cell

(Hint: in JSudoku, this constraint can be implemented by putting Anti-kNight and Anti-Elephant together.)

So if all 81 cells have this constraint (ignoring out of bound cells), the following puzzle has a unique solution:

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

Note this puzzle is perfectly symmetrical (90 degree rotational). Also it is obviously minimal because it has only 8 clues. (For any puzzle using 9 incomparable symbols 8 is the absolute minimum number of clues.)

It is also diagonal (Sudoku X) and have 9 disjoint groups (e.g. r147c147) but you don't need these constraints to achieve a unique solution. (However using both will probably make the puzzle more human solvable.:idea: )

This is the only simple constraint I found working for this clue pattern. However there are at least 2 other constraints which, combined with a couple of more well known constraints, give a unique solution.

The first one is this:

Code: Select all
Big cross

. . . . . . . . .
. . . . . . . . .
. . x . . . x . .
. . . x . x . . .
. . . . o . . . .
. . . x . x . . .
. . x . . . x . .
. . . . . . . . .
. . . . . . . . .

All the x cells can't have the same value as the o cell

(Hint: in JSudoku, this constraint can be implemented by putting Anti-King and Anti-Elephant together.)

Combined with DG (Disjoing Group) and Windoku, the clue pattern above yields a unique solution. (Note the puzzle is also diagonal but it is not a necessary constraint.)

The second one is this:

Code: Select all
Anti-Ostrich
(Ostrich = (1,5) leaper)

. . . . . . . . .
. . . . . . . x .
. . o . . . . . .
. . . . . . . x .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. x . x . . . . .
. . . . . . . . .

All the x cells can't have the same value as the o cell

Again, combined with DG (Disjoing Group) and Windoku, the clue pattern above yields a unique solution. (And again the puzzle is also diagonal but it is not a necessary constraint.)

But most important is the "Big Square" 8-clue puzzle above. I will see if anyone can find such a puzzle with a simpler constraint.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Wed Dec 17, 2008 10:58 am

Didn't think it over completely, but this something with just 0s and 1s might be elegant.
Code: Select all
11111
10000
01001
00100
00011

What if the constraint is the following:
No 5-number-pattern may occur more than once in the total grid.
Two 5-number-patterns are the same if they are
-literally the same, or
-the same after mirroring, for example 11100 and 00111
The above grid is invalid since 10000 occurs both in row 2 and c5.
Does any valid grid exist?
Could we include the main diagonals / and \ in the constraint?
Could we create puzzles by starting with a valid grid and leaving out clues?
evert
 
Posts: 187
Joined: 26 August 2005

Postby udosuk » Wed Dec 17, 2008 3:41 pm

evert wrote:
Code: Select all
11111
10000
01001
00100
00011

The above grid is invalid since 10000 occurs both in row 2 and c5.

But c5 is 10101.

On the other hand, c1 is 11000 & r5 is 00011. Also r3 is 01001 & c3 is 10010.

A quick analysis:

There are 32 different strings of 5 bits, with 8 of them self-mirroring, which makes a total of 20 essentially different strings:

Code: Select all
00000,00100,01010,01110
11111,11011,10101,10001
00001,00011,00101,01001,00010,00110
11110,11100,11010,10110,11101,11001

Even if you include both diagonals, there are only 5+5+2=12 lines, so I'll be very surprised if there is no valid solution.

On the other hand, if you include the broken diagonals, there are exactly 20 lines, so it will be very elegant if all these 20 lines can be essentially different 5-bit strings.:)

(It will also be very elegant if the 12 non-self-mirroring strings can form the 5 rows, 5 columns, 2 diagonals.:idea: )
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Thu Dec 18, 2008 4:01 am

More thoughts:

Representing each 5-bit string with a number, we can have the following scheme:

Self-mirroring numbers (8):
00,04,10,14,17,21,27,31

Non-self-mirroring numbers (12):
01,02,03,05,06,07,09,11,13,15,19,23
16,08,24,20,12,28,18,26,22,30,25,29

The top row contains the smaller member of a mirroring-pair.

Or, more instinctively, we can generate 20 numbers of essentially different strings this way:

First five: 00,04,06,08,10 (first six even numbers dropping 02)
Next five: 24,20,18,16,14 (the five above subtracted from 24)
Next ten: 31,27,25,23,21,07,11,13,15,17 (the 10 above subtracted from 31, i.e. complement)

I'm about to write a program to work it out, but here is one constructed manually:

Code: Select all
00110
00010
00111
01010
11110

Only 5 rows and 5 columns essentially different (diagonals are copying r1 & r5), and the self-mirroring strings are used. Surely this can be improved.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Fishes

Postby HATMAN » Sat Dec 27, 2008 5:21 am

Another symmetrical layout with fishes added to the pyramids, with the X this is minimal and using symmetry it is human solvable (well JSudoku solvable).

Image
HATMAN
 
Posts: 310
Joined: 25 February 2006
Location: Saudi Arabia

Postby udosuk » Sun Dec 28, 2008 1:43 am

Excellent puzzle Maurice!:D

Here is a PS code for the puzzle:

Triple click below to select the code I wrote:3x3:d:k:17:11273:11273:11273:11273:11273:11018:18:19:20:10508:11273:257:11273:11018:11018:11018:10763:10508:10508:10508:11273:11018:514:11018:10763:10763:9742:10508:1028:10508:11018:11018:10763:771:10763:9742:9742:10508:10508:21:9997:9997:10763:10763:9742:1798:9742:9487:9487:9997:1541:9997:10763:9742:9742:9487:2055:9487:9232:9997:9997:9997:9742:9487:9487:9487:9232:2312:9232:9997:22:23:24:9487:9232:9232:9232:9232:9232:25:

Or if you prefer, you can use the following code and enter the 8 given clues manually:

Triple click below to select the code I wrote:3x3:d:k:9:11521:11521:11521:11521:11521:11522:10:11:12:11523:11521:11521:11521:11522:11522:11522:11524:11523:11523:11523:11521:11522:11522:11522:11524:11524:11525:11523:11523:11523:11522:11522:11524:11524:11524:11525:11525:11523:11523:13:11526:11526:11524:11524:11525:11525:11525:11527:11527:11526:11526:11526:11524:11525:11525:11527:11527:11527:11528:11526:11526:11526:11525:11527:11527:11527:11528:11528:11528:11526:14:15:16:11527:11528:11528:11528:11528:11528:17:

Very interestingly, with the 1st code my version of JSudoku need a handful of chains to crack it, while with the 2nd one it doesn't use chains but applies a truckload of grouped turbot fishes (45+).:!:

And finally, for the courageous souls who'd like to tackle this one manually, here is the solution grid for you to check if you're on the right track:

Triple click below to read the solution I wrote:642975318
738164592
159382746
584216937
926753481
371498625
463827159
815649273
297531864
udosuk
 
Posts: 2698
Joined: 17 July 2005


Return to Sudoku variants