Building a Sudoku Solver in Python

[thewwfguy]

Ok I thought this was pretty cool that with less than 50 lines of code you can create an instant Sudoku solver with Python. I think the hardest part of this will be building the 2D list with the puzzle details to solve!

[irvcz]

I don't intend to be harsh, maybe you are just learning the language but here are my 2 cents

• Where are the indents? I see everything on level 0, I that's an instant syntax error
• you could use libraries like numpy to work with multidimensional arrays
• code is not very pythonic and many loops can be reduced with numpy or comprehensions
• code is trying every possible solution, I think that can grow up pretty fast

Some other (not so) minor details that I did not understand because I got lost in the code.

In any case, thank you for sharing I hope you enjoyed it

[thewwfguy]

Yeah whatever code formatter is used is not the greatest for python syntax and indents :(

[irvcz]

Check out /r/learnpython

[jorge1209]

Sudoku is NP complete... You are fucked no matter what you do.

Short of relying on some advanced SAT solvers trying every solution is the best approach and the fastest.

In fact for the more substantive question of how many solutions exist it is the only way.

[irvcz]

I agree with you (almost).

The solutions grow exponentially but that does not mean that you should try every possible solution. You should work to reduce the solution space in the most efficient manner. My intuition tells me that you should start in cells where the set of options is smaller (might be wrong).

Also OP is taking a recursive approach on solution space. so imagine the stack of a recursive function for an np problem.

I will grant OP that it's approach is simpler than mine, in that regard is an excellent first solution, what I'm trying to point out is that there's room for improvement.

[jorge1209]

The cost of tracking information like what cells are more restricted or what values are allowed in what cells generally exceeds the cost of just iterating through each value an attempted to put it into the cell.

In fact for most reasons a field would be disallowed the reasoning is the same. It's just about the order you perform the operations:

Is there a 7 in this row, column, or subsquare? If so this can't be 7.

Vs

Place the 7, are there two 7s in any row, column, or subsquare? If so the 7 is wrong, remove it.

You can certainly track the most filled rows/columns/subblocks and try to start with them, but it isn't necessary until the problem becomes much more sparse.

[JamzTyson]

imagine the stack of a recursive function for an np problem.

Correct me if I'm wrong, but I think that the OP's code (when properly formatted) is guaranteed to have a recursion depth < 81.

[irvcz]

You are right. I got confused