Sudoku - Rekursives Zurückverfolgen möglich-Lösungs-Zähler

Question

Ich arbeite an einem kleinen persönlichen Sudoku und versuche es zu erweitern.

Bis jetzt habe ich den "Solve" Teil funktioniert, mit einer rekursiven Backtracking-Methode, die wahr zurückgibt, wann immer es gelingt, die Rekursion zu lösen.

Jetzt versuche ich einen einzigartigen Solution Board Generator zu bauen, und ich habe ziemlich viele Informationen online gefunden, wie es implementiert werden kann.

Allerdings kämpfe ich im ersten Schritt, der mein boolescher rekursiver Backtracking-Algorithmus ist, in einen rekursiven Algorithmus, der die Anzahl möglicher Lösungen festhält. Dies ist wichtig um zu überprüfen, ob mein generiertes Board eindeutig ist.

Bei einer größeren Notiz habe ich festgestellt, dass ich mit diesem Problem vor der Implementierung einiger rekursiver Sortierungen kämpfte: Wie man eine boolesche rekursive Funktion in eine rekursive Funktion umwandelt, die eine Art von count (int/long) zurückgibt , ohne die Funktionalität zu verlieren? Gibt es irgendwelche Richtlinien oder Techniken?

Angehängt ist der Arbeitscode soweit.

import java.util.Scanner; 

public class Sudoku { 

    int[][] board; 

    public Sudoku(){} 

    public Sudoku(int n){ 
     this.board=new int[n][n]; 
    } 

    /* Creates an NxN game.board in a two-dimensional array*/ 
    public static int[][] createBoard(int n) 
    { 
     int[][] board = new int[n][n]; 
     for (int i=0; i<board.length; i++) 
      for (int j=0; j<board[i].length; j++) 
       board[i][j]=0; 
     return board; 
    } 

    /* prints the game.board*/ 
    public static void printBoard(int[][] b) 
    { 
     int buffer=(int)Math.sqrt(b.length); 
     // fitting the bottom line into any size of game.board 
     String btm=new String(new char[buffer*buffer*3+buffer+1]).replace("\0", "_"); 

     for (int i=0; i<b.length; i++) 
     { 
      if (i%buffer==0) 
       System.out.println(btm); 
      for (int j=0; j<b[i].length; j++) 
      { 
       if (j%buffer==0) 
        System.out.print("|"); 
       if (b[i][j]==0) 
        System.out.print(" _ "); 
       else 
        System.out.print(" " + b[i][j] + " "); 
      } 
      System.out.println("|"); 
     } 
     System.out.println(btm); 
    } 

    /* returns true if a number can be inserted in a row, otherwise returns false. */ 
    public static boolean checkLegalRow(int[][] b, int row, int num) 
    { 
     for (int i=0; i<b.length; i++) 
     { 
      if (b[row][i]==num) 
       return false; 
     } 
     return true; 
    } 
    /* returns true if a number can be inserted in a column, otherwise returns false.*/ 
    public static boolean checkLegalCol(int[][] b, int col, int num) 
    { 
     for (int i=0; i<b.length; i++) 
     { 
      if (b[i][col]==num) 
       return false; 
     } 
     return true; 
    } 

    /*returns true if number can be inserted in its local box.*/ 
    public static boolean checkLegalBox(int[][] b, int row, int col, int num) 
    { 
     int buffer=(int)Math.sqrt(b.length); 
     for (int i=0, adjRow=row-(row%buffer); i<buffer; i++, adjRow++) 
     { 
      for (int j=0, adjCol=col-(col%buffer); j<buffer; j++, adjCol++) 
      { 
       if (b[adjRow][adjCol]==num) 
        return false; 
      } 
     } 
     return true; 
    } 

    /*allows user input for a sudoku game.board*/ 
    public static void fillInBoardConsole(int[][] b) 
    { 
     Scanner sc = new Scanner(System.in); 
     System.out.print("Please enter a row: "); 
     int r=sc.nextInt(); 
     System.out.print("Please enter a column: "); 
     int c=sc.nextInt(); 
     System.out.print("Please enter a number from 1 to "+b.length+": "); 
     int num=sc.nextInt(); 
     while (num>b.length || num<1) 
     { 
      System.out.print("Please enter a number from 1 to "+b.length+": "); 
      num=sc.nextInt(); 
     } 
     b[r][c]=num; 
     sc.close(); 
    } 

