CODEWITHSUNDEEP
javaalgorithmsudoku
user3034861
user3034861

Reputation:

Unexpected output when generating a Sudoku grid

I have written the following class to generate a Sudoku grid. I am not able to understand some of the results from the program. Can anyone explain?

public class SudokuUtility {

    static final int max = 8;
    static final int min = 0;
    static final int digitMax = 9;
    static final int digitMin = 0;

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

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

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


    public static int[][] makeAGrid(String option) {

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

        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 (noConflict(grid, row, col, randomNumber)) {
                grid[row][col] = randomNumber;
            } else {
                i = i - 1; // Nullify this iteration
            }
        }

        int zeroCount = 0;

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (grid[i][j] == 0) {
                    zeroCount++;
                }
                System.out.print(grid[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println("No of zeros in the " + option + " puzzle = " + zeroCount + " and noOfCellsGenerated = " + noOfCellsToBeGenerated);

        return grid;
    }

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

The output is:

0  6  0  0  0  1  0  7  0  
0  9  0  4  0  0  0  1  0  
0  8  0  0  3  0  0  0  0  
0  0  0  7  0  0  0  0  0  
9  0  0  8  0  0  0  0  0  
0  7  0  0  6  0  2  0  0  
7  5  0  0  0  0  0  0  9  
8  0  0  0  4  0  0  0  0  
0  1  0  0  7  0  0  6  0  

No of zeros in the hard puzzle = 59 and noOfCellsGenerated = 24

There should be 24 generated numbers. Actually there are 21. Is my logic wrong? But I am pretty sure about the logic. What is missing in my understanding?

Upvotes: 0

Views: 75

Answers (1)

enlait
enlait

Reputation: 616

I have run your code with some added logging and the issue is exactly what I meant in my comment.

If you hit the same cell (row, col) twice, but with a different random value, noConflict returns true and the old value gets overriden.

You should check that the cell is empty in your noConflict method.

Upvotes: 1

Related Questions