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

scala-sudoku's Issues

optionally log the search tree

so can gather some metrics.

dicsover rules how to solve it more efficiently etc...
later ML to traininig DLX? to suggest "intuitively" which DFS path start? etc etc etc

DLX too slow and seems looping forever.

The test case is very very slow.
There is a sort of memory leak or "inifinite" loop in the design.
investigate the sudoku problem transformation to exact cover problem.
It should not take more than few seconds or less to solve a sudoku.

Refactor tests and code

Tests seems using some helpers function used in the code too.

Some tests are duplicated can be just iterated changing parameters.

The code and tests require clean up overall.