A Sudoku solver In this problem, you will write a program that solves Sudoku puz
ID: 3790952 • Letter: A
Question
A Sudoku solver
In this problem, you will write a program that solves Sudoku puzzles using recursive backtracking.
A Sudoku puzzle consists of a 9x9 grid in which some of the cells have been filled with integers from the range 1-9. To solve the puzzle, you fill in the remaining cells with integers from the same range, such that each number appears exactly once in each row, column, and 3x3 subgrid.
Most of the functionality of your program should go in a class called Puzzle, which you will use to represent an individual Sudoku puzzle. You have been provided with skeleton code for this class in the file Puzzle.py, including:
a field called values that refers to a two-dimensional list of integers. This list is used to store the current contents of the cells of the puzzle, such that values[r][c] stores the current value in the cell at row r, column c of the puzzle. A value of 0 is used to indicate a blank cell.
a field called valIsFixed that refers to a two-dimensional list of booleans. It is used to record whether the value in a given cell is fixed (i.e., part of the original puzzle). valIsFixed[r][c] is true if the value in the cell at row r, column c is fixed, and valIsFixed[r][c] is false if the value in that cell is not fixed. For example, in the original puzzle above, there is a fixed 4 in the cell at row 0, column 1 (the second cell in the top row), and thus valIsFixed[0][1] would be true for that puzzle.
a field called subgridHasValue that refers to a three-dimensional list of booleans. This list allow us to determine if a given 3x3 subgrid of the puzzle already contains a given value. For example, subgridHasValue[0][0][4] will be true if the 3x3 subgrid in the upper left-hand corner of the board (a subgrid that we are identifying using the indices [0][0]) already has a 4 in one of its cells. See the comments accompanying this field for more information about the numbering of the subgrids.
partial implementations of methods called placeValue() and removeValue() that place a value in a given cell and remove a value from a given cell by updating the fields mentioned above. You will need to add code to these methods to update the other fields that you add.
a full implementation of a method called readFrom() that takes a file as its only parameter and reads in a specification of a puzzle from that file. This method assumes that a puzzle specification consists of nine lines of text – one for each row of the puzzle – and that each line contains nine digits separated by whitespace. Here again, 0 is used to indicate a blank cell. For example, the specification of the initial puzzle above would begin:
0 4 0 0 0 3 7 0 0
0 8 9 7 0 0 1 0 0
…
The method reads in the puzzle specification and makes the corresponding changes to the fields mentioned above. You should not need to change this method, because it calls placeValue(), and you are already modifying that method as needed. However, we do recommend that you read this method over.
the full implementation of a method called display() that prints out the current state of the Puzzle object on which it is invoked.
the skeleton of a method called solve() that you will implement. This is the recursive-backtracking method, and it should return true if a solution to the puzzle is found and false if no solution has been found (i.e., if the method is backtracking). If the initial call to this method returns false, that means that no solution can be found – i.e., that the initial puzzle is not valid. If there is more than one solution (which can happen if the initial puzzle does not have enough numbers specified), your code should stop after finding one of them.
Each invocation of the solve() method is responsible for finding the value of a single cell of the puzzle. The method takes a parameter n, which is the number of the cell that the current invocation of this method is responsible for. We recommend that you consider the cells one row at a time, from top to bottom and left to right, which means that they would be numbered as follows:
0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
18 ...
a partial implementation of a constructor. You will need to add code to initialize the fields that you add.
In addition to completing the methods mentioned above, you should also add to the Puzzle class whatever additional fields or methods that are needed to maintain the state of a Sudoku puzzle and to solve it using recursive backtracking. In particular, we recommend adding two fields: one to keep track of whether a given row already contains a given value, and one to keep track of whether a given column already contains a given value.
We have also given you a separate file (Sudoku.py) that contains the Sudoku solver test code. You shouldn’t need to change this method (or any other code in this file), but we encourage you to review its use of the methods of the Puzzle class. In particular, note that it displays the puzzle after the solution is found, and thus it isn’t necessary for your recursive-backtracking method to display it. Finally, there are four sample puzzle files: puzzle1.txt, puzzle2.txt, no_solution.txt (which has no solution), and multi_sol.txt (which has multiple solutions), for you to test your solutions.
Additional hints and suggestions:
Take advantage of the second template in the notes for recursive backtracking – the one in which the method returns a boolean.
As mentioned above, the recursive solve method takes a single parameter n that represents the number of the cell that the current invocation is responsible for. You will need to use n to compute the row and column indices of the cell, and you should be able to do so using simple arithmetic operations (+, –, *, /, and %).
Make sure that you take advantage of the subgridHasValue field – along with the fields that you will add to keep track of the values in a given row and a given column of the puzzle – when deciding whether a particular value can be assigned to a particular cell. You should not need to scan through the puzzle to determine if a given value is valid. See the notes for n-Queens for another example of efficient constraint checking.
Make sure that you use the placeValue() and removeValue() methods when updating the state of the puzzle, and that you add code to these methods as needed to update the fields that you add to the Puzzle class.
Make sure that you don’t attempt to assign a new number to cells that are filled in the original puzzle – i.e., cells whose values are fixed. Your solve() method will need to skip over these cells somehow.
A sample run of the program is shown below.
Please enter the name of puzzle file: puzzle1.txt
Here is the initial puzzle:
-------------------------------------
| | 4 | | | | 3 | 7 | | |
-------------------------------------
| | 8 | 9 | 7 | | | 1 | | |
-------------------------------------
| | | | | | 4 | 2 | | |
-------------------------------------
| | | | | | | | | 1 |
-------------------------------------
| 6 | | | 5 | 1 | 8 | | | 9 |
-------------------------------------
| 2 | | | | | | | | |
-------------------------------------
| | | 5 | 3 | | | | | |
-------------------------------------
| | | 6 | | | 1 | 9 | 4 | |
-------------------------------------
| | | 1 | 2 | | | | 6 | |
-------------------------------------
Here is the solution:
-------------------------------------
| 1 | 4 | 2 | 9 | 8 | 3 | 7 | 5 | 6 |
-------------------------------------
| 5 | 8 | 9 | 7 | 2 | 6 | 1 | 3 | 4 |
-------------------------------------
| 7 | 6 | 3 | 1 | 5 | 4 | 2 | 9 | 8 |
-------------------------------------
| 9 | 5 | 8 | 4 | 3 | 2 | 6 | 7 | 1 |
-------------------------------------
| 6 | 3 | 7 | 5 | 1 | 8 | 4 | 2 | 9 |
-------------------------------------
| 2 | 1 | 4 | 6 | 9 | 7 | 5 | 8 | 3 |
-------------------------------------
| 4 | 7 | 5 | 3 | 6 | 9 | 8 | 1 | 2 |
-------------------------------------
| 3 | 2 | 6 | 8 | 7 | 1 | 9 | 4 | 5 |
-------------------------------------
| 8 | 9 | 1 | 2 | 4 | 5 | 3 | 6 | 7 |
-------------------------------------
----------------------------------------------------------------------------------------------------------------------------------
class Puzzle():
# the dimension of the puzzle grid
DIM = 9
# the dimension of the smaller subgrids within the grid
SUBGRID_DIM = 3
"""
// values
// The current contents of the cells of the puzzle.
// values[r][c] gives the value in the cell at row r, column c.
// The rows and columns are numbered from 0 to DIM-1.
// valIsFixed
// Indicates whether the value in a given cell is fixed
// (i.e., part of the original puzzle).
// valIsFixed[r][c] is true if the value in the cell
// at row r, column c is fixed, and valIsFixed[r][c] is false
// if the value in that cell is not fixed.
// subgridHasValue
// This 3-D array allows us to determine if a given
// subgrid (i.e., a given SUBGRID_DIM x SUBGRID_DIM region
// of the puzzle) already contains a given value.
// We use 2 indices to identify a given subgrid.
// For example:
//
// (0,0) (0,1) (0,2)
//
// (1,0) (1,1) (1,2)
//
// (2,0) (2,1) (2,2)
//
// For example, subgridHasValue[0][2][5] will be true if
// the subgrid in the upper right-hand corner already has
// a 5 in it, and false otherwise.
//
// If a given cell of the board has indices [r][c], it falls
// within the subgrid with indices [r//3][c//3] using integer
// division.
//
/**
* Constructs a new Puzzle object, which initially
* has all empty cells.
*/
"""
def __init__(self):
self.values = [[0 for col in range(Puzzle.DIM)] for row in range(Puzzle.DIM)]
self.valIsFixed = [[False for col in range(Puzzle.DIM)] for row in range(Puzzle.DIM)]
self.subgridHasValue = [[[False for val in range(Puzzle.DIM + 1)] for col in range(Puzzle.DIM)] for row in range(Puzzle.DIM)]
# Reads in a puzzle specification from the specified file,
# and uses it to initialize the state of the puzzle. The
# specification should consist of one line for each row, with the
# values in the row specified as digits separated by spaces. A
# value of 0 should be used to indicate an empty cell.
def readFrom(self, file):
for row in range(Puzzle.DIM):
self.values[row] = file.readline().split()
for r in range(Puzzle.DIM):
for c in range(Puzzle.DIM):
self.values[r][c] = eval(self.values[r][c])
print("val= ", self.values[r][c])
if self.values[r][c] != 0:
self.valIsFixed[r][c] = True
self.subgridHasValue[r // Puzzle.SUBGRID_DIM][c // Puzzle.SUBGRID_DIM][self.values[r][c]] = True
# Displays the current state of the puzzle.
# You should not change this method.
def display(self):
for r in range(Puzzle.DIM):
#printRowSeparator()
for c in range(Puzzle.DIM):
#print("r= " + str(r) + ", c= " + str(c))
print("|", end="")
if self.values[r][c] == 0:
print(" ", end="")
else:
print(" " + str(self.values[r][c]) + " ", end="")
print("|")
#printRowSeparator()
# A private helper method used by display()
# to print a line separating two rows of the puzzle.
def printRowSeparator(self):
for i in range(Puzzle.DIM):
print("----", end="")
print("-", end="")
"""
// XXX: add your additional methods here.
// In particular, we recommend adding methods to keep track
// of whether a given row or column already contains a given value.
// You should be able to use a similar approach to what we've
// done for the subgrids, but it will be simpler, because each
// row and column can be identified by a single integer.
"""
# place the specified value in the cell with the
# specified coordinates, and update the state of
# the puzzle accordingly.
def placeValue(self, row, col, val):
self.values[row][col] = val;
self.subgridHasValue[row // Puzzle.SUBGRID_DIM][col // Puzzle.SUBGRID_DIM][val] = True
# XXX: add code to make any necessary changes to
# the fields that you add.
# remove the specified value from the cell with the
# specified coordinates, and update the state of
# the puzzle accordingly.
def removeValue(self, row, col, val):
self.values[row][col] = 0
self.subgridHasValue[row // Puzzle.SUBGRID_DIM][col // Puzzle.SUBGRID_DIM][val] = False
# XXX: add code to make any necessary changes to
# the fields that you add.
# Note that the third dimension of the array has a length
# of DIM + 1, because we want to be able to use the possible
# values (1 through 9) as indices.
# XXX: add code to initialize the fields that you add.
"""
* This is the key recursive-backtracking method.
* Returns true if a solution has been found, and false otherwise.
*
* Each invocation of the method is responsible for finding the
* value of a single cell of the puzzle. The parameter n
* is the number of the cell that a given invocation of the method
* is responsible for. We recommend that you consider the cells
* one row at a time, from top to bottom and left to right,
* which means that they would be numbered as follows:
*
* 0 1 2 3 4 5 6 7 8
* 9 10 11 12 13 14 15 16 17
* 18 ...
"""
def solve(self, n):
pass
----------------------------------------------------------------------------------------------
from Puzzle import *
fileName = input("Please enter the name of puzzle file: ")
inputFile = open(fileName, "r")
puzzle = Puzzle()
puzzle.readFrom(inputFile)
inputFile.close()
print(" Here is the initial puzzle: ")
puzzle.display()
if puzzle.solve(0):
print(" Here is the solution: ")
else:
print(" No solution could be found.")
print("Here is the current state of the puzzle:")
puzzle.display()
Explanation / Answer
import os cwd = os.getcwd() filename = cwd + "/sudoku1.txt" grid = [] l = grid with open(filename) as f: for line in f: grid.append([int(i) for i in line.split()]) def printGrid(result): # prints grid with result for i in grid: print(i) def allDifferent1D(l): for e in l: if e != 0: # ignores that there are many zeros if l.count(e) > 1: #make sure only has 1 instance of a number return False return True def allDifferent2D(l): for row in l: if not allDifferent1D(row): return False for c in range(len(l)): col = [] for r in range(len(l)): col.append(l[r][c]) if not allDifferent1D(col): return False return True def checkAll3By3s(grid): #function goes through and assigns numbers in arrays and checks the grid for i in [0,3,6]: for j in [0,3,6]: column = [] column.append(grid[i][j:j+3]) column.append(grid[i+1][j:j+3]) column.append(grid[i+2][j:j+3]) w =[] for k in column: for p in k: w.append(p) if allDifferent1D(l) == False: return False else: return True def isValidSudoku(grid): # Check all rows and columns if (not allDifferent2D(grid)): return False if (not checkAll3By3s(grid)): return False return True def complete(grid): #function that weather parameter is correct solution for i in grid: for b in i: if b == 0: return False #if it has zeros, then not complete else: return True # returns true if there are no zeros def checker(): #function to call checkAll3by3 if checkAll3By3s(grid) == true: return grid else: return False def solveSudoku(grid): #main function to solve if complete(grid) == True: # return grid elif isValidSudoku(grid) == False: # return None for i in grid: for b in range(0,9): # goes the indincies if i[b] == 0: for w in range(1,10): # sets w to be a number, 1,2,3,4,5,6,7,8 or 10 i[b] = w # sets the spot in i[b] to the number c = solveSudoku(grid) if c != None: return c # recursion i[b] = 0 # sets b back to 0 return None #return none, only happen once we have done everythign result = solveSudoku(grid) if result != None: print("The solution is:") printGrid(result) else: print("There is no solution.")
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.