Swift doesn't return the correct value in recursive function

Question

I tried to implement backtracking solution for a sudoku solver in swift. This is my code:

func solve(board: [[Int]]) -> (isSolved: Bool, board: [[Int]]){
    var board = board
    var empty_pos: (Int, Int)
    var check_empty = findEmpty(board: board)

    if check_empty.isEmpty == false{
        return (true, board)
    }else{
        empty_pos = check_empty.pos

        for num in 1..<10{
            if isValid(board: board, num: num, pos: empty_pos){

                board[empty_pos.0][empty_pos.1] = num

                if solve(board: board).isSolved{
                    return (true, board)
                }else{
                    board[empty_pos.0][empty_pos.1] = 0
                }
            }
        }
    }
    return (false, board)}

When I run the code, the function returns true with the original board. However, when I print the board in the if solved block, I noticed that function solves the board, but it doesn't return it, and continues to call the function until it makes all of the 0 values 0 again. I think the function doesn't quit in the if solve(board: board).isSolved part. What should I do to solve this? Thank you!

I would recommend you make a SudokuBoard struct to abstract over the [[Int]]. Then you could just make a solve method on it that returns SudokuBoard?, either nil (no solution), or a solved board. — Alexander
I would also recommend against using recursion in cases that are easily done by looping. — Alexander

Dávid Pásztor Dávid Pásztor · Accepted Answer · 2019-12-20T14:01:26

The issue is that you are not returning the modified return value from solve, but just discarding it and returning the local variable board.

You should be saving the return value from the recursive call and if its isSolved property is true, return the board from the recursive call, not the local var.

func solve(board: [[Int]]) -> (isSolved: Bool, board: [[Int]]) {
    var board = board
    var emptyPos: (Int, Int)
    var checkEmpty = findEmpty(board: board)

    if !checkEmpty.isEmpty {
        return (true, board)
    } else {
        emptyPos = checkEmpty.pos

        for num in 1..<10 {
            if isValid(board: board, num: num, pos: emptyPos){

                board[emptyPos.0][emptyPos.1] = num

                let solved = solve(board: board)
                if solved.isSolved {
                    return (true, solved.board)
                } else{
                    board[emptyPos.0][emptyPos.1] = 0
                }
            }
        }
    }
    return (false, board)
}

Unrelated to your question, but you should be conforming to the Swift naming convention, which is lowerCamelCase for variable and function names.

Swift doesn't return the correct value in recursive function

1 Answers