I'll post the code below, but a brief first.
The solver takes an array, finds an empty square represented by a 0, and checks to see if any number 1-9 fits. If so, it replaces it, and moves onto the next square.
For days it just would fill out half the board, but after some tinkering I got it to magically work, but I really don't know how. You'll see that below the two functions, next_empty_square and is_valid, I have the main loop that performs the operation, which is this:
for n in range(1, 10): ## here is our main loop
if is_valid(y, x, n, board):
board[y][x] = n
if sudoku_solver(board):
return board
board[y][x] = 0
This main loop is where I am confused. I don't know why "if sudoku_solver(board):" suddenly makes it backtrack(it didn't before I worded it specifically this way), and why "board[y][x] =0" doesn't just reset the same square over and over. I am pretty new to this and am learning on my own, so any help would be very much appreciated. Working with grids and lists and arrays is one thing but this recursion stuff really makes my brain hurt.
testboard = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
def sudoku_solver(board):
def next_empty_square(board):
"""Takes a sudoku board and returns the first empty square in the form of a row(y), column(x) coordinate"""
for y in range(9):
for x in range(9):
if board[y][x] == 0:
return y, x
if next_empty_square(board) is None: #if the board is full, it will return none. In that case, return true.
return True
y, x = next_empty_square(board) #gives us the coordinates for the next empty square to use for the is_valid function
def is_valid(y, x, n, board):
"""Takes a y coordinate, an x coordinate, a number(n), and our sudoku board. It checks to see if the number fits in
the coordinates of our board by checking the row, column and 3x3 grid in which the coordinate occurs for other instances of that number."""
for i in range(9): #This loop checks the row
if board[y][i] == n:
return False
for i in range(9): #this loop checks the column
if board[i][x]== n:
return False
ygrid = (y//3)*3
xgrid = (x//3)*3
for i in range(0,3): #This loop checks the 3x3 grid
for j in range(0,3):
if board[ygrid+i][xgrid+j]==n:
return False
return True
for n in range(1, 10): ## here is our main loop
if is_valid(y, x, n, board):
board[y][x] = n
if sudoku_solver(board): ## this is where I have a problem. I am not sure why this recursive function works! Why does it backtrack?
return board
board[y][x] = 0 # I am also not sure why this resets the square that it needs to. It seems like it would just reset the same square over and over
return False
def sudoku_printer(board):
"""Takes our array and prints it to look like a sudoku board"""
for i in range(len(board)):
if i%3 == 0:
print("- - - - - - - - - - - -")
for j in range(len(board[0])):
if j %3 == 0:
print( "| ", end ="")
if j == 8:
print(str(board[i][j])+ " |")
else:
print(str(board[i][j]) + " ", end ="")
print("- - - - - - - - - - - -")
sudoku_printer(sudoku_solver(testboard))
