Action , Fun , Games with Java : Solving Sudoku Puzzle:

Hi All,

Today , We will take a look at how java can help is solving one of the most famous logical and mind teaser games i.e. Sudoku. We will create a simple Java program that will help in Solving Sudoku Puzzles. So lets begin:

When it comes to Games , many of us would have comes across many puzzle teasers games like Crosswords and Sudoku .Sudoku is a logical puzzle game, originally created in puzzle books and then made available in countless newspapers worldwide.

Sudoku is one of the most popular puzzle games of all time. The goal of Sudoku is to fill a 9×9 grid with numbers so that each row, column and 3×3 section contain all of the digits between 1 and 9.

What is Sudoku : It is a popular Japanese puzzle game based on the logical placement of numbers. Sudoku doesn’t require any special calculation or special math skills; all that is needed is brain with concentration.

How to play Sudoku :The goal of Sudoku is to fill in a 9×9 grid with digits so that each column, row, and 3×3 section contain the numbers between 1 to 9. At the beginning of the game, the 9×9 grid will have some of the squares filled in. The task is to use logic to fill in the missing digits and complete the grid. An import point to note is , a move is incorrect if:

a) Any row contains more than one of the same number from 1 to 9
b) Any column contains more than one of the same number from 1 to 9
c) Any 3×3 grid contains more than one of the same number from 1 to 9

Why to play Sudoku : Sudoku is also an excellent brainteaser game. If played regularly, it may help improvements of one’s concentration and overall problem solving ability.

Solving Sudoku with Java : Today , We will try to solve Sudoku puzzle with a simple java a program by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The 0 indicates empty cells. Here is a sample input board is shown and the valid solution is shown below:

Input :

Output :

There can be many possible solutions to 1 Sudoku problem . One of the solution is mentioned above.

Approach :

The first idea that comes to mind , is to generate all possible ways to fill the cells with numbers from 1 to 9, and then check them to arrive at the solution that mean Sudoku Requirement . This means there will be larger no of possible ways to check for solution. It will be 9^{81} operations to do, where 9 is a number of available digits and 81 is a number of cells to fill. Hence , to avoid such large computations, we will take a look at how to optimize the solution. Here , We will sue the concept of Back-tracking to arrive at the solution.

Backtracking is a general algorithm technique for finding solutions to some computational problems that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. For more info on Back Tracking , please check https://en.wikipedia.org/wiki/Backtracking

Steps for Java Program:

Now we are ready to create a java class with name : SimpleSudokuSolver .it has many methods like :

1. printBoard : it prints the input and output board .
2. solveSudokuPuzzle : main method to solve the Sudoku Puzzle
3. applyBacktracking method : for applying the backtrack algorithm technique from row = 0, col = 0.

The program will start from the upper left cell row = 0, col = 0. Proceed till the first free cell is found. Then , program will Iterate over the numbers from 1 to 9 and try to put each number din the (row, col) cell of the sudoku matrix board. If number is not yet in the current row, column and box :
then populate the number in the identified place in matrix (row, col) cell.
we will store down the number is now present in the current row, column and box. This way , the program will continue the operations of filling the numbers in cells.
If we’re on the last cell row == 8, col == 8 :That means that we’ve solved the sudoku.
Else
Proceed to place further numbers.
Backtrack if the solution is not yet here : remove the last number from the (row, col) cell.

The other methods are self explanatory with comments. Java program and outputs .

Sudoku Solver

Complete java program is available my Github Repo: https://github.com/connect2grp/funwithjava/blob/4881dc6f0ce07decde21b6b0fa19364e5993340d/funwithjava/src/com/grp/connect/games/sudoku/SimpleSudokuSolver.java

Hope you have enjoyed cracking Sudoku puzzle with me on this post.

See you Soon . Happy Coding !!