스도쿠 (Sudoku) solver backtracking

Question

스도쿠 솔버를 탐색 중이며 백 트랙킹을 사용하고 있습니다. 이제는이 코드를 찾았지만 백 트랙킹이나 다른 알고리즘을 사용하고 있는지 확실하지 않습니다.

도움을 주시면 감사하겠습니다.

abstract class SudoKiller { 
private SudokuBoard sb; // Puzzle to solve; 

public SudoKiller(SudokuBoard sb) { 
    this.sb = sb; 
} 


private boolean check(int num, int row, int col) { 
    int r = (row/sb.box_size) * sb.box_size; 
    int c = (col/sb.box_size) * sb.box_size; 

    for (int i = 0; i < sb.size; i++) { 
     if (sb.getCell(row, i) == num || 
      sb.getCell(i, col) == num || 
      sb.getCell(r + (i % sb.box_size), c + (i/sb.box_size)) == num) { 
      return false; 
     } 
    } 
    return true; 
} 


public boolean guess(int row, int col) { 
    int nextCol = (col + 1) % sb.size; 
    int nextRow = (nextCol == 0) ? row + 1 : row; 

    try { 
     if (sb.getCell(row, col) != sb.EMPTY) 
      return guess(nextRow, nextCol); 
    } 
    catch (ArrayIndexOutOfBoundsException e) { 
      return true; 
    } 

    for (int i = 1; i <= sb.size; i++) { 
     if (check(i, row, col)) { 
      sb.setCell(i, row, col); 
      if (guess(nextRow, nextCol)) { 
       return true; 
      } 
     } 
    } 
    sb.setCell(sb.EMPTY, row, col); 
    return false; 
} 
} 

만약 이것이 역 추적하지 않는다면 쉽게 "변환"할 수 있습니까?

전체 프로젝트는 the authors site에서 찾을 수 있습니다.

Answer 1

재귀를 통해 역 추적하는 것처럼 보입니다.

sb.setCell(i, row, col); 

을 여기에서 우리는 뒤로 단계 : 여기

우리는 앞으로 단계

sb.setCell(sb.EMPTY, row, col);