Sudoku Puzzle
Sudoku is a popular puzzle game in newspapers and mobile apps. The Sudoku board is a 9 × 9 grid in which the player must place the digits 1 to 9 once, and only once, in each row, column, and 3 × 3 subgrid. The game begins with a few spaces already filled in with digits, called givens. A well-formed Sudoku puzzle will have only one possible valid solution.
Objects of the SudokuGrid class are the data structures that represent the Sudoku grid. You can call their methods to make modifications to, or retrieve information about, the grid. For example, the makeMove() method places a number on the grid, the resetGrid() method restores the grid to its original state, and isSolved() returns True if all the solution’s numbers have been placed on the grid.
The main part of the program, starting on line 141, uses a SudokuGrid object and its methods for this game, but you could also copy and paste this class into other Sudoku programs you create to reuse its functionality.
sudoku_puzzle.py
1"""Sudoku Puzzle, by Al Sweigart al@inventwithpython.com
2The classic 9x9 number placement puzzle.
3More info at https://en.wikipedia.org/wiki/Sudoku
4This code is available at https://nostarch.com/big-book-small-python-programming
5Tags: large, game, object-oriented, puzzle"""
6
7import copy, random, sys
8
9# This game requires a sudokupuzzle.txt file that contains the puzzles.
10# Download it from https://inventwithpython.com/sudokupuzzles.txt
11# Here's a sample of the content in this file:
12# ..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..
13# 2...8.3...6..7..84.3.5..2.9...1.54.8.........4.27.6...3.1..7.4.72..4..6...4.1...3
14# ......9.7...42.18....7.5.261..9.4....5.....4....5.7..992.1.8....34.59...5.7......
15# .3..5..4...8.1.5..46.....12.7.5.2.8....6.3....4.1.9.3.25.....98..1.2.6...8..6..2.
16
17# Set up the constants:
18EMPTY_SPACE = '.'
19GRID_LENGTH = 9
20BOX_LENGTH = 3
21FULL_GRID_SIZE = GRID_LENGTH * GRID_LENGTH
22
23
24class SudokuGrid:
25 def __init__(self, originalSetup):
26 # originalSetup is a string of 81 characters for the puzzle
27 # setup, with numbers and periods (for the blank spaces).
28 # See https://inventwithpython.com/sudokupuzzles.txt
29 self.originalSetup = originalSetup
30
31 # The state of the sudoku grid is represented by a dictionary
32 # with (x, y) keys and values of the number (as a string) at
33 # that space.
34 self.grid = {}
35 self.resetGrid() # Set the grid state to its original setup.
36 self.moves = [] # Tracks each move for the undo feature.
37
38 def resetGrid(self):
39 """Reset the state of the grid, tracked by self.grid, to the
40 state in self.originalSetup."""
41 for x in range(1, GRID_LENGTH + 1):
42 for y in range(1, GRID_LENGTH + 1):
43 self.grid[(x, y)] = EMPTY_SPACE
44
45 assert len(self.originalSetup) == FULL_GRID_SIZE
46 i = 0 # i goes from 0 to 80
47 y = 0 # y goes from 0 to 8
48 while i < FULL_GRID_SIZE:
49 for x in range(GRID_LENGTH):
50 self.grid[(x, y)] = self.originalSetup[i]
51 i += 1
52 y += 1
53
54 def makeMove(self, column, row, number):
55 """Place the number at the column (a letter from A to I) and row
56 (an integer from 1 to 9) on the grid."""
57 x = 'ABCDEFGHI'.find(column) # Convert this to an integer.
58 y = int(row) - 1
59
60 # Check if the move is being made on a "given" number:
61 if self.originalSetup[y * GRID_LENGTH + x] != EMPTY_SPACE:
62 return False
63
64 self.grid[(x, y)] = number # Place this number on the grid.
65
66 # We need to store a separate copy of the dictionary object:
67 self.moves.append(copy.copy(self.grid))
68 return True
69
70 def undo(self):
71 """Set the current grid state to the previous state in the
72 self.moves list."""
73 if self.moves == []:
74 return # No states in self.moves, so do nothing.
75
76 self.moves.pop() # Remove the current state.
77
78 if self.moves == []:
79 self.resetGrid()
80 else:
81 # set the grid to the last move.
82 self.grid = copy.copy(self.moves[-1])
83
84 def display(self):
85 """Display the current state of the grid on the screen."""
86 print(' A B C D E F G H I') # Display column labels.
87 for y in range(GRID_LENGTH):
88 for x in range(GRID_LENGTH):
89 if x == 0:
90 # Display row label:
91 print(str(y + 1) + ' ', end='')
92
93 print(self.grid[(x, y)] + ' ', end='')
94 if x == 2 or x == 5:
95 # Display a vertical line:
96 print('| ', end='')
97 print() # Print a newline.
98
99 if y == 2 or y == 5:
100 # Display a horizontal line:
101 print(' ------+-------+------')
102
103 def _isCompleteSetOfNumbers(self, numbers):
104 """Return True if numbers contains the digits 1 through 9."""
105 return sorted(numbers) == list('123456789')
106
107 def isSolved(self):
108 """Returns True if the current grid is in a solved state."""
109 # Check each row:
110 for row in range(GRID_LENGTH):
111 rowNumbers = []
112 for x in range(GRID_LENGTH):
113 number = self.grid[(x, row)]
114 rowNumbers.append(number)
115 if not self._isCompleteSetOfNumbers(rowNumbers):
116 return False
117
118 # Check each column:
119 for column in range(GRID_LENGTH):
120 columnNumbers = []
121 for y in range(GRID_LENGTH):
122 number = self.grid[(column, y)]
123 columnNumbers.append(number)
124 if not self._isCompleteSetOfNumbers(columnNumbers):
125 return False
126
127 # Check each box:
128 for boxx in (0, 3, 6):
129 for boxy in (0, 3, 6):
130 boxNumbers = []
131 for x in range(BOX_LENGTH):
132 for y in range(BOX_LENGTH):
133 number = self.grid[(boxx + x, boxy + y)]
134 boxNumbers.append(number)
135 if not self._isCompleteSetOfNumbers(boxNumbers):
136 return False
137
138 return True
139
140
141print('''Sudoku Puzzle, by Al Sweigart al@inventwithpython.com
142
143Sudoku is a number placement logic puzzle game. A Sudoku grid is a 9x9
144grid of numbers. Try to place numbers in the grid such that every row,
145column, and 3x3 box has the numbers 1 through 9 once and only once.
146
147For example, here is a starting Sudoku grid and its solved form:
148
149 5 3 . | . 7 . | . . . 5 3 4 | 6 7 8 | 9 1 2
150 6 . . | 1 9 5 | . . . 6 7 2 | 1 9 5 | 3 4 8
151 . 9 8 | . . . | . 6 . 1 9 8 | 3 4 2 | 5 6 7
152 ------+-------+------ ------+-------+------
153 8 . . | . 6 . | . . 3 8 5 9 | 7 6 1 | 4 2 3
154 4 . . | 8 . 3 | . . 1 --> 4 2 6 | 8 5 3 | 7 9 1
155 7 . . | . 2 . | . . 6 7 1 3 | 9 2 4 | 8 5 6
156 ------+-------+------ ------+-------+------
157 . 6 . | . . . | 2 8 . 9 6 1 | 5 3 7 | 2 8 4
158 . . . | 4 1 9 | . . 5 2 8 7 | 4 1 9 | 6 3 5
159 . . . | . 8 . | . 7 9 3 4 5 | 2 8 6 | 1 7 9
160''')
161input('Press Enter to begin...')
162
163
164# Load the sudokupuzzles.txt file:
165with open('sudokupuzzles.txt') as puzzleFile:
166 puzzles = puzzleFile.readlines()
167
168# Remove the newlines at the end of each puzzle:
169for i, puzzle in enumerate(puzzles):
170 puzzles[i] = puzzle.strip()
171
172grid = SudokuGrid(random.choice(puzzles))
173
174while True: # Main game loop.
175 grid.display()
176
177 # Check if the puzzle is solved.
178 if grid.isSolved():
179 print('Congratulations! You solved the puzzle!')
180 print('Thanks for playing!')
181 sys.exit()
182
183 # Get the player's action:
184 while True: # Keep asking until the player enters a valid action.
185 print() # Print a newline.
186 print('Enter a move, or RESET, NEW, UNDO, ORIGINAL, or QUIT:')
187 print('(For example, a move looks like "B4 9".)')
188
189 action = input('> ').upper().strip()
190
191 if len(action) > 0 and action[0] in ('R', 'N', 'U', 'O', 'Q'):
192 # Player entered a valid action.
193 break
194
195 if len(action.split()) == 2:
196 space, number = action.split()
197 if len(space) != 2:
198 continue
199
200 column, row = space
201 if column not in list('ABCDEFGHI'):
202 print('There is no column', column)
203 continue
204 if not row.isdecimal() or not (1 <= int(row) <= 9):
205 print('There is no row', row)
206 continue
207 if not (1 <= int(number) <= 9):
208 print('Select a number from 1 to 9, not ', number)
209 continue
210 break # Player entered a valid move.
211
212 print() # Print a newline.
213
214 if action.startswith('R'):
215 # Reset the grid:
216 grid.resetGrid()
217 continue
218
219 if action.startswith('N'):
220 # Get a new puzzle:
221 grid = SudokuGrid(random.choice(puzzles))
222 continue
223
224 if action.startswith('U'):
225 # Undo the last move:
226 grid.undo()
227 continue
228
229 if action.startswith('O'):
230 # View the original numbers:
231 originalGrid = SudokuGrid(grid.originalSetup)
232 print('The original grid looked like this:')
233 originalGrid.display()
234 input('Press Enter to continue...')
235
236 if action.startswith('Q'):
237 # Quit the game.
238 print('Thanks for playing!')
239 sys.exit()
240
241 # Handle the move the player selected.
242 if grid.makeMove(column, row, number) == False:
243 print('You cannot overwrite the original grid\'s numbers.')
244 print('Enter ORIGINAL to view the original grid.')
245 input('Press Enter to continue...')