通过递归求解数独

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

去兔子洞一点点。解决Sudoko看起来像Constraint-Satisfaction在类似于N-Queens Problem的上下文中的应用可以使用MIN-CONFLICTS算法与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 

冲突函数计算通过一个特定的值违反约束的数量伪代码，鉴于当前分配的其余部分。