I got my answer (assuming it's correct...) by a combination of deduction and brute force.

 

Because the digit 0 only appears in the numbers 10...99 about half as many times as any other digit, and is not the leading digit of any of them, it makes sense to take care of 0 as the trailing digit right off the bat: put one 0 in the middle of the grid, surrounded by 1-8, and put the other 0 in one of the least useful corner squares, with a 9 joining it to the first group. Then let the program assign four 1's and three of every other nonzero digit randomly across the remaining squares of the grid. 

 

This strategy produces an answer to the riddle in as little as 6 seconds.

 

Imports System
Imports System.IO
Imports System.Text
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
    Dim grid(5, 6) As Integer
    Dim digit As Integer
    Dim answer0 As Integer
    Dim answer1 As Integer
    Dim success As Integer = 0
    Dim flag1 As String
    Dim flag2 As String
    Dim interval0 As Integer = 0
    Dim interval1 As Integer = 10000
    Sub Main()
        Randomize()
        Dim display As String
        Console.WriteLine("Start: " & TimeOfDay)
        flag1 = "n"
        While flag1 = "n"
            scatter_digits()
        End While
        Console.WriteLine("Eureka !!!!!")
        For index0 As Integer = 0 To 4
            display = ""
            For index1 As Integer = 0 To 5
                display &= Str(grid(index0, index1))
            Next
            Console.WriteLine(display)
        Next
        Console.WriteLine("End: " & TimeOfDay)
        Console.ReadLine()
    End Sub

    Sub scatter_digits()
        preformat_grid()
        place_digits()
        For answer0 = 1 To 9
            For answer1 = 0 To 9
                find_number_in_grid()
                If flag2 = "n" Then
                    Exit Sub
                End If
            Next
        Next
        flag1 = "y"
    End Sub

    Sub place_digits()
        Dim sub0 As Integer
        Dim sub1 As Integer
        Dim flag4 As String
        Dim limit As Integer
        Dim posn As Integer
        Dim display As String
        Dim positions(19, 2) As Integer
        positions(0, 0) = 0
        positions(0, 1) = 0
        positions(1, 0) = 0
        positions(1, 1) = 1
        positions(2, 0) = 0
        positions(2, 1) = 2
        positions(3, 0) = 0
        positions(3, 1) = 3
        positions(4, 0) = 0
        positions(4, 1) = 4
        positions(5, 0) = 0
        positions(5, 1) = 5
        positions(6, 0) = 1
        positions(6, 1) = 0
        positions(7, 0) = 1
        positions(7, 1) = 4
        positions(8, 0) = 1
        positions(8, 1) = 5
        positions(9, 0) = 2
        positions(9, 1) = 0
        positions(10, 0) = 2
        positions(10, 1) = 4
        positions(11, 0) = 2
        positions(11, 1) = 5
        positions(12, 0) = 3
        positions(12, 1) = 0
        positions(13, 0) = 3
        positions(13, 1) = 5
        positions(14, 0) = 4
        positions(14, 1) = 0
        positions(15, 0) = 4
        positions(15, 1) = 1
        positions(16, 0) = 4
        positions(16, 1) = 2
        positions(17, 0) = 4
        positions(17, 1) = 3
        positions(18, 0) = 4
        positions(18, 1) = 4
        digit = 1
        limit = 18
        While 100 > 0
            posn = Int((limit - 0 + 1) * Rnd() + 0)
            sub0 = positions(posn, 0)
            sub1 = positions(posn, 1)
            If posn < limit Then
                For index0 As Integer = posn To limit - 1
                    positions(index0, 0) = positions(index0 + 1, 0)
                    positions(index0, 1) = positions(index0 + 1, 1)
                Next
            End If
            grid(sub0, sub1) = digit
            digit += 1
            If digit > 9 Then
                digit = 1
            End If
            limit -= 1
            If limit < 0

                Exit While
            End If
        End While
    End Sub
   

    Sub preformat_grid()
        For index0 As Integer = 0 To 4
            For index1 As Integer = 0 To 5
                grid(index0, index1) = -999
            Next
        Next
        grid(1, 1) = 1
        grid(1, 2) = 2
        grid(1, 3) = 3
        grid(2, 1) = 8
        grid(2, 2) = 0
        grid(2, 3) = 4
        grid(3, 1) = 7
        grid(3, 2) = 6
        grid(3, 3) = 5
        grid(3, 4) = 9
        grid(4, 5) = 0
    End Sub

 

    Sub find_number_in_grid()
        flag2 = "n"
        For index0 As Integer = 0 To 3
            For index1 As Integer = 0 To 4
                If answer0 = grid(index0, index1) And _
                answer1 = grid(index0, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0, index1) And _
                answer0 = grid(index0, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer0 = grid(index0 + 1, index1) And _
                answer1 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0 + 1, index1) And _
                answer0 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer0 = grid(index0, index1) And _
                answer1 = grid(index0 + 1, index1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0, index1) And _
                answer0 = grid(index0 + 1, index1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer0 = grid(index0, index1 + 1) And _
                answer1 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0, index1 + 1) And _
                answer0 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer0 = grid(index0, index1) And _
                answer1 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0, index1) And _
                answer0 = grid(index0 + 1, index1 + 1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer0 = grid(index0, index1 + 1) And _
                answer1 = grid(index0 + 1, index1) Then
                    flag2 = "y"

                    Exit Sub
                End If
                If answer1 = grid(index0, index1 + 1) And _
                answer0 = grid(index0 + 1, index1) Then
                    flag2 = "y"

                    Exit Sub
                End If
            Next
        Next
    End Sub
End Module