• Custom User Avatar

    The recursive backtracking structure is clear, what did you to reach sub 3s performance?

  • Custom User Avatar

    Hi Kacarott, I have corrected myself in the 2nd reply; sorry about the confusion.

    As mentioned in the 2nd comment in the question, "the minimum requirement for unique solution is 17 givens" is a bit misleading.
    17 is not a condition to have multiple solutions.

  • Custom User Avatar

    I took another look, the solver is correct; the assumption that givens >= 17 would guarantee a unique solution is falsy.

    Puzzle:
[8, 0, 0, 0, 0, 5, 0, 0, 0]
[0, 0, 0, 8, 0, 4, 0, 0, 0]
[0, 0, 0, 3, 0, 0, 0, 0, 6]
[0, 8, 0, 0, 0, 9, 7, 4, 3]
[0, 5, 0, 0, 0, 8, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 7, 0]
[0, 3, 0, 5, 0, 0, 0, 8, 0]
[9, 7, 2, 4, 0, 0, 0, 5, 0]

Solutions:
[8, 9, 1, 2, 6, 5, 4, 3, 7]
[6, 2, 3, 8, 7, 4, 1, 9, 5]
[7, 4, 5, 3, 9, 1, 8, 2, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[4, 5, 7, 6, 3, 8, 9, 1, 2]
[3, 1, 9, 7, 4, 2, 5, 6, 8]
[5, 6, 8, 9, 1, 3, 2, 7, 4]
[1, 3, 4, 5, 2, 7, 6, 8, 9]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 9, 1, 2, 6, 5, 4, 3, 7]
[6, 2, 3, 8, 7, 4, 1, 9, 5]
[7, 4, 5, 3, 9, 1, 8, 2, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 7, 6, 4, 8, 9, 1, 2]
[4, 1, 9, 7, 3, 2, 5, 6, 8]
[5, 6, 8, 9, 1, 3, 2, 7, 4]
[1, 3, 4, 5, 2, 7, 6, 8, 9]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', '-', '-', 'X', '-', '-', '-', '-']
['X', '-', '-', '-', 'X', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 2, 3, 6, 1, 5, 4, 9, 7]
[6, 9, 7, 8, 2, 4, 1, 3, 5]
[1, 4, 5, 3, 9, 7, 8, 2, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 4, 7, 6, 8, 9, 1, 2]
[7, 1, 9, 2, 4, 3, 5, 6, 8]
[5, 6, 8, 9, 3, 1, 2, 7, 4]
[4, 3, 1, 5, 7, 2, 6, 8, 9]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', 'X', 'X', 'X', 'X', '-', '-', 'X', '-']
['-', 'X', 'X', '-', 'X', '-', '-', 'X', '-']
['X', '-', '-', '-', '-', 'X', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', 'X', 'X', 'X', '-', '-', '-', '-']
['X', '-', '-', 'X', '-', 'X', '-', '-', '-']
['-', '-', '-', '-', 'X', 'X', '-', '-', '-']
['X', '-', 'X', '-', 'X', 'X', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 2, 1, 9, 6, 5, 4, 3, 7]
[6, 9, 3, 8, 7, 4, 1, 2, 5]
[7, 4, 5, 3, 2, 1, 8, 9, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[4, 5, 7, 6, 3, 8, 2, 1, 9]
[3, 1, 9, 7, 4, 2, 5, 6, 8]
[5, 6, 8, 2, 1, 3, 9, 7, 4]
[1, 3, 4, 5, 9, 7, 6, 8, 2]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', 'X', '-', 'X', '-', '-', '-', '-', '-']
['-', 'X', '-', '-', '-', '-', '-', 'X', '-']
['-', '-', '-', '-', 'X', '-', '-', 'X', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', 'X', '-', 'X']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['-', '-', '-', 'X', '-', '-', 'X', '-', '-']
['-', '-', '-', '-', 'X', '-', '-', '-', 'X']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 2, 1, 9, 6, 5, 4, 3, 7]
[6, 9, 3, 8, 7, 4, 1, 2, 5]
[7, 4, 5, 3, 2, 1, 8, 9, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 7, 6, 4, 8, 2, 1, 9]
[4, 1, 9, 7, 3, 2, 5, 6, 8]
[5, 6, 8, 2, 1, 3, 9, 7, 4]
[1, 3, 4, 5, 9, 7, 6, 8, 2]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', 'X', '-', 'X', '-', '-', '-', '-', '-']
['-', 'X', '-', '-', '-', '-', '-', 'X', '-']
['-', '-', '-', '-', 'X', '-', '-', 'X', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', '-', '-', 'X', '-', 'X', '-', 'X']
['X', '-', '-', '-', 'X', '-', '-', '-', '-']
['-', '-', '-', 'X', '-', '-', 'X', '-', '-']
['-', '-', '-', '-', 'X', '-', '-', '-', 'X']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 2, 1, 9, 6, 5, 4, 3, 7]
[6, 9, 3, 8, 7, 4, 1, 2, 5]
[7, 4, 5, 3, 1, 2, 8, 9, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 7, 6, 4, 8, 2, 1, 9]
[4, 1, 9, 7, 2, 3, 5, 6, 8]
[5, 6, 8, 2, 3, 1, 9, 7, 4]
[1, 3, 4, 5, 9, 7, 6, 8, 2]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', 'X', '-', 'X', '-', '-', '-', '-', '-']
['-', 'X', '-', '-', '-', '-', '-', 'X', '-']
['-', '-', '-', '-', 'X', 'X', '-', 'X', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', '-', '-', 'X', '-', 'X', '-', 'X']
['X', '-', '-', '-', 'X', 'X', '-', '-', '-']
['-', '-', '-', 'X', 'X', 'X', 'X', '-', '-']
['-', '-', '-', '-', 'X', '-', '-', '-', 'X']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 9, 3, 6, 1, 5, 4, 2, 7]
[6, 2, 7, 8, 9, 4, 1, 3, 5]
[1, 4, 5, 3, 7, 2, 8, 9, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 4, 7, 6, 8, 9, 1, 2]
[7, 1, 9, 2, 4, 3, 5, 6, 8]
[5, 6, 8, 9, 3, 1, 2, 7, 4]
[4, 3, 1, 5, 2, 7, 6, 8, 9]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', '-', 'X', 'X', 'X', '-', '-', 'X', '-']
['-', '-', 'X', '-', 'X', '-', '-', 'X', '-']
['X', '-', '-', '-', 'X', 'X', '-', 'X', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', 'X', 'X', 'X', '-', '-', '-', '-']
['X', '-', '-', 'X', '-', 'X', '-', '-', '-']
['-', '-', '-', '-', 'X', 'X', '-', '-', '-']
['X', '-', 'X', '-', '-', '-', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']

[8, 9, 3, 6, 1, 5, 4, 2, 7]
[6, 2, 7, 8, 9, 4, 1, 3, 5]
[1, 4, 5, 3, 2, 7, 8, 9, 6]
[2, 8, 6, 1, 5, 9, 7, 4, 3]
[3, 5, 4, 7, 6, 8, 9, 1, 2]
[7, 1, 9, 2, 4, 3, 5, 6, 8]
[5, 6, 8, 9, 3, 1, 2, 7, 4]
[4, 3, 1, 5, 7, 2, 6, 8, 9]
[9, 7, 2, 4, 8, 6, 3, 5, 1]

['-', '-', 'X', 'X', 'X', '-', '-', 'X', '-']
['-', '-', 'X', '-', 'X', '-', '-', 'X', '-']
['X', '-', '-', '-', 'X', 'X', '-', 'X', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
['X', '-', 'X', 'X', 'X', '-', '-', '-', '-']
['X', '-', '-', 'X', '-', 'X', '-', '-', '-']
['-', '-', '-', '-', 'X', 'X', '-', '-', '-']
['X', '-', 'X', '-', 'X', 'X', '-', '-', '-']
['-', '-', '-', '-', '-', '-', '-', '-', '-']
  • Custom User Avatar

    Potential an error in the checker script:

    The following input generates a false error message "invalid should raise error":
    I have (possibly) replicated how to the two solutions are found on different paths, but they are the same.
    Below is my results without early exit; with givens == 27, the question cannot have multiple solutions.

    givens =  29
Puzzle:
[9, 0, 0, 5, 0, 0, 0, 0, 4]
[0, 0, 7, 0, 4, 0, 3, 0, 0]
[6, 0, 0, 0, 0, 3, 0, 7, 5]
[0, 4, 0, 0, 2, 0, 7, 0, 0]
[7, 0, 2, 0, 0, 0, 0, 0, 1]
[0, 0, 3, 0, 8, 0, 0, 5, 0]
[4, 2, 0, 1, 0, 0, 0, 0, 7]
[0, 0, 1, 0, 6, 0, 5, 0, 0]
[3, 0, 0, 0, 0, 5, 0, 0, 8]

Solutions:
[9, 3, 8, 5, 1, 7, 2, 6, 4]
[2, 5, 7, 8, 4, 6, 3, 1, 9]
[6, 1, 4, 2, 9, 3, 8, 7, 5]
[5, 4, 9, 3, 2, 1, 7, 8, 6]
[7, 8, 2, 6, 5, 4, 9, 3, 1]
[1, 6, 3, 7, 8, 9, 4, 5, 2]
[4, 2, 5, 1, 3, 8, 6, 9, 7]
[8, 7, 1, 9, 6, 2, 5, 4, 3]
[3, 9, 6, 4, 7, 5, 1, 2, 8]

[9, 3, 8, 5, 1, 7, 2, 6, 4]
[2, 5, 7, 8, 4, 6, 3, 1, 9]
[6, 1, 4, 2, 9, 3, 8, 7, 5]
[5, 4, 9, 3, 2, 1, 7, 8, 6]
[7, 8, 2, 6, 5, 9, 4, 3, 1]
[1, 6, 3, 7, 8, 4, 9, 5, 2]
[4, 2, 5, 1, 3, 8, 6, 9, 7]
[8, 7, 1, 9, 6, 2, 5, 4, 3]
[3, 9, 6, 4, 7, 5, 1, 2, 8]