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 puzzle using rule1 and rule2 recursively and filled some cells which helps us to reduce no of rows when we convert it in to exact cover form.Applying algorithm X will give us a solution.
Input format :-First line of it take size of sudoku puzzle(say n).i.e Sudoku will be of n2*n2. For an example if we have input say 3 , then 9*9 sudoku will be there.
Next n2 lines will be space seperated sudoku input.
Here is a sample input format for sudoku:-
3
4 0 6 0 0 0 0 2 0
0 2 0 6 8 0 1 0 5
0 1 8 0 0 0 0 0 3
0 8 0 7 0 5 3 0 0
0 0 7 0 3 0 5 0 0
0 0 3 8 0 6 0 1 0
8 0 0 0 0 0 4 7 0
6 0 1 0 7 4 0 3 0
0 4 0 0 0 0 6 0 1
Here is a sample output format:-
----------------------
|4 7 6 |1 5 3 |9 2 8 |
|3 2 9 |6 8 7 |1 4 5 |
|5 1 8 |4 2 9 |7 6 3 |
----------------------
|2 8 4 |7 1 5 |3 9 6 |
|1 6 7 |9 3 2 |5 8 4 |
|9 5 3 |8 4 6 |2 1 7 |
----------------------
|8 3 5 |2 6 1 |4 7 9 |
|6 9 1 |5 7 4 |8 3 2 |
|7 4 2 |3 9 8 |6 5 1 |
----------------------
Time Taken:->0.001 seconds
Code has been uploaded in www.github.com , you can view and download the code from below link:-
Comments
Post a Comment