Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have written this following Sudoku Generator. How good/bad is this? How can I improve this?

import java.util.Random;

public class SudokuUtility {

    static final int max = 8;
    static final int min = 0;

    static final int digitMax = 9;
    static final int digitMin = 1;

    static final int easyMin = 36;
    static final int easyMax = 49;

    static final int mediumMin = 32;
    static final int mediumMax = 35;

    static final int hardMin = 22;
    static final int hardMax = 27;


    public static void main(String[] args) {

        int[][] grid = new int[9][9];

        String option = "hard";

        Random random = new Random();

        int row = 0;
        int col = 0;

        int randomNumber = 0;
        int noOfCellsToBeGenerated = 0;

        if ("easy".equals(option)) {
            noOfCellsToBeGenerated = random.nextInt((easyMax - easyMin) + 1) + easyMin;
        } else if ("medium".equals(option)) {
            noOfCellsToBeGenerated = random.nextInt((mediumMax - mediumMin) + 1) + mediumMin;
        } else {
            noOfCellsToBeGenerated = random.nextInt((hardMax - hardMin) + 1) + hardMin;
        }

        for (int i = 1; i <= noOfCellsToBeGenerated; i++) {
            row = random.nextInt((max - min) + 1) + min;
            col = random.nextInt((max - min) + 1) + min;
            randomNumber = random.nextInt((digitMax - digitMin) + 1) + digitMin;

            if (grid[row][col] == 0 && noConflict(grid, row, col, randomNumber)) {
                grid[row][col] = randomNumber;
            } else {
                i--;
            }

        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(grid[i][j] + "  ");
            }
            System.out.println();
        }

    }

    public static boolean noConflict(int[][] array, int row, int col, int num) {

        for (int i = 0; i < 9; i++) {
            if (array[row][i] == num) {
                return false;
            }
            if (array[i][col] == num) {
                return false;
            }
        }

        int gridRow = row - (row % 3);
        int gridColumn = col - (col % 3);
        for (int p = gridRow; p < gridRow + 3; p++) {
            for (int q = gridColumn; q < gridColumn + 3; q++) {
                if (array[p][q] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}
share|improve this question

2 Answers 2

up vote 10 down vote accepted

Algorithm

Your algorithm is a bit flawed. One might think that it was that easy, but with your current approach one of three things can happen:

  • The result has exactly one solution (A traditional Sudoku)
  • The result has many solution (Not seen as a traditional Sudoku, as there's no way to logically deduce one solution)
  • The result has no solutions (Yes, although unlikely, this is a possible outcome of your current approach)

A different approach to generating Sudokus is to fill the entire grid first with a valid and completed Sudoku puzzle, and then (pseudocode following):

  • Remove a number
  • Check if the current puzzle is solvable using a Sudoku solving algorithm
    • If it is solvable, continue
    • If it is not solvable, put the number you just removed back and either try removing another number, or stop.

By using this different approach your result Sudoku is guaranteed to be solvable and have only one solution.

Making it object-oriented

Your main method is doing many many things, I would recommend changing your main method to do only this:

private static final int DEFAULT_SIZE = 9;
public static void main(String[] args) {
    Sudoku sudoku = new Sudoku(DEFAULT_SIZE, DEFAULT_SIZE);
    sudoku.generate(Difficulty.HARD); // Using @Jeroen's lovely enum!
    sudoku.output();
}

With this structure of your main method, you can see that I'm expecting you to create a Sudoku class. You will hopefully see that you will have many benefits by having a specific Sudoku class. By having a Sudoku class, it will be much easier to expand your code, read your code, modify specific parts of your code, and create a world of new amazing Sudoku-ness.

Example of an unsolvable puzzle

For the sake of simplicity, consider a 4x4 puzzle divided into 2x2 boxes:

  12 34
  -----
a|00 03
b|02 04
 |
c|10 00
d|40 00

This puzzle does not break any Sudoku rules in it's current state, however, it is not possible to create a finished Sudoku puzzle from this state!

If you don't believe me, I ask: Which number should be in the top-left corner?

  • It cannot be a 1, as there is a 1 on position c1.
  • It can't be a 2 as there's a 2 in the same box on position b2.
  • It can't be a 3 as there's a 3 on a4.
  • It also can't be a 4 as there's a 4 on d1.

There is no valid number we can put in the top-left corner, and therefore it is unsolvable!

share|improve this answer
    
Andre Forsberg Thank you very much. But, how come the puzzle won't have any solution? I am not able to understand. –  user35013 May 10 at 8:11
1  
@Phoenix See the edit to my question for an example of an unsolvable puzzle. –  Simon André Forsberg May 10 at 8:34

Enums

Your mins and maxes (and difficulties) are all over the place. Consider grouping them into an enum like this:

public enum Difficulty {
    EASY(36, 49),
    MEDIUM(32, 35),
    HARD(22, 27);

    private final int min;
    private final int max;

    Difficulty(int min, int max){
        this.min = min;
        this.max = max;
    }

    public int getMinimum(){
        return min;
    }

    public int getMaximum(){
        return max;
    }
}

This will also fix the "easy".equals() problem you'll get when the option passed contains uppercase letters (or misspelled alltogether).

Likewise you can now add another method that calculates the range for your random call: (mediumMax - mediumMin) + 1) + mediumMin.

Naming

What is a "SudokuUtility"? This looks like the actual game to me (somewhat). Are you absolutely sure this isn't a part of your game class?

There's no need to abbreviate noOfCellsToBeGenerated, numberOfCellsToBeGenerated is just fine.

The method noConflict isn't very pleasant because it starts from a negative point of view. Consider hasConflict instead (remember: method names start with a verb because they represent an action).

Magic values

In your nested loops you're iteration to an upper value of 9. What is this value? Where does it come from? What does it mean? If you put it in a variable like amountOfCells (I don't know its actual purpose), it's a lot clearer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.