Construct a program that uses an agent to solve a Sudoku puzzle as a Constraint
ID: 3911553 • Letter: C
Question
Construct a program that uses an agent to solve a Sudoku puzzle as a Constraint Satisfaction Problem, with the following guidelines:
Since 3 x 3 puzzles are too trivial for a computer, your program should use 4 x 4 puzzles (also known as Super Sudoku puzzles; see Figure 2 for an example).
The program should read a Sudoku puzzle from a text file. The user should be able to browse the file system to select this file. See Figure 2 for the format the text file should obey. Please be sure you follow this format, as I will test your program by loading my own test puzzles. How you represent the puzzle within your program is entirely up to you.
You do not need to generalize your program to cover other sizes of Sudoku puzzles, so you can assume all puzzles tested will be of the 4 x 4 variety.
Any set of 16 unique symbols can be used for a 4 x 4 Sudoku puzzle. The standard set consists of the same characters used in hexadecimal arithmetic (numerals 0-9 plus letters A-F). This is the symbol set I will use in my tests. You may use any symbols you wish, but make sure your program can handle any set of 16 unique characters that can be represented in a text file. In keeping with the standard CSP terminology, I will refer to the cells in the puzzle as the variables, and the chosen domain of valid characters as the values.
Build 2 separate agents for solving the puzzles:
An uninformed agent that attempts to solve the puzzle by starting with the first empty cell and progressing from left to right, top to bottom. This is considered the default variable selector.
A CSP agent that uses the MRV heuristic to reduce the size of the search space. The order in which cells should be assigned using this heuristic is in order of increasing number of possible values. The number of possible values for a given cell is determined by looking at the row, column, and box that have that cell in common, and subtracting from 16 the number of unique values that are already present. The range can be anywhere from 1 to 16 for an empty cell.
You may find it useful to implement the backtracking search algorithm, the pseudocode for which is shown on page 215 of the text. This is not a strict requirement, but this algorithm is a good, general purpose backtracking search that is suitable for CSPs.
To measure the relative efficiencies of the two agents, incorporate the ability to maintain counts of the total numbers of cell assignments attempted using each method of selecting variables to assign. Feel free to measure the actual running time if you wish, but counting the total number of attempted variable assignments will give the best, implementation-independent estimate of relative efficiency.
You may use any programming language you wish, provided I am able to install and compile your code on Windows 7. One exception to this is that I cannot accept programs written in any Visual Studio version prior to .NET, since programs written in earlier versions like VB6 do not convert easily. Currently the only version of Visual Studio I am running is Visual Studio 2010.
You are not required to build an extensive framework for this assignment, so do not feel obligated to conform to the framework described by the authors in the text.
Test both agents on a variety of 4 x 4 Sudoku puzzles
Use at least 5 different puzzles in your tests. Try to ensure the puzzles have different levels of difficulty.
Compare the results of your two agents on each puzzle you test.
Write a brief discussion of your observations.
6 0 5 F7B-E-A-1--6-D -91AF-0-85D7E4-c 05-69c---B-EA-3- -C-E-2-B--A-7860 E05---2F-7---1c- -4-8-DC--E-593-- -29--1-D-A-04- D67-A-98--BF 9B-D-130c8-F5A- 8F4569EA7D-CB 6A 745BEE-12D9 7--1DBFC-A-04--E 5-F9c-61240D-7E- A--7-F-DE-580-2- -0-5E7-F63C--14 CE 640-7B5D9F DIC 5 93 2 9 0 4 9 8 CIB 5 D E Figure 2. An example of a Super Sudoku puzzle. The right panel indicates the proper format for representing the puzzle in the test puzzle file; '-' characters indicate unfilled c ellsExplanation / Answer
from constraint import *
# Normalizes sudoku solution
def dataNormalize (data):
"""
args: data; output from sudoku_solve()
returns: Normalized output of input - Diplayed at console
"""
sudoku_nums = [ eachPos[1] for eachPos in sorted( data[0].items() ) ]
for step in xrange(0,81,9):
print sudoku_nums[step:step+9]
# Solves the sudoku puzzle
def sudoku_solve ():
"""
args: None
returns: Sudoku solution
return type: list
description:
* It reads sudoku puzzle input via text file.
* Creates problem instance, sudoku = Problem()
* Adds sudoku input and their indices as variables
* Adds constraints to the problem
1. No two numbers in a row should be same
2. No two numbers in a column should be same
3. No two numbers in a 3x3 box shoud be same
* returns the solution
"""
# reads the puzzle from file
## ENTER FILE NAME HERE
fileName = raw_input("Enter file name: ")
if fileName.strip() == "":
fileName = "ExamplePuzzle.txt"
puzzleNums = open(fileName).read()
# stores the numbers in a list. Ex: [1,2,9,0,3...]
puzzleNums = [ int(eachNum) for eachNum in puzzleNums.split() ]
# Problem instance created.
# Recursive backtracking is used here
sudoku = Problem( RecursiveBacktrackingSolver() )
# List of 9x9 sudoku puzzle indices. Ex: [(0,0), (0,1).. (9,9)]
sudokuIndex = [ (row, col) for row in range(9) for col in range(9) ]
# adding variables to the sudoku instance
for eachIndex,eachNum in zip(sudokuIndex, puzzleNums):
# If empty location is found, its range is set to 1-10
if eachNum == 0:
sudoku.addVariable(eachIndex, range(1,10) )
# If not an empty location, its a value is assigned
else:
sudoku.addVariable(eachIndex, [eachNum] )
# constraints for each row and column
# counting from 0-9 (numeber of rows/ columns)
var = 0
for aCount in range(9):
# A list of locations present in a row.
rowIndices = [ (var, col) for col in range(9) ]
# Adding constraint
# No two numbers in a row should be same
sudoku.addConstraint( AllDifferentConstraint(), rowIndices )
# A list of locations present in a column
colIndices = [ (row, var) for row in range(9) ]
# Adding constraint
# No two numbers in a column should be same
sudoku.addConstraint( AllDifferentConstraint(), colIndices )
var+=1
# constraints for each block (3x3) of board
# Finding all boxes in sudoku board. Its 9 in this case
rowStep = 0
colStep = 0
while rowStep < 9:
colStep = 0
while colStep < 9:
# list of locations present in a box
boxIndices = [ (row, col) for row in range(rowStep, rowStep+3)
for col in range(colStep, colStep+3)]
# Adding constraint
# No two numbers in the box should be same
sudoku.addConstraint( AllDifferentConstraint(), boxIndices )
colStep+=3
rowStep+=3
# return the solution
return sudoku.getSolutions()
if __name__ == '__main__':
print "sudoku output "
dataNormalize( sudoku_solve() )
raw_input(" Enter any key to exit")