pythonsudoku

Backtracking Sudoku solver is getting stuck - Python


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

Solution

  • 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.)