Sudoku, also called Number Place, is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contains all of the digits from 1 to 9.
In that tutorial, we are going to develop a Sudoku Solver in Java with Eclipse. We will use a recursive BackTracking approach. A simple, almost naive, approach. In a future tutorial, you will learn to implement a more clever approach.
Note that you can also watch this tutorial in video on YouTube :
Designing the Board
First step is to design the board to represent a Sudoku grid. It will be a 2D array of integers. Numbers will be stored from 1 to 9. A zero will indicate the cell of the grid is not assigned.
In the constructor of the Sudoku class, we will copy the 2D array of integers entered in parameters in the 2D array property of our class :
Checking the rules of Sudoku
To be considered as solved, a Sudoku grid must respect some constraints :
- Each row that composes the grid must contain all of the digits from 1 to 9
- Each column that composes the grid must contain all of the digits from 1 to 9
- Each nine 3×3 subgrids composing the grid must contain all of the digits from 1 to 9
So, after each step of our BackTracking algorithm, we will check if the grid stays valid or no. If yes, we will continue by trying other assignments to other cells of the grid. Otherwise, we will try a new value for the current cell.
The implementation of the checking of these 3 rules is made like that :
Implementing BackTracking Algorithm
As explained on Wikipedia :
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction 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.
In our Sudoku class, we create a solution method to implement this algorithm. In our implementation, we will stop the algorithm after one solution is found. It is good because a correct Sudoku grid has an uniq solution.
We iterate on the grid, and then, we try to assign a value on an empty cell. If the grid is correct after this assignment, we call recursively the solve method and we return true. Otherwise, we return false and then, the algorithm can try another assignment for the current cell.
This recursive approach gives us the following complete code for our Sudoku class :
At the end of the class, you should have noted the presence of the display method which is used to display a grid on the screen in console mode.
Our Sudoku Solver in Action!
The last step is to put our Sudoku Solver in Action!
We enter a grid to solve and then, we call the solve method in the main entry point of our class. Once the resolution is done, you should have the following result on the screen with the grid solved :
To go further
That?s all for that tutorial. In the next tutorial, you will discover how to create a more clever Sudoku Solver by using the Dancing Link Algorithm.
Waiting for this tutorial, why not playing in Sudoku on your Android device directly? You can try this Sudoku Android App for free on the Google Play Store :
Sudoku Number Place – Apps on Google Play
Sudoku, originally called Number Place, is a logic-based, combinatorial number-placement puzzle.The objective is to?
play.google.com
If you have some questions concerning this tutorial, don?t hesitate to use the comments section below.
If you want to discover some books to learn Java programming, I advise you to read the following article with my selection of the Top 6 Best Books for Java programming :
Top 6 Best Books for learning Java Programming
Twenty-five years after its creation, Java is still the most popular programming language according to the latest TIOBE?
medium.com
Other Java Articles You May Like to ExploreThe 2019 Java Developer RoadMap10 Things Java and Web Developer Should Learn in 201910 Testing Tools Java Developers Should Know5 Frameworks Java Developers Should Learn in 20195 Courses to Learn Big Data and Apache Spark in Java10 Courses to learn DevOps for Java Developers10 Books Every Java Programmer Should Read10 Tools Java Developers uses in their day-to-day work10 Tips to become a better Java Developer
