Thursday, March 24, 2011

How to write a sudoku generator ?

The idea is to start with an empty grid. Then repeatedly fill a random digit to a random cell, until a valid puzzle is produced. A puzzle is valid if it has a unique solution. The number of solution can be found using a modified version of SudokuSolver.java described in the previous article.


To compile :

javac SudokuGenerator.java

To run, you must supply an integer seed :
java SudokuGenerator 0

The file out.txt will be generated :

Puzzle in plain text format :
.....2...
1.6....39
....6.5.1
....9....
.........
..9.2....
.9...4...
.....5...
...6.8...

Puzzle in Java String format :
    String puzzle = ".....2..."+
                    "1.6....39"+
                    "....6.5.1"+
                    "....9...."+
                    "........."+
                    "..9.2...."+
                    ".9...4..."+
                    ".....5..."+
                    "...6.8...";

Supplying a different seed will generate a different puzzle.

Full source can be found here : SudokuGenerator.java


Thanks for reading. Comments are welcome.

Patching


A reader's comment pointed out that there are two issues.
The fix is now available at :
Sudoku Generator - A Bug Fixing Patch
Posted by Ivan Macteki at 1:31 AM
Labels:

9 comments:

  1. Renan HJune 22, 2013 at 7:56 PM

    I still do not understand, how to link the generator with the solver (from the previous article). I want to generate a puzzle, and show it, with the solution by elimination and the solution recursive. how can i do it. sorry for the ignorance.

    ReplyDelete
  2. Ivan MactekiJune 23, 2013 at 12:02 AM

    1. The solver is independent on the generator.
    2. The generator needs a solver, because the solver will answer the questions : Is there any solution ? if yes, is the solution a unique solution ?
    3. Once a puzzle is generated by the generator, you may feed it to the solver.

    There is no automatic linkage, you need to type out.txt to view the puzzle, then copy and paste the puzzle to the "puzzle" variable in main() of the solver.

    If you want automatic linkage, you may need to modify both the solver and the generator yourself.

    ReplyDelete
    Replies
    1. UnknownJuly 9, 2013 at 2:30 PM

      Hi,
      I think your generator works incorrectly. I recently read that it was prooved that minimal number of clues in sudoku can be 17, any sudoku with less clues has more than 1 solution, however for some values of seed your algorithm generate sudoku with less clues and says that it has unique solution. For example if seed = 28 it gives
      Puzzle in plain text format :
      7........
      ....8...1
      64.......
      .........
      ..8....2.
      .........
      ......9..
      .....1...
      .........

      Puzzle in Java String format :
      String puzzle = "7........"+
      "....8...1"+
      "64......."+
      "........."+
      "..8....2."+
      "........."+
      "......9.."+
      ".....1..."+
      ".........";
      which have more than 1 solution.

      Delete
  3. Renan HJune 23, 2013 at 7:01 AM

    ok, i will try. thanks a lot!

    ReplyDelete
  4. Ivan MactekiJuly 10, 2013 at 7:53 AM

    First of all. Thank you for reading and really trying the program.

    I agree that the puzzle generated by seed 28 provides too few hints that make it difficult for human solving.

    However, I can only find a single solution (with my own solver and some third party solvers) :
    7 8 1 2 3 4 5 6 9
    2 3 5 6 8 9 4 7 1
    6 4 9 1 5 7 2 3 8
    1 2 3 4 6 5 8 9 7
    4 5 8 7 9 3 1 2 6
    9 6 7 8 1 2 3 4 5
    3 1 2 5 7 6 9 8 4
    8 7 4 9 2 1 6 5 3
    5 9 6 3 4 8 7 1 2

    Would you please provide another solution to prove that it is not unique ?

    I must admit that this generator is not a great one. It just provides a starting point.

    Yet you may use this tools to build a puzzle database by some human judgement. For example, just build a list of 1000 puzzles and select 100 good looking one from them. You may either store the list of good seeds or just store the puzzles in any format you wish.

    ReplyDelete
    Replies
    1. UnknownJuly 10, 2013 at 11:00 AM

      Hi, here is alternative solution for that sudoku
      7 8 1 4 5 9 2 3 6
      2 3 5 6 8 7 4 9 1
      6 4 9 1 3 2 5 7 8
      3 9 2 8 1 4 7 6 5
      4 1 8 5 7 6 3 2 9
      5 6 7 2 9 3 8 1 4
      1 2 4 7 6 5 9 8 3
      8 7 3 9 4 1 6 5 2
      9 5 6 3 2 8 1 4 7
      I found it by http://www.sudoku9x9.com/sudoku_solver_9x9.php

      Store a list of good seeds could be a good approach, but I afraid that there could be 'bad' sudokus there(with more amount of hints, which makes difficult to determine them) so it is not applicable.
      By the way your tutorial is one of the best that I found, it allows to generate sudokus with very wide range of hints and the main issue is that sometimes it generates invalid sudokus, so it will be nice if you can find and resolve this issue.
      P.S.
      I notice one more issue
      For some values of seed your algorithm falls into infinite loop. for example if seed = 9. I think those 2 problems should be connected somehow.

      Delete
    2. Ivan MactekiJuly 11, 2013 at 7:56 AM

      Thank you very much.
      Fix is now available at :
      http://java.macteki.com/2013/07/sudoku-generator-bug-fixing-patch.html

      Delete
  5. BulletproofApril 25, 2014 at 12:24 AM

    Hi, Ivan...It is a good program to generate Sudoku puzzles. But your program does not explain the method to generate puzzles of varying complexity like hard,tough,super-tough,easy,moderate etc. How is this decided? Please comment. Thank you

    ReplyDelete
    Replies
    1. Ivan MactekiApril 26, 2014 at 9:45 AM

      Please visit my new post on sudoku rating.
      http://java.macteki.com/2014/04/difficulty-rating-for-sudoku-puzzle.html

      Delete

Subscribe to: Post Comments (Atom)