Click here to Skip to main content
15,867,568 members
Articles / Desktop Programming / Swing

Sudoku Game in Java

Rate me:
Please Sign up or sign in to vote.
4.73/5 (34 votes)
18 Apr 2012CPOL7 min read 325K   34K   64   47
A Sudoku game written in Java which generates its own games on the fly.

sudokuinjava/Sudoku.jpg

Introduction

This article is on the implementation of a Sudoku game in Java. This version includes an intuitive interface with the ability to use help and to check for errors. Turning on help will mark all possible fields for the selected number. After checking for errors, the program marks valid fields green and invalid fields red. The rules used in this implementation are as follows:

  • An integer may only appear once in ...
    • ... the same row.
    • ... the same column.
    • ... the same 3x3 region.
  • A game has only one solution.

Implementation

Model

The most important part of this application is in the Game class, which includes the following functionality:

  • Generate a new solution;
  • Generate a new game from a solution;
  • Keep track of user input;
  • Check user input against generated solution;
  • Keep track of selected number;
  • Keep track of help is on or off.

Because the Game class extends Observable, it can and does notify observers when certain changes have been performed. This particular application contains two observers, ButtonPanel and SudokuPanel. When the Game class executes setChanged() followed by notifyObservers(...), the observers will execute their update(...) method.

Besides the Game class, the model consists of an enumeration called UpdateAction which will tell observers what kind of update has taken place.

Generate Solution

Before we can start generating a game, we must first generate a solution. This is achieved by the method below, which needs to be called by the user as generateSudoku(new int[9][9], 0). The following steps are taken:

  1. Check if a solution is found.
    • Found -> solution is returned.
    • Not found -> continue.
  2. 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.
  3. Y (of current field) is found by dividing the current index by the count of fields in a row.
  4. An ArrayList is filled with the numbers 1 to 9 and shuffled. Shuffling is important because otherwise you always get the same solution.
  5. As long as there are numbers in the ArrayList, the following will be executed:
    1. 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.
    2. Found number is placed on the current location.
    3. The method is recursively called with an increase of the index, and the returning value is stored in a variable.
    4. If this variable is not null, it is returned; otherwise, the current location is put back to 0 (meaning the field is a blank).
  6. null is returned. This part will never be reached, hopefully.
Java
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;
}

As previously said, the method getNextPossibleNumber(int[][], int, int, List<Integer>) is used for obtaining the next possible number. 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 possible, the number is returned. If the list is empty and thus no number is possible at this location, -1 is returned.

Java
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;
}

Generate Game

Generating a game is simply achieved by constantly removing a random field and making sure the game is still valid. Valid means there is only one solution. This is achieved by the methods below. The user should call the first method, which uses the second method. I will describe the steps again.

  1. A list is filled with all possible positions.
  2. The list is shuffled. I do not know why. I suspect that this way, the blanks are better distributed. With the result that the game is harder.
  3. The list is passed to the method generateGame(int[][], List<Integer>) and the return value will be returned.
Java
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);
}
  1. As long as there are positions in the list, the following will be executed:
    1. A position is taken from the list and stored in a variable.
    2. x and y are calculated from this position.
    3. Value at this position is stored in the variable temp.
    4. Value at this position is set to 0 (meaning the field is a blank).
    5. This step is critical. As the removal of the value at the position means that the game is no longer valid, the value at the position is put back. Otherwise the game stays the same.
  2. The game is returned.
Java
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;
}

As you can see, this method is used to pass default values. So why the new int[] { 0 }? This is the most common way of passing an integer by reference, instead of by value.

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

A valid game has in every row, every column, and every region the numbers 1 to 9. Additionally, there should only be one solution existing. To achieve this, all open fields are 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 (hence game is an incomplete solution), so if there are less than two solutions, the game is valid and the method returns true. Step by step:

  1. Check if a solution is found.
    • Found -> increase numberOfSolutions and return true if it equals 1; false otherwise.
    • Not found -> continue.
  2. Calculate x and y from index.
  3. Check if current field is a blank (equals 0).
    • True
      1. Fill a list with numbers 1 to 9.
      2. While the list contains numbers, execute the following:
        1. Get the next possible number. If the returned value equals -1, perform a break resulting a return of true.
        2. Set this number at current field.
        3. 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.
        4. Restore value of current field to 0 (meaning it is blank).
    • False
      1. Call this method recursively and instantly check against the returned value.
        • True -> continue (resulting in returning true).
        • False -> return false.
  4. Return true.
Java
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;
}

Check Game

With checking user input, we 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 (meaning no number is selected). All observers are notified that the model has changed with the corresponding UpdateAction.

Java
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);
}

View & Controller

There is not much to say about the view part, only the structure of the panels. The controllers react to user input and implement changes to the model. The model notifies it has been changed. The view responses to this notification and updates. These updates of the view are limited to changing colors and changing the number of a field. There is no rocket science involved.

Sudoku

The view also is the entry point of this application; the Sudoku class contains the main method. This class builds up the user interface by creating a JFrame and placing SudokuPanel and ButtonPanel inside this frame. It also creates the Game class, and adds SudokuPanel and ButtonPanel as observers to it.

