스도쿠를 해결하기위한 역 추적 알고리즘

Question

자바 콘솔 애플리케이션에서 스도쿠를 해결하기 위해 역 추적 알고리즘을 구현하려고했습니다. 전에는 알고리즘을 구현 한 적도 없었고, 아마 몇 편의 유튜브 비디오 만 보아도 충분하지 않았습니다. 왜냐하면 그것이 제대로 작동하지 않는 것 같기 때문입니다.

온라인으로 찾은 실제 스도쿠로 보드를 수동으로 채웠습니다. 그러나 첫 번째 사각형을지나 가지 않습니다. 처음에는 두 번 for-loop에서 모든 것을 중첩하려했지만 그 중 하나는 작동하지 않습니다.

유효한 이동 방법을 올바르게 테스트 했으므로 문제가 분명히 없습니다. 감사합니다.

public class Sudoku { 

    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; 
    } 

    public static void printBoard(int[][] b) 
    { 
     int buffer=(int)Math.sqrt(b.length); 
     String btm=new String(new char[buffer*buffer*3+buffer+1]).replace("\0", "_"); // fitting for all board size 
     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. 
    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. 
    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 NxN 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; 
    } 

    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; 
    } 

    public static void solveBacktrack(int[][] b, int row, int col) 
    { 
     for (int k=1; k<=b.length; k++) 
      { 
       if (legalMove(b,row,col,k)) 
       { 
        b[row][col]=k; 
        if (row==b.length-1 && col==b.length-1) 
         printBoard(b); 
        else 
        { 
         //printBoard(b); 
         if (col==b.length-1) 
          solveBacktrack(b,row+1,0); 
         else 
          solveBacktrack(b,row,col+1); 
        } 
       } 
      } 
    } 

    public static void main(String[] args) 
    { 
     int[][] board=createBoard(9); 
     board[0][1]=4; board[1][0]=6; board[2][1]=8; board[2][2]=9; board[0][3]=6; board[2][5]=3; board[1][7]=3; 
     board[1][8]=1; board[3][3]=4; 
     board[3][0]=2; board[3][2]=1; board[3][4]=5; board[3][7]=7; board[3][8]=8; board[4][1]=5; 
     board[4][3]=3; board[4][5]=7; board[5][0]=3; board[5][1]=6; board[5][4]=2; board[5][5]=8; board[5][8]=5; 
     board[6][3]=1; board[6][6]=6; board[6][7]=4; board[7][0]=4; board[7][1]=3; board[7][8]=9; board[8][2]=6; 
     board[8][5]=9; 
     printBoard(board); 
     solveBacktrack(board,0,0); 
    } 
} 

Answer 1

확인 방법이 잘못되었습니다. 셀이 주석에 언급 된 @stark로 사용되었는지 확인하지 않습니다. 그래서 여기

는 checkLegalMove에 대한 보정입니다 :

public static boolean checkLegalMove(int[][] b, int row, int col, int num) { 
    if (b[row][col] != 0) // occupied 
    return false; 
    // check row 
    for (int i = 0; i < b[row].length; i++) { 
    if (b[row][i] == num) 
     return false; 
    } 
    // check column 
    for (int i = 0; i < b.length; i++) { 
    if (b[i][col] == num) 
     return false; 
    } 
    // check box with some integer math 
    for (int i = row/3 * 3; i < (row/3 + 1) * 3; i++) { 
    if (i == row) // row already checked 
     continue; 
    for (int j = col/3 * 3; j < (col/3 + 1) * 3; j++) { 
     if (j == col) // column already checked 
     continue; 
     if (b[i][j] == num) 
     return false; 
    } 
    } 
    return true; 
} 

이의도 solveBacktrack 방법의 문제, 많은, 나는 주석이있는 일을 다시 작성하는 것이 더 쉽습니다 생각 (아무 리셋, 잘못된 중첩됩니다 루프, 마지막 셀이 이미 점유되었을 수 있음).

우선 물건을 다시 도우미 기능을 소개하는 것입니다, 그래서 당신은 당신이 스도쿠를 해결 한 때 알고 값 다시 안 :

private static boolean solved; 

public static void solveBacktrack(int[][] b) { 
    solved = false; 
    boolean found = false; 
    // find first free cell and start solving 
    for (int i = 0; i < 0 && !found; i < b.length; i++) { 
    for (int j = 0; j < b[i].length; j++) { 
     if (b[i][j] == 0) { 
     found = true; 
     solveBacktrack(b, i, j); 
     break; 
     } 
    } 
    } 
    if (!found) // no free cell found, sudoku already solved 
    solved = true; 
} 

을 그리고 마지막으로 재귀 함수 :

private static void solveBacktrack(int[][] b, int row, int col) { 
    for (int k = 1; k <= b.length; k++) { 
    if (checkLegalMove(b, row, col, k)) { 
     b[row][col] = k; 
     // find next free space 
     int nextRow = row, nextCol = col; 
     while(nextRow < b.length && b[nextRow][nextCol] != 0) { 
     if (nextCol + 1 == b[nextRow].length) { 
      nextCol = 0; 
      nextRow++; 
     } else { 
      nextCol++; 
     } 
     } 
     if (nextRow == b.length) { 
     solved = true; 
     break; 
     } 
     solveBacktrack(b, nextRow, nextCol); 
     if (!solved) 
     b[row][col] = 0; // reset if not solved 
     else 
     break; 
    } 
    } 
}