Dichiarazione corretta delle variabili nel tour ricorsivo dei cavalieri (compiti a casa Java)

Question

Ho difficoltà a trovare il bug nel mio codice per il mio ultimo progetto dell'anno scolastico (il mio primo anno da studente CS). Sono bloccato sulla ricorsione nella mia implementazione del problema del tour dei cavalieri. Ecco il file in questione: https://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

In particolare, il mio problema è con questa sezione di codice (a partire da linea 265):

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; 

che è la fine di findTour(). Questa è la parte del programma che mette alla prova tutte le possibili mosse dal quadrato corrente (ovvero le celle), restituendo true se il tour può essere completato dal nuovo spostato in piazza. Se il tour non può essere completato dal quadrato, entra nel else {e annulla la mossa. Questo è dove il problema è penso.

In questo momento, con il codice impostato come sopra, il programma viene intrappolato in un loop ricorsivo infinito.

Prendere nota di questa parte della dichiarazione else{:

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

Questa parte del codice modifica la piazza di scacchiera a -1, il che significa che è non visitato (1 = visitati). Come sopra, la corrente corrente e la colonna corrente della nuova mossa vengono utilizzate per riportare il quadrato a non visitato. Questi valori vengono quindi reimpostati ai valori dei salti precedenti utilizzando currentRowStorage e currentColumnStorage.

Se cambio il codice per

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

non ne trova un tour non corretta in cui l'ultimo 1/3 o così delle mosse sono semplicemente saltando avanti e indietro tra alcune piazze. Questo sarebbe prevedibile dato che non gestisce correttamente la procedura di reset.

Sospetto che il mio problema sia dovuto a dove sto dichiarando le mie variabili. Questo è il mio primo problema ricorsivo complesso e non sono sicuro se sto gestendo correttamente il passaggio tra currentRow/Column e currentRow/ColumnStorage. Devo dichiararli più o meno localmente?

Ecco la pagina che descrive il progetto: http://cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

Ecco sezione del requisiti:

Se il tour non viene completata, quindi findTour determina l'elenco (eventualmente vuoto) di celle libere che sono raggiungibili dalla cella corrente del cavaliere e memorizza questo elenco in una variabile elencata localmente, candidateNextMoves. È fondamentale che questa variabile di lista sia dichiarata locale al metodo. Se questa lista è vuota, non c'è il modo per estendere il tour parziale corrente, quindi findTour dovrebbe restituire false. Se la lista non è vuota, findTour prova ad estendere il tour ad ogni mossa dell'elenco come segue. Si itera sopra l'elenco, e per ogni cella dell'elenco fa la prossima mossa a quella cella, aggiornando tutto di L (l'elenco delle mosse nel tour), B (l'array 2D di lo stato della scheda (visitato, non visitato)), currRow e currCol a riflettono questa mossa. Quindi chiama se stesso in modo ricorsivo, assegnando il risultato della chiamata a una variabile booleana dichiarata localmente, che è possibile assegnare a "successo".Se il successo è assegnato true, findTour restituisce true. Se il successo è falso, findTour annulla la mossa appena fatta, o "backtracks", e prova la prossima mossa di candidateNextMoves. manterrà una variabile int statica, backtrackCount, che viene inizializzata da a 0 e incrementata per ogni annullamento di una mossa.

Una nota: ho chiamato il mio "tourFound" booleano invece di "successo".

Answer 1

Come spesso accade con la ricorsione infinita, il primo posto da verificare è la tua condizione per come pensi di uscirne. In questo caso, si può sfuggire solo se

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

Controllare il vostro algoritmo e l'inizializzazione di qualcosa che avrebbe impedito di raggiungere currentMoveNumber numberOfMovesOnBoard.

Suggerimento: quali sono le condizioni iniziali prima di immettere il metodo ricorsivo?