数独回溯算法失败

Question

我正在尝试生成一个sudoku板，虽然我可以生成一个解决方案，但现在我需要删除用户可以填充的方块。为了做到这一点，我想使用回溯检查，每次我删除一个方块，板是1，仍然可以解决，2，只有一个解决方案。

问题

当我在这个板上测试我的回溯算法(其中零是空方格)时，它返回这个解决方案。显然，我不希望在第一行中出现几个9s，例如。

我的代码

- (BOOL) solveArray: (NSArray*) numArray {
    NSMutableArray* board = [numArray mutableCopy];
    for (int i=0; i<9; i++) { //make all of the arrays mutable as well (since it's 2D)
        [board replaceObjectAtIndex:i withObject:[board[i] mutableCopy]];
    }

    //if everything is filled in, it's done
    if (![self findUnassignedLocation:board]) {
        NSLog(@"\n%@", [SudokuBoard sudokuBoardWithArray:board]);
        return TRUE;
    }

    NSArray* poss = [[SudokuBoard sudokuBoardWithArray:board] possibleNumbersForRow:self.arow Col:self.acol];


    //if there are no options for a location, this didn't work.
    if ([poss count] == 0) {
        return FALSE;
    }

    //otherwise, continue recursively until we find a solution
    else {
        for (int i=0; i<[poss count]; i++) {
            //make a tentative assignment
            board[self.arow][self.acol] = poss[i];
            //return, if successful, done
            if ([self solveArray:board]) {
                return TRUE;
            }
            //if that didn't work, unmake it and retry with other options
            board[self.arow][self.acol] = [NSNumber numberWithInt:0];
        }
    }
    return FALSE;
}

对我可能出错的地方有什么想法吗？

Answer 1

每个递归级别都需要自己的行和列变量。也就是说，行和列应该是solveArray和findUnassignedLocation输出的输入，而不是成员变量。实际上，当出现回溯失败级别的行和列时，调用方将重用它。

考虑到一些指定的位置正在被覆盖，也许findUnassignedLocation也包含一个错误。

假设结果无效，也许possibleNumbersForRow也包含一个错误。