java - 回溯算法解数独

Question

我一直在尝试实现一个回溯算法来解决 Java 控制台应用程序中的数独问题。我以前从未实现过该算法，可能只看几个 youtube 视频还不够，因为它似乎并没有像我认为的那样工作。

我用我在网上找到的实际数独手动填充了面板。但是，它不会经过第一个方 block 。最初我试图将整个事情嵌套在一个双 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;
    }
  }
}