なぜ私のアルゴリズムはstackoverflow例外を返すのですか？

Question

ランダムな（0と2の間の）数で二次元配列を塗りつぶすアルゴリズムを行う必要があります。唯一の条件は、同じ数を水平方向と垂直方向に3回以上持つことができることです。例

[0,0,1,2,1 
0,1,2,1,2 
1,2,0,1,0] 

については は

[0,0,0,2,1 
0,1,2,1,2 
1,2,0,1,0] 

または

[0,0,1,2,1 
0,1,1,1,2 
1,2,1,1,0] 

が間違ってokです。

public class CandyHelper { 

    private final int minimumChainLength = 3; 
    private final int searchChainSize = 3; 

    public Candy[][] randomInit(int rowCount, int columnCount) { 
     Candy[][] map = new Candy[rowCount][columnCount]; 
     for (int row = 0; row < rowCount; ++row) { 
      for (int column = 0; column < columnCount; ++column) { 
       // Fill square with random candy. 
       Random rand = new Random(); 
       int value = rand.nextInt(3); 
       Candy candy = new Candy(); 
       candy.setType(value); 
       map[row][column] = candy; 
      } 
     } 

     if (findHint(map)) { 
      //System.out.println("Winning conditions"); 
      map = null; 
      map = randomInit(rowCount, columnCount);   
     } else { 
      System.out.println("no wining"); 
     } 

     return map; 
    } 

    // Function which searches for match of at least `MinimumChainLength`. 
    private boolean findHint(Candy[][] map) { 
     int rowCount = map.length; 
     int columnCount = map.length; 

     List<Candy> hintMove = new ArrayList<Candy>(); 

     // Search rows. 
     for (int row = 0; row < rowCount; ++row) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < columnCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[row][chainStart]); 
       for (int nextInChain = chainStart + 1; nextInChain < columnCount; ++nextInChain) { 
        if (map[row][nextInChain].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[row][nextInChain]); 
        } else { 
         break; 
        } 
       }   
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // Search columns. 
     for (int column = 0; column < columnCount; ++column) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < rowCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[chainStart][column]); 
       for (int nextInChain = chainStart + 1; nextInChain < rowCount; ++nextInChain) { 
        if (map[nextInChain][column].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[nextInChain][column]); 
        } else { 
         break; 
        } 
       } 
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // No chain was found, so clear hint. 
     hintMove.clear(); 
     return false;  
    } 

} 

と私のPOJO：

だからここに私のアルゴリズムである

public class Candy { 
    private int type; 

    public int getType() { 
     return type; 
    } 

    public void setType(int type) { 
     this.type = type; 
    } 

    @Override 
    public String toString() { 
     return "Candy{" + "type=" + type + '}'; 
    } 

} 

私は、スタックオーバーフローエラーを取得を開始10×10の配列から開始します。 修正するにはどうすればよいですか？

ありがとうございます。

Answer 1

あなたの問題は、この行です：

map = randomInit(rowCount, columnCount); 

は、基本的にあなたが再帰的にrandomInitを起動しようとしているfindHintがtrueを返すたびに。これは、FindHintがtrueを返す確率が大きければ大きいほど、スタックオーバーフローの可能性が高くなることを意味します。あなたのケースでは、グリッドを大きくするほど、FindHintがtrueを返す確率が高くなります。サイズ10では、stackoverflowで終わることはほぼ確実です。

私はすべて正直なのですが、マップを返すのではなく、ここでrandomInitをなぜ呼び出すのかは分かりません。

Answer 2

findHint()がtrueの場合は、randomInit()というコードを実行していないと思います。 findHint()のコードには何も問題はありません（いくつかのパフォーマンスの調整を除けば - たとえば、そこにいくつあるかを数えるだけのマッチのリストを作成する必要はありません）が、おそらくこの問題に遭遇するだけです10x10のグリッド上に表示されます。 3種類しかないオブジェクトの10x10グリッドは、連続して3つある可能性が非常に高く、可能性としては、randomInit()がスタックオーバーフローを起こすのに十分な時間を呼び出すことになります。

私は100％あなたが望むものを確信していません。randomInit() Nのセットがなくなるまでランダムなグリッドを生成したい場合は、グリッド生成コードを別のメソッド（generate()と呼ぶ）に入れてから、randomInit()をwhileループで呼び出すことをお勧めします。

boolean setFound; 
do { 
    map = generate(rowCount, columnCount); 
    setFound = findHint(map); 
} while (setFound);