Basic Sudoku Solver

Question

For my programming class I had to make a sudoku solver.

import time  # Used to add a delay for user readability

ROWS = COLS = possibleValues = 9  # The rows and columns of the board
GRID_ROWS = GRID_COLS = 3  # The rows and columns in which there are lines
possibleBoard = []


"""Functions"""

def board_filler():
    """Creates the sudoku board from user input"""
    board = [[] for _ in range(ROWS)]  # Creates the nested list to contain the board
    for x in range(ROWS):
        for y in range(COLS):
            # Takes an input makes sure it is good, and if not ask for another one, if it is add it to the list
            while True:
                number = input(
                    f"Please enter an integer for the square in column {x + 1} and in row {y + 1} (hit enter for no number): ")
                try:
                    number = int(number)  # Makes the input that was a string into a number
                    if number > 9 or number < 1:
                        raise ValueError
                    else:
                        board[x].append(number)  # Add the number to the list
                    break  # Exit the loop and let it move on to the next number
                # If its not a number, or a number more 9 or less than 1 runs this
                except (TypeError, ValueError):
                    # If its empty, adds just a space to the list
                    if not number:
                        board[x].append(" ")
                        break
                    else:
                        print("Please enter an integer between 1 and 9, or just hit enter")

    return board


def board_printer(board):
    """Prints the sudoku board"""
    counter = 0  # Makes sure it does not print extra lines
    for row in range(ROWS):
        s = ''  # A variable to contain the row before its printed
        # Adds the items from the list to the variable
        for col in range(COLS):
            s += str(board[row][col]) + ' '
            if not (col + 1) % GRID_COLS:
                s += '| '
        s = s[:-2]  # Removes trailing characters
        print(s)
        # Prints the line of lines
        if not (row + 1) % GRID_ROWS and counter < 2:
            print('-' * len(s))
            counter += 1


def line_solver(board):
    """Remove confirmed values from the possible values in the lines"""
    global possibleBoard
    # Checks to see if there are any duplicate numbers in each row, then removes them from the possible board
    for x in range(ROWS):
        for y in range(COLS):
            if board[x][y] == " ":
                for z in range(COLS):
                    try:
                        possibleBoard[x][y].remove(board[x][
                                                       z])  # Removes values from the possibleBoard that are in the same row as a number on the board
                    # If the number that the code is trying to remove has already been removed, do nothing
                    except (ValueError, AttributeError):
                        pass
    for x in range(ROWS):
        for y in range(COLS):
            if board[x][y] == " ":
                for z in range(ROWS):
                    try:
                        possibleBoard[x][y].remove(board[z][
                                                       y])  # Removes values from the possibleBoard that are in the same row as a number on the board
                    # If the number that the code is trying to remove has already been removed, do nothing
                    except (ValueError, AttributeError):
                        pass
    return board


def square_solver(board):
    """Remove confirmed values from the possible values in the squares"""
    global possibleBoard
    # Sets up a modulator to multiply by to get the 3x3 grid of one square with the first value being the rows and the second being the column
    blockNum = [0, 0]
    for _ in range(9):
        # A loop that checks the 9 numbers in one of the squares
        for x in range(3):
            for y in range(3):
                if not board[(blockNum[0] * 3) + x][(blockNum[1] * 3) + y] == " ":  # Checks if that square a number
                    # Checks all the empty spots in one of the squares for that number, then removes them
                    for z in range(3):
                        for w in range(3):
                            try:
                                # Removes the number from the possible board
                                possibleBoard[(blockNum[0] * 3) + z][(blockNum[1] * 3) + w].remove(
                                    board[(blockNum[0] * 3) + x][(blockNum[1] * 3) + y])
                            # If it can't do anything, run this
                            except (ValueError, AttributeError):
                                pass
        blockNum = block_num(blockNum)
    return board

def board_updater(board):
    """Makes it so if there is any number on the board, that that number is a definite on the possible board"""
    global possibleBoard
    for x in range(ROWS):
        for y in range(COLS):
            if not board[x][y] == " ":
                possibleBoard[x][y] = board[x][y]

