housekeeping, fitted heuristic solver with arguments for heuristics t…

…o use, added tester script
jdukewich · Apr 30, 2019 · 758890a · 758890a
1 parent 5b248a6
commit 758890a
Show file tree

Hide file tree

Showing 8 changed files with 184 additions and 232 deletions.
diff --git a/csp.py b/csp.py
@@ -27,11 +27,11 @@
 
 from __future__ import absolute_import, division, print_function
 
-import heuristic
+from heuristics import variable_heuristic, value_heuristic
 from constraint import Solver
 
 
-class RecursiveBacktrackingSolver(Solver):
+class HeuristicRecursiveBacktrackingSolver(Solver):
     """
     Recursive problem solver with backtracking capabilities
     Examples:
@@ -55,15 +55,26 @@ class RecursiveBacktrackingSolver(Solver):
     NotImplementedError: RecursiveBacktrackingSolver doesn't provide iteration
     """
 
-    def __init__(self, forwardcheck=True):
+    def __init__(self, value_heuristic_id=None, variable_heuristic_id=None, forwardcheck=True):
         """
+        @param variable_heuristic: string identifier of the variable heuristic to use
+                                   choose from {degree, mrv, random, deg+mrv, mrv+random}
+                                   leave blank for no variable heuristic
+
+        @param value_heuristic: string identifier of the value heruistic to use
+                                choose from {random, lcv, least_used}
+                                leave blank for no value heuristic
+
         @param forwardcheck: If false forward checking will not be requested
                              to constraints while looking for solutions
                              (default is true)
         @type  forwardcheck: bool
         """
         self._forwardcheck = forwardcheck
 
+        self._variable_heuristic_id = variable_heuristic_id
+        self._value_heuristic_id = value_heuristic_id
+
     def recursiveBacktracking(
         self, solutions, domains, vconstraints, assignments, single
     ):
@@ -73,7 +84,7 @@ def recursiveBacktracking(
         ##############################################################
         # Use different heuristics for selecting unassigned variable #
         ##############################################################
-        lst = heuristic.variable_heuristic(domains, vconstraints, 'mrv')
+        lst = variable_heuristic(domains, vconstraints, self._variable_heuristic_id)
 
         for item in lst:
             if item[-1] not in assignments:
@@ -96,7 +107,7 @@ def recursiveBacktracking(
         ################################################
         # Change heuristics for order of domain values #
         ################################################
-        newlst = heuristic.value_heuristic(assignments, domains, domains[variable], 'none')
+        newlst = value_heuristic(assignments, domains, domains[variable], self._value_heuristic_id)
 
         for value in newlst:
             assignments[variable] = value

diff --git a/helper_functions.py b/helper_functions.py
@@ -0,0 +1,109 @@
+import csv
+
+from constraint import Problem, AllDifferentConstraint
+from classes import Board
+
+from datetime import datetime
+
+
+def read_standard_puzzles(input_file):
+    """
+    Reads puzzles from 3x3 csv format.
+
+    :param input_file: name of input file to be read
+    :return: an array of 2D array boards
+    """
+    puzzles = []
+    with open(input_file) as f:
+        for line in f:
+            to_add = [[None for i in range(9)] for j in range(9)]
+            for i in range(len(line)-2):
+                to_add[i // 9][i % 9] = int(line[i]) if line[i] != '.' else 0
+            puzzles.append(to_add)
+
+    return puzzles
+
+
+def read_jumbo_puzzles(input_file):
+    """
+    Reads multiple 4x4 sudoku puzzle in csv format.
+
+    :param input_file: name of input file to be read
+    :return: an array of 2D array boards
+    """
+    read_puzzles = []
+    with open(input_file, 'r') as f:
+        reader = csv.reader(f, delimiter=',')
+        for row in reader:
+            to_add = []
+            for i in range(16):
+                add_row = []
+                for j in range(16):
+                    add_row.append(int(row[16*i+j]))
+                to_add.append(add_row)
+            read_puzzles.append(to_add)
+    return read_puzzles
+
+
+def read_big_puzzle(input_file):
+    """
+    Reads one 4x4 sudoku puzzle in csv format.
+
+    :param input_file: name of input file to be read
+    :return: an array of 2D array boards
+
+    NOTE: did not make it into the final version of the project :(
+    """
+    puzzle = []
+    infile = csv.reader(open(input_file), delimiter=',')
+
+    for row in infile:
+        puzzle.append([int(entry) for entry in row])
+
+    return puzzle
+
+
+def solve_puzzles(puzzles, solver):
+    """
+    Solves an array of sudoku puzzles, recording runtime.
+
+    :param puzzles: an array of 2D array boards
+    :param solver: the CSP solver to be used
+    :return: none
+    """
+    fail_count = 0
+    start_time = datetime.now()     # start timer (for runtime)
+
+    for puzzle in puzzles:
+        # initialize Board
+        b = Board(puzzle)
+
+        sudoku = Problem(solver)      # initialize CSP with custom solver
+
+        # add variables for each square, indexed 1...size^2
+        for index in range(b.board_size ** 2):
+            value = b.get_value(index)
+
+            if value == 0:
+                sudoku.addVariable(index, range(1, b.board_size + 1))
+            else:
+                sudoku.addVariable(index, [value])
+
+        # add uniqueness constraints to each row, column, and subsquare
+        for i in range(b.board_size):
+            sudoku.addConstraint(AllDifferentConstraint(), [el[0] for el in b.row(i)])
+            sudoku.addConstraint(AllDifferentConstraint(), [el[0] for el in b.col(i)])
+            sudoku.addConstraint(AllDifferentConstraint(), [el[0] for el in b.subsquare(i)])
+
+        sln = sudoku.getSolution()      # solve CSP
+
+        if sln:
+            # assign solved values
+            for index, value in sln.items():
+                b.set_value(index, value)
+        else:
+            fail_count += 1
+
+    # perform/display runtime calculation
+    runtime = datetime.now() - start_time
+    print("Runtime: {} seconds ({} failed)".format(runtime.total_seconds(), fail_count))
diff --git a/heuristic.py → heuristics.py b/heuristic.py → heuristics.py
diff --git a/16x16.csv → jumbo_size_sudokus.csv b/16x16.csv → jumbo_size_sudokus.csv
diff --git a/main.py b/main.py
diff --git a/make_boards.py b/make_boards.py
@@ -8,7 +8,7 @@ def generate():
     Makes post requests to a website to generate 16 by 16 sudoku boards. Uses BeautifulSoup to parse the HTML
     and then writes to a CSV.
     """
-    with open('16x16.csv', 'w') as csvfile:
+    with open('jumbo_size_sudokus.csv', 'w') as csvfile:
         writer = csv.writer(csvfile, delimiter=',')
 
         # Can change this for more puzzles, each post request makes 5 puzzles