Dynamic constraint project

For fans of Killer Sudoku, Samurai Sudoku and other variants

Dynamic constraint project

Postby evert » Sun Oct 19, 2008 1:58 pm

I’m working on a sudoku solver and generator that dynamically ‘reads’ the constraint groups (lines, boxes, diagonals etc) from somewhere else (user interface). So the user can click any nine cells and the program will take them as a constraint.

Has anybody else written something similar?

This is how far I got:
It’s working more or less.:D I’ve tested various sudoku variants. The UI needs some more work before the nine cells can be clicked.

Before solving or generating a puzzle, it calculates possibilities for interactions and conjugate eliminations. It also handles any naked and hidden subsets.
Speed is a little bit less then I hoped in advance.:(

Hopefully this can be used in order to explore Sudoku constraints and combinations.

Here’s a puzzle for a Sudoku constraint suggested by udosuk::D
Code: Select all
A..|...|...
.A.|...|...
..A|...|...
---+---+---
...|..A|...
...|.A.|...
...|A..|...
---+---+---
...|...|A..
...|...|.A.
...|...|..A

...|...|8..
9..|.4.|...
...|..9|2..
---+---+---
87.|.1.|...
...|...|.51
...|5..|62.
---+---+---
6..|...|...
...|2..|..4
...|.76|...


Here’s an Asterisk-X puzzle:
Code: Select all
...|...|...
...|.A.|...
..A|...|A..
---+---+---
...|...|...
.A.|.A.|.A.
...|...|...
---+---+---
..A|...|A..
...|.A.|...
...|...|...
+ two main diagonals:

...|..3|...
9..|...|...
2.7|...|...
---+---+---
.3.|...|...
...|...|..5
...|...|...
---+---+---
14.|.2.|...
..6|.5.|...
.8.|...|.9.
evert
 
Posts: 186
Joined: 26 August 2005

Re: Dynamic constraint project

Postby tarek » Mon Oct 20, 2008 11:41 am

evert wrote:Has anybody else written something similar?
JC for his JSudoku has done that .... Very good program too

My solver is not publicly available. I can easily modify these constraints though (As you & JC know).
evert wrote:Here’s a puzzle for a Sudoku constraint suggested by udosuk::D
Code: Select all
A..|...|...
.A.|...|...
..A|...|...
---+---+---
...|..A|...
...|.A.|...
...|A..|...
---+---+---
...|...|A..
...|...|.A.
...|...|..A

...|...|8..
9..|.4.|...
...|..9|2..
---+---+---
87.|.1.|...
...|...|.51
...|5..|62.
---+---+---
6..|...|...
...|2..|..4
...|.76|...
The smiley is a giveaway, udosuk actually UN-suggested it & he is no ZORRO fan either.

tarek
User avatar
tarek
 
Posts: 2607
Joined: 05 January 2006

Re: Dynamic constraint project

Postby evert » Mon Oct 20, 2008 1:34 pm

tarek wrote:JC for his JSudoku has done that .... Very good program too
I'll take a look into this!
tarek wrote:udosuk actually UN-suggested it & he is no ZORRO fan either.
OK I was aware just a little teasing
evert
 
Posts: 186
Joined: 26 August 2005

Re: Dynamic constraint project

Postby udosuk » Mon Oct 20, 2008 11:00 pm

tarek wrote:
evert wrote:Here’s a puzzle for a Sudoku constraint suggested by udosuk::D
Code: Select all
A..|...|...
.A.|...|...
..A|...|...
---+---+---
...|..A|...
...|.A.|...
...|A..|...
---+---+---
...|...|A..
...|...|.A.
...|...|..A

...|...|8..
9..|.4.|...
...|..9|2..
---+---+---
87.|.1.|...
...|...|.51
...|5..|62.
---+---+---
6..|...|...
...|2..|..4
...|.76|...
The smiley is a giveaway, udosuk actually UN-suggested it & he is no ZORRO fan either.

I UN-suggested it because if you swap r46 or swap c46 you'll get a simple "\-puzzle" (i.e. X-puzzle without the non-leading diagonal). So it is nothing interesting at all.

Similarly, tarek's "Zorro" is simply an isomorph of the "leading diamond" variant with a simple r46 swap.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby evert » Sun Oct 26, 2008 9:12 am

I am trying the following variant.

We have the classical rows, columns and boxes and further we have 4 groups:
Code: Select all
A . .|. . .|. . A
. A .|. . .|. A .
. . .|A . A|. . .
-----|-----|-----
. . .|. A .|. . .
. . A|. . .|A . .
. . .|. . .|. . .
-----|-----|-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

and similarly rotated:

. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----|-----|-----
. . .|. . .|. . .
. . B|. . .|B . .
. . .|. B .|. . .
-----|-----|-----
. . .|B . B|. . .
. B .|. . .|. B .
B . .|. . .|. . B

C . .|. . .|. . .
. C .|. . .|. . .
. . .|. C .|. . .
-----|-----|-----
. . C|. . .|. . .
. . .|C . .|. . .
. . C|. . .|. . .
-----|-----|-----
. . .|. C .|. . .
. C .|. . .|. . .
C . .|. . .|. . .

. . .|. . .|. . D
. . .|. . .|. D .
. . .|. D .|. . .
-----|-----|-----
. . .|. . .|D . .
. . .|. . D|. . .
. . .|. . .|D . .
-----|-----|-----
. . .|. D .|. . .
. . .|. . .|. D .
. . .|. . .|. . D
(Whineglass sudoku?)

Surprisingly, it is very easy to find a 9-clue puzzle.

For example:
Code: Select all
. . .|. . .|. . .
. 5 1|. . 2|. . .
. . .|. . .|. . 4
-----|-----|-----
. . .|. . .|. 8 9
. . .|. . .|. . .
. . .|. . .|. . .
-----|-----|-----
. . .|. . .|7 . .
. 6 .|. . .|. . .
. . .|. . 4|. . .
However the search for an 8 clue is now running for several hours.

It surprises me that a 9 clue is found so easely (below 10 seconds) and 8 clues is so hard to find.
Also it surprises me that so few clues are needed after only adding 4 additional constraint groups.

I'm aware that 8 clues is the theoretical minimum.
evert
 
Posts: 186
Joined: 26 August 2005

Postby udosuk » Mon Oct 27, 2008 7:34 am

Quite an interesting variant. Each of the 4 extra groups contains an exclusive V-shaped triplet of cells, and shares exactly 2 cells with each of the other 3 groups. "Wineglass Sudoku" sounds okay (for me).

Your example puzzle can be solved with singles/subsets/intersections/cell-pointing. No fish/chain required at all, which is pretty nice.:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby coloin » Thu Oct 30, 2008 7:27 am

Code: Select all
Surprisingly, it is very easy to find a 9-clue puzzle.


Perhaps the reason is there arnt very many essentially different grids [x9!] with the property. I dont think there will be many of the 6^8 *2 vanilla isomorphs either. [? 8 * 2]

How many non-isomorphic ways are there to complete clues in the [*] cells ?

Code: Select all
* . .|. . .|. . *
. * .|. . .|. * .
. . .|* * *|. . .
-----|-----|-----
. . *|. * .|* . .
. . *|* . *|* . .
. . *|. * .|* . .
-----|-----|-----
. . .|* * *|. . .
. * .|. . .|. * .
* . .|. . .|. . *



In Stormdoku we had a few 8-puzzles but there were only 3 essentially different grids. [2/3 were significantly automorphic]

C
coloin
 
Posts: 1629
Joined: 05 May 2005


Return to Sudoku variants