You could use our implementations in order to solve Sudoku problems, generate non-symmetrical or symmetrical Sudoku, and rate Sudoku problems.
Moreover you could create a printable pdf with as many problems from each difficulty level as you desire. You can take a look at a pdf-example in https://github.com/BurnYourPc/Sudoku/blob/master/SudoProblems/SudoPdf/SudokuProblems1.pdf
Every Sudoku that is generated is saved as png in the corresponding folder. The image below is an example of a sudoku problem that is generated by our implementation:
We rate 5 levels of difficulty (very Easy, Easy, Medium, Hard, very Hard) and divide them inτο symmetrical and non-symmetrical problems. 11 symmetrical patterns can be generated, but is very easy to add as many as you wish (in utils/GeneratorsUtils.py).
We use pyhton 3.5.2
Run main.py in src/main folder
- Solvers
Our main solver is a recursive backtracking algorithm using two methods for input (Single candidate and Single position method). We implement a variaty of methods for cell rejection. You could build your own backtracking solver adding these methods.
- Generators
Our main Generator uses a Top-Down technique with a Simulated Annealing variant and guarantees unique solution. It begins from a full-solved grid and randomly removes a cell only if outcomes a unique solution grid. If it is, the generator continues the removal proccess until we have a grid with the desirable number of known cells. Otherwise it returns to the previous recursive call and tries another removal.
That proccess can efficiently generate sudoku problems with 25-24 known cells, but not less. So we added a simulated annealing technique. That is: In each step we define a probability p(n) ( n is the number of known cells in each step and if n1 <= n2 then p(n1) <= p(n2) ) that the generator would fill 2 cells at random. So this way we can exceed the local optimums (from the point of view of grid's structure) and generate sudoku problems even with 21 known cells (or even 20 but it's slow). The parametrs of the simulated annealing may take improvement.
In practice it's more convenient to generate sudoku from 22 to 32 cell known at most. So when you choose to generate sudoku problems you have to give the number of problems you want to be generated. Then for each new sudoku problem the generator chooses a random number, k, between 22 and 32 and generates a grid with k known cells.
Moreover we set time limit (15 sec.) for a sudoku problem to be generated, for better time efficient in practise. If the time limit is violated then a new full solved grid is generated and we repeat the proccess. You can use the time limitless generator if you want.
We have experimentally concluded that when a sudoku is generated its level is more possible to be very Easy, then very Hard, Easy, Medium and Hard.
In addition we implement a Bottom-up technique generator, but it's not very effective and needs a lot of improvement.
- Rating Sudoku
For rating sudoku problems we follow Narendra Jussien method in his book "A to Z of SUDOKU". He gives a catalog of 10 rules that could be used to solve sudoku. You can sort this catalog from easiest to most difficult rule to understand and use. The difficulty level of a grid is defined by the minimal required level of rules that is maximally needed to solve the grid.
-->To improve
(a) A gui for a sudoku grid and a menu bar. (b) Add generators (genetic for example), change and improve existing (speed, simulated annealing parametrs). (c) Add some different raters (genetic). (d) Add some more exotic solvers (hopfield neural network, integer programming). (e) Add a new level (expert)