C++ Sudoku Generator

ultimato33 · Posted: Thu Jan 21, 2010 5:56 pm Post subject: C++ Sudoku Generator

Hello Everyone
Making a sudoku generator+solver program on C++ was what I decided to make over the christmas holidays.But when I went onto the generating puzzles part of it , I got stuck. I could not find a way to make a error free Sudoku Generator.
I would be very grateful if i get some Help.
Expecting a favorable reply
With Regards

JasonLion · Posted: Thu Jan 21, 2010 7:14 pm Post subject:

There are several different ways to write a Sudoku puzzle generator. The two most common approaches are:

1) Add a few digits at random and then check to see if the puzzle can still be solved (one or more solutions). If there is more than one solution, try again adding more digits until you have only a single solution. If there are not any solutions then remove the digits you just added and try again. If there is exactly one solution then stop.

2) Build a completely filled in valid Sudoku grid. This can be done using a solver that makes a random choice each time it needs to guess. Then remove clues, checking that there is still only on solution after each set of removals. If there are several solutions, replace the digits just removed and try removing something else. Continue until there are an appropriate number of clues remaining.

Both approaches depend on having a fast brute force solver. Both approaches also create puzzles of random difficulty levels. Additional work is required to determine the difficulty level of the puzzle and decide if it is appropriate.

You can constrain the maximum difficulty level of the puzzle by replacing the brute force solver with a human techniques solver that only uses the techniques you are interested in. Depending on your goals, and the desired difficulty rating, this may be slower than using a brute force solver and determining difficulty afterwards.