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   

Sudoku generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Mon Apr 14, 2008 10:27 am    Post subject: Sudoku generator Reply with quote

[EDIT]Latest version available - October 6th 2008[END EDIT]
For anyone interested, i've been updating my pattern based sudoku generator recently and is now downloadable, just click here. Visual Basic source code is available too.
Since there's no Help file, i will provide some information here...

This is the interface:



How to generate sudokus:
-Choose a base pattern (using "Next" or "Previous" buttons, or create a new one by toggling the cells on/off with the mousecursor. The red cells are those where the givens are to be generated.
-Choose the required modifications, there are only a few modifications possible. The first one, 'Random patterns' will force the generator to randomly choose a pattern (from those in the database) for each sudoku that is to be generated. The second option 'Limited to "Very Hard"' will limit the generated sudokus to the "Very Hard" level. With the third option you can make the generator try to expand the base pattern with 1, 2 or 3 extra givens which will only occur if the base pattern has multiple solutions making attempts to find a unique solution. By default, this option is set to "Don't expand, seek sequential". This default option will seek for the first unique sudoku from a maximum of 250 sequential attempts based on the first randomly generated givens. If no unique sudoku is found within 250 attempts, the givens are randomly regenerated, and so on. You have the ability to change the number of sequential attempts.
The last option is for checking the generated sudokus if they are minimal, this means that all clues are needed to have a unique solution. There's a similar option for testing sudokus on uniqueness.

The whole generator is based on my pseudo-dancing links brute force solver written in Visual Basic. See topic "DANCING LINKS and VISUAL BASIC"

The patterns have some restrictions...
-a minimum of 20 givens is required
-more than one empty row within the same band is not allowed
-more than one empty column in the same stack is not allowed
-more then four empty boxes are not allowed

About the randomly generated givens...
-the given cells are adressed in random order (by using a randomly re-ordered GivenMap-array)
-each given cell will recieve the available candidates in random order (by using a randomly re-ordered multiple CandidateMap-array)

About the levels...
1) Very Easy - Sudokus requiring only hidden singles
2) Easy - Sudokus also requiring naked singles
3) Medium - Sudokus also requiring box-line reductions and/or pointing pairs
4) Hard - Sudokus also requiring naked subsets
5) Very hard - Sudokus also requiring hidden subsets

Generated sudokus not answering to these levels are called "others".

Output files:
The following output file types are available:

1) MPQ Sudoku file type
Very Easy: Sudoku_Very_Easy.sds
Easy: Sudoku_Easy.sds
Medium: Sudoku_Medium.sds
Hard: Sudoku_Hard.sds
Very Hard: Sudoku_Very_Hard.sds
Others: Sudoku_Others.sds

Each file can hold multiple sudokus, format is built up this way:
There's no file-header, and each sudoku is saved in a 166 bytes long record. The first 81 bytes are reserved for the sudoku to be solved, and are saved in binary format. The following 81 bytes are holding the solution, also in binary format. The last 4 bytes of each sudoku record are reserved for keeping the best solving time for that sudoku, 2 bytes (in fact, an integer value) for the minutes, and another integer value for the seconds.
To import them with MPQ Sudoku, see the help file topic MPQ Sudoku – File Check and Import (only for advanced users)

2) Simple Sudoku file type
Very Easy: Very_Easy_0001.ss, Very_Easy_0002.ss, ...
Easy: Easy_0001.ss, Easy_0002.ss, ...
Medium: Medium_0001.ss, Medium_0002.ss, ...
Hard: Hard_0001.ss, Hard_0002.ss, ...
Very Hard: Very_Hard_0001.ss, Very_Hard_0002.ss, ...
Others: Others_0001.ss, Others_0002.ss, ...
Each file holds one sudoku, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
...|123|...
..1|...|4..
.5.|...|.6.
-----------
7..|..5|..3
8..|...|..9
2..|7..|..6
-----------
.3.|...|.5.
..7|...|2..
...|948|...


3) SudoCue file type
Very Easy: Very_Easy_0001.sdk, Very_Easy_0002.sdk, ...
Easy: Easy_0001.sdk, Easy_0002.sdk, ...
Medium: Medium_0001.sdk, Medium_0002.sdk, ...
Hard: Hard_0001.sdk, Hard_0002.sdk, ...
Very Hard: Very_Hard_0001.sdk, Very_Hard_0002.sdk, ...
Others: Others_0001.sdk, Others_0002.sdk, ...
Each file holds one sudoku, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
...123...
..1...4..
.5.....6.
7....5..3
8.......9
2..7....6
.3.....5.
..7...2..
...948...


