스도쿠 - 재귀 역 추적 가능 - 솔루션 카운터

Question

나는 약간의 스도쿠를 개발 중이며 확장하려고 노력 중이다.

지금까지 재귀를 해결할 때마다 true를 반환하는 재귀 backtracking 메서드를 사용하여 "Solve"파트가 작동했습니다.

이제는 고유 한 솔루션 보드 생성기를 만들려고하고 있으며 구현 방법에 대한 정보가 온라인에서 많이 발견되었습니다.

그러나 첫 번째 단계는 가능한 솔루션 수를 유지하는 재귀 알고리즘에 대한 부울 재귀 역 추적 알고리즘입니다. 생성 된 게시판이 고유한지 여부를 확인하는 것이 중요합니다.

몇 가지 재귀 적 정렬을 구현할 때 이전에이 문제로 고민했다는 것을 깨달았습니다. 부울 재귀 함수를 일종의 카운트 (int/long)를 반환하는 재귀 함수로 변환하는 방법 , 기능을 잃지 않고? 따라야 할 지침이나 기술이 있습니까?

첨부 된 코드는 지금까지 작업 코드입니다.

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

이러한 기능은 해결책을 찾을 때 재귀에서 종료하지 않음으로써 구현 대신 함수의 외부 어딘가 (외부 구조에 해당 솔루션을 덤프 만 카운트를 필요로하는 경우, 카운터를 만들 수 있지만, 솔루션이 발견되면 그것을 증가 시키십시오), 그리고 막 다른 골목을 치는 것처럼 계속 검색하십시오. 이 (추상 코드)의 라인에 뭔가 :

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()은 스도쿠의 경우 "이 셀에 넣어 다음 번호를 선택"에 대한 자리 표시 자입니다. TYPE은 불완전한 솔루션을 나타내는 구조체의 자리 표시 자이며, 경우에 따라 int[][] b, int row, int col을 합친 것입니다.