Algorytm Sudoku, brutalna siła [zamknięta]

Question

Apr 18, 2012, 09:43 PM

Algorytm Sudoku, brutalna siła [zamknięta]

Próbuję rozwiązać planszę sudoku za pomocą algorytmu brutalnej siły, nie mogę naprawdę uzyskać poprawnego działania tego algorytmu.

Dla każdego wiersza, kolumny i pola tworzony jest obiekt, który zawiera wszystkie kwadraty (komórki) należące do faktycznie kolumny, kwadratu i wiersza, jest to używane w legalValue (), aby sprawdzić, czy wartość może być umieszczona w komórce.

Nie mogę znaleźć struktury, która sprawia, że algorytm działa.

<code>    boolean setNumberMeAndTheRest(Board board) {


    if(getNext() == null) {
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();
    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

        } else {
            for(int i = 1; i <= board.getDimension(); i++) {
                if(legalValue(i)) {
                    setValue(i);

                    if(getNext().setNumberMeAndTheRest(board)) {
                        return true;
                    } else {
                        setValue(i);
                    }
                }
            }
            return false;
        }
    }

    return false;
}
</code>

Oto legalValue (int i);

<code>/**
 * Checks if value is legal in box, row and column.
 * @param value to check.
 * @return true if value is legal, else false.
 */
boolean legalValue(int value) {
    if(box.legalValue(value) && row.legalValue(value) && columne.legalValue(value)) {
        return true;
    }
    return false;
}
</code>

<code>**4x4 Sudoku board INPUT**

0 2 | 1 3
0 0 | 0 4
---------
0 0 | 0 1
0 4 | 3 2

**Expected OUTPUT**

4 2 | 1 3
3 1 | 2 4
---------
2 3 | 4 1
1 4 | 3 2

**Actually OUTPUT**

4 2 | 1 3
2 4 | 3 4
---------
3 0 | 0 1
0 4 | 3 2
</code>

Dodano resetowanie tablicy

<code>boolean setNumberMeAndTheRest(Board board) {

    Board original = board;

    if(getNext() == null) { 
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();

    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

        } else {
            for(int i = 1; i <= board.getDimension(); i++) {
                if(legalValue(i)) {
                    setValue(i);

                    if(getNext().setNumberMeAndTheRest(board)) {
                        return true;
                    } else {
                        setValue(i);
                    }
                }
            }
            board = original;
            return false;
        }
    }
    board = original;
    return false;
}
</code>

Ona jest rozwiązaniem po długim czasie: D

<code>boolean setNumberMeAndTheRest(Board board) {

    if(next == null) {
        board.saveSolution();
        return true;
    }

    if(this instanceof DefinedSquare) {
        return next.setNumberMeAndTheRest(board);
    }

    for(int i = 1; i <= board.getDimension(); ++i) {
        if(legalValue(i)) {
            setValue(i);

            if(next.setNumberMeAndTheRest(board)) {
                return true;
            }
        }
    }
    setValue(0);
    return false;
}
</code>