4) Into Sudoku file type
Very Easy: Very_Easy_0001.sud, Very_Easy_0002.sud, ...
Easy: Easy_0001.sud, Easy_0002.sud, ...
Medium: Medium_0001.sud, Medium_0002.sud, ...
Hard: Hard_0001.sud, Hard_0002.sud, ...
Very Hard: Very_Hard_0001.sud, Very_Hard_0002.sud, ...
Others: Others_0001.sud, Others_0002.sud, ...
Each file holds one sudoku, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
000123000
001000400
050000060
700005003
800000009
200700006
030000050
007000200
000948000


5) Sudoku Explainer file type
Very Easy: Very_Easy_0001.txt, Very_Easy_0002.txt, ...
Easy: Easy_0001.txt, Easy_0002.txt, ...
Medium: Medium_0001.txt, Medium_0002.txt, ...
Hard: Hard_0001.txt, Hard_0002.txt, ...
Very Hard: Very_Hard_0001.txt, Very_Hard_0002.txt, ...
Others: Others_0001.txt, Others_0002.txt, ...
Each file holds one sudoku, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
...123...
..1...4..
.5.....6.
7....5..3
8.......9
2..7....6
.3.....5.
..7...2..
...948...


6) 81 character text string (.)
Very Easy: Sudoku_Very_Easy.txt
Easy: Sudoku_Easy.txt
Medium: Sudoku_Medium.txt
Hard: Sudoku_Hard.txt
Very Hard: Sudoku_Very_Hard.txt
Others: Sudoku_Others.txt
Each file holds multiple sudokus, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
...123.....1...4...5.....6.7....5..38.......92..7....6.3.....5...7...2.....948...


7) 81 character text string (0)
Very Easy: Sudoku_Very_Easy_0.txt
Easy: Sudoku_Easy_0.txt
Medium: Sudoku_Medium_0.txt
Hard: Sudoku_Hard_0.txt
Very Hard: Sudoku_Very_Hard_0.txt
Others: Sudoku_Others_0.txt
Each file holds multiple sudokus, format is built up this way:
There's no file-header, and each sudoku is saved in text-format like this example:
Code:
000123000001000400050000060700005003800000009200700006030000050007000200000948000


For each output filetype there will be a subfolder created in the application folder

Pattern files:
[EDIT May 11th 2008] Each base pattern is saved as a record within a file called Pattern.rec and this file is kept in the application folder. The old pattern filetypes are still distributed, but are converted to the new filetype the first time you will run the program along with your own or imported pattern files. The program will keep track of the generate peformance for each pattern[END EDIT]

A pattern browser is under the "Pick" button.
You can, under some restrictions, import patterns from the original MPQ Sudoku files as well with the "Import" button.

And last but not least, you can check sudokus for uniqueness (see explanation in the textbox at the interface)
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


Last edited by Lunatic on Tue Oct 07, 2008 5:05 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Sun May 11, 2008 7:10 am    Post subject: Reply with quote

May 11th 2008 - New update available - see above description
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Tue May 13, 2008 7:07 pm    Post subject: Reply with quote

I tried your generator and didn't mind it.

If you are still working on improving it I would suggest allowing a choice that cycles through the stored patterns and does one puzzle in each until stopped.

I print puzzles out and solve them and wouldn't much like them to all look the same. Smile

Next I'd add a few interesting methods, such as skyscraper, x-wing, xy wing and UR1.

Well done so far, it works and is quite capable at making newspaper type puzzles.
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu May 15, 2008 9:06 pm    Post subject: Reply with quote

wapati wrote:
If you are still working on improving it I would suggest allowing a choice that cycles through the stored patterns and does one puzzle in each until stopped.


It allready crossed my mind too, I don't like to solve sudokus with the same pattern again and again either. For now I have over 18000 different patterns available, so the next option "Random patterns" is on the drawing table...

And maybe a print function...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Oct 07, 2008 4:57 pm    Post subject: Reply with quote

wapati wrote:
If you are still working on improving it I would suggest allowing a choice that cycles through the stored patterns and does one puzzle in each until stopped.


Ok, it took a while but the option you requested is now (October 6th 2008) implemented. (see checkbox "Random patterns" in the "Generator Modifications" section.

Regards,
Marc.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
onthink

Joined: 29 Mar 2009
Posts: 6
:

Items
PostPosted: Sun Mar 29, 2009 12:39 pm    Post subject: Reply with quote

It do need talents.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software 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