#73
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.

The Program in Action

When you run sudoku.py, the output will look like this:

Sudoku Puzzle, by Al Sweigart [email protected]
--snip--
   A B C   D E F   G H I
1  . . . | . . . | . . .
2  . 7 9 | . 5 . | 1 8 .
3  8 . . | . . . | . . 7
   ------+-------+------
4  . . 7 | 3 . 6 | 8 . .
5  4 5 . | 7 . 8 | . 9 6
6  . . 3 | 5 . 2 | 7 . .
   ------+-------+------
7  7 . . | . . . | . . 5
8  . 1 6 | . 3 . | 4 2 .
9  . . . | . . . | . . .

Enter a move, or RESET, NEW, UNDO, ORIGINAL, or QUIT:
(For example, a move looks like "B4 9".)
--snip--

How It Works

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.


  1. """Sudoku Puzzle, by Al Sweigart [email protected]
  2. The classic 9x9 number placement puzzle.
  3. More info at https://en.wikipedia.org/wiki/Sudoku
  4. This code is available at https://nostarch.com/big-book-small-python-programming
  5. Tags: large, game, object-oriented, puzzle"""
  6. 
  7. import 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:
 18. EMPTY_SPACE = '.'
 19. GRID_LENGTH = 9
 20. BOX_LENGTH = 3
 21. FULL_GRID_SIZE = GRID_LENGTH * GRID_LENGTH
 22. 
 23. 
 24. class 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. 
141. print('''Sudoku Puzzle, by Al Sweigart [email protected]
142. 
143. Sudoku is a number placement logic puzzle game. A Sudoku grid is a 9x9
144. grid of numbers. Try to place numbers in the grid such that every row,
145. column, and 3x3 box has the numbers 1 through 9 once and only once.
146. 
147. For 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. ''')
161. input('Press Enter to begin...')
162. 
163. 
164. # Load the sudokupuzzles.txt file:
165. with open('sudokupuzzles.txt') as puzzleFile:
166.     puzzles = puzzleFile.readlines()
167. 
168. # Remove the newlines at the end of each puzzle:
169. for i, puzzle in enumerate(puzzles):
170.     puzzles[i] = puzzle.strip()
171. 
172. grid = SudokuGrid(random.choice(puzzles))
173. 
174. while 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...')

Exploring the Program

Try to find the answers to the following questions. Experiment with some modifications to the code and rerun the program to see what effect the changes have.

What error happens if you delete or rename the sudokupuzzles.txt file and run the program?
What happens if you change str(y + 1) on line 91 to str(y)?
What happens if you change if y == 2 or y == 5: on line 99 to if y == 1 or y == 6:?