How to Generate a -complete- sudoku board? algorit

问题:

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.

Thanks in advance.

回答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).

回答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 

回答3:

Your problem is you are using Strings. Try a recursive algorithm using integers. This algorithm will be useful for a sudoku of any size. While choosing random numbers within each call does work, it'll take much longer. If you choose a set of random numbers to go through if the next cell doesnt work, then you will not use the same number again. This algorithm will create a unique puzzle every time.

public class Sudoku {
    //box size, and game SIZE ==> e.g. size = 3, SIZE = 9
    //game will be the game
    private int size, SIZE;
    private int[][] game;

    public Sudoku(int _size) {
        size = _size;
        SIZE = size*size;
        game = generateGame();
    }

    //This will return the game
    private int[][] generateGame() {
        //Set everything to -1 so that it cannot be a value
        int[][] g = new int[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++)
            for(int j = 0; j < SIZE; j++)
                g[i][j] = -1;

        if(createGame(0, 0, g))
            return g;
        return null;
    }

    //Create the game
    private boolean createGame(int x, int y, int[][] g) {
        //An array of integers
        Rand r = new Rand(SIZE);

        //for every random num in r
        for(int NUM = 0; NUM < size; NUM++) {
            int num = r.get(NUM);

            //if num is valid
            if(isValid(x, y, g, num)) {
                //next cell coordinates
                int nx = (x+1)%SIZE, ny = y;
                if(nx == 0) ny++;

                //set this cell to num
                g[x][y] = num;

                //if the next cell is valid return true
                if(createGame(nx, ny, g)) return true;

                //otherwise return false
                g[x][y] = -1;
                return false;
            }
        }
        return false;
    }

    private boolean isValid(int x, int y, int[][] g, int num) {
        //Rows&&Cols
        for(int i = 0; i < SIZE; i++)
            if(g[i][y] == num || g[x][i] == num) return false;
        //Box
        int bx = x - x%size;, by = y - y%size;
        for(int i = bx; i < bx + size; i++) {
            for(int j = by; j < by + size; j++) {
                if(g[i][j] == num)return false;
            }
        }
        return true;
    }
}

public class Rand {
    private int rSize;
    private int[] r; 
    public Rand(int _size) {
        rSize = _size;
        r = new int[size];
        for(int i = 0; i < rSize; r++)r[i] = i;
        for(int i = 0; i < rSize*5; r++) {
            int a = (int)(Math.random()*rSize);
            int b = (int)(Math.random()*rSize);
            int n = r[a];
            r[a] = r[b];
            r[b] = n;
    }
    public void get(int i) {
        if(i >= 0 && i < rSize) return r[i]; return -1;
    } 
}

回答4:

You're going to have to implement a backtracking algorithm.

• For each of the 81 locations, generate the set 1 through 9.
• Repeat until solved
  • Solve one location. Pick one number from the set.
  • Remove that number from all the sets in the same row, column, and square.
  • If a conflict arises, backtrack to a known good position, and solve a different location.

You will probably have to use recursive functions so that you can backtrack.

回答5:

You have at least few ways to do that, but usually you will need recurrence / backtracking. It would be great to have the solver also, just to check if partly filled puzzle has solution (and the unique one - for stoping criteria - if you want the real sudoku).

While performing backtracking / recurrence you will need:

• to randomly select available empty cell (you can optimize this step by measuring digidts still free on the given cell, and then sorting)

• to randomly select still available digit in that cell

• you fill the cell and check if the solution exists, if yes - go further, if not - perform the step back.

Starting points: - starting with completely empty puzzle - starting with partially filled puzzle - starting with solved puzzle (there are a lot of transformations not changing the solution existence, but making the puzzle different - i.e.: reflection, rotation, transposition, segment swapping, columns / rows swapping within segments, permutation, etc.)

I was recently using the Janet Sudoku library which provides solver, generator and puzzle transformation methods.

Janet Sudoku website

Please refer to the below source codes available on the GitHub

Sudoku Solver

Sudoku Generator

Sudoku Transformations

Library usage is pretty simple, ie:

SudokuGenerator g = new SudokuGenerator();
int[][] puzzle = g.generate();
SudokuSolver s = new SudokuSolver(puzzle);
s.solve();
int[][] solvedPuzzle = s.getSolvedBoard();

Best regards,

回答6:

Just generate some random number between 1 to 9 and see it it fits the given cell[i][j] it promises you a new set of numbers every time as every cell number is generated randomly based on the current system time .

public int sudokuNumberSelector(int i, int j, int[][] sudoku) {
    while (true) {
        int temp = (int) ((System.currentTimeMillis()) % 9) + 1;//Just getting some random number
        while (temp < 10) {
        boolean setRow = false, setColomn = false, setBlock = false;
            for (int a = 0; a < 9; a++) {
                if (sudoku[a][j] == temp) {
                    setRow = true;
                    break;
                }
            }

            for (int a = 0; a < 9; a++) {
                if (sudoku[i][a] == temp) {
                    setColomn = true;
                    break;
                }
            }
            for (int a = i - (i % 3); a < i - (i % 3)+ 3; a++) {
                for (int b = j - (j % 3); b < j - (j % 3)+3; b++) {
                    if (sudoku[a][b] == temp) {
                        setBlock = true;
                        a = 3;
                        b = 3;
                    }
                }
            }
            if(setRow | setColomn | setBlock == false){
                return temp;
            }
            temp++;
        }
    }
}