def solver(board):
    """Solves a few number of the sudoku board"""
    global possibleBoard
    board_updater(board)
    board = line_solver(board)
    board = square_solver(board)
    # Sets up the counter and a modulator to multiply by to get the 3x3 grid of one square with the first value being the rows and the second being the column
    counter = [0] * 9
    blockNum = [0, 0]
    for _ in range(9):
        for x in range(3):
            for y in range(3):
                # Checks the possible board and counts how many time a possible number appears
                if type(possibleBoard[(blockNum[0] * 3) + x][(blockNum[1] * 3) + y]) == list:
                    for z in range(len(possibleBoard[(blockNum[0] * 3) + x][(blockNum[1] * 3) + y])):
                        counter[possibleBoard[(blockNum[0] * 3) + x][(blockNum[1] * 3) + y][z] - 1] += 1
        for x in range(len(counter)):
            # Checks to see if there was any times only one number appeared
            if counter[x] == 1:
                for y in range(3):
                    for z in range(3):
                        try:
                            # Finds the solo number, and makes that number definite
                            if (x + 1) in possibleBoard[(blockNum[0] * 3) + y][(blockNum[1] * 3) + z]:
                                board[(blockNum[0] * 3) + y][(blockNum[1] * 3) + z] = x + 1
                        except TypeError:
                            pass
        blockNum = block_num(blockNum)
        # Rests the counter
        counter = [0] * 9
    for x in range(ROWS):
        for y in range(COLS):
            # If there is only one number in the possibleBoard list, set that as a definite value on the possibleBoard list and add it to the board list
            if type(possibleBoard[x][y]) == list and len(possibleBoard[x][y]) == 1:
                board[x][y] = possibleBoard[x][y][0]
    return board


def filler():
    """Fills the possible board"""
    listOfLists = [[], [], [], [], [], [], [], [], []]
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # All numbers are possible on an empty board so it fills it with all numbers
    # Adds 9 empty lists to the row list to represent the 9 squares
    for x in range(ROWS):
        for _ in range(ROWS):
            listOfLists[x].append([])
    # Puts the list with the numbers 1-9 in each square
    for x in range(ROWS):
        for y in range(COLS):
            listOfLists[x][y] = numbers.copy()
    return listOfLists


def solve_check():
    """Checks if board is solved"""
    for x in range(ROWS):
        for y in range(COLS):
            if type(possibleBoard[x][y]) == list:
                return False
    return True


"""Repeated code segments"""

def block_num(blockNum):
    """Increments the square"""
    blockNum[1] += 1
    if blockNum[1] > 2:
        blockNum[0] += 1
        blockNum[1] = 0
    return blockNum


possibleBoard = filler()
board = board_filler()
# Solves some numbers, prints the new board then waits to allow user to see changes
while True:
    if solve_check():
        break
    board_printer(board)
    time.sleep(1)
    prevBoard = board
    board = solver(board)
    print("")
# Loops so that if entered from the command line, it does not close
while True:
    pass

As this was the most complicated program I have ever done,I focused on making it work, rather than making it pretty or readable (which caused lots of headache when doing solver function). Looking at the code, there is a lot of things that I wish I had done differently.

Things I Don't Like

• There are a lot of nested for loops that get very confusing
• It's not modular
• solver is really long
• It takes longer to solve then I like

What would be the best way to fix these things, and is there any other things I should change?

Things to Note

• board_filler and board_printer were reviewed in this question
• solver was made after everything else, as I forgot to add it originally
• The reason it goes into the loop at the end is so that if it is run in the command line, it does not close once it is done solving it
• Despite wanting it to go faster, I still want to user to still be able to see it solve the sudoku puzzle

Answer 1

• I think you're over-commenting, but you're a student, so your professor probably is requiring more than needed.
• I think your code has some pretty big problems even after my answer. Over use of globals, lack of SRP, and I don't think your code works with all Sodoku boards. But my answer is long enough.

In board_filler:

• I'd prefer the name create_board, it's not really filling something passed to it, it's creating something.
• Don't raise types, raise instances. raise ValueError(...)
• When raising an error always enter a description.
• Don't use errors for standard control flow. Your if that raises the error can very easily be in the else of the try.
• You can clean up the function by only using two ifs to handle correct numbers and empty cells.
• You can populate board when you are in the loops. You can use a generator function to make the entire function a little more clean too.
• IMO your code violates SRP. By making the innermost while loop be it's own function, you can easily use two comprehensions to make create_board really clean.
• Stop relying on globals and enter the cols and rows.

def get_cell(x, y):
    """Get cell from user input."""
    number = input(
        f"Please enter an integer for the square in column {x + 1}"
        f" and in row {y + 1} (hit enter for no number): "
    )
    while True:
        try:
            number = int(number)
        except TypeError:
            if not number:
                return " "
        else:
            if 1 <= number <= 9:
                return number
        print("Please enter an integer between 1 and 9"
              ", or just hit enter")


def create_board(cols, rows):
    """Create a Sudoku board from user input."""
    return [
        [get_cell(x, y) for y in range(cols)]
        for x in range(rows)
    ]

In board_printer:

