Comment réparer cette erreur de débordement de pile?

Question

J'ai donc ce que je pense être un bon code pour un solveur de sudoku en java mais j'ai besoin d'aide avec cette méthode. Il me donne un débordement de pile quand je l'incorpore dans une méthode principale. Le problème est que ma méthode ne sait pas comment faire demi-tour et réparer ses erreurs. J'ai besoin d'un drapeau booléen (celui qui, contrairement à celui utilisé dans le code ci-dessous, fonctionne de préférence) ou quelque chose pour le faire savoir quand il devrait revenir et quand il peut encore aller de l'avant et continuer à résoudre le jeu. Merci pour toute aide que vous pouvez donner

public void play(int r, int c){//this method throws the StackOverflowError 
    if(needAtLoc(r,c).size()==9){ 
     int num=1+generator.nextInt(9); 
     setCell(r,c,num,this); 

    if(c<8){ 
    System.out.println(this);/////////////// 
    play(r, c+1); 
    } 
    else{ 
    play(r+1, 0); 
    } 
} 
else{ 
    if(needAtLoc(r,c).size()==0){//no possible moves THIS IS THE PROBLEM LINE!!! 
    if(c>0){ 
     play(r, c-1);//play last cell, in column to left 
    } 
    else{ 
     if(r==0){ 
     play(r,c);//first square, so must play again (can't go back) 
     } 
     else{ 
     play(r-1, 8);/*first cell of row so must go to previous row and 
        the end column*/ 
     } 
    } 
    } 

    else{//if there are possible moves 
    int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size())); 
    setCell(r,c,num,this);//set the value of the cell 
    System.out.println(this);////////////// 
    if(r==8 && c==8){//the end of the cell has been reached so must end recursive call 
     return; 
    } 
    else{ 
     if(c<8){ 
     play(r, c+1);//normal, next cell 
     } 
     else{ 
     play(r+1, 0);/*last cell in row so we go to next one 
        in the first column ("return" button)*/ 
     }  
    } 
    } 
} 
} 

Answer 1

Plutôt que de résoudre cela pour vous, je ferais quelques suggestions pour y remédier. 9 heures est amplement suffisant.

1) Votre code est difficile à lire. Essayez de l'espacer un peu. Donnez à vos variables des noms significatifs qui soient clairs (cela vous aide, vous et d'autres personnes, à lire votre code). Vous avez peut-être fait une erreur simple et le code propre rendra ces plus faciles à repérer. Essayez de le diviser en plus petites méthodes car cela le rendra plus lisible et plus facile à maintenir.

2) Les débordements de pile sont causés (en général je crois) lorsque vous faites trop d'appels de méthode imbriqués et sont typiques du code récursif. Par conséquent, faites votre récursivité claire. Assurez-vous que vous avez un cas de base qui se terminera.

Désolé de ne pas vous donner "la réponse" mais comme cela ressemble à des devoirs, je pense qu'il ya plus de valeur à apprendre à résoudre vous-même. J'espère que cela semble juste.

Answer 2

Je pense que vous appelez récursivement play(). Essayez de vérifier s'il y a une condition d'arrêt à votre appel récursif.

Answer 3

Votre code lance une exception de flux de pile car vous n'atteignez jamais une condition de fin qui termine votre récursivité, ou du moins il n'est pas évident de voir une condition de fin de récursion en lisant votre code.

Votre code n'est pas bien structuré, donc vous aurez du mal à le déboguer. Essayez de restructurer votre code, cela vous aidera à repenser le problème. Aussi, s'il vous plaît commenter votre code :)

Answer 4

Je suis d'accord avec Tom, mais voici un indice.

Il n'y a pas de condition et de retour pour mettre fin aux appels récursifs.

Answer 5

Vous appelez récursivement le jeu sans jamais revenir et il semble que vous initialisez un nouvel ensemble de variables chaque fois en haut de la fonction.

Essayez de séparer l'initialisation de la partie récursive. Vous avez également besoin d'une condition de fin claire pour mettre fin à la récursivité, par ex. (if (isBoardFilled() == true)) renvoie.

Structurez-le de manière à ce que vous ajoutiez un numéro à la carte, le tester par rapport aux contraintes et si cela réussit, ajoutez un autre numéro (recurse) ou backtrack en supprimant le dernier numéro et réessayez.

Answer 6

