Soduku

Problem Statement:
      Solve the given Soduku

Fig Soduku

Download Source Code
Solution: 
      For optimally solving the above soduku, we would require the technique of Backtracking.

Back-Tracking is a technique which incrementally builds candidates to a solution, and it rejects the candidate as soon as it determines the choosing that particular candidate will not lead to valid solution.
Back-Tracking takes the advantage of choosing and rejecting a candidate in a solution with the help of combined effect of Tail and Head Recursion.

In this problem , backtracking fills up a valid cell with the number , and moves the to the next cell and assumes the same set of conditions as was with the previous cell. At any cell if all numbers from '1' to '9' are invalid, then we back track to the previous cell and fill that with another valid number, then we move to the next cell and continue the process until all cells are filled which will give the solution or the first cell is tried with all numbers fro  1 to 9 and still soduku was not solved, then soduku is unsolvable.

The Backtracking sub-routine is shown below: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/** * Subroutine to solve the Soduku * @return true if soduku is solvable */ public boolean solve(int row, int col) { if (soduku[row][col] != BLANK) nextCell(row, col); else { // Try the vacant cell with every Number for (int num = 1; num <= size; num++) { // check if current number can fit the cell with the given // constraints if (isValid(row, col, num)) { soduku[row][col] = num; // Assuming to be true if (row == size - 1 && col == size - 1) { printSoduku(); return true; } if (solve(row, col)) // will be called again and other cells return true; // will be processed // printSoduku(); soduku[row][col] = BLANK; // Reverting } } } return false; // will be reached if for any cell none of the number(1-9) // fit } /** * Find the next free cell * @return , true if free cell found and currentRow and currentColumn are set */ private void nextCell(int row, int col) { if (col < size - 1) solve(row, col + 1); else if (row < size - 1) solve(row + 1, 0); }

To Check if a cell is valid is shown below, for a number to be valid in a cell it should not appear in 
1. the row of that cell
2. the column of that cell
3. the box, the cell belongs to

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/** * check validity of number at the given position, combining the result of 3 * conditions * @return true, if the number can fit at the current position */ private boolean isValid(int row, int col, int num) { return checkRow(row, col, num) && checkCol(row, col, num) && checkBox(row - row % boxSize, col - col % boxSize, num); } /** * Check particular for the existance of given number (in a particular row) * @return true if the number does not exist */ private boolean checkRow(int row, int col, int num) { for (int c = 0; c < size; c++) if (soduku[row][c] == num) return false; return true; } /** * Check particular for the existance of given number (in a particular col) * @return true if the number does not exist */ private boolean checkCol(int row, int col, int num) { for (int r = 0; r < size; r++) if (soduku[r][col] == num) return false; return true; } /** * Check particular for the existance of given given BOX * @return true if the number does not exist */ private boolean checkBox(int row, int col, int num) { for (int r = 0; r < boxSize; r++) { for (int c = 0; c < boxSize; c++) { if (soduku[r + row][c + col] == num) return false; } } return true; }

Happy Coding !! :)