Posts

Showing posts from December, 2014

Sudoku using dancing link - Java implementation

Image
Here is a algorithm which uses dancing link to solve algorithm X(exact cover) that solves upto 100*100 sudoku. Algorithm has been implemented using  JAVA and can be able to solve Sudoku of any difficulty level(easy,hard,very hard).
Algorithm works as follows:-
1.) Algorithm first find out the number of possible elements in each cell , algorithm for this can be seen in the code.
2.) After this apply rule1 which says finds  that cell which has a single possible element , this works recursively until we find single possible element.
3.) After this apply rule2 which says if there is a number which can go into only one cell, then assign that number to that cell.
4.) Rule2 and rule1 run recursively.
5.) Still if we find possible number of elements in some cell then create a dancing link for sudoku puzzle , reduce the puzzle in to exact cover form and solve it using algorithm X in a efficient way.To make it efficient,first we implemented rule1 and rule2 ,firstly algorithm try to solve sudoku…