再帰的な騎士ツアー（Java宿題）の変数の宣言を修正しました

Question

私の学年の最後のプロジェクト（CS学生としての私の最初の年）のバグを見つけられません。私は騎士のツアーの問題の私の実装で再帰に立ち往生しています。 https://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

具体的には、私の問題は、コードのこのセクションにある（ライン265から始まる）：findTourの終わりを（）である

else{ 
    for(int i = 0; i < numberOfPossibleNextMoves; i++){ 
     Cell nextCellToMoveTo = candidateNextMoves.get(i); 

     int currentRowStorage = currentRow; 
     int currentColumnStorage = currentColumn; 
     currentRow = nextCellToMoveTo.row; 
     currentColumn = nextCellToMoveTo.column; 

     listOfMoves.add(nextCellToMoveTo); 
     chessBoard[currentRow][currentColumn] = 1; 
     currentMoveNumber++; 

     boolean tourFound = findTour(); 

     if(tourFound){ 
     return true; 
      } 
      else{ // Undo the last move just made 
       backtrackCount++; 
       chessBoard[currentRow][currentColumn] = -1; 
       currentRow = currentRowStorage; 
       currentColumn = currentColumnStorage;                            
       listOfMoves.remove(nextCellToMoveTo); 
       currentMoveNumber--;   
      } 
     } 
     return false; 

ここで問題となっているファイルです。これは、現在の四角形（別名セル）から可能なすべての移動をテストし、新しく移動された四角形からツアーを完了できる場合にtrueを返すプログラムの一部です。正方形からツアーを完了できない場合は、elseに移動し{移動を元に戻します。これは私が思うところです。

今のところ、コードセットが上記のように設定されているため、プログラムは無限ループでトラップされます。 else{声明のこの部分の

をメモ：

chessBoard[currentRow][currentColumn] = -1; 
currentRow = currentRowStorage; 
currentColumn = currentColumnStorage; 

コードのこの部分は、それが（1 =が訪問した）未訪問であることを意味する-1にチェス盤の広場を、変更します。上のように、新しい移動のcurrentRowとcurrentColumnは、正方形をunvisitedに戻すために使用されます。これらの値は、currentRowStorageとcurrentColumnStorageを使用して以前のジャンプ値にリセットされます。

私は

currentRow = currentRowStorage; 
currentColumn = currentColumnStorage; 
chessBoard[currentRow][currentColumn] = -1; 

にコードを変更すると、それは成功したもので1/3最後または移動は、単にいくつかの正方形の間で前後にジャンプしているのように間違ったツアーを見つけました。これは、リセット手順を正しく処理しないと想定されると予想される。

私の問題は、変数を宣言している場所が原因であると思われます。これは私の最初の複雑な再帰的な問題で、currentRow/ColumnとcurrentRow/ColumnStorageの間の切り替えを正しく処理しているかどうかはわかりません。私はそれらを多かれ少なかれローカルに宣言すべきですか？ここで

は、プロジェクトを記述するページです。ここでhttp://cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

は、要件の該当するセクションです：

ツアーが完了していない場合は、findTourはの（おそらく 空の）リストを決定します騎士の 現在のセルから到達可能な空きセルを見つけ、ローカルに宣言されたリスト の変数candidateNextMovesにこのリストを格納します。このリスト変数 をメソッドに対してローカル宣言することが重要です。このリストが空の場合、 現在の部分ツアーを拡張する方法がないため、findTourは falseを返します。リストが空でない場合、findTourは ツアーを次のようにリスト上の移動ごとに延長しようとします。それはリスト を繰り返し、リストの各セルはそのセルに次の移動を行います。 L（ツアーの移動リスト）、B（ の2D配列（visited、not visisted））、currRow、およびcurrColを に変更するとこの動きが反映されます。次に、再帰的に自身を呼び出し、 呼び出しの結果を局所的に宣言されたブール変数に割り当てます。 は「成功」と名付けられます。成功がtrueに設定されている場合、findTourは を返します。成功した場合は、findTourは直前の移動を取り消します。または を「取り戻し」、候補nextMovesの次の移動を試みます。 は、に初期化され、移動の取り消しごとにインクリメントされる静的int変数backtrackCountを保持します。

メモ：私は、「成功」ではなく「ブーリアン」という名前の「tourFound」を呼び出しました。

Answer 1

しばしば無限の再帰の場合と同様に、最初に確認する場所は、あなたがそれから抜け出すことを計画する方法のためのあなたの状態です。

if(currentMoveNumber == numberOfMovesOnBoard){ 
    return true; 
    } 

この場合、あなただけ逃げることができるnumberOfMovesOnBoardに達することからcurrentMoveNumberを妨げる何かのためにあなたのアルゴリズムと初期化を確認してください。

ヒント：あなたはあなたの再帰的なメソッドを入力する前に、あなたの開始条件は何ですか？