Thursday, 7 April 2016

Sudoku Solver : Solve any level of Sudoku

Sudoku Solver :
This is implemented by simple back-tracking algorithm (Backtracking Ref) in Javacript.

Simple steps to solve your Sudoku :
     1. Download the file  Sudoku Solver
     2. Make sure the downloaded file should be save as .html  file, else rename it to <filename>.html
     3. Open downloaded file in browser

Algorithm :
Input : A 2D 9x9 array (arr) with having valid and solvable input values.
            Valid - No number (1-9) is repeated in a same row, same column or same 3x3 box.
            Solvable - Even though the input is valid, but there is a chance of not having the solution for a                               particular input if that is randomly generated.

boolean solveSudoku(arr[9][9])
               Find an EMPTY cell (r, c) from the array 
               If no EMPTY cell found then
                         return TRUE ; // i.e the array is filled i.e. solved
                         for num from 1 to 9
                                 check if arr[r][c] is SAFE to put num
                                 if SAFE then
                                            arr[r][c] = num; //update cell with num, consider this is a part of the goal
                                            // call recursively solveSudoku(arr) to solve next EMPTY cell
                                            result = solveSudoku(arr) 
                                            if result is FALSE then   // No solution  exist with arr[r][c] = num 
                                                      arr[r][c] = 0;  // Revert back the considered solution
                                                      return TRUE; // We reached at the goal by taking arr[r][c] =num
                       end for
                       return FALSE;   // No solution exists, since no number from 1 to 9 can be placed at(r,c)

For SAFE checking :
boolean isSafe(arr[9][9], roe, col, num)
        if num is present in same row or same column or same inner 3x3 box then
                 return FALSE
                return TRUE

Get Source Code here.

Thank You for Visiting the blog.

No comments:

Post a Comment