Speed up Sudoku Solver

I made this Sudoku solver using depth first search, it takes less than 0.1 second to solve any simple solution(no guessing), but if the solution requires guessing (thus using the DFS) its time grows exponentially.

One puzzle ('hard') makes 10 consecutive branches in the search, thus allowing 210 (I guess) possible outcomes. It takes around 40 seconds to beat this puzzle.

HARD - 3 RUNS
Total: 114.4 seconds
Mean: 38.13433 seconds
Max: 38.67300 seconds
Min: 37.74700 seconds

get_missing_values()
Called: 475437 times per run(1426311 total)
Running for 87.362s(in 3 runs) / 29.12073s per run
create_cells()
Called: 47700 times per run(143100 total)
Running for 19.419s(in 3 runs) / 6.47302s per run
get_next_moves()
Called: 47700 times per run(143100 total)
Running for 6.117s(in 3 runs) / 2.03890s per run
depth_first_search()
Called: 1 times per run(3 total)
Running for 0.856s(in 3 runs) / 0.28532s per run
possible_moves()
Called: 47700 times per run(143100 total)
Running for 0.647s(in 3 runs) / 0.21570s per run
main()
Called: 1 times per run(1 total)
Running for 0.056s(in 3 runs) / 0.01876s per run
win()
Called: 1 times per run(3 total)
Running for 0.000s(in 3 runs) / 0.00002s per run


As you can see, the source of the most 'work' is the method get_missing_values from the class Cell, which takes 76% of all the workload. This method searches for every cell in the grid and compare it to the others to get what possible values could be placed there. I tried to squeeze it as much as I could, using multiple if-conditions, but it still takes a lot of work.

`import functools
import time

DEBUGGER_TIMER = {}

def timeit(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
t_start = time.clock()
ret = func(*args, **kwargs)
t_end = time.clock() - t_start
function_name = func.__name__
if function_name in DEBUGGER_TIMER:
DEBUGGER_TIMER[function_name][0] += t_end
D

I think it would be fairly faster to store which numbers have already been used in two int[9] arrays and in one int[3][3] matrix. Then using bitmaps to represent which number have been used in each column, row and group.

For example, when you put 3 in the cell (3,4), you would:

row[3] |= 1<<3. column[4] |= 1<<3, group[1][2] |= 1<<3 and then you could check if a number is in a row, col or group with if row[rowNumber] & 1<<number: etc.

You get the point. That would be fairly faster in my opinion. Although I don't have any benchmark. I think this because then, instead of checking every cell for each new value, you check only 3 (once per # you want to discard, so 27 total).

How it works?

row is an array of 9 positions. Each int stores the info for which number has been used in the specified row.
As you know, an int is stored as a 32-bit binary number. When you do row[3] |= 1<<3 what you are actually doing is setting the 4th least significant bit to one. So if the number was (I'm only going to use 10 bits for clarity) 0000000000 it becomes 0000001000. That way, when you have a row that for example has the 1, 3, 9 used. You would have the number marked as 1000001010 (The last 0 is never marked, this to use base 1 for clarity of code). Now, how can you know which bit is marked? Well, using bitwise and &. So you create the number which only has the bit you want to ask for marked 1<<number, and then use & to extract a number that only might have that number marked (as every other bit will be compared to 0 and always yield 0). So you do row[3] & 1<<9 for example to ask if, in the row number 3, the number 9 has been used. In the bottom, you would be doing (keeping with the example of the row with 1, 3, 9):

1000001010 &
1000000000
----------
1000000000

This will yield a positive (i.e. non-zero) number, which you can "if" to see it's truth value.

If it was false (for example, asking for 8):

1000001010 &
0100000000
----------
0000000000

This would yield 0, so the if would be false.

Update: Further modifications

In order to not recreate over and over the entire state of the board (using store so many times). You could keep one state at the beginning of ROWS, COLUMNS and GROUPS. And then, each time you store something in the stack, put there also what is the move you made (row, column, group and value). So, each time you pop something from the stack, you store the move at that point (only one thing to be stored, much more efficient). And at the end of the cycle you can unstore it by simply doing (for example) ROWS[row] &= ~(1<<value). This is how I understand your code, it might not be right, but you can analyze this and tell me if it might work.

StackExchange Code Review Q#74715, answer score: 6