0

まだ数独ソルバーに取り組んでいますが、またトラブルに遭遇しました。数独ソルバーが機能するようになりましたが、非常に「難しい」数独ボードを解こうとすると、スタック オーバーフロー エラーが原因で、ソルバーが可能な解決策がないことを教えてくれます。はい、これらのボードには解決策があることを私は知っています。

私はブルート フォース アルゴリズムを使用しています。正方形 1 (または、必要に応じて [0][0]) から開始し、最初の正当な値を挿入します。次に、次の正方形への再帰呼び出しを行います。私の関数がボード全体を通過しておらず、有効な値が存在しないことが判明した場合、関数は前の正方形に移動し、そこで値をインクリメントしようとします。それが失敗した場合は、さらに後ろに移動します。可能な解決策がない振り出しに終わった場合、終了します。

私のコードがきれいではなく、おそらくまったく効果がないことは認めますが、私はベストを尽くそうとしている 1 年生であることを覚えておいてください。ただし、コードを効果的にする方法についてのコメントは気にしません:)

最終的な事前定義された数のない正方形の場合、ソルバー関数は次のとおりです。

public void fillRemainderOfBoard(Square sender){

    try {

        while(true){
            if(currentPos > boardDimension){
                if(previous != null){
                    this.setNumrep(-1);
                    this.setCurrentPos(1);
                    previous.setCurrentPos(previous.getCurrentPos()+1);
                    previous.fillRemainderOfBoard(this);
                    return;
                } else if(sender == this){
                    this.setCurrentPos(1); 
                } else {
                    break;
                }
            }
            if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){
                currentPos++;
            } else {
                this.setNumrep(currentPos);
                currentPos++;
                break;
            }
        }

        if(this != last){
            next.setNumrep(-1);
            next.fillRemainderOfBoard(this);
        } else {

            return;
        }
    } catch (StackOverflowError e){
        return;
    }
}

私のコードでは、numrep 値は、ボード上の正方形が表す値です。currentPos 変数は、1 から始まり、正方形が表す正当な値に達するまで増加するカウンターです。

事前定義された数の正方形の場合、同じ関数を次に示します。

public void fillRemainderOfBoard(Square sender){
    if((sender.equals(this) || sender.equals(previous)) && this != last){
        System.out.println(next);
        next.fillRemainderOfBoard(this);
    } else if (sender.equals(next) && this != first) {
        previous.fillRemainderOfBoard(this);
    } else {
        System.out.println("No possible solutions for this board.");
    }
}

さて、私の問題は、私が言ったように、関数が数独を非常にうまく解決することです。簡単なもの。多数の事前定義された数字と 1 つの解しかない数独などのトリッキーな数独は、プログラムをスタック オーバーフローに陥らせ、考えられる解がないことを教えてくれます。これは、メモリ管理に関して何か不足していること、または再帰関数で呼び出すオブジェクトを複製するプログラムが不足していることを示していると思いますが、それらを修正する方法がわかりません。

どんな助けでも大歓迎です！私のコードも自由に選んでください。私はまだ学んでいます (ああ、私たちはいつもそうではありませんか?)。

__ _ __ _ _ __ _ _ ____編集_ __ _ __ _ _ __ _ _ _ _ _ _

バックトラックの良いアイデアを思いついた Piotr のおかげで、コードを書き直しました。ただし、数独をまったく解決することはできません。ボードが空の場合でも、39 番目の正方形に到達し、その後ずっと false を返します。これが私の現在のコードです：

public boolean fillInnRemainingOfBoard(Square sender){
    if(this instanceof SquarePredef && next != null){
        return next.fillInnRemainingOfBoard(this);
    } else if (this instanceof SquarePredef && next == null){
        return true;
    }

    if(this instanceof SquareNoPredef){
        currentPos = 1;
        if(next != null){
            System.out.println(this.index);
            for(; currentPos <= boardDimension; currentPos++){
                if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){
                    continue;
                } else {
                    System.out.println("Box has " + currentPos + "? " + thisBox.hasNumber(currentPos));
                    this.setNumrep(currentPos);
                    System.out.println("Got here, square " + index + " i: " + numrep);
                }

                if(next != null && next.fillInnRemainingOfBoard(this)){
                    System.out.println("Returnerer true");
                    return true;
                } else {

                }
            }
        }
        if(next == null){
            return true;
        }
    }
    System.out.println("Returning false. Square: " + index + " currentPos: " + currentPos);
    return false;
}

現在のオブジェクトが最後のオブジェクトかどうかを確認する必要があったため、少し複雑にする必要がありました。したがって、追加の if テスト。ああ、私が boardDimension を使用している理由は、この数独ソルバーが 9 x 9 の数独だけでなく、あらゆる数独を解けるからです :)

私のエラーを見つけることができますか？どんな助けでも大歓迎です！

4

1 に答える 1

1

だからあなたの問題はここにあります：

previous.fillRemainderOfBoard(this);

そしてここ

next.fillRemainderOfBoard(this);

基本的に、スタックに関数呼び出しが多すぎます。これは、何度も前後に移動しているためです。答えが見つかる前に、実際にはどの呼び出しからも戻っていません (または、StackOverflowError :) を取得します)。再帰関数を使用してスタックサイズを増やす代わりに、ループを使用して問題を解決する方法を考えてみてください (ほとんどの場合、ループは再帰ソリューションのパフォーマンスよりも優れています)。わかりましたので、次のようなことができます（疑似コード）：

boolean fillRemainderOfBoard(Square sender){
 if (num_defined_on_start) {
     return next.fillRemainderOfBoard(this);
 } else {
   for (i = 1; i < 9; ++i) {
     if (setting i a legal_move)
        this.setCurrentPos(i);
     else
        continue;
     if (next.fillRemainderOfBoard(this))
       return true;
   }
   return false;
}

スタック サイズは ~81 になります。

于 2013-04-12T23:01:26.877 に答える