raffaello/scala-sudoku

sudoku solver with dancing links in scala

Sudoku Problem

it is converted to an Exact Cover Problem

Conversion Strategy

to enforce a cell with a clue, it will set to 0 all the others column constraints relative to that specific grid cell.

So basically is reducing for each clue a number of 32 ones

• 36 are total for 9 values for each grid position

Convert back from DLX solution to the grid

The unique solution is composed by 81 elements, each of them is composed by 4 values representing the row of those 4 columns:

give them in ascending order, the first value represent the cell constraints from which would be simple recovering the row and column value of the grid just by doing an integer division and getting the remainder.

the value at that point can be retrieved by one of the other 3 values by inverting their position.

For consistency it is enforced a check among the value returned.

JVM tuning

No real need of it

Others GC tuning

Algorithms

• -XX:+UseG1GC
• -XX:+UseConcMarkSweepGC

Logging

• -XX:+PrintGCDetails
• -XX:+PrintGCDateStamps
• -XX:+PrintGCTimeStamps

TODO

• n-Queens problem
• generalize sudoku
• solve with integer programming
• use C/C++ scala native dlx algorithm

References

• An Integer Programming Model for the Sudoku Problem
• Solve Sudoku Puzzles Via Integer Programming
• Sudoku Puzzles Generating: from Easy to Evil
• Dancing Links

Related References:

• Complexity of n-Queens Completion