Home > Software engineering >  Java: Sudoku Array not Filling
Java: Sudoku Array not Filling

Time:06-07

I've been trying to build a sudoku, starting with a 9x9 array that ensures no numbers in a given column nor row are the same (ie sudoku without the 3x3 boxes). I've set my code as seen below, but I keep running into a runtime error that I think stems from the do-while statement where the array won't finish filling. However, if I add 10 to the new randomized number (within the do-while statement) the array will finish filling. I've also created a lengthy "check" method that checks whether the current cell is the same as any of the others in that column or row and returns true only if the number is original. I have not included that method for simplicity. Is there something I'm missing?

import java.util.Random;

public class S9x9 {

    public static void main (String[] args){
        int [][] nines = new int [9][9];
        Random rand = new Random();

        for (int i = 0; i < nines.length; i  ) {
            for (int j = 0; j < nines.length; j  ) {
                nines[i][j] = rand.nextInt(9)   1;
                if (!(check(nines,i,j))) {
                    do
                        nines[i][j] = rand.nextInt(9)   1;
                    while (!(check(nines, i, j)));
                }
                System.out.print(nines[i][j]   " ");
            }
            System.out.print("\n");
        }
    }
}

CodePudding user response:

Your algorithm will end up in a deadlock quite soon. Suppose you have this:

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

There is no valid number to put in the last place. I suggest you change your algorithm to weed out all invalid numbers before using random generation. If there are zero candidates, you have to backtrack.

CodePudding user response:

The problem is that you can deadlock yourself when you don't use any backtrack algorithm in finding a sudoku solution. Assume your two for() loops have already found the following grid:

xxx xxx x1x
xxx xxx x2x
xxx xxx x3x

xxx xxx x4x
567 891 2?.
... ... ...

... ... ...
... ... ...
... ... ...

The place with the ? marker, where your current i and j values are, cannot have any valid number since all the digits are already "used". Check other questions like How to solve Sudoku by backtracking and recursion? on how backtrack works for sudokus.

  • Related