回溯法

概念

回溯法的概念有点类似于深度优先,使用的是穷举法,在使用数据之前先保存数据,当下一步走不通时,回退到上一步,重新操作,直到所有的数据都能走通.

下面介绍几种经典的回溯示例:

1.九宫格

image.png

回溯方式:使用变量保存前一个数据
九宫格填法:
1.在第一行中间填1
2.在前一个的右上角填后一个数
3.若右上角有数则回到上一步,填到前一个的下方
4.边界,超出上边界移到最下方,超出右边界移到最左

public class 九宫格{
  int n = 5;//九宫格行数
  int x = 1;//从1开始填
  int[][] array = new Array[n][n];//九宫格
  int row = 0;//行数
  int col = n/2;//列数
  array[row][col] = x;//在第一行中间填上1
  
  while(x<n*n){//循环结束条件
    //记录当前的值
    int tempRow = row;
    int tempCol = col;
    x++;
    row = row--;
    if(row<0){
      row = n-1;
    }
    col = col++;
    if(col>n-1){
      col = 0;
    }
    if(array[row][col]==0){
      array[row][col] = x;
    }else{
      //不满足条件时,回溯
      row = tempRow;
      col = tempCol;
      row++;
      array[row][col] = x;
    } 
  }
   
}

2.八皇后

image.png

回溯方式:通过递归栈回溯
八皇后规则:在8行8列的数组中,填入8个皇后,从第一行开始,一行一行填,每个皇后的竖直方向和左右对角线不予许填.

判断规则:
使用数组 int [] array = new int[8];来表示结果,数组下标表示行号,值表示列号
若我们要在第n行填入皇后,就要从n行0列开始填,每次填入时判断能否填入
竖直方向不能填,即第n行前面的每一行列号不能与第n行相同,即array[i] != array[n]
对角线不能填入,即:abs(n-i)!=abs(array[n]-array[i]).

    public class 八皇后{
      //数组下标代表行,数组值代表列  
      int [] array = new int[8];
      eightQueens();

      public void eightQueens(int row){
  
        if(row==8){
          printresult();
          return;
        }        

        for(int col = 0;col<8;col++){
          array[row] = col;
          if(judge(row)){//回溯的地方,如果第row行能填,就填row+1行,否则row不变,即继续填第row行的下一个列(col++)
            eightQueens(row+1);
          }
        }        
      }
  
  public boolean judge(int n){
        for(int i = 0;i<n;i++){
          if(array[i] = array[n]|| Math.abs(n-i)==Math.abs(array[n]-array[i])){
            return false;
          }
        }
        return true;
  }
    
  public void printresult(){
      for(int i = 0;i<array.length;i++){
        System.out.print(array[i]+" ");
      }
      System.out.println();
   }
  }

数独

image.png

回溯方式:变量保存加递归栈
数独规则,每行填1-9不相同,每列填1-9不相同,每个9宫格填1-9不相同.

用一个9*9的二维数组来保存当前的数独表,当在数独表中填入一个数时,这样来判断是否满足条件

1. 若在书读表row行col列填入的数k,二维数组是result,那么,遍历i从1-9,result[row][i] != k && result[i][col] != k
2. 每个宫(3*3的九宫格)中不重复,首先我们需要确定当前填入的数是在哪一个宫中,
   我们用当前数的行和列除以3,再乘以3,可以得到当前九宫格的左上角的行和列,即 int tempRow = row/3 * 3;
   int tempCol = col/3 * 3;然后再遍历3 * 3,可以得到当前的宫中是否可填.

//所在的宫中没有重复
int tempRow = row/3;
int tempCol = col/3;
for(int i=0;i<3;i++){
  for(int j=0;j<3;j++){
    if(result[tempRow*3+i][tempCol*3+i]==k){
      return false;
    }
  }
}

public class 数独问题{
  public int[][] result = new int[9][9];
  public void sudoku(){
    sudoku(0,0);
  }
  
  public void sudoku(int row,int col){
    
    if(row==8&&col==9){
      printResult();
      return;
    }    

    if(j==9){
      row++;
      j = 0;
    }

    if(result[row][col]==0){
       for(int i = 0;i<=9,i++){
          if(judge(row,col,i)){
            result[row][col] = k;
            sudoku(row,col+1);
            result[row][col] = 0;
          }
        }
    }else{
        sudoku(row,col+1);
     }
  }

public boolean judge(int row,int col,int k){
  //行和列没有重复  
  for(int i = 0;i<9;i++){
    if(result[row][i]==k||result[i][col]==k){
      return false;
    }
   }

//所在的宫中没有重复
int tempRow = row/3;
int tempCol = col/3;
for(int i=0;i<3;i++){
  for(int j=0;j<3;j++){
    if(result[tempRow*3+i][tempCol*3+i]==k){
      return false;
    }
  }
}

  return true;
}

public void printResult(){
  for(int i = 0;i<9;i++){
    for(int j = 0;j<9;j++){
      System.out.print(result[i][j]+" ");
    }
    System.out.println();
  }
System.out.println("----------");
}

}