×
Please, log in to give us a feedback. Click here to login

×

You must be logged to download. Click here to login

×

MrBool is totally free and you can help us to help the Developers Community around the world

Yes, I'd like to help the MrBool and the Developers Community before download

×

MrBool is totally free and you can help us to help the Developers Community around the world

Yes, I'd like to help the MrBool and the Developers Community before download

In this article I will use a version which includes an intuitive interface which has the ability to use help and to check for errors. If we turn on help it will mark all the possible fields for selected a number. Then after checking the errors, the program will mark all the valid fields green and invalid fields red. The rules which will be used for implementation are: An integer will appear only once in the same row, same column, and the same 3*3 region. There is only one solution for the game. Now for implementation of this game, the most vital part is game class which should contain the following functionality:

- Make a new solution;
- Make a new game from a solution;
- Maintain track of user input;
- Verify user input against generated solution;
- Maintain track of selected number;
- Maintain track of help which could be on or off.

When certain changes have been performed, observers will be informe since the game class extends observable. The application contains two observers, ButtonPanel and SudokuPanel. When the Game class executes set Changed () followed by notifyObservers(...), the observers will execute their update(...)method. The model consists of an enumeration called UpdateAction which will tell observers what kind of changes have taken place.

First of all we have to generate a solution before we start generating a game. There is a method to generate a solution which is given below which have to be called by a user as generateSudoku(new int[9][9],0). The following steps are taken:

- Verify if a solution is found.
- Found -> solution is returned.
- Not found -> continue.

- X (of current field) is found by finding the remainder of the division of the current index by the count of fields in a row using the modulo operation.
- Y (of current field) is found by dividing the current index by the count of fields in a row.
- An ArrayList is filled with the numbers 1 to 9 and shuffled. Shuffling is important because otherwise you always get the same solution.
- As long as there are numbers in the ArrayList, the following will be executed:
- The next possible number is obtained by the method getNextPossibleNumber(int[][], int, int, List<Integer>), which will be explained later on. If there's no next possible number (return value of -1), null is returned.
- Found number is placed on the current location.
- The method is recursively called with an increase of the index, and the returning value is stored in a variable.
- If this variable is not null, it is returned; otherwise, the current location is put back to 0 (meaning the field is blank).
- Null is returned. This part will never be reached, hopefully.

**Listing 1**: Shows the code for generating a solution

private int[][] generateSolution(int[][] game, int index) { if (index > 80) return game; int x = index % 9; int y = index / 9; List<Integer> numbers = new ArrayList<Integer>(); for (int i = 1; i <= 9; i++) numbers.add(i); Collections.shuffle(numbers); while (numbers.size() > 0) { int number = getNextPossibleNumber(game, x, y, numbers); if (number == -1) return null; game[y][x] = number; int[][] tmpGame = generateSolution(game, index + 1); if (tmpGame != null) return tmpGame; game[y][x] = 0; } return null; }

For obtaining the next possible number this method getNextPossibleNumber(int[][], int, int, List<Integer>) is used. It takes a number from the list and checks whether it is possible at the given x and y position in the given game. When found , the number is returned. If the list is empty and thus no number is available at this location, -1 is returned.

**Listing 2**: Shows the code to get next possible number

private int getNextPossibleNumber(int[][] game, int x, int y, List<Integer> numbers) { while (numbers.size() > 0) { int number = numbers.remove(0); if (isPossibleX(game, y, number) && isPossibleY(game, x, number) && isPossibleBlock(game, x, y, number)) return number; } return -1; }

Now the next step is to generate a game. We can simply generate a game by constantly removing a random field but making sure that the game is still valid. Validity of game means that there is only one solution. We can achieve this by methods given below. First of all, user should call the first method, which in turn uses the second method. I will again describe the steps:

- A list is filled with all possible positions.
- The list is shuffled. I think that this method by which the blanks are better distributed. With the result that the game is harder.
- The list is passed to the method generateGame(int[][], List<Integer>) and the appropriate value will be returned.

** Listing 3**: Shows the code to generate a game

private int[][] generateGame(int[][] game) { List<Integer> positions = new ArrayList<Integer>(); for (int i = 0; i < 81; i++) positions.add(i); Collections.shuffle(positions); return generateGame(game, positions); }

- As long as there are positions in the list, the following will be executed:
- Store a position in the variable which is taken from the list.
- Now calculate the x and y from this position.
- Value at this position is stored in the variable temp.
- Value at this position is set to 0 (meaning the field is blank).
- This step is significant. As the elimination of the value at the position means that the game is no longer valid, the value at the position is placed back. Otherwise the game stays the same.
- The game is returned.

