INSTRUCTIONS —> Python In this project you will focus on constraint satisfaction
ID: 3852982 • Letter: I
Question
INSTRUCTIONS —> Python
In this project you will focus on constraint satisfaction problems. You will be implementing the AC-3 and backtracking algorithms to solve Sudoku puzzles. The objective of the game is just to fill a 9 x 9 grid with numerical digits so that each column, each row, and each of the nine 3 x 3 sub-grids (also called boxes) contains one of all of the digits 1 through 9. If you have not played the game before, you may do so at sudoku.com to get a sense of how the game works. Please read all sections of the instructions carefully.
I. Introduction
Consider the Sudoku puzzle as pictured above. There are 81 variables in total, i.e. the tiles to be filled with digits. Each variable is named by its row and its column, and must be assigned a value from 1 to 9, subject to the constraint that no two cells in the same row, column, or box may contain the same value.
In designing your classes, you may find it helpful to represent a Sudoku board with a Python dictionary. The keys of the dictionary will be the variable names, each of which corresponds directly to a location on the board. In other words, we use the variable names Al through A9 for the top row (left to right), down to I1 through I9 for the bottom row. For example, in the example board above, we would have sudoku["B1"] = 9, and sudoku["E9"] = 8. This is the highly suggested representation, since it is easiest to frame the problem in terms of variables, domains, and constraints if you start this way. In this project, we will use the number zero to indicate tiles that have not yet been filled.
II. What You Need To Submit
Your job in this project is to write driver.py, which intelligently solves Sudoku puzzles. Your program will be executed as follows: $ python driver.py
In the starter code folder, you will find the file sudokus_start.txt, containing hundreds of sample Sudoku puzzles to be solved. Each Sudoku puzzle is represented as a single line of text, which starts from the top-left corner of the board, and enumerates the digits in each tile, row by row. For example, the first Sudoku board in sudokus_start.txt is represented as the string: 003020600900305001001806400008102900700000008006708200002609500800203009005010300
When executed as above, replacing "" with any valid string representation of a Sudoku board (for instance, taking any Sudoku board from sudokus_start.txt), your program will generate a file called output.txt, containing a single line of text representing the finished Sudoku board. Since this board is solved, the string representation will contain no zeros. Here is an example of an output: 483921657967345821251876493548132976729564138136798245372689514814253769695417382
You may test your program extensively by using sudokus_finish.txt, which contains the solved versions of all of the same puzzles.
Note on Python 3
As usual, if you choose to use Python 3, then name your program driver_3.py. In that case, the grader will automatically run your program using the python3 binary instead. Please only submit one version. If you submit both versions, the grader will only grade one of them, which probably not what you would want. To test your algorithm in Python 3, execute the game manager like so:
$ python3 driver_3.py
III. AC-3 Algorithm
First, implement the AC-3 algorithm. Test your code on the provided set of puzzles in sudokus_start.txt. To make things easier, you can write a separate wrapper script (bash, or python) to loop through all the puzzles to see if your program can solve them. How many of the puzzles you can solve? Is this expected or unexpected? Report the puzzles you can solve with AC-3 alone in hw_sudoku_UNI.txt. Reporting the index of the puzzles you can solve with Sudoku is enough. Report also your observations, running time, and any relevant information about your implementation.
IV. Backtracking Algorithm
Now, implement backtracking search using the minimum remaining value heuristic. The order of values to be attempted for each variable is up to you. When a variable is assigned, apply forward checking to reduce variables domains.
Test your code on the provided set of puzzles in sudokus_start.txt. Use your AC-3 implementation to reduce the domains of variable before you perform backtracking search.
Can you solve all puzzles now? Report the puzzles you can solve now using AC-3 followed by backtracking search. Report your observations, running time, difference in running time between backtracking alone and backtracking preceded with AC-3 and any relevant information about your implementation (no specific format of the write-up will be provided, use your best judgment).
V. Important Information
1. Test-Run Your Code
Please test your code and make sure it successfully produces an output file with the correct format. Make sure the format is the same the example provided above.
2. Time Limit
By now, we expect that you have a good sense of appropriate data structures and object representations. Naive brute-force approaches to solving Sudoku puzzles may take minutes, or even hours, to [possibly never] terminate. However, a correctly implemented backtracking approach as specified above should take well under a minute per puzzle. The grader will provide some breathing room, but programs with much longer running times will be killed.
3. Just for fun
Try your code on the world’s hardest Sudoku and see if you can solve them! There is nothing to submit here, just for fun. Here is an example:
Sudoku:
800000000003600000070090200050007000000045700000100030001000068008500010090000400
Solution:
812753649943682175675491283154237896369845721287169534521974368438526917796318452
sudokus_start.txt: https://github.com/ryanwc/ConstraintFactory/blob/master/sudokus_start.txt
sudokus_finish.txt: https://github.com/ryanwc/ConstraintFactory/blob/master/sudokus_finish.txt
648|715|329 315|82-9-647 792-463-158 139-672-584 264-358-731 587-13-4-296 973|586|412 456-291-873 821-347-96-5 ABCDEFGH 8 2 4 3 4 9 3 3 37 6 9 821 ABCDEFGHExplanation / Answer
driver.py
-----------------------------------------------------------------------------
# coding: utf-8
# In[34]:
from collections import OrderedDict
# In[45]:
import time
# In[46]:
import sys
# In[2]:
def init_variables():
V = OrderedDict()
for x in range(ord('A'), ord('I')+1):
for i in range(1, 10):
V[chr(x) + str(i)] = 0
return V
# In[6]:
V = init_variables()
# In[2]:
len('003020600900305001001806400008102900700000008006708200002609500800203009005010300'),len(V)
# In[33]:
assigments = '094000130000000000000076002080010000032000000000200060000050400000008007006304008'
for i,v in enumerate(V):
#print v, assigments[i]
pass
# In[5]:
# variable domain values
def init_domains(V):
D = OrderedDict()
for x in V:
D[x] = range(1, 10)
return D
#print D
# In[18]:
D = init_domains(V)
# In[22]:
#D
# In[8]:
#assign initial value domains
def init_values(V, D, vals):
for i, x in enumerate(V):
if int(vals[i]) != 0:
D[x] = [int(vals[i])]
# In[ ]:
# In[9]:
#constraints
#1. 3x3, row, column must contain values from 1 to 9
import numpy as np
C1 = {}
b = np.array(V.keys())
b = b.reshape(9,9)
#print b
C1 = {}
for i in range(3, 12, 3):
#print i,i-3
#print b[i-3:i]
for e in range(3,12,3):
#print e
by_3 = b[i-3:i,e-3:e]
by_3_lst = []
for c in by_3:
by_3_lst.extend(c)
#print by_3_lst
C1['-'.join(by_3_lst)] = range(1,10)
#print C1,len(C1)
# In[28]:
#print b
# In[10]:
#row , column constraints
C2 = {}
C3 = {}
for i in range(0,9):
k_row = '-'.join(b[:, i].tolist())
k_col = '-'.join(b[i, :].tolist())
C2[k_row] = range(1, 10)
C3[k_col] = range(1, 10)
# In[11]:
C = zip(C1,C2,C3)
def neighbors(v, C):
''' v - a variable to find its neighbors'''
#check in 3x3 grid
n_lst = []
for c1, c2,c3 in C:
if v in c1:
c1_lst = c1.split('-')
c1_lst.remove(v)
for c1_ in c1_lst:
if not c1_ in n_lst:
n_lst.append(c1_)
if v in c2:
c2_lst = c2.split('-')
c2_lst.remove(v)
for c2_ in c2_lst:
if not c2_ in n_lst:
n_lst.append(c2_)
if v in c3:
c3_lst = c3.split('-')
c3_lst.remove(v)
for c3_ in c3_lst:
if not c3_ in n_lst:
n_lst.append(c3_)
#print n_lst
return n_lst
# In[12]:
#neighbors('A1',C)
# In[13]:
from copy import deepcopy
def revise(X_i, X_j):
revised = False
Dx = deepcopy(D)
#print Dx[X_j]
DX_j = []
for x in Dx[X_i]:
for y in Dx[X_j]:
if x == y:
#print y
DX_j.append(y)
#print Dx[X_j] , DX_j
if Dx[X_j] == DX_j:
D[X_i].remove(x)
revised = True
#break
#print D[X_i]
return revised
# In[60]:
D['A1'] = [1,2,3]
D['A2'] = [1,2,3]
# In[61]:
revise('A1', 'A2')
# In[314]:
D['A1'], D['A2']
# In[14]:
binary_cs = []
for c1, c2, c3 in C:
c1_lst = c1.split('-')
c2_lst = c2.split('-')
c3_lst = c3.split('-')
for i in range(0, len(c1_lst)):
if i + 1 < len(c1_lst):
pass
for j in range(i+1, len(c1_lst)):
binary_cs.append((c1_lst[i], c1_lst[j]))
binary_cs.append((c2_lst[i], c2_lst[j]))
binary_cs.append((c2_lst[i], c2_lst[j]))
#print len(binary_cs), len(C1), len(C2), len(C3)
#print binary_cs
# In[16]:
import Queue
def ac3():
q = Queue.Queue()
for arc in binary_cs:
#print arc
q.put(arc)
#print q.empty()
while not q.empty():
X_i, X_j = q.get()
if revise(X_i, X_j):
if len(D[X_i]) == 0:
return False
n_lst = neighbors(X_i, C)
n_lst.remove(X_j)
for X_k in n_lst:
q.put((X_k, X_i))
return True
# In[17]:
ac3()
# In[70]:
D['A1']
# In[19]:
def select_unsigned_variable(V, D, C):
'''The variable with fewest remaining values in its domain'''
selected_variable = ''
smallest_possible = 9
for v in V:
if len(D[v]) > 1 and len(D[v]) <= smallest_possible:
selected_variable = v
smallest_possible = len(D[v])
return selected_variable
# In[20]:
V = init_variables()
D = init_domains(V)
init_values(V, D, assigments)
# In[21]:
select_unsigned_variable(V, D, C)
# In[22]:
def is_complete(D):
for x in D:
if len(D[x]) != 1:
return False
return True
# In[30]:
def is_consistent(var, d, D, C):
consistent = True
neighbors_lst = neighbors(var, C)
#print var , neighbors_lst, len(neighbors_lst)
for x in neighbors_lst:
#print D[x], d
if D[x] == [d]:
consistent = False
break
return consistent
# In[24]:
def backtrack(assigment, V, D, C):
if is_complete(D):
return assigment
var = select_unsigned_variable(V, D, C)
domain = D[var]
for d in D[var]:
if is_consistent(var, d, D, C):
assigment[var] = [d]
D[var] = [d]
result = backtrack(assigment, V, D, C)
if result:
return result
del assigment[var]
D[var] = domain
return {}
# In[25]:
def backtracking_search(V, D, C):
return backtrack({}, V, D, C)
# In[42]:
sudokus_start = []
with open('sudokus_start.txt','r') as _file:
for line in _file.readlines():
#print int(line)
sudokus_start.append(line.replace(' ', ''))
_file.close()
solved = 0
start_time = time.time()
elapsed = 0
'''for start in sudokus_start:
V = init_variables()
D = init_domains(V)
init_values(V,D, start)
if backtracking_search(V, D, C):
solved += 1
elapsed = time.time() - start_time
if elapsed > 360 + 5 :
break;
print 'Solved=%d in %.2f seconds' % (solved, elapsed)
'''
# In[43]:
V = init_variables()
D = init_domains(V)
init_values(V,D, assigments)
#assignment = backtracking_search(V, D, C)
# In[44]:
assigments
# In[39]:
D
# In[ ]:
if __name__ == '__main__':
#print sys.argv
inital_assigment = sys.argv[1]
V = init_variables()
D = init_domains(V)
start = time.time()
init_values(V,D, inital_assigment)
backtracking_search(V, D, C)
print 'Solved in %.2f seconds' % (time.time() - start)
with open('output.txt', 'w') as _file:
assigments = D.values()
assignment_lst = []
for a in assigments:
assignment_lst.append(a[0])
assigments = ''.join(str(val) for val in assignment_lst)
print 'Assigments [{}]'.format(assigments)
print assigments
_file.write(assigments)
_file.close()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.