java - 通过递归解决数独

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 看起来像是在类似于 N-Queens 问题的上下文中应用 Constraint-Satisfaction，MIN-CONFLICTS 算法可用于与模拟退火相结合来找到最佳解决方案。

考虑来自 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

在给定当前分配的其余部分的情况下，CONFLICTS 函数会计算特定值违反的约束数量。