INSTRUCTIONS —> Python In this project you will focus on constraint satisfaction

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 ABCDEFGH

Explanation / Answer

driver_3.py

from sys import argv
from time import clock
from copy import deepcopy

class Csp:
    def __init__(self, vars, doms, cons):
        self.vars = vars # variables
        self.doms = doms # domains
        self.cons = cons # constrains

def ac3(csp):
    arcs = csp.arcs
    while arcs:
        i, j = arcs.pop()
        if revise(csp, i, j):
            if not csp.doms[i]:
                return False
            for k in csp.neig[i]:
                arcs.add((k, i))
    if any(len(v) > 1 for v in csp.doms.values()):
        return 'not unique!!'
    return True

def revise(csp, i, j):
    revised = False
    for x in csp.doms[i]:
        if not any(csp.cons(x, y) for y in csp.doms[j]):
            csp.doms[i].remove(x)
            revised = True
    return revised

def backtrack_search(csp):
    ac3(csp)
    doms = csp.doms
    assignments = {}
    for var in csp.vars:
        if len(doms[var]) == 1:
            assignments[var] = doms[var]
    return backtrack(assignments, csp)

def backtrack(assignments, csp):
    if len(assignments) == len(csp.vars):
        return assignments
    var = min_rem_val(assignments, csp)
    vars_neig_assig = csp.neig[var] & assignments.keys()
    for val in csp.doms[var]:

        csp_backup = deepcopy(csp)
        assignments_backup = deepcopy(assignments)
        if all(val != csp.doms[v] for v in vars_neig_assig):
            assignments[var] = [val]
            csp.doms[var] = [val]
            if forward_check(csp, var, val):
                result = backtrack(assignments, csp)
                if result is not None:
                    return result
        csp = csp_backup
        assignments = assignments_backup
    return None

def min_rem_val(assignments, csp):
    max = 9
    for var in csp.vars:
        if var not in assignments:
            l = len(csp.doms[var])
            if l <= max:
                max = l
                min = var
    return min

def forward_check(csp, var, val):
    for v in csp.neig[var]:
        if val in csp.doms[v]:
            csp.doms[v].remove(val)
            if len(csp.doms[v]) == 0:
                return False
    return True

class Sudoku(Csp):
# construct sudoku into Csp data structure
    def __init__(self, input):
        def stitch(X, Y):
            return [x + y for x in X for y in Y]
        def box(Z):
            return [Z[i*3:i*3+3] for i in range(3)]
        rows = 'ABCDEFGHI'
        cols = '123456789'
        vars = stitch(rows, cols)
        divisions = ([stitch(rows, col) for col in cols] +
                    [stitch(row, cols) for row in rows] +
                    [stitch(rbox, cbox) for rbox in box(rows) for cbox in box(cols)])
        division = {var : ([u for u in divisions if var in u])
                     for var in vars}
        neig = {var : (set(sum(division[var], [])) - set([var]))
                     for var in vars}
        arcs = set()
        for var in vars:
            for peer in neig[var]:
                arcs.add((var, peer))
        i = 0
        doms = {}
        for var in vars:
            if input[i] == '0':
                doms[var] = list(range(1,10))
            else:
                doms[var] = [int(input[i])]
            i += 1
        def cons(x, y):
            return x != y

        super().__init__(vars, doms, cons)
        self.neig = neig
        self.arcs = arcs

def main():
    csp = Sudoku(argv[1])
    solver2 = backtrack_search(csp)
    s2 = ''
    for var in csp.vars:
        for n in solver2[var]:
            s2 += str(n)
    with open("output.txt", "w") as output:
        output.write(s2)

if __name__ == '__main__':
     To generate output.txt
    #############################################################
    main()

    # To generate hw_sudoku_UNI.txt
    #############################################################
     with open('sudokus_start.txt') as input_file:
        inputs = [line.rstrip(' ') for line in input_file]
     s1 = ''
     for n in range(len(inputs)):
         for_start = clock()
         csp = Sudoku(inputs[n])
         solver1 = ac3(csp)
        if solver1 == True:
            sol = ''
            for var in csp.vars:
                for val in csp.doms[var]:
                            sol += str(val)
           s1 += str(n+1)+ ' ' + 'running-time = ' + str(clock() - for_start)[:5]+ ' ' + 'solution = ' + sol + ' '
    with open("hw_sudoku_jh3846.txt", "w") as hw_sudoku_jh3846:
        hw_sudoku_jh3846.write(s1)
    #############################################################

    # To test all sudokus_start.txt
    #############################################################
    with open('sudokus_start.txt') as input_file:
       inputs = [line.rstrip(' ') for line in input_file]
    with open('sudokus_finish.txt') as results:
        results = [line.rstrip(' ') for line in results]
    s3 = ''
    for n in range(len(inputs)):
        for_start = clock()
        csp = Sudoku(inputs[n])
        sol = ''
        solver3 = backtrack_search(csp)
        for var in csp.vars:
            for val in solver3[var]:
                 sol += str(val)
         s3 += sol + ' '
         print(n+1, results[n] == sol, sol, clock()-for_start)
     with open("my_results.txt", "w") as my_results:
         my_results.write(s3)
    #############################################################

  
sudokus_start.txt

003020600900305001001806400008102900700000008006708200002609500800203009005010300
000260701680070090190004500820100040004602900050003028009300074040050036703018000
000100702030950000001002003590000301020000070703000098800200100000085060605009000

sudokus_finish.txt

483921657967345821251876493548132976729564138136798245372689514814253769695417382
435269781682571493197834562826195347374682915951743628519326874248957136763418259
956138742237954816481672953594867321128593674763421598879246135312785469645319287

output.txt

483921657967345821251876493548132976729564138136798245372689514814253769695417382

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.