    /* returns true if all the conditions for sudoku legal move are met: there is no 
* number on the same row, column, box, and the cell isn't taken*/ 
    public static boolean legalMove(int[][] b, int row, int col, int num) 
    { 
     return checkLegalRow(b,row,num) && checkLegalCol(b,col,num) && checkLegalBox(b,row,col,num) && b[row][col]==0; 
    } 

    /* returns true if the initial board setting is legal*/ 
    public static boolean initialLegal(int[][] b) 
    { 
     int num; 
     for (int i=0; i<b.length; i++) 
     { 
      for (int j=0; j<b[i].length; j++) 
      { 
       if (b[i][j]!=0) 
       { 
        num=b[i][j]; 
        b[i][j]=0; 
        if (!(checkLegalRow(b,i,num) && checkLegalCol(b,j,num) && checkLegalBox(b,i,j,num))) 
        { 
         b[i][j]=num; 
         return false; 
        } 
        else 
         b[i][j]=num; 
       } 
      } 
     } 
     return true; 
    } 

    /* using backtrack algorithm and recursion to solve the sudoku*/ 
    public static boolean solveBacktrack(int[][] b, int row, int col) 
    { 
     /*If the cell is already taken by a number: 
     * case 1: if its the last cell (rightmost, lowest) is already taken, sudoku solved 
     * case 2: if its the rightmost cell not on the if it is the rightmost column but not 
     * the lowest row, go to the leftmost cell in next row 
     * case 3: if it's a regular cell, go for the next cell*/ 
     if (b[row][col]!=0) 
     { 
      if (col==b.length-1) 
       if (row==b.length-1) 
       { 
        //printgame.board(b); // case 1 
        return true; 
       } 
       else 
        return solveBacktrack(b,row+1,0); // case 2 
      else 
       return solveBacktrack(b,row,col+1); // case 3 
     } 

     boolean solved=false; 

     for (int k=1; k<=b.length; k++) //iterates through all numbers from 1 to N 
     { 
      // If a certain number is a legal for a cell - use it 
      if (legalMove(b,row,col,k)) 
      { 
       b[row][col]=k; 
       if (col==b.length-1) // if it's the rightmost column 
       { 
        if (row==b.length-1) // and the lowest row - the sudoku is solved 
        { 
         //printgame.board(b); 
         return true; 
        } 
        else 
         solved=solveBacktrack(b,row+1,0); // if its not the lowest row - keep solving for next row 
       } 
       else // keep solving for the next cell 
        solved=solveBacktrack(b,row,col+1); 
      } 
      if (solved) 
       return true; 
      else //if down the recursion sudoku isn't solved-> remove the number (backtrack) 
      { 
       b[row][col]=0; 
      } 
     } 
     return solved; 
    } 

    /* public static long solveCountSolutions(int[][]b, int row, int col, long counter) 
    { 

    } 
    */ 


    public static void main(String[] args) 
    { 
     Sudoku game = new Sudoku(9); 
     game.board[0][2]=5;game.board[0][1]=3; game.board[0][0]=1; 
     game.board[8][2]=4;game.board[8][4]=3;game.board[8][6]=6; 
     printBoard(game.board); 
     if (initialLegal(game.board)) 
      System.out.println(solveBacktrack(game.board,0,0)); 
     else 
      System.out.println("Illegal setting"); 
     printBoard(game.board); 
    } 
} 

Answer 1

Eine solche Funktion durch nicht Austritt aus der Rekursion implementiert werden könnte, wenn eine Lösung gefunden wird, sondern dass die Lösung auf eine externe Struktur Dump (wenn Sie nur Zählungen benötigen, einen Zähler irgendwo außerhalb der Funktion machen, aber sichtbar, und erhöhen Sie es, sobald eine Lösung gefunden wird), und dann weiter suchen, als ob Sie eine Sackgasse getroffen haben. Etwas in Zeile dieses (abstract code):

static int solutions=0; 
bool recursiveSolver(TYPE data) { 
    TYPE newData; 
    while (!nextChoice(data)) { 
     if (solved(data)) { 
      // return true; not now, we count instead 
      solutions++; 
     } 
     newData=applyNextChoice(data); // for recursion 
     if (recursiveSolver(newData)) { 
      return true; // will never hit, but checking is needed for solver to work 
     } 
    } 
    // all choices checked, no solution 
    return false; 
} 

applyNextChoice() ist ein Platzhalter für "nächste Nummer wählen, in diese Zelle setzen" bei Sudoku. TYPE ist ein Platzhalter für welche Struktur, die eine unvollständige Lösung darstellt, in Ihrem Fall eine kombinierte int[][] b, int row, int col.