Su Doku random puzzle generator.

ID:265640
 
Oct 4 2006, 9:49 am
This is giving me a headache! Basically, I'm generating these puzzles by picking a number and going through each 3x3 section, sticking the number into a random position into the 3x3 section of the puzzle and doing the following checks on it:
- Checking if a number is already there (of course!)
- Looking at the row for the same number
- Looking at the column for the same number.

It goes through each number this way. The problem lies in that when the final section of puzzle is reached, the number only has on available position, and if there is already number there... bam! Infinite loop. Any ideas on how to fix this?
Oct 4 2006, 10:35 am
for one method, I suggest making a list holding onto the numbers 1 to 9, and making it subtract all the numbers used within the same box and lines... may get kinda messy but ensures that all numbers will be unique per box and line, which is the Su-doku way! >_>

- GhostAnime
Oct 4 2006, 11:04 am
I am actually making a library/demo for sudoku puzzle generation... I started almost an hour ago... I am almost done... just trying to track down bugs that might exist...

§atans§pawn
Oct 4 2006, 11:22 am
To implement a sudoku puzzle generator, you need to use a backtracking solver, something similar to dancing links but without the use of pointers. (There's an array-based method of solving sudoku somewhere that will serve.) I generate them like so:

  • Add a predetermined number of clues that don't appear to conflict, like 18 of them.
  • Run through the solver. If there are no solutions, keep removing clues until there are 1 or more.
  • As long as there are multiple solutions, keep adding clues at random from one of the available solution grids and re-solving.
  • Once there is only one solution, test each clue at random and try to remove one without causing the puzzle to become invalid. If you can remove one, do so and repeat the loop again.

    This can be implemented in BYOND. What I found incredibly difficult was getting a human-style solver implemented in DM to tell you how hard the puzzle is. I eventually abandoned that idea.

    In any case, puzzle generation in BYOND is going to be slow.

    Lummox JR
Oct 4 2006, 11:29 am
In response to Lummox JR
I never thought about that aspect. I am only making something that will generate where the numbers will go. At least, that's all it will be at the moment.

§atans§pawn
Oct 4 2006, 1:11 pm (Edited on Oct 4 2006, 2:27 pm)
In response to Lummox JR
Luckily, I'm doing this in python. This just happened to be the only community I visit where I knew I would get an intelligent response.

I'll definitely try your method. Seeing as how it runs through the solver multiple times, I'll need to optimize my solver algorithm(I sort of got lazy on it).

Thanks for the advice.
Oct 4 2006, 2:22 pm
In response to GhostAnime
Actually, I do just that (well, a variation of it). What happens is you get a to a number in the last 3x3 block, and it only has one position avaiable because every other row and column have been used up for the other sections, and that row or column might already have the number in it.

The method you suggested seems logical, however, after testing numerous times, I noticed that my algorithm got stuck on the last 3x3 section everytime it got stuck. So there could be only one possibility -- The only remaining position left was invalid.
Oct 5 2006, 8:10 am
In response to Prodigal Squirrel
Prodigal Squirrel wrote:
Luckily, I'm doing this in python. This just happened to be the only community I visit where I knew I would get an intelligent response.

I'll definitely try your method. Seeing as how it runs through the solver multiple times, I'll need to optimize my solver algorithm(I sort of got lazy on it).

Thanks for the advice.

The first code I ever found for a sudoku generator was in python, so that might work for you.

You may also want to try the sudoku programmers' forum at setbb.com.

Lummox JR