3

可能重复：
Java中的数独求解器，使用回溯和递归

我正在创建一个使用递归和蛮力解决数独的程序。我的关键问题是我不明白我怎么能想象到它会被卡住。

该程序的一般算法如下：

  1. 找出数独中零的数量。

  2. 在第一个 0 的位置（getNextEmpty 方法执行此操作），插入一个数字（insertnumber 检查以确保值符合数独规则，如果符合则返回 true）。

  3. 然后我进行递归调用，当不再有零时结束（n 是零的数量）。

  4. 如果程序到了卡住的地步，我必须回溯改变一块。但这怎么可能？

Cell 类实际上将要调整的单元格的位置保存在 [row, column] 格式的数组中。它具有返回与该单元格关联的行、列或更小的网格的方法。

我不是要求手持或所有代码，只要朝着正确的方向轻推就足够了，因为我对理解递归很感兴趣。

public static int[][] getSolution(int[][] grid) {
    for (int i = 0; i < 9; i++) {
        System.arraycopy(grid[i], 0, SolveSudoku.grid[i], 0, 9);
    }// end for
    int n = getZeroes();
    return getSolution(n);
}//end getSolution

private static int[][] getSolution(int n) {
    if (n == 0) {
        return grid;        
    }//end if
    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break;
        }else {
            //I do not understand what I should do here
        }
    }//end for
    return getSolution(n - 1);
}//end getSolution
4

2 回答 2

2

朝着正确的方向轻推。您的方法需要稍作调整，因为您没有跟踪解决网格所需的所有信息。

private static int[][] getSolution(int n) {
    if (n == 0) {
       return grid;        
    }//end if

    Cell cell = getNextEmpty();
    boolean fits = false;
    for (int i = 0; i <= 9; i++) {
        fits = insertNumber(cell, i);
        if (fits) {
            break; // means i fits in Cell
        } else {
            // i doesn't fit... try the next i
            // don't need to do anything
        }
    }//end for
    if (!fits) {
        // There are no numbers that fit in this Cell
        // What should happen?
        // Did I make a bad guess?
        // How do I BACKTRACK and correct a previous guess?
    }
    return getSolution(n - 1);
}//end getSolution
于 2012-03-01T00:31:58.793 回答
1

通常在递归蛮力中，您使用类似于以下代码的语法。这样做是因为你可以在你做了任何动作之后计算，那是新的“起始位置”。所以它会类似于这样：

private void Guess(int[][] grid)
{
    if(/**grid is a solution **/)
        //signal success
    else
    {
        if(/*seed out any bad, unacceptable answers you may have missed*/)
            return;//this includes cases when there are no more zeros
        //for every possible move,
        //make a modified grid, with one move done, and call
        Guess(ModifiedGrid);//for every possible move, generally you can modify
        //grid itself, because its passed by value
    }
}
于 2012-03-01T00:27:59.107 回答