search

kying18 / sudoku

Sudoku solver using backtracking
122 stars 74 forks source link

Problem I have noticed #2

Open a-s-cash opened 3 years ago

a-s-cash commented 3 years ago

Hi! thank you so much for your helpful tutorial. I have noticed that when I run the code with a sudoku puzzle that is already wrong (for example there is already two of the same digits in one row) it freezes.

kying18 commented 3 years ago

Ah yes, initially I wanted the spec to be that only valid puzzles will be able to be solved. That's why I did not consider the case where the initial puzzle is invalid. Perhaps you can add that component and create a pull request!

koffie commented 3 years ago

@a-s-cash Do you have an example sudoku where it hangs? I think the code should actually return for wrong sudoku's. However the answer that the code produces will be wrong (it might return True in some case where it should actually return False).

If for example your wrong sudoko was

[[ 1, 1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],

 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],

 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1],
 [-1,-1,-1, -1,-1,-1,  -1,-1,-1]]

Then it might appear to hang, but it is not in an infinite loop, it just has too many possibilities to try that it won't return in any reasonably time.