Sudoku solving/generating algorithm issue

Question

I am creating a program that will generate sudoku puzzles in vb.net, and due to the way I am doing this I require it to solve a board position (accessing the cells in a specific, random order) and then to solve it again in reverse order. I am using a recursive solver for this.

This is the code I am working with:

Public Function solve(ByRef board() As Integer) As Boolean
    For i = 0 To 80
        If board(order(i)) = 0 Then
            For j = 1 To 9
                board(order(i)) = j
                If check_conflicts(board, order(i)) = False Then
                    If solve(board) = True Then
                        Return True
                    End If

                End If
            Next
            board(order(i)) = 0
            Return False
        End If
    Next

    Return True
End Function

where check_conflicts is a function that determines whether a particular cell assignment directly conflicts with the board (hence the board is passed and the index of the cell order(i) is also passed). This function works as expected when the order is a list of 0 to 80, however if order is a randomly shuffled list then the function takes incredibly long (sometimes upwards of a minute) but usually gets the correct answer. When order is a list of numbers from 80 to 0, the function does not solve anything and always returns false.

I have tried stepping through the code but it is difficult with a recursive function. I wonder if anybody can see a logical error I have made, thank you!

Answer 1

This function works as expected when the order is a list of 0 to 80, however if order is a randomly shuffled list then the function takes incredibly long (sometimes upwards of a minute) but usually gets the correct answer.

The reason may be that while the recursion tree grows exponentially with the recursion depth, when you process the numbers row by row (rather than in a random order), most of the invalid arrangements are cut out early. You'll never have to process the second row with the first row being inconsistent.

When order is a list of numbers from 80 to 0, the function does not solve anything and always returns false.

A couple suggestions:

1) Try replacing order(i) with 80-i to make sure the problem is not in the order() function;

2) Every time you call check_conflicts(board, order(i)), call also check_conflicts(inverse(board), 80-order(i)) and throw an exception if their results are not equal.