Simple Sudoku Solver in Python
I am going to provide a much more over-the-top strategies to deal with Sudoku rather than outright code snippets so you can try it out on your own.
[Also I am avoiding code-refactor, so that you can focus on Algorithm first, and then we will talk about Code Design, and finally implementation]

However, if you need more explicit help or I am not clear enough, leave a comment, and I would provide more details as needed.

So, the first thing I noticed about your program is that you implement a simple way to select which cell to fill: Find the first empty one, and try filling that.

There is a much more efficient way to do this: find the cell which has only one Value, and fill that first, this will lead you to fill in first few digits of board pretty quickly, and constrain your solution space.

For this: Just iterate over every cell, and store it in dict what are possible values this cell can have. 
Naively: A Cell C can have only values which are not available in its row, its column and its box.
This will lead to something like this:

A1 -- {1, 3, 5}
A2 - {1, 6}
A3 - {6}


and so on...

Now, fun fact! You found out that A3 has only one value, so you fill in that. What this means is that you can now remove 6 from A row and 3rd column as well the box, which will further give 1-value cells, and you can repeat this process till there are no 1-value cells are left.

This will give tremendous speed improvements over your current solution.

But we are not done yet!



Moving forward, there are two ways to go:


Improve our function which determines the values for cell. Remember, our naive function was that a cell has values which are not in row, cell and box. But in Sudoku, we apply other logics as well. For example if both A2 and A3 has value of {2, 4}, then we know that no other cell in A row can have value of 2 and 4, and we can remove it. There are several such strategies which can help you out.
This is how Humans solve Sudoku
Next is Computer's way. Now, you already have a solution which is close to this, which is to have a backtracking mechanism. However, instead of selecting cell randomly, select a cell with least possible values to fill in the random value. For example if you have to choose between A2 which has 2 choices and A4 which has 3 possible choices, fill in A2 first.




These will result in very fast Sudoku solvers :)