Sudoku-Solver - Backtracking

[Kenta1561]

Hallo,

ich versuche gerade einen Sudoku-Solver (4x4) nach dem Backtracking-Prinzip (https://en.wikipedia.org/wiki/Sudoku_solving_algorithms) zu programmieren, jedoch habe ich da eine Problemstelle:

package main.java;

import java.util.ArrayList;
import java.util.Random;

public class Creator {

    int copy[][];
    int number;

    private void create() {
        int[][] sudokuArray = new int[4][4];
        sudokuArray[0][0] = 1;
        sudokuArray[1][1] = 2;
        sudokuArray[2][1] = 1;
        sudokuArray[2][0] = 4;
        sudokuArray[3][2] = 1;
        sudokuArray[0][3] = 3;
        sudokuArray[2][3] = 2;
        copy = sudokuArray;
        Random rand = new Random();
        for(int x = 0; x < 4; x++) {
            for(int y = 0; y < 4; y++) {
                number = rand.nextInt(4) + ;
                if(copy[x][y] == 0) {
                    while(true) {
                        if(rowCheck(y) & columnCheck(x) & boxCheck(x,y)) {
                            copy[x][y] = number;
                            break;
                        } else {
                            //?
                        }
                    }
                }
            }
        }
    }

    private boolean rowCheck(int y) {
        boolean isValid = true;
        for(int a = 0; a < 4; a++) {
            if(copy[a][y] == number) {
                isValid = false;
            }
        }
        return isValid;
    }

    private boolean columnCheck(int x) {
        boolean isValid = true;
        for(int a = 0; a < 4; a++) {
            if(copy[x][a] == number) {
                isValid = false;
            }
        }
        return isValid;
    }

    private boolean boxCheck(int x, int y) {
        boolean isValid = true;
        int box = -1;
        if(x < 2) {
            if(y < 2) {
                box = 0;
            } else {
                box = 2;
            }
        } else {
            if(y < 2) {
                box = 1;
            } else {
                box = 3;
            }
        }
        ArrayList<Integer[]> toCheck = new ArrayList<>();
        switch(box) {
            case 0:
                toCheck.add(new Integer[]{0,0});
                toCheck.add(new Integer[]{0,1});
                toCheck.add(new Integer[]{1,0});
                toCheck.add(new Integer[]{1,1});
                break;
            case 1:
                toCheck.add(new Integer[]{2,0});
                toCheck.add(new Integer[]{2,1});
                toCheck.add(new Integer[]{3,0});
                toCheck.add(new Integer[]{3,1});
                break;
            case 2:
                toCheck.add(new Integer[]{0,2});
                toCheck.add(new Integer[]{0,3});
                toCheck.add(new Integer[]{1,2});
                toCheck.add(new Integer[]{1,3});
                break;
            case 3:
                toCheck.add(new Integer[]{2,2});
                toCheck.add(new Integer[]{2,3});
                toCheck.add(new Integer[]{3,2});
                toCheck.add(new Integer[]{3,3});
                break;
            default:
                System.exit(1);
                break;
        }
        for(Integer[] intArray : toCheck) {
            if((intArray[0] != x) & (intArray[1] != y)) {
                if(copy[intArray[0]][intArray[1]] == number) {
                    isValid = false;
                }
            }
        }
        return isValid;
    }

    public static void main(String[] args) {
        Creator creator = new Creator();
        creator.create();
    }

}

Also zunächst muss ich zugeben, meine checkBox()-Methode scheint nicht ganz optimal zu sein, hätte man vielleicht kürzer und schlauer zusammenfassen können.
Darum geht es aber eigentlich gar nicht. Um die create()-Methode nochmal zusammenzufasen: Zunächst mache ich ein zweidimensionales Integer-Array und trage dort die vorgegebenen Zahlen ein. Danach kopiere ich dann mein Integer-Array in copy. Und dann soll ja schließlich eigentlich nur eine zufällige Zahl zwischen 1 und 4 generiert werden und wenn das Feld bei x und y leer ist, soll die Zahl eingetragen werden. Wenn ich dann aber mit x bei 3 bin, also ganz rechts im Sudoku, und egal welche Zahl bei rand generiert wird, einer der Check-Methoden (checkBox(), checkRow(), checkColumn()) false zurückgibt, dann kommt man ja zu else, welches nichts enthält und man steckt in der Endlosschleife while(true). Und genau das soll ja nicht passieren, was passieren soll, ist, dass wenn alle Zahlen überprüft worden sind und die Zahlen nicht gültig sind, soll die ganze Reihe gelöscht und nochmal probiert werden.

Also, meine Frage ist: Wie kann ich überprüfen, ob bei einer Random-Zahl alle Zahlen überprüft worden sind und somit die Reihe gelöscht werden soll?

LG
Kenta1561

 

[Java20134]

Erstelle doch für ein Feld eine Set und kontrolliere, ob die Größe des Sets bei neun liegt! Aber da gibt es bestimmt noch eine bessere Idee!

 

[thecain]

Wieso random? zähl doch einfach von 1-4 hoch. zudem müsste der algorithmus mMn rekursiv sein, damit das Grid auch sauber (einfach) zurückgesetzt werden kann. Dann kann das while true raus und die beiden Ifs so machen wie es auch auf wikipedia steht