java - 递归:如何尝试整数 1 到 9 的不同组合，以及(部分)反向序列以在出错时重新开始？

Question

语言:Java

目标:一般:解决数独游戏

特定的:创建一个递归方法 solve() :

• 检查数字是否与行、列或框中的其他数字冲突
• 如果不是这种情况，则在给定的空白处填充 [1-9] 之间的整数，然后移至下一个空白处
• (部分或全部)如果空格不能被 [1-9] 之间的整数填充而不冲突，则反转进度。然后重试，直到所有空格都被填满(并且数独已解决)。

问题:循环尝试填写整数 n 但总是会先尝试最小的数字。如果我要使用递归，整数将始终相同。

问题: 1.如何让代码填写1到9之间的数字，包括1到9。

1. 您如何使用递归来部分或完全清除进度并尝试不同的数字。

2. (extra) 到目前为止，我已经构建了部分解决数独问题的代码(直到无法填充空白方 block )，但现在它甚至没有填充第一个方 block ，尽管它之前已经填充了。这不是我的主要问题，但如果有人注意到这个问题，请指出，我将不胜感激。

审阅: 我正在阅读有关递归的类(class)资料，但找不到正确的信息。

免责声明:方法 printMatrix 之外的所有 println 命令都用于测试

这里是有问题的方法:

       // prints all solutions that are extensions of current grid
      // leaves grid in original state
void solve() {
//local variables
int[] currentSquare;
int currentRow;
int currentColumn;
boolean checkConflict;
currentSquare = new int[2];

//saftey limit for testing
int limit;
limit = 0;

while(findEmptySquare() != null){

  currentSquare = findEmptySquare().clone();
  currentRow = currentSquare[0];
  currentColumn = currentSquare[1];
  //System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3

  if(currentSquare[0] != -1){

    for(int n = 1; n <= ms; n++){
      checkConflict = givesConflict(currentRow, currentColumn, n);
      if(checkConflict == false){
        grid[currentRow][currentColumn] = n;
      }//end if
    }//end for
  }//end if
  else{
    System.out.println("solve: findEmptySquare was -1");
    break;
  }

  //Safety limit
  limit++;
  if (limit > 20){
    System.out.println("break");
    break;
  }//end if

}//end while
}

下面是查找空方 block 的方法:

// finds the next empty square (in "reading order")
// returns array of first row then column coordinate
// if there is no empty square, returns .... (FILL IN!)
int[] findEmptySquare() {
int[] rowcol;
int[] noMoreCells;
rowcol = new int[2];
noMoreCells = new int[2];
noMoreCells[0] = -1;
noMoreCells[1] = -1;

for(int r = 0; r < ms; r++){
  for(int c = 0; c < ms; c++){
    if(grid[r][c] == 0){
      if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one
        rempty = r;
        cempty = c;
        rowcol[0] = r; // 0 for row
        rowcol[1] = c; // 1 for column
        //System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3
        return rowcol;
      }//end if
      else{
        System.out.println("findEmptySquare: found same empty square twice");
        return noMoreCells;
      }//end else
    }//end if
  }//end for
}//end for

System.out.println("findEmptySquare: no more empty cells");
return null;  //no more empty cells
}

如有必要，整个代码(缩进很乱，因为我不得不在 stackoverflow 上手动添加空格):

 // Alain Lifmann. Date: 26/9/2015
// Description of program: runs sudoku game
import java.util.*;

class Sudoku {
  int ms = 9; //maze Size
  int rempty; //keeping track of empty squares, row nr. (array)
  int cempty; //keeping track of empty squares, column nr. (array)
  int SIZE = 9;     // size of the grid
  int DMAX = 9;     // maximal digit to be filled in
  int BOXSIZE = 3;  // size of the boxes 
  int[][] grid;     // the puzzle grid; 0 represents empty