SudokuPanel and Fields

SudokuPanel contains 9 sub panels each containing 9 fields. All sub panels and fields are placed in a GridLayout of 3x3. Each sub panel represents a region of a Sudoku game, and is primarily used for drawing a border visually separating each region. They also get the SudokuController added to them, which is in charge of processing user input by mouse.

ButtonPanel

ButtonPanel contains two panels with a titled border. The first panel contains three buttons. Button New for starting a new game, button Check for checking user input, and button Exit for exiting the application. The second panel contains 9 toggle buttons placed inside a button group. This way, they react like radio buttons. Clicking one of these toggle buttons will set the corresponding selected number in the Game class.

Points of Interest

  • For passing an integer by reference instead of by value, use an integer array.
  • Java
    isValid(game, 0, new int[] { 0 });
    private boolean isValid(int[][] game, int index, int[] numberOfSolutions);
  • Finding the base x and y values of a region, use the following:
  • Java
    int x1 = x < 3 ? 0 : x < 6 ? 3 : 6;
    int y1 = y < 3 ? 0 : y < 6 ? 3 : 6;

History

  • Initial release.

Apologies

One, if I have driven you mad with my bad English, I apologize. Two, if I have driven you mad before because usually my source doesn't contain comments, I apologize, and I can tell you, in this case, it does. Not because I acknowledge their usefulness, but to avoid discussions. Three, if I didn't mention before that you can use your right mouse button to clear a field, I apologize.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer Fortes Solutions BV
Netherlands Netherlands
It's good to be me.

Comments and Discussions

 
QuestionProblem in isValid() Pin
Member 139251285-Jun-19 20:53
Member 139251285-Jun-19 20:53 
QuestionMissing main function, no compiling Pin
Member 1418490626-Mar-19 8:09
Member 1418490626-Mar-19 8:09 
Questiony and x Pin
Member 1238113522-Mar-16 18:44
Member 1238113522-Mar-16 18:44 
QuestionProj Folder Pin
Member 1234733223-Feb-16 15:09
Member 1234733223-Feb-16 15:09 
Questioncode does not RUN Pin
Member 1217609421-Dec-15 22:42
Member 1217609421-Dec-15 22:42 
Questionurgent Pin
Member 1221759719-Dec-15 4:20
Member 1221759719-Dec-15 4:20 
Questionjust want to ask this Pin
Member 1176014921-Jun-15 6:05
Member 1176014921-Jun-15 6:05 
Questionwhat the algorithm you use? Pin
Bang Jhidat Paho1-Oct-14 8:07
Bang Jhidat Paho1-Oct-14 8:07 
QuestionFilling in the fields Pin
branoc4-Apr-14 23:30
branoc4-Apr-14 23:30 
Questionthanks a lot Pin
Member 107250554-Apr-14 6:36
Member 107250554-Apr-14 6:36 
Questionloading and saving sudoku Pin
Marco Giadone24-Jan-14 3:51
Marco Giadone24-Jan-14 3:51 
QuestionSudoku... Pin
Melgx29-Nov-13 5:56
Melgx29-Nov-13 5:56 
QuestionSUDOKU Pin
Member 1043154927-Nov-13 22:30
Member 1043154927-Nov-13 22:30 
AnswerRe: SUDOKU Pin
ichsanelf28-Nov-13 13:37
ichsanelf28-Nov-13 13:37 
Questionadd backtracking algorithm Pin
ichsanelf27-Nov-13 19:50
ichsanelf27-Nov-13 19:50 
AnswerRe: add backtracking algorithm Pin
Melgx29-Nov-13 5:59
Melgx29-Nov-13 5:59 
GeneralRe: add backtracking algorithm Pin
ichsanelf29-Nov-13 14:11
ichsanelf29-Nov-13 14:11 
QuestionButtons Disappear? Pin
CodeKing49918-Jan-13 12:44
CodeKing49918-Jan-13 12:44 
If you convert the getSystemLookAndFeelClassName to getCrossPlatformLookAndFeelClassName, the numbers on the buttons disappear? Whats a fix for this?
Questionsudoku code Pin
Sai Sathveer26-Dec-12 3:57
Sai Sathveer26-Dec-12 3:57 
GeneralMy vote of 5 Pin
Serhiy Perevoznyk10-Oct-12 7:05
Serhiy Perevoznyk10-Oct-12 7:05 
QuestionNumbers to Letters Pin
Yuwan Enginco23-Sep-12 1:30
Yuwan Enginco23-Sep-12 1:30 
QuestionEnd results? Pin
Kikert Wiliams13-Sep-12 20:24
Kikert Wiliams13-Sep-12 20:24 
AnswerRe: End results? Pin
developer0014-Sep-12 11:40
developer0014-Sep-12 11:40 
Questioncant run the program Pin
Kikert Wiliams12-Sep-12 5:47
Kikert Wiliams12-Sep-12 5:47 
AnswerRe: cant run the program Pin
Eric Beijer12-Sep-12 6:17
Eric Beijer12-Sep-12 6:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.