**Listing 4**: Shows the code for the method which is used to pass default values

private int[][] generateGame(int[][] game, List<Integer> positions) { while (positions.size() > 0) { int position = positions.remove(0); int x = position % 9; int y = position / 9; int temp = game[y][x]; game[y][x] = 0; if (!isValid(game)) game[y][x] = temp; } return game; }

Now we use new int[] {0} as it is the most common way of passing an integer by address instead of by value.

**Listing 5**: Show the code for passing an integer

private boolean isValid(int[][] game) { return isValid(game, 0, new int[] { 0 }); }

In a valid game there are numbers 1 to 9 in every row, every column, and every region. There should be only one solution. For achieving this, all open fields should be filled with the first valid value. Even after finding a solution, the search continues by putting the next valid value in an open field. If a second solution is found, then the search will be stopped and the method returns false. There will always be at least one solution. So if there are less than two solutions, the game is valid and the method returns true. Now the steps for achieving this:

- Ensure if a solution is found.
- Found -> increase numberOfSolutions and return true if it equals 1; false otherwise.
- Not found -> continue.
- Compute x and y from index.
- Verify if current field is blank (equals 0).
- True
- Fill a list with numbers 1 to 9.
- While the list contains numbers, execute the following:
- Get the next possible number. If the returned value equals -1, perform a break resulting a return of true.
- Set this number at current field.
- Call this method recursively and instantly check against the returned value.
- True -> one or no solution found, continue search.
- False -> more than one solution found, stop searching. Restore game and return false.
- Restore value of current field to 0 (meaning it is blank).
- False
- Call this method recursively and instantly check against the returned value.
- True -> continue.
- False -> return false.
- Return true

**Listing 6**: Shows the code to check for valid game

private boolean isValid(int[][] game, int index, int[] numberOfSolutions) { if (index > 80) return ++numberOfSolutions[0] == 1; int x = index % 9; int y = index / 9; if (game[y][x] == 0) { List<Integer> numbers = new ArrayList<Integer>(); for (int i = 1; i <= 9; i++) numbers.add(i); while (numbers.size() > 0) { int number = getNextPossibleNumber(game, x, y, numbers); if (number == -1) break; game[y][x] = number; if (!isValid(game, index + 1, numberOfSolutions)) { game[y][x] = 0; return false; } game[y][x] = 0; } } else if (!isValid(game, index + 1, numberOfSolutions)) return false; return true; }

Now we will check the game by checking user input. With checking input we will compare each field in the game against the corresponding field in the solution. The result is stored in a two dimensional Boolean array.

The selected number is also set to 0 which mean no number is selected. Now all observers are informed that the model has changed with the corresponding UpdateAction.

**Listing 7**: Shows the code to check the game

public void checkGame() { selectedNumber = 0; for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) check[y][x] = game[y][x] == solution[y][x]; } setChanged(); notifyObservers(UpdateAction.CHECK); }

**Figure 1**: Shows the snapshot of a Sudoku game that is developed

Finally, in this article, we have learnt about the game Sudoku and the method of building it using o JAVA . We have followed a step by step approach for making this application.

Diksha Sahni

I have done my bachelor in Computer Science and I am well versed with programming languages such as JAVA, C#, html and done courses on Android development.

What did you think of this post?

SUPPORT US

SUPPORT US

Related Posts

To have full access to this post (or download the associated files) you must have **MrBool Credits**.

See the prices for this post in Mr.Bool Credits System below:

**Individually** – in this case the price for this post is **US$ 0,00 (Buy it now)**

in this case you will buy only this video by paying the full price with no discount.

**Package of 10 credits** - in this case the price for this post is **US$ 0,00**

This subscription is ideal if you want to download few videos. In this plan you will receive a discount of 50% in each video.**Subscribe for this package!**

**Package of 50 credits** – in this case the price for this post is **US$ 0,00**

This subscription is ideal if you want to download several videos. In this plan you will receive a discount of 83% in each video.**Subscribe for this package!**

> More info about MrBool Credits

See the prices for this post in Mr.Bool Credits System below:

This subscription is ideal if you want to download few videos. In this plan you will receive a discount of 50% in each video.

This subscription is ideal if you want to download several videos. In this plan you will receive a discount of 83% in each video.

> More info about MrBool Credits

Click here to login

If you don't have a MrBool registration, click here to register (free)