Return to Revisions

Let's break it down, piece by piece.

Generating a matrix

First, move the "generating a potential sudoku matrix" into a separate function. And, we can improve it by making use of list comprehensions:

def generate_sudoku_matrix():
 """Generates a 9x9 matrix with random numbers from 1 to 9, leaving 0s as unsolved."""
 return [[0 if random.random() < 0.1 else random.randint(1, 9)
 for _ in range(9)]
 for _ in range(9)]

Note the use of _ for throw-away variables.

Validating a matrix

First of all, I would call the function check_valid() instead of check_invalid() since you are returning True in case a matrix is valid. Though, a better name would probably be something like is_valid_sudoku().

The function itself is over-complicated and also violates the DRY principle because you basically repeat the same exact check for rows, columns and 3x3 squares.

What if instead we would define a reusable function that would validate a "block" (row, column or square):

def is_valid_block(block):
 """Returns true if a block (row, column or square) is a valid Sudoku block."""
 return len(block) == 9 and sum(block) == sum(set(block))

And apply it to all the 3 cases:

from itertools import chain
def is_valid_sudoku(matrix):
 """Returns True if a Sudoku matrix is valid, False otherwise."""
 # check each row
 for row in matrix:
 if not is_valid_block(row):
 return False
 # check each column
 for col in zip(*matrix):
 if not is_valid_block(col):
 return False
 # check each 3x3 square
 for i in range(0, 9, 3):
 for j in range(0, 9, 3):
 square = list(chain(row[j:j + 3] for row in matrix[i:i + 3]))
 if not is_valid_block(square):
 return False
 return True

We can also take it a step further and make use of generators and all():

def generate_blocks(matrix):
 """Generates rows, columns and 3x3 squares for a Sudoku matrix."""
 for row in matrix:
 yield row
 for col in zip(*matrix):
 yield col
 
 for i in range(0, 9, 3):
 for j in range(0, 9, 3):
 yield list(chain(*(row[j:j + 3] for row in matrix[i:i + 3])))
def is_valid_sudoku(matrix):
 """Returns True if a Sudoku matrix is valid, False otherwise."""
 return all(is_valid_block(block) for block in generate_blocks(matrix))

Solving Sudoku

First of all, move the initial map setup to a separate function to keep the "main" function clean and readable.

I don't particularly like the way you handle exiting the function, using the global found variable. It makes difficult to follow the flow of the program and hurts modularity and separation of concerns.

The other place for improvements is the temporary map and matrix modifications and rollbacks. Though, I am not sure if copying the data structures to pass it to the next recursive call would be cleaner and faster.

I have never written a sudoku solver before, but here is how I would think about implementing the brute-force solution (I guess that is just a different approach and it's not related to the code review):

• define the is_valid_solved_sudoku() function that would validate if a matrix is a valid solved sudoku matrix. The function would be quite similar to the is_valid_sudoku() except the way you would check each of the "blocks" - you would not allow for 0 anymore
• then, the is_valid_solved_sudoku() positive result will be our recursive base condition
• then, on each recursive call, we find the position of the next unsolved cell (with 0 value)
• for each row_index, col_index of the 0 cell, get the set of impossible values/excluded numbers from the corresponding row, column and square
• make a recursive call for every number excluding the numbers from a set of excluded numbers we've constructed on the previous step

Code Style and other issues and suggestions:

• use pretty-printing via pprint instead of a regular print
• unused square_x and square_y variables in the "main" part of the script (that might be actually an error/bug, since, I was expecting you to use them to make a key for the square_map dictionary)
• organize imports per PEP8 (reference)
• two blank lines between the functions (reference)