java – 递归：如何尝试不同的整数1到9的组合,以及(部分)反向序

目标：
general：解决一个数独游戏

具体：做一个递归方法solve()：

>检查数字是否与行,列或框中的其他数字冲突
>如果不是这样,则在给定的空白空间中填入[1-9]之间的整数,然后移动到下一个空白区域
>(部分或全部)如果空间不能被[1-9]之间的整数填充而没有冲突,则会反转进度.然后再试一次,直到填满所有空格(并解决数独).

问题：
循环尝试填充整数n,但总是先尝试最小的数字.
如果我使用递归,整数将始终是相同的.

题：
1.如何使代码填充1到9之间的数字.

>如何使用递归来部分或完全擦除进度并尝试不同的数字.
>(额外)我到目前为止已构建代码来部分解决数独(直到空方块无法填充),但现在它甚至没有填充第一个方块,即使它之前做过.这不是我的主要问题,但如果有人注意到这个问题,我会非常感激,如果有人指出的话.

回顾：
我正在阅读关于递归的课程材料,但无法找到正确的信息.

免责声明：
方法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
}

这是找到空方块的方法：

// 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,1,9,4 },//original      
  // { 0,//to get more solutions
{ 3,7,0 },{ 0,{ 7,5,2,9 },3,{ 9,1 },2 },{ 4,8,};

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

  // a test-sudoku modified to be incomplete
  int[][] testsudoku2 = new int[][] {         
{ 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,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,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,3));
 System.out.println(rowConflict(0,1));
 System.out.println(colConflict(0,1));
 System.out.println(boxConflict(0,1));
 findEmptySquare();
 */
  }// end solveIt

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