Reputation:
How to solve Sudoku with Python?
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"')
Upvotes: 1
Views: 673
Answers (1)
Reputation: 881363
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
38eliminated because all the other values in row one dictate that.It then has
246eliminated because of the column (irrelevant because the row already eliminated them).The 3x3 eliminates
152486of which only8has an effect. That means the cell is now3and it is now discovered.The second undiscovered cell in row one now has all but
8eliminated 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
Nvalues, those values can be eliminated elsewhere, An example is a row with three empty cells with possibilities12,12, and123. Since the first two must be1and2, the third must be3even though you don't know which of the others is1or2.
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, 29set, the middle one must be a1. - the sixth row with its
59, 89, 59set, the middle one must be a8. - the second column with only the seventh row containing a
7, so it must be7. - the second column with its
69, 56, 59set, 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 :-)
Upvotes: 2