How to solve Sudoku with Python?

Question

I was wondering how to solve this Sudoku board in Python using Human input and Computer solving. I have a Human and Computer solve def. I tried using rows and columns to solve and it just wouldn't print the results on the board every time it would work. I tried doing these using things such as for 'i in range'. But when I would run the program it would be working but not printing the results each time it was solving it. Thank you!

import time, sys, random

def print_board(sudoku):
for i in range(9):
    print(sudoku[i][0:3],'|',sudoku[i][3:6],'|',sudoku[i][6:9])
    if i==5 or i==2:
        print('-'*51)
        
if __name__ == '__main__':
 # Don't change the layout of the following sudoku examples
sudoku1 = [
    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],
    ['2', ' ', '3', '7', '8', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', ' ', ' ', ' ', ' ', '9', ' '],
    ['4', ' ', ' ', ' ', '6', '1', ' ', ' ', '2'],
    ['6', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '4', ' ', ' ', ' ', '1', ' ', '7'],
    [' ', ' ', ' ', ' ', '3', '7', '9', '4', ' '],
]
sudoku2 = [
    [' ', ' ', ' ', '3', ' ', ' ', ' ', '7', ' '],
    ['7', '3', '4', ' ', '8', ' ', '1', '6', '2'],
    ['2', ' ', ' ', ' ', ' ', ' ', ' ', '3', '8'],
    ['5', '6', '8', ' ', ' ', '4', ' ', '1', ' '],
    [' ', ' ', '2', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', '8', ' ', ' ', '2', '5', '4'],
    [' ', '7', ' ', ' ', ' ', '2', '8', '9', ' '],
    [' ', '5', '1', '4', ' ', ' ', '7', '2', '6'],
    ['9', ' ', '6', ' ', ' ', ' ', ' ', '4', '5'],
]
sudoku3 = [
    ['8', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '3', '6', ' ', ' ', ' ', ' ', ' '],
    [' ', '7', ' ', ' ', '9', ' ', '2', ' ', ' '],
    [' ', '5', ' ', ' ', ' ', '7', ' ', ' ', ' '],
    [' ', ' ', ' ', ' ', '4', '5', '7', ' ', ' '],
    [' ', ' ', ' ', '1', ' ', ' ', ' ', '3', ' '],
    [' ', ' ', '1', ' ', ' ', ' ', ' ', '6', '8'],
    [' ', ' ', '8', '5', ' ', ' ', ' ', '1', ' '],
    [' ', '9', ' ', ' ', ' ', ' ', '4', ' ', ' '],
]
sudoku4 = [
    [' ', '4', '1', ' ', ' ', '8', ' ', ' ', ' '],
    ['3', ' ', '6', '2', '4', '9', ' ', '8', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', '7', ' '],
    [' ', ' ', ' ', '4', '7', ' ', '2', '1', ' '],
    ['7', ' ', ' ', '3', ' ', ' ', '4', ' ', '6'],
    [' ', '2', ' ', ' ', ' ', ' ', ' ', '5', '3'],
    [' ', ' ', '7', ' ', '9', ' ', '5', ' ', ' '],
    [' ', ' ', '3', ' ', '2', ' ', ' ', ' ', ' '],
    [' ', '5', '4', ' ', '6', '3', ' ', ' ', ' '],
]
option = 2

if option == 1:
    sudoku = sudoku1
elif option == 2:
    sudoku = sudoku2
elif option == 3:
    sudoku = sudoku3
elif option == 4:
    sudoku = sudoku4
else:
    raise ValueError('Invalid choice!')

# Player Types | Computer or Player depending on the input below!
def Human_play():
   print('The Human Plays.')

def Computer_play():
   print('The Computer Plays')

# Chooses Player Type
Player_Type = ''
while Player_Type != 'Human' or 'Computer':
   Player_Type = input('"Human" or "Computer" solve?: ')
if Player_Type == 'Human' or 'human' or 'HUMAN':
    Human_play()
    print_board(sudoku)
    break
elif Player_Type == 'Computer' or 'computer' or 'COMPUTER':
    Computer_play()
    print_board(sudoku)
    break
else:
    print('Invalid Player Type!\nMake sure you use "Human" or "Computer"')

Answer 1

You would solve it programmatically the same way you would solve it as an intelligent human.

Have a set of discovery rules that you apply to groups (rows, columns, or 3-by-3s) to eliminate possibilities, or select values where there is but one possibility.

For example, consider the first three rows in the first puzzle:

    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],

As a human, I would realise that only 38 is allowed in the two empty cells in row one but 8 is disallowed in the first cell because it's already in the top left 3x3. You just get your code to do the same thing, along the lines of:

• Start with all empty cells on the board containing the full range 123456789. You now have discovered cells (with one possible value) and undiscovered cells (with two or more possibilities).

• For each undiscovered cell, apply discovery rules one by one. The first undiscovered cell in row one has all but 38 eliminated because all the other values in row one dictate that.

• It then has 246 eliminated because of the column (irrelevant because the row already eliminated them).

• The 3x3 eliminates 152486 of which only 8 has an effect. That means the cell is now 3 and it is now discovered.

• The second undiscovered cell in row one now has all but 8 eliminated because of the row (it's the one value remaining).

---

I actually implemented such a beast that would actually do this^(a). It fully solved simple Sudoku puzzles with relatively simple rules like those given above, but the more complicated ones had to use look-ahead to find impossible situations and discard them. For example, let's say you followed all the basic discovery rules but you still have undiscovered cells.

Just set one of the empty cells with two (or the smallest number of) possibilities to a specific value and then carry on. You'll eventually figure out that either:

• You end up with a duplicate value in a group (in which case you go back and set the original cell to the other possibility).

• You finish the puzzle successfully in which case you made the right choice originally.

• You get the same situation (at least two possibilities in every empty cell).

In that final case, you just have to do the same thing again. You have to handle multiple branches in your search space but that's reasonably easy with recursion.

---

The discovery strategies are basically self-contained, such as:

• If a group already has a specific (discovered) value, that value can be eliminated from every other undiscovered cell in the group.

• If the cell in question has a value not found anywhere else in the group, it must be that value.

• If a group has N cells which only allow the same N values, those values can be eliminated elsewhere, An example is a row with three empty cells with possibilities 12, 12, and 123. Since the first two must be 1 and 2, the third must be 3 even though you don't know which of the others is 1 or 2.

---

Applying just those two rules to every cell one by one, and repeating as many times as necessary, solves the first puzzle completely:

sudoku1 = [
    ['3', '1', '5', '4', '7', '8', '2',  '6', '9'],
    ['9', '4', '2', '3', '5', '6', '7',  '1', '8'],
    ['7', '8', '6', '2', '1', '9', '4',  '3', '5'],
    ['2', '9', '3', '7', '8', '4', '6',  '5', '1'],
    ['1', '6', '7', '5', '2', '3', '8',  '9', '4'],
    ['4', '5', '8', '9', '6', '1', '3 ', '7', '2'],
    ['6', '7', '9', '1', '4', '2', '5',  '8', '3'],
    ['8', '3', '4', '6', '9', '5', '1',  '2', '7'],
    ['5', '2', '1', '8', '3', '7', '9',  '4', '6'],
]

---

Here's the code you can start with, it implements only the first elimination rule shown above:

import time

puzzle = [
    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],
    ['2', ' ', '3', '7', '8', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', ' ', ' ', ' ', ' ', '9', ' '],
    ['4', ' ', ' ', ' ', '6', '1', ' ', ' ', '2'],
    ['6', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '4', ' ', ' ', ' ', '1', ' ', '7'],
    [' ', ' ', ' ', ' ', '3', '7', '9', '4', ' '],
]

# Expand empty cells to full range of possible values.

for row in range(len(puzzle)):
    for col in range(len(puzzle[row])):
        if puzzle[row][col] == " ":
            puzzle[row][col] = "123456789"

# Exit if everything solved.

while not all([(len(cell) == 1) for row in puzzle for cell in row]):
    for row in range(len(puzzle)):
        for col in range(len(puzzle[row])):
            print(f" {puzzle[row][col]:10} ", end="")
        print()
    print("Press ENTER: ", end="")
    input()

    # Allow for full cycle with no change to break, this means
    # current rule set is not enough.

    changed = False

    # Process each undiscovered cell.

    for row in range(len(puzzle)):
        for col in range(len(puzzle[row])):
            if len(puzzle[row][col]) != 1:
                # Eliminate all values in row.

                for col2 in range(len(puzzle[row])):
                    if col2 != col and len(puzzle[row][col2]) == 1:
                        if puzzle[row][col2] in puzzle[row][col]:
                            changed = True
                            puzzle[row][col] = puzzle[row][col].replace(puzzle[row][col2], "")

                # Eliminate all values in column.

                for row2 in range(len(puzzle)):
                    if row2 != row and len(puzzle[row2][col]) == 1:
                        if puzzle[row2][col] in puzzle[row][col]:
                            changed = True
                            puzzle[row][col] = puzzle[row][col].replace(puzzle[row2][col], "")

                # Eliminate all values in 3x3.

                base_row = row - row % 3
                base_col = col - col % 3

                for row2 in range(base_row, base_row + 3):
                    for col2 in range(base_col, base_col + 3):
                        if (row2 != row or col2 != col) and len(puzzle[row2][col2]) == 1:
                            if puzzle[row2][col2] in puzzle[row][col]:
                                changed = True
                                puzzle[row][col] = puzzle[row][col].replace(puzzle[row2][col2], "")

    if not changed:
        break

That's enough to get it to a state where you can see the second rule would start to kick in (though I've modified the output slightly for formatting purposes):

1-9   1     5     4     7     1-9   2     6     9
1-9   4     2     3     5     6     7     1-9   8
1-9   8     6     1-9   1-9   1-9   1-9   3     1-9
2     1-9   3     7     8     1-9   1-9   1-9   1-9
1-9   1-9   7     1-9   1-9   1-9   1-9   9     1-9
4     1-9   1-9   1-9   6     1     1-9   1-9   2
6     1-9   1-9   1     1-9   1-9   1-9   1-9   1-9
1-9   1-9   4     1-9   1-9   1-9   1     1-9   7
1-9   1-9   1-9   1-9   3     7     9     4     1-9
Press ENTER:

3     1       5    4       7     8      2      6    9
9     4       2    3       5     6      7      1    8
7     8       6    29      129   29     45     3    45
2     569     3    7       8     459    456    5    146
158   56      7    25      24    2345   3468   9    1346
4     59      89   59      6     1      38     78   2
6     23579   89   1       249   2459   358    28   35
58    2359    4    25689   29    259    1      28   7
158   25      18   2568    3     7      9      4    56
Press ENTER:

3     1       5    4       7       8      2      6   9
9     4       2    3       5       6      7      1   8
7     8       6    29      129     29     45     3   45
2     69      3    7       8       49     46     5   146
158   56      7    25      24      2345   3468   9   1346
4     59      89   59      6       1      38    78   2
6     23579   89   1       249     2459   358   28   35
58    2359    4    25689   29      259    1     28   7
158   25      18   2568    3       7      9     4    56
Press ENTER:

Implementing the other rules would take care of, for example:

• the third row with its 29, 129, 29 set, the middle one must be a 1.
• the sixth row with its 59, 89, 59 set, the middle one must be a 8.
• the second column with only the seventh row containing a 7, so it must be 7.
• the second column with its 69, 56, 59 set, this eliminates all those numbers from other cells in the column.

---

^(a) Mostly as an exercise in coding. I much prefer solving them myself. In any case, the current thing keeping my aging brain functional is Kakuro, you should give that a try :-)