Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

How to generate specific patterns

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
MCondron

Joined: 17 Jul 2006
Posts: 35
:
Location: Houston, TX

Items
PostPosted: Fri Dec 29, 2006 3:27 pm    Post subject: How to generate specific patterns Reply with quote

I've been working on a small solver program for a while and have had a heck of a time finding examples of puzzles requiring more advanced methods to solve for debugging it (e.g. franken swordfish is my latest addition). So this launched me into a new project -- creating puzzles with specific patterns.

I have seen mention made here and there of "template" generators, which seems to mean something that can generate puzzles with givens at specific locations; is this right?

Has any work been done on generating puzzles which match a template of a particular solution method, rather than a set of locations of givens? Certainly I can generate lots of random puzzles and filter out those few that have, say, a sashimi jellyfish or franken swordfish or whatever I'm looking for, but that is extremely inefficient since many of these creatures are so rare.

I have made some progress on this idea and posted an example elsewhere, but before I work too much harder on this, I want to make sure I'm not reinventing the wheel and rolling it over well-trodden ground.

What I'm currently doing is reading in a (hand-crafted) template file and using it to build lists of what givens can be placed in each cell in order not to violate the desired template structure. Then I randomly fill each vacant cell until the puzzle has a unique solution (tested by DLX) (tossing out of course any attempt to fill a cell that produces an invalid puzzle). Once I have a set of givens with a unique solution, I test to make sure that the solution method I'm looking for is still there and not wiped out by some other simpler technique that may have fallen out of the filled in cells, and that it can be solved without having to resort to DLX.

Here's an example of the template file I'm using:
Code:
1 . . | . / . | / / .
. . . | . X . | X X .
. . . | . 3 . | 6 7 .
---------------------
. . . | . 4 . | X X .
. . . | . 5 . | X X .
. . . | . 6 . | X X .
---------------------
. . . | . 7 . | 2 8 .
. . . | . X . | X X .
. 1 . | . / . | / / .

This was generated by hand to guide the generator on producing franken swordfishes. A numerical digit represents a fixed given clue. An X represents part of the root of the technique I'm trying to create (by default, this will always use 1's in the pattern). The '/' cells are the rest of the root ("base"). To generate the puzzle, I block any cell that can see an X from having a 1. I've also manually guaranteed that none of the '/' cells can have a 1 by stragegically placing explicit digits.

Here are a few examples of what I produced using this template:
Code:
....6..5.............3.67...784...3....59...9...6......4.7.28.7.9.......123..4..
1..9....2........5..5.3.67..7..4...6.9.35........68....3..7.28.7.4......51....3..
14.....3.2..6.9..4....3.67..9..4...772.85........6....4...7.28...........15......
1.5....92.....4...8...3.67.5...4.....2.95...8....6.....53.7.28.7....6..3.1.......
1.7...3...9.........5.3.67.2..94.....7.35........68..5....7.28...8.....651.6.4...
1.....4...9........8..3.67....74...93...5....7...62...9...7428.........561.8..3..
1...2.3959....6..2....3.67.7...48....6..52.......6...7.9..7.28..3......421..9...3
1.79......3......88...3467.5...4....96..52..3.4.86...9.59.7.28.........621.6...5.
1................4.4..3.67.....4...8..8.5....25.96....5..67.28......5..3.16.9....
1.....5.9.26.......5.43.67.5.734........5.....8.267...3...7.28.6.8.......1.5..4..

A run of a few hours generated 2600 puzzles which demonstrate a franken swordfish, of which 90 do not require "more advanced" methods to solve (meaning just other smaller fish, no large chains or coloring or stuff like that).

So, two basic questions:
1. Is this something new? If so I will pursue it further.
2. Does anyone see a way to recast this problem as an exact cover problem? I spent a couple of days thinking about this and decided it cannot be, but I may very well be wrong.

Mike
Back to top
View user's profile Send private message
kiwy

Joined: 30 Mar 2007
Posts: 12
:

Items
PostPosted: Sun Apr 01, 2007 1:24 pm    Post subject: Reply with quote

I find some puzzles
Code:

172...9..6..4....2....3.67...5.42....4..53......76......6.7428..3...8....18...5.7
16....9..........45.2.3.67..3..42...6.7.5.....2..6...3..9.7428..4...8....1..9.5..
1....53.95........8.413.67..2..41.......5........67..4.49.7.28....8....7.1...3...
16..8.94.3.8..4......13.67...394...5.9..51......76...96...7.28...........1..2.79.


is those fit your asked?
Back to top
View user's profile Send private message
north55

Joined: 02 Dec 2006
Posts: 43
:

Items
PostPosted: Mon Apr 02, 2007 4:17 pm    Post subject: Re: How to generate specific patterns Reply with quote

MCondron wrote:


Has any work been done on generating puzzles which match a template of a particular solution method, rather than a set of locations of givens? Certainly Mike


I haven't seen any other succesfull attempt at generating a specific pattern that doesn't involve generating nearly at random and filtering the results.

The closest I have seen was Ocean's observation that "the braid" creates more Swordfish than does most patterns.

Interesting, what you have done!
Back to top
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Tue Apr 17, 2007 10:06 pm    Post subject: Reply with quote

Three points which may interest you

JPF seems to be the leader in this ! see here

2.
RW Has given an excellent demonstration of how/why we are able to generate hard puzzles here

We are getting a 16 clue template eg
Code:
*-----------*
 |1..|.2.|..3|
 |.4.|...|.5.|
 |..6|...|7..|
 |---+---+---|
 |...|???|...|
 |7..|???|..9|
 |...|???|...|
 |---+---+---|
 |..1|...|4..|
 |.5.|...|.6.|
 |3..|.1.|..2|
 *-----------*
.........

We find the all the ways the puzzle is solved with a complete box 5 and then we remove as many clues as possible from box 5 !

By picking a 16 clue template it appears we can get puzzles which are without particular solving techniques.


3
MCondron wrote:
Does anyone see a way to recast this problem as an exact cover problem?


YES - Setting a sudoku puzzle from a valid grid is an exact cover problem !

Outline
Large number of "unavoidable" sets
Each set has to be covered by one clue [tricky]
Each clue needs to uniquely cover at least one set [not usually a problem][minimal]

see Unique Solution

But can we use this to set hard puzzles ?........maybe

Regards
C
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Sun Apr 29, 2007 7:47 am    Post subject: Reply with quote

coloin wrote:

MCondron wrote:
Does anyone see a way to recast this problem as an exact cover problem?

YES - Setting a sudoku puzzle from a valid grid is an exact cover problem !

Outline
Large number of "unavoidable" sets
Each set has to be covered by one clue [tricky]
Each clue needs to uniquely cover at least one set [not usually a problem][minimal]

see Unique Solution

perhaps i misunderstood something,
but it seems to me that MCondron's template (with "X" and "/") is something rather more complex --
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron