1

重複の可能性:
数独アルゴリズム、ブルート フォース

数日間、私は数独を解くためのブルート フォース アルゴリズムを書こうとしましたが、私の問題は、アルゴリズムが 100% 機能することは決してないということです。

アルゴリズムは Square クラス、再帰関数にあります。

public abstract class Square {

private Square next;

private Box box;
private Row row;
private Columne columne;

private int value;

Square(int value, Box box, Row row, Columne columne) {
    this.value = value;
    this.box = box;
    this.row = row;
    this.columne = columne;
}

void setNumberMeAndTheRest(Board board) {
    if(getNext() == null) {
        System.out.println("next == null");
        for(int i = 1; i <= board.getDimension(); i++) {
            if(legalValue(i)) {
                setValue(i);
            }
        }
        board.saveSolution();
        return;
    } else {
        if(this instanceof DefinedSquare) {
            getNext().setNumberMeAndTheRest(board);

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

int getValue() {
    return value;
}

void setValue(int value) {
    this.value = value;
}

void setNext(Square next) {
    this.next = next;
}

public Square getNext() {
    return next;
}

/**
 * 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;
}
4

2 に答える 2

2

あなたの問題はここにあると思います

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

legalValue(i) が i の現在の状態に関係なく true を返す場合は、バック トラッキングを行っています。そうでない場合は、バック トラッキングを行っていません。

ほとんどのバックトラッキングがどのように見えるかは、htis のような osmething です

    for(int i = 1; i <= board.getDimension(); i++) {
        if(legalValue(i)) {
            setValue(i);
                // boolean indicating whether solution was found
            if(getNext().setNumberMeAndTheRest(board))
               return true;
            else
               unsetValue(i)
        }
    }

正方形 i が既に設定されているときに legalValue が false を返すかどうかを知るには、さらにコードが必要です

これを試して、私が正しい軌道に乗っているかどうかを確認するか、すべてのコードを投稿してください

    System.out.println("STARTING ITERATION")
    for(int i = 1; i <= board.getDimension(); i++) {

        if(legalValue(i)) {
            System.out.println("GOING " + i)
            setValue(i);
            getNext().setNumberMeAndTheRest(board);
        }
    }
    System.out.println("ENDING ITERATION")

グリッドを埋めてからバックトラックせずに停止する場合、問題は setValue(i) を呼び出してから legalValue(i+1) を呼び出すことであり、値がすでに設定されているためfalse が返されます。その場合、再帰の後に同等の「unset」が必要です

于 2012-04-17T15:01:01.493 に答える
1

アルゴリズムをざっと見てみると、各正方形で可能な値を 1 つだけ試しているように見えます。正当な値を見つけることができないマスに到達すると、あきらめます。バックトラックして、以前に埋められた正方形で代替の正当な値を試すメカニズムが必要です。

例として、ミニ 4x4 パズルを次に示します。

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

あなたのアルゴリズムは、私が知る限り、ここまで到達してから終了します。

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

終了する代わりに、戻って、挿入した 2 つの値のいずれかを変更する必要があります。

于 2012-04-17T14:55:55.050 に答える