How to Generate a -complete- sudoku board? algorithm error

Question

I'm trying to generate a complete (ie, each cell filled with a number) Sudoku-like board. It's for something else that has nothing to do with sudokus, so I am not interested in reaching a sudoku with white squares that can be solved, or anything that has to do with sudokus. Don't know if you know what I mean.

I've done this in java:

private int sudokuNumberSelector(int x, int y, int[][] sudoku) {

    
    boolean valid = true;
    String validNumbers = new String();
    int[] aValidNumbers;
    int squarexstart = 0;
    int squareystart = 0;
    int b = 0;                          // For random numbers
    Random randnum = new Random();
    randnum.setSeed(new Date().getTime());
    
    // Check numbers one by one
    for(int n = 1; n < 10; n++) {
        
        valid = true;
        
        // Check column
        for(int i = 0; i < 9; i++) {
            if(sudoku[i][y] == n) {
                valid = false;
            }
        }
        
        // Check file
        for(int j = 0; j < 9; j++) {
            if(sudoku[x][j] == n) {
                valid = false;
            }
        }
        
        // Check square
        switch (x) {
        case 0: case 1: case 2: squarexstart = 0; break;
        case 3: case 4: case 5: squarexstart = 3; break;
        case 6: case 7: case 8: squarexstart = 6; break;
        }
        
        switch (y) {
        case 0: case 1: case 2: squareystart = 0; break;
        case 3: case 4: case 5: squareystart = 3; break;
        case 6: case 7: case 8: squareystart = 6; break;
        }
        
        for(int i = squarexstart; i < (squarexstart + 3); i++ ) {
            for(int j = squareystart; j < (squareystart + 3); j++ ) {
                if(sudoku[i][j] == n) {
                    valid = false;
                }
            }
        }
        
        // If the number is valid, add it to the String
        if(valid) {
            validNumbers += n;
        }
    }
    
    if(validNumbers.length() != 0) {
                
        // String to int[]
        aValidNumbers = fromPuzzleString(validNumbers);
        
        // By this random number, return the valid number in its position
        Log.d(TAG, "NUMBERS: " + validNumbers.length()); 
        
        // Select a random number from the int[]
        b = randnum.nextInt((aValidNumbers.length));
        
            
        return aValidNumbers[b];

    } else {
        return 0;
    }
}

This method is called from this piece of code:

int[][] sudoku = new int[9][9];

for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sudoku[i][j] = sudokuNumberSelector(i, j, sudoku);
            }
        }

But it is not as easy as it seemed! When the algorithm has generated a part of the board like this one, and the loop is on the cell on bold:

|||164527389|||
|||983416257|||
|||257938416|||
|||719352648|||
|||3256791**0**0|||
|||000000000|||
|||000000000|||
|||000000000|||
|||000000000|||

There are no numbers to put in this cell, because all the numbers according to the rules of sudoku are already on the column, row or square!

It is a nightmare for me. Is there any way to this to work? If not, i guess I have to redo everything as if I were making a Sudoku game.

Answer 1

The problem is that it is not possible to generate a complete board using random numbers in most cases, you have to use backtracking in cases when it is not possibe to fi the next cell. I have once written a sudoku game, so here's the piece of code that generates filled board.

This is the Cell class.

 public class SudokuCell implements Serializable {

    private int value;
    private boolean filled;
    private HashSet<Integer> tried;

    public SudokuCell() {
        filled = false;
        tried = new HashSet();
    }

    public boolean isFilled() {
        return filled;
    }

    public int get() {
        return value;
    }

    public void set(final int number) {
        filled = true;
        value = number;
        tried.add(number);
    }

    public void clear() {
        value = 0;
        filled = false;
    }

    public void reset() {
        clear();
        tried.clear();
    }

    public void show() {
        filled = true;
    }

    public void hide() {
        filled = false;
    }

    public boolean isTried(final int number) {
        return tried.contains(number);
    }

    public void tryNumber(final int number) {
        tried.add(number);
    }

    public int numberOfTried() {
        return tried.size();
    }
 }

