Алгоритм обратного отслеживания для решения Sudoku

Question

Я пытаюсь реализовать алгоритм обратного отслеживания для решения Sudoku в приложении Java-консоли. Я никогда раньше не реализовывал алгоритм, и, вероятно, смотреть на несколько видеороликов на YouTube было недостаточно, потому что, похоже, он не работает, как мне кажется.

Я заполнил вручную доску фактическим судоку, который я нашел в Интернете. Однако он не проходит мимо первого квадрата. Первоначально я пытался вложить все это в двойной цикл for, но это, похоже, не работает.

Я правильно проверил правильные методы перемещения, поэтому проблема явно отсутствует. Оцените любую помощь.

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