I am creating a sudoku game and right now in python and I am stuck on creating a solved board. The functions below create the board and checks if a move is valid, respectively. Each list in the board is a square in the final Sudoku board. The index of the lists are like so:
0 1 2
3 4 5
6 7 8
The index of each element in each list of the board is like so:
0 1 2
3 4 5
6 7 8
The create_Board() function keeps getting stuck at random times. I think that it is because there is no possible move in the next spot. Any suggestions? Here is my code:
def create_Board():
board = [ # initiates the board
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
i = 0
while i < 81: # loops through each square in the board
square = ((i // 9) // 3) * 3 + ((i % 9) // 3)
spot = ((i // 9) % 3) * 3 + ((i % 9) % 3)
board[square][spot] = 0
nums = [j for j in range(1, 10)] # the possible numbers that can be put in the spot
rand.shuffle(nums) # shuffles the numbers
for n in nums:
if is_Valid_Move(board, n, square, spot): # checks if putting that number there is valid
board[square][spot] = n
i += 1 # continues to the next spot
break
elif n == nums[-1]: # if the number is invalid and we reach the end of the array of nums, this moves back 1 spot and tries again
board[square][spot] = 0
i -= 1
return board
def is_Valid_Move(board, num, square, spot):
board[square][spot] = num
f = True
count = 0
for s in board[square]: # checks this square
if s == num:
count += 1
if count > 1:
f = False
count = 0
for i in range(square // 3 * 3, square // 3 * 3 + 3): # checks the row
for j in range(spot // 3 * 3, spot // 3 * 3 + 3):
if board[i][j] == num:
count += 1
if count > 1:
f = False
#return True
count = 0
for i in range(square % 3, 9, 3): # checks the column
for j in range(spot % 3, 9, 3):
if board[i][j] == num:
count += 1
if count > 1:
f = False
return f
The problem is that when you return to a previous square, you might pick the same number as last time. And this is exactly what's happening: you get to a square, k, where there is only one possibility, then move to square k+1, it gets stuck, goes back to k, and k again finds the only possible number, and goes on to k+1 with the very same board. (If there is also only one possibility for k+1, then you just bounce back and forth, and I think that's what's actually happening.) So, as long as you're making forward progress, you need to remember which numbers you've tried in each square and not reuse those. (When you come to a square after generating a new number for the previous square, then you can start from a new random list for that square.)