J'ai réussi à être plus concis et plus clair, mais il ne fonctionne toujours pas ... J'ai juste besoin d'une poussée sur le bord et je suis libre à la maison.Je l'ai largué tant d'heures gaspillées dans ce projet:

public ArrayList<Integer> needAtLoc(int r, int c){ 
    int bc=c/3;//the column within the SudokuBoard 
    int blc; 

    /*The two posibilities for the column within each SudokuBlock:*/ 
    if(c>=0 && c<3) { 
     blc=c; 
    } 
    else { 
     blc=c%3; 
    } 
    int br=r/3; //the row within the SudokuBoard 
    int blr; 

    /*The two possiblities for the row within each SudokuBlock:*/ 
    if(r>=0 && r<3) { 
     blr=r; 
    } else { 
     blr=r%3; 
    } 
    ArrayList<Integer> needR = new ArrayList<Integer>(); 
    needR=checkR(r);// 
    needR.trimToSize(); 
    System.out.println(needR);////////////// 
    ArrayList<Integer> needC=new ArrayList<Integer>(); 
    needC=checkC(c); 
    needC.trimToSize(); 
    System.out.println(needC);///////////// 
    ArrayList<Integer> needBl=new ArrayList<Integer>(); 
    needBl=this.board[br][bc].updateMissing(); //that method updates and returns an ArrayList 
    needBl.trimToSize(); 
    ArrayList<Integer> poss=new ArrayList<Integer>(); 
    poss.clear(); 
    for(Integer e: needBl){ 
     if(needC.contains(e) && needR.contains(e)){ 
      poss.add(e); 
     } 
    } 

    return poss; 
} 

//this method throws the StackOverflowError 
public void play(int r, int c){ 
    int bc=c/3; //the column within the SudokuBoard 
    int blc; 
    /*The two posibilities for the column within each SudokuBlock:*/ 
    if(c>=0 && c<3) { 
     blc=c; 
    } else { 
     blc=c%3; 
    } 
    int br=r/3; //the row within the SudokuBoard 
    int blr; 

    /*The two possiblities for the row within each SudokuBlock:*/ 
    if(r>=0 && r<3) { 
     blr=r; 
    } else { 
     blr=r%3; 
    } 
    if(needAtLoc(r,c).size()==9){ 
     int num=1+generator.nextInt(9); 
     this.board[br][bc].setValue(blr, blc, num); 
     if(c<8){ 
      System.out.println(this);/////////////// 
      play(r, c+1); 
     } else{ 
      play(r+1, 0); 
     } 
    } else{ 
     if(needAtLoc(r,c).size()==0){ //no possible moves 
      if(c>0){ 
       bc=(c-1)/3; 
       if(c>0 && c<4) { 
        blc=c-1; 
       } else { 
       blc = (c-1) % 3; 
      } 
     this.board[br][bc].setValue(blr, blc, 0); 
     play(r, c-1); 
    } 
    else{ 
     blc=0; 
     bc=0; 
     if(r==0){ 
     blr=0; 
     br=0; 
     this.board[br][bc].setValue(blr, blc, 0); 
     play(r,c); 
     } 
     else{ 
     br=(r-1)/3; 
     if(r>0 && r<4) {blr=r-1;} 
     else {blr=(r-1)%3;} 
     this.board[br][bc].setValue(blr, blc, 0); 
     play(r-1, 8); 
     } 
    } 
    } 

    else{//if there are possible moves 
     int num=needAtLoc(r,c).remove(generator.nextInt(needAtLoc(r,c).size())); 
     this.board[br][bc].setValue(blr, blc, num); 
     System.out.println(this);////////////// 
     if(r==8 && c==8){ 
     return; 
     } 
     else{ 
     if(c<8){ 
      play(r, c+1); 
     } 
     else{ 
      play(r+1, 0); 
     }  
     } 
    } 
    } 
} 

Answer 7

Je pense que votre problème est là que vous avez:

if(r==0) 
{ 
    play(r,c);//first square, so must play again (can't go back) 
} 

C'est parce que vous ne semblez pas modifier tout état ici et vous passez les mêmes valeurs qui vous ont fait arriver à cette étape en premier lieu. On dirait une récursion infinie pour moi.

Veuillez également aligner votre code correctement car il est trop difficile à lire lorsqu'il est mal aligné et peut-être fournir quelques indices sur ce que font les autres méthodes. Bonne chance!