Sudoku Backtracking Algorithm Failure

Question

I'm trying to generate a sudoku board, and although I can generate a solution, I now need to remove squares that a user can then fill in. In order to do this, I'd like to use backtracking to check each time that I remove a square, the board is 1. still solvable and 2. has only one solution.

The Problem

When I test my backtracking algorithm on this board (where the zeroes are empty squares), it returns this solution. Obviously I would prefer not to end up with several 9s in the first row, for example.

My Code

- (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;
}

Any thoughts on where I might be going wrong?

Answer 1

Each level of recursion needs its own row and column variables. That is, row and column should be inputs to solveArray and outputs of findUnassignedLocation instead of being member variables. As it is, when there is backtracking the row and column of the failed level get reused by the caller.

Given that some assigned locations are being overwritten, maybe findUnassignedLocation also contains an error.

Given that the result is invalid, maybe possibleNumbersForRow also contains an error.