/sudoku_solver_in_java

A simple Sudoku Solver in Java

Primary LanguageJavaMIT LicenseMIT

Sudoku Solver in Java

A simple Sudoku Solver (for order-3 problems i.e. 9x9 boards) in standard Java 16.

JUnit Jupiter is used as testing framework for (minimal) testing.

This was written to test the idea of "Constraint Solving" and "Constraint Propagation" on a simple problem.

Currently the intial board is not given on the command line but is constructed through a dedicated method. Take a look at the test methods for this.

If you run Sudoku.main(), default initial settings will be loaded into the Board structure and the corresponding problem will be solved.

Take a log at example.log for example output.

TODO

  • Read the initial board as text input from the command line and output a more nicely printed board.
  • The "alldifferent" constraint misses the trick that if there are n decision variables with the same domain of size n, none of the values in that domain can appear in any decision variable being monitored by that constraint.
  • More tests.

Done differently

With languages that provide the right abstraction you can go right for it in a few lines:

Prolog

MiniZinc

Some reading

  • Sudoku at Wikipedia.
  • Mathematics of Sudoku at Wikipedia.
  • Sudoku as a Constraint Problem by Helmut Simonis.
  • Sudoku as a SAT Problem (PDF) by Inês Lynce and Joël Ouaknine. We read: "In the extended encoding, the resulting CNF formula will have 11,988 clauses, apart from the unit clauses representing the pre-assigned entries. From these clauses, 324 clauses are nine-ary and the remaining 11,664 clauses are binary. The nine-ary clauses result from the four sets of at-least-one clauses (4⋅9⋅9 = 324). The 11,664 binary clauses result from the four sets of at-most-one clauses (4⋅9⋅9·[36 pairings of 2 elements from 9])."
  • Analysis of Sudoku Solving Algorithms by M.Thenmozhi, Palash Jain, Sai Anand, Saketh Ram (2017)
    • This paper references the "Dancing Links" algorithm by Donald Knuth described in: Dancing links: "The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes."
  • Complexity and Completeness of Finding Another Solution and Its Application to Puzzles by Takayuki YATO and Takahiro SETA: The "Number Place" (i.e. Sudoku) problem is NP-complete (i.e. belongs to the set of "hardest" problems in NP). In the paper Sudoku as a SAT Problem we also read "Note, however, that generalized Sudoku puzzles satisfying "has only one solution" and "can be solved with only reasoning, i.e. with no search" are polynomial-time solvable."
  • Sudoku Puzzle Complexity by Sian K. Jones, Paul A. Roach and Stephanie Perkins (2009): How "hard" a puzzle feels in an informal sense.
  • A Hybrid Approach for the Sudoku Problem: Using Constraint Programming in Iterated Local Search, appears in IEEE Intelligent Systems (Volume: 32, Issue: 2, Mar.-Apr. 2017)
    • This article is paywalled but a (non-beautified) version of the paper as well as the software that goes with it can officially be found here.
    • The paper describes a hybrid approach to solve Sudoku problems of rank 3 to 5. Experiments show that Constraint Propgation does not do well on rank 4 problems. For rank 5 problems, only the hybrid approach and a simulated annealing-based algorithm still manage, with the hybrid approach needing much less time to find an optimal solution (i.e. a solution fulfilling all constraints). At rank 5, problems around ~45% of fixed cells cause both approaches to fail at finding an optimal solution.
  • Solving and Analyzing Sudokus with Cultural Algorithms by Timo Mantere and Janne Koljonen: On using genetic algorithms on Sudoku problems.

Specifically about the "All Different" Constraint

The present code does not use this goodness!