재귀에 의한 스도쿠 해결

Question

스도쿠를 풀기 위해 재귀를 쓰려고 시도했지만 재귀에 문제가 있습니다. 해결할 수 없다면 해결할 수 있지만 루프가 무한하게됩니다.

public static boolean recursion (int sodukuMatrix[][],int posRow, int posCol ,int i){ 

    if (posRow==0 && posCol==0 && i==10) 
     return false; 

    if(there is existing number){ 
     if (posCol==8 && posRow==8) 
      return true; 
     call recursion with next square 
    } 
    else { 
     i=sodukuMatrix[posRow][posCol]+1; 
     while (i<10){ 
      if (function: if I put i at the current location it is ok){ 
       sodukuMatrix[posRow][posCol]=i;   
       if (posCol==8 && posRow==8) 
        return true; 
       call recursion with next square 
      } 
      else  
       i++; 
     } 
     sodukuMatrix[posRow][posCol]=0; 
     return false; 
    } 
    return false; 
} 
} 

Answer 1

토끼의 구멍을 조금 아래로 이동하십시오. 스도 코를 해결하는 것은 N-Queens Problem A MIN-CONFLICTS과 비슷한 맥락에서 Constraint-Satisfaction의 응용 프로그램처럼 보이며 최적의 솔루션을 찾기 위해 Simulated Annealing과 조합하여 사용할 수 있습니다.

는 현재 할당의 나머지 주어진 Peter Norvig's Artificial Intelligence a Modern Approach

function MIN-CONFLICTS(csp, max_steps) returns a solution or failure 
    inputs: csp, a constraint satisfaction problem 
    max_steps, the number of steps allowed before giving up 

    current <- an initial complete assignment for csp 
    for I = 1 to max_steps do 
    if current is a solution for csp then return current 
    var <- a randomly chosen conflicted variable from csp.VARIABLES 
    value <- the value v for var that minimizes CONFLICTS(var, v, current, csp) 
    set var = value in current 
    return failure 

충돌 함수는 특정 값에 의해 위반 제약 조건의 수를 계산에서이 의사를 고려하십시오.