이 역 추적으로 만 첫 번째 해결 방법을 찾는 방법

Question

나는 첫 번째 가능한 해결책을 반환하는 스도쿠 해결사를 작성하려고합니다. 나는 void 메소드를 사용하여 가능한 모든 해결책을 인쇄 할 수 있었지만 첫 번째 발견에서 멈출 수는 없습니다.

부울 메서드로 전환하고 true 트리를 반환하는 것입니다 - 하지만 올바른 방법을 찾을 수 없습니다.

나는 항상 컴파일 오류 (method must return boolean)를 시도 어떤 식 으로든.

public boolean recursiveSolve(int line, int column) { 
    if(line == N) // N is the board size (9) 
     return true; 
    // if Cell is not empty - continue 
    if(board1.getCell(line, column) != 0) { 
     return nextCell(line, column); 
    } 
    // if Cell empty - solve 
    else { 
     for(int i = 1; i <= N; i++) { 
      board1.setCell(line, column, i); // set value to cell 
      if(board1.boardIsOk())   // check if the board is legal 
       return nextCell(line, column); // continue 
     } 
     board1.setCell(line, column, 0);  // backtrack 
    } 
} 

private boolean nextCell(int line, int column) { 
    if(column < 8) 
     return recursiveSolve(line, column+1); // progress up the row 
    else 
     return recursiveSolve(line+1, 0);  // progress down the lines 
} 

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

Answer 1

로 변경

 if(board1.boardIsOk())   // check if the board is legal 
      return nextCell(line, column); // continue 

여기에 대부분의 재귀 되돌아 문제에 대한 일부 의사입니다.

이미 해결책이있는 경우 성공을 신고하십시오.

는 (현재 위치에서 모든 가능한 선택) {

에 대한 그 선택을 확인하고 경로를 따라 한 단계를 취할.

재귀를 사용하여 새 위치에서 문제를 해결하십시오.

재귀 호출이 성공하면 다음 상위 수준으로 성공을보고하십시오.

루프의 시작 부분에있는 상태를 복원하려면 현재 선택을 취소하십시오.

}

보고가 실패했습니다.

다음은 Stanford 강의를 기반으로 한 실제 코드입니다. Java에서 다시 작성하고 주석을 포함했습니다.

Boolean SolveSudoku(int[][] grid) 
{ 
    int row, col; 

    if(!FindUnassignedLocation(grid, row, col)) 
     //all locations successfully assigned 
     return true; 

    for(int num = 1; num <= 9; num++) 
    { 
     //if number is allowed to be placed in the square 
     if(NoConflicts(grid, row, col, num)) 
     { 
      //place the number in the square 
      grid[row][col] = num; 

      //recur, if successful then stop 
      if(SolveSudoku(grid)) 
       return true; 

      //undo and try again 
      grid[row][col] = UNASSIGNED; 
     } 
    } 
    //this triggers backtracking from early decisions 
    return false; 
} 

몇 가지 방법을 구현하면됩니다. 매우 간단합니다.

Answer 2

 if(board1.boardIsOk()) {   // check if the board is legal 
      boolean solved = nextCell(line, column); // continue 
      if (solved) { 
       return true; 
      ] 
     } 
    ... 
    return false;