Here's the Field class (it's really handy to keep all data in just one object).

 public class SudokuField implements Serializable {

    private final int blockSize;
    private final int fieldSize;
    private SudokuCell[][] field;

    public SudokuField(final int blocks) {
        blockSize = blocks;
        fieldSize = blockSize * blockSize;
        field = new SudokuCell[fieldSize][fieldSize];
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j] = new SudokuCell();
            }
        }
    }

    public int blockSize() {
        return blockSize;
    }

    public int fieldSize() {
        return fieldSize;
    }

    public int variantsPerCell() {
        return fieldSize;
    }

    public int numberOfCells() {
        return fieldSize * fieldSize;
    }

    public void clear(final int row, final int column) {
        field[row - 1][column - 1].clear();
    }

    public void clearAllCells() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j].clear();
            }
        }
    }

    public void reset(final int row, final int column) {
        field[row - 1][column - 1].reset();
    }

    public void resetAllCells() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                field[i][j].reset();
            }
        }
    }

    public boolean isFilled(final int row, final int column) {
        return field[row - 1][column - 1].isFilled();
    }

    public boolean allCellsFilled() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                if (!field[i][j].isFilled()) {
                    return false;
                }
            }
        }
        return true;
    }

    public int numberOfFilledCells() {
        int filled = 0;
        for (int i = 1; i <= fieldSize; ++i) {
            for (int j = 1; j <= fieldSize; ++j) {
                if (isFilled(i, j)) {
                    ++filled;
                }
            }
        }
        return filled;
    }

    public int numberOfHiddenCells() {
        return numberOfCells() - numberOfFilledCells();
    }

    public int get(final int row, final int column) {
        return field[row - 1][column - 1].get();
    }

    public void set(final int number, final int row, final int column) {
        field[row - 1][column - 1].set(number);
    }

    public void hide(final int row, final int column) {
        field[row - 1][column - 1].hide();
    }

    public void show(final int row, final int column) {
        field[row - 1][column - 1].show();
    }

    public void tryNumber(final int number, final int row, final int column) {
        field[row - 1][column - 1].tryNumber(number);
    }

    public boolean numberHasBeenTried(final int number, final int row, final int column) {
        return field[row - 1][column - 1].isTried(number);
    }

    public int numberOfTriedNumbers(final int row, final int column) {
        return field[row - 1][column - 1].numberOfTried();
    }

    public boolean checkNumberBox(final int number, final int row, final int column) {
        int r = row, c = column;
        if (r % blockSize == 0) {
            r -= blockSize - 1;
        } else {
            r = (r / blockSize) * blockSize + 1;
        }
        if (c % blockSize == 0) {
            c -= blockSize - 1;
        } else {
            c = (c / blockSize) * blockSize + 1;
        }
        for (int i = r; i < r + blockSize; ++i) {
            for (int j = c; j < c + blockSize; ++j) {
                if (field[i - 1][j - 1].isFilled() && (field[i - 1][j - 1].get() == number)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean checkNumberRow(final int number, final int row) {
        for (int i = 0; i < fieldSize; ++i) {
            if (field[row - 1][i].isFilled() && field[row - 1][i].get() == number) {
                return false;
            }
        }
        return true;
    }

    public boolean checkNumberColumn(final int number, final int column) {
        for (int i = 0; i < fieldSize; ++i) {
            if (field[i][column - 1].isFilled() && field[i][column - 1].get() == number) {
                return false;
            }
        }
        return true;
    }

    public boolean checkNumberField(final int number, final int row, final int column) {
        return (checkNumberBox(number, row, column)
                && checkNumberRow(number, row)
                && checkNumberColumn(number, column));
    }

    public int numberOfPossibleVariants(final int row, final int column) {
        int result = 0;
        for (int i = 1; i <= fieldSize; ++i) {
            if (checkNumberField(i, row, column)) {
                ++result;
            }
        }
        return result;
    }

    public boolean isCorrect() {
        for (int i = 0; i < fieldSize; ++i) {
            for (int j = 0; j < fieldSize; ++j) {
                if (field[i][j].isFilled()) {
                    int value = field[i][j].get();
                    field[i][j].hide();
                    boolean correct = checkNumberField(value, i + 1, j + 1);
                    field[i][j].show();
                    if (!correct) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public Index nextCell(final int row, final int column) {
        int r = row, c = column;
        if (c < fieldSize) {
            ++c;
        } else {
            c = 1;
            ++r;
        }
        return new Index(r, c);
    }

    public Index cellWithMinVariants() {
        int r = 1, c = 1, min = 9;
        for (int i = 1; i <= fieldSize; ++i) {
            for (int j = 1; j <= fieldSize; ++j) {
                if (!field[i - 1][j - 1].isFilled()) {
                    if (numberOfPossibleVariants(i, j) < min) {
                        min = numberOfPossibleVariants(i, j);
                        r = i;
                        c = j;
                    }
                }
            }
        }
        return new Index(r, c);
    }

    public int getRandomIndex() {
        return (int) (Math.random() * 10) % fieldSize + 1;
    }
}

And finally the function that fills the game board

private void generateFullField(final int row, final int column) {
    if (!field.isFilled(field.fieldSize(), field.fieldSize())) {
        while (field.numberOfTriedNumbers(row, column) < field.variantsPerCell()) {
            int candidate = 0;
            do {
                candidate = field.getRandomIndex();
            } while (field.numberHasBeenTried(candidate, row, column));
            if (field.checkNumberField(candidate, row, column)) {
                field.set(candidate, row, column);
                Index nextCell = field.nextCell(row, column);
                if (nextCell.i <= field.fieldSize()
                        && nextCell.j <= field.fieldSize()) {
                    generateFullField(nextCell.i, nextCell.j);
                }
            } else {
                field.tryNumber(candidate, row, column);
            }
        }
        if (!field.isFilled(field.fieldSize(), field.fieldSize())) {
            field.reset(row, column);
        }
    }
}

The point is that you save the numbers you've already tried for each cell before moving on. If you have to the dead end, you simply need to try another number for the previous cell. If none are possible, erase that cell and step one cell back. Sooner or later you will get it done. (It actuay takes tiny amount of time).

Answer 2

Start out with a solved Sudoko like this:

ABC DEF GHI
329 657 841 A
745 831 296 B
618 249 375 C

193 468 527 D
276 195 483 E
854 372 619 F

432 716 958 G 
587 923 164 H 
961 584 732 I

And then permutate it by switching columns and switching rows. If you only switch within the following groups ABC, DEF, GHI, the Sudoku is still solved.

A permutated version (switching columns):

BCA DFE IGH   
293 675 184 A 
457 813 629 B 
186 294 537 C 

931 486 752 D 
762 159 348 E 
548 327 961 F 

324 761 895 G 
875 932 416 H 
619 548 273 I 

And after some more permutation (switching rows):

BCA DFE IGH   
293 675 184 A 
186 294 537 C 
457 813 629 B 

931 486 752 D 
548 327 961 F 
762 159 348 E 

875 932 416 H 
619 548 273 I 
324 761 895 G