• Stop relying on globals. You're just limiting the functionality and reusability of your code without really any benefit.
• Use enumerate, rather than range and indexes.
• Rather than using modulo arithmetic for each row, you can just make a new list using slices.
• You don't need to use modulo arithmetic to display the line. You can just check if the row index is 3 or 6.

def board_printer(board):
    """Prints the sudoku board."""
    for y, row in enumerate(board, 1):
        format_row = (
            row[0:3]
            + ['|']
            + row[3:6]
            + ['|']
            + row[6:9]
        )
        line = ' '.join(map(str, format_row))
        print(line)
        if y in (3, 6):
            print('-' * len(line))

In filler:

• You should merge both loops into one. You can also merge listOfLists into this loop too.
• Your name listOfLists isn't PEP 8 compliant.
• To make the code more reliable you can pass the amount of rows and columns. And also pass what you want to default to.

import copy


def filler(rows, columns, value):
    """Fills the possible board."""
    board = []
    for _ in range(rows):
        row = []
        for _ in range(columns):
            row.append(copy.deepcopy(value))
    return board

in line_solver:

• You don't need two nested loops. if board[x][y] == " ": and the proceeding loops are the same.
• Make two new functions for filling vertically and horizontally.
• There is no need to return.
• Stop relying on globals and just use enumerate.

def remove_existing_horizontal(board, x, y):
    for z in range(len(board[0])):
        try:
            possibleBoard[x][y].remove(board[x][z])
        except (ValueError, AttributeError):
            pass

def remove_existing_vertical(board, x, y):
    for z in range(len(board)):
        try:
            possibleBoard[x][y].remove(board[z][y])
        except (ValueError, AttributeError):
            pass


def line_solver(board):
    """Remove confirmed values from the possible values in the lines."""
    for x, row in enumerate(board):
        for y, item in enumerate(row):
            if item == " ":
                remove_existing_horizontal(board, x, y)
                remove_existing_vertical(board, x, y)

In square_solver:

• blockNum is a PEP 8 naming violation.
• Use != rather than not foo == bar.
• You can simplify your code by making a function that does all the blockNum[0] * 3 + x noise.
• Don't return board.

def square_positions(x, y):
    x *= 3
    y *= 3
    return (
        (x + i, y + j)
        for i in range(3)
        for j in range(3)
    )


def square_solver(board):
    """Remove confirmed values from the possible values in the squares"""
    for block_y in range(3):
        for block_x in range(3):
            for x, y in square_positions(block_x, block_y):
                if board[x][y] != " ":
                    for i, j in square_positions(block_x, block_y):
                        try:
                            possibleBoard[i][j].remove(board[x][y])
                        except (ValueError, AttributeError):
                            pass

In solver:

• Use square_positions that we defined before.
• Use isinstance not type to check the type of a value.
• Use enumerate not for i in range(len(foo)): foo[i].
• Stop using ROWS and COLS and instead use enumerate.

def solver(board):
    """Solves a few number of the sudoku board"""
    global possibleBoard
    board_updater(board)
    line_solver(board)
    square_solver(board)

    counters = [0] * 9
    for block_y in range(3):
        for block_x in range(3):
            for x, y in square_positions(block_x, block_y):
                if isinstance(possibleBoard[x][y], list):
                    for z in range(len(possibleBoard[x][y])):
                        counters[possibleBoard[x][y][z] - 1] += 1
            for i, counter in enumerate(counters, 1):
                # Checks to see if there was any times only one number appeared
                if counter == 1:
                    for x, y in square_positions(block_x, block_y):
                        try:
                            if i in possibleBoard[x][y]:
                                board[x][y] = i
                        except TypeError:
                            pass
    counters = [0] * 9
    for x, row in enumerate(possibleBoard):
        for y, item in enumerate(row):
            if (isinstance(item, list)
                and len(item) == 1
            ):
                board[x][y] = item[0]
    return board

Answer 2

while True:
    if solve_check():
        break

would be a lot more obvious as:

while not solve_check():

And I'd be tempted to change conditions like this:

if not (row + 1) % GRID_ROWS and counter < 2:

to one of:

if (not (row + 1) % GRID_ROWS) and counter < 2:
if not ((row + 1) % GRID_ROWS and counter < 2):

to make it more obvious which you really meant.

Answer 3

It may not be what you are supposed to be learning, but if you use brute force to solve Sudoku, you'll do fine with easy ones (30 clues, asymmetric), but you'll struggle with difficult ones (fewer than 20 clues, symmetrical diagonally) - so why not use a SAT solver library like Google OR Tools to do the solving? Learning to use 3rd party libraries in your program would be an invaluable software development skill, and you'll probably get the fastest solver in your class!

If you choose to do this, your solver will need 9 binary variables for each square - one for each of the possible numbers 1-9.