Friday, September 5, 2014

SuDoKu solver (Print all solutions for a given Puzzle) AI Java Implementation

Solves a board if it is possible to solve it, otherwise prints an error : Unsolvable.

First of all Rules for SuDoKu (9x9):

1. Every row and every column intersection number must be unique in that row and column.
2. Every 3x3 grid must have numbers from 1-9 with no repitition.

Keep in mind:

Not every random number placements on a 9x9 board is a SOLVABLE sudoku puzzle.
There MAY be multiple solutions for a given sudoku puzzle. [These are generally incomplete puzzles].

Algorithm applied:

1. Numbers already placed on the board initially are not to be touched! Just skip them.
2. Try to place every number from 1 to 9 on the next cell (using a recursive step - a recursive call for each cell placement).
3. If a number is placed. Call this same function on the next cell.
4. If current number did not get placed, successive recursive calls will get the board to fail, returning true(board failed) so the previous recursive call should try next number on that call's cell.
5. In between if an untouchable number (initially placed number) arrives, just skip it by calling recursion for next cell placement.
6. Function solve returns true is board fails to print "Unsolvable".
7. Remove the commented lines to see the actual calculations.

Code:


9 2 6 5 7 1 4 8 3
3 5 1 4 8 6 2 7 9
8 7 4 9 2 3 5 1 6
5 8 2 3 6 7 1 9 4
1 4 9 2 5 8 3 6 7
7 6 3 1 4 9 8 2 5
2 3 8 7 9 4 6 5 1
6 1 7 8 3 5 9 4 2
4 9 5 6 1 2 7 3 8


9 2 6 5 7 1 4 8 3
3 5 1 4 8 6 2 7 9
8 7 4 9 2 3 5 1 6
5 8 2 3 6 7 1 9 4
1 4 9 2 5 8 3 6 7
7 6 3 1 9 4 8 2 5
2 3 8 7 4 9 6 5 1
6 1 7 8 3 5 9 4 2
4 9 5 6 1 2 7 3 8

No comments:

Post a Comment