FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    How to generate specific patterns          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 Posted: Fri Dec 29, 2006 3:27 pm    Post subject: How to generate specific patterns 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 kiwy Joined: 30 Mar 2007 Posts: 12 : Items Posted: Sun Apr 01, 2007 1:24 pm    Post subject: 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 north55 Joined: 02 Dec 2006 Posts: 43 : Items Posted: Mon Apr 02, 2007 4:17 pm    Post subject: Re: How to generate specific patterns 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 coloin Joined: 05 May 2005 Posts: 97 : Items Posted: Tue Apr 17, 2007 10:06 pm    Post subject: 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 Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Sun Apr 29, 2007 7:47 am    Post subject: 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron