objective-c - 数独回溯算法失败

Question

我正在尝试生成一个数独板，虽然我可以生成一个解决方案，但我现在需要删除用户随后可以填写的方 block 。为了做到这一点，我想使用回溯来检查每次我移除一个正方形时，棋盘就是 1. 仍然可解且 2. 只有一个解。

问题

当我在 this board 上测试我的回溯算法时(其中零是空方 block )，它返回 this solution .例如，显然我不希望在第一行以几个 9 结尾。

我的代码

- (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 也包含错误。