      // a challenge-sudoku from the web
  int[][] somesudoku = new int[][] {         
{ 0, 6, 0,   0, 0, 1,    0, 9, 4 },    //original      
  // { 0, 0, 0,   0, 0, 1,    0, 9, 4 }, //to get more solutions
{ 3, 0, 0,   0, 0, 7,    1, 0, 0 }, 
{ 0, 0, 0,   0, 9, 0,    0, 0, 0 }, 

{ 7, 0, 6,   5, 0, 0,    2, 0, 9 }, 
{ 0, 3, 0,   0, 2, 0,    0, 6, 0 }, 
{ 9, 0, 2,   0, 0, 6,    3, 0, 1 }, 

{ 0, 0, 0,   0, 5, 0,    0, 0, 0 }, 
{ 0, 0, 7,   3, 0, 0,    0, 0, 2 }, 
{ 4, 1, 0,   7, 0, 0,    0, 8, 0 }, 
  };

  // a test-sudoku from oncourse
  int[][] testsudoku = new int[][] {         
{ 1, 2, 3,   4, 5, 6,    7, 8, 9 },      
{ 4, 5, 6,   7, 8, 9,    1, 2, 3 },
{ 7, 8, 9,   1, 2, 3,    4, 5, 6 }, 

{ 2, 1, 4,   3, 6, 5,    8, 9, 7 },
{ 3, 6, 5,   8, 9, 7,    2, 1, 4 },
{ 8, 9, 7,   2, 1, 4,    3, 6, 5 },

{ 5, 3, 1,   6, 4, 2,    9, 7, 8 },
{ 6, 4, 2,   9, 7, 8,    5, 3, 1 },
{ 9, 7, 8,   5, 3, 1,    6, 4, 2 },
  };

  // a test-sudoku modified to be incomplete
  int[][] testsudoku2 = new int[][] {         
{ 0, 0, 3,   0, 5, 6,    7, 8, 0 },      
{ 0, 5, 0,   7, 0, 0,    1, 0, 3 },
{ 7, 0, 0,   1, 0, 3,    4, 5, 6 }, 

{ 2, 1, 4,   3, 6, 5,    8, 0, 7 },
{ 3, 0, 5,   8, 0, 7,    0, 1, 0 },
{ 0, 9, 7,   0, 1, 4,    3, 0, 5 },

{ 0, 0, 0,   6, 4, 2,    9, 7, 8 },
{ 0, 4, 2,   9, 7, 8,    0, 0, 1 },
{ 0, 0, 0,   5, 3, 1,    0, 4, 0 },
  };

  int solutionnr = 0; //solution counter

  // ----------------- conflict calculation --------------------

  // is there a conflict when we fill in d at position r,c?
  boolean givesConflict(int r, int  c, int d) {
if(rowConflict(r, d) == true){
  return true;
}//end if
if(colConflict(c, d) == true){
  return true;
}//end if
if(boxConflict(r, c, d) == true){
  return true;
}//end if     
return false;
  }//end givesConflict


  boolean rowConflict(int r, int d) {
    for(int i = 0; i < ms; i++){
  if(d == grid[r][i]){
    //System.out.println("rowconflict r:"+r+" d:"+d);
    return true;
  }//end if
    }//end for

    return false; //no conflict
  }

  boolean colConflict(int c, int d) {
    for(int i = 0; i < ms; i++){
  if(d == grid[i][c]){
    //System.out.println("column conflict c:"+c+" d:"+d);
    return true;
  }//end if
    }//end for

    return false; //no conflict
  }

  boolean boxConflict(int rr, int cc, int d) { //test 5,3,1
int rs; // Box-row start point
int cs; // Box-column start point
rs = rr - rr%3;
cs = cc - cc%3;
//System.out.println("box start is row "+rs+" , column "+cs);

for(int r = rs; r < rs + 3; r++ ){
  for(int c = cs; c < cs + 3; c++){

    if(d == grid[r][c]){
      //System.out.println("r:"+r+" c:"+c);
      return true;
    }//end if

  }//end for
}//end for

    return false; //no conflict
  }

  // --------- solving ----------

  // finds the next empty square (in "reading order")
  // returns array of first row then column coordinate
  // if there is no empty square, returns .... (FILL IN!)
  int[] findEmptySquare() {
int[] rowcol;
int[] noMoreCells;
rowcol = new int[2];
noMoreCells = new int[2];
noMoreCells[0] = -1;
noMoreCells[1] = -1;

    for(int r = 0; r < ms; r++){
      for(int c = 0; c < ms; c++){
    if(grid[r][c] == 0){
      if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one
        rempty = r;
        cempty = c;
        rowcol[0] = r; // 0 for row
        rowcol[1] = c; // 1 for column
        //System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3
        return rowcol;
      }//end if
      else{
        System.out.println("findEmptySquare: found same empty square twice");
        return noMoreCells;
      }//end else
    }//end if
  }//end for
    }//end for

    System.out.println("findEmptySquare: no more empty cells");
    return null;  //no more empty cells
      }

  // prints all solutions that are extensions of current
  // leaves grid in original state
  void solve() {
//local variables
int[] currentSquare;
int currentRow;
int currentColumn;
boolean checkConflict;
currentSquare = new int[2];

//saftey limit for testing
int limit;
limit = 0;

while(findEmptySquare() != null){

  currentSquare = findEmptySquare().clone();
  currentRow = currentSquare[0];
  currentColumn = currentSquare[1];
  //System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3

  if(currentSquare[0] != -1){

    for(int n = 1; n <= ms; n++){
      checkConflict = givesConflict(currentRow, currentColumn, n);
      if(checkConflict == false){
        grid[currentRow][currentColumn] = n;
      }//end if
    }//end for
  }//end if
  else{
    System.out.println("solve: findEmptySquare was -1");
    break;
  }

  //Safety limit
  limit++;
  if (limit > 20){
    System.out.println("break");
    break;
  }//end if

}//end while
  }

  // ------------------------- misc -------------------------

  // print the grid, 0s are printed as spaces
  void printMatrix(){
int ms; //matrix Size
ms = 9;
//layer indication symbols
String end;
String mid;
String cut;
end = "+";
mid = "-";
cut = "";
for(int i = 0; i < 2*ms-1; i++){
  cut = cut + mid;
}//end for

    System.out.println(end+cut+end);
for(int i = 0; i < ms; i++){
  if( i % 3 == 0 && i != 0){
    System.out.println(mid+cut+mid);
  }//end if
  for(int j = 0; j < ms; j++){
    if( j % 3 == 0){
      System.out.print("|");
    }//end if
    else{
      System.out.print(" ");
    }//end else
    if(grid[i][j] != 0){
      System.out.print(grid[i][j]);
    }//end if
    else{
      System.out.print(" ");
    }//end else
  }//end for j
  System.out.print("|");
  System.out.println();
}//end for i
System.out.println(end+cut+end);
  }//end method

  // reads the initial grid from stdin
  void read() {
Scanner sc = new Scanner(System.in);

for (int r=0; r<SIZE; r++) {
  if (r % BOXSIZE == 0) {
    sc.nextLine(); // read away top border of box
  }
  for (int c=0; c < SIZE; c++) {
    if (c % BOXSIZE == 0) {
      sc.next(); // read away left border of box
    }
    String square = sc.next();
    if (".".equals(square)) {
      grid[r][c] = 0;  // empty sqaure
    } else {
      grid[r][c] = Integer.parseInt(square);
    }
    //System.out.print(grid[r][c]);
  }
  sc.nextLine(); // read away right border

}
sc.nextLine(); // read away bottom border
  }

  // --------------- where it all starts --------------------




  void solveIt() {
grid = somesudoku.clone();     // set used grid (before doing anything else)
printMatrix();
solve();
printMatrix();


/* test material
 printMatrix();
 //System.out.println(givesconflict(1,1,3));
 System.out.println(rowConflict(0,1));
 System.out.println(colConflict(0,1));
 System.out.println(boxConflict(0,0,1));
 findEmptySquare();
 */
  }// end solveIt

  public static void main(String[] args) {
new Sudoku().solveIt();
  }
  }

Answer 1

这个问题可以通过回溯来解决。您必须遍历所有可能的选项，但是当您遇到错误的问题时，请从该路径返回。您可以从此链接找到有关代码的帮助 http://learnfreecodes.blogspot.in/2015/11/sudoku-solver-using-backtracking-in-java.html