Skip to content

Commit a23462f

Browse files
dmeoliantmarakis
dmeoli
authored and
antmarakis
committed
added SAT solvers heuristics and Conflict-Driven Clause Learning SAT solver with tests (aimacode#1114)
* changed queue to set in AC3 Changed queue to set in AC3 (as in the pseudocode of the original algorithm) to reduce the number of consistency-check due to the redundancy of the same arcs in queue. For example, on the harder1 configuration of the Sudoku CSP the number consistency-check has been reduced from 40464 to 12562! * re-added test commented by mistake * added the mentioned AC4 algorithm for constraint propagation AC3 algorithm has non-optimal worst case time-complexity O(cd^3 ), while AC4 algorithm runs in O(cd^2) worst case time * added doctest in Sudoku for AC4 and and the possibility of choosing the constant propagation algorithm in mac inference * removed useless doctest for AC4 in Sudoku because AC4's tests are already present in test_csp.py * added map coloring SAT problems * fixed typo errors and removed unnecessary brackets * reformulated the map coloring problem * Revert "reformulated the map coloring problem" This reverts commit 20ab0e5. * Revert "fixed typo errors and removed unnecessary brackets" This reverts commit f743146. * Revert "added map coloring SAT problems" This reverts commit 9e0fa55. * Revert "removed useless doctest for AC4 in Sudoku because AC4's tests are already present in test_csp.py" This reverts commit b3cd24c. * Revert "added doctest in Sudoku for AC4 and and the possibility of choosing the constant propagation algorithm in mac inference" This reverts commit 6986247. * Revert "added the mentioned AC4 algorithm for constraint propagation" This reverts commit 03551fb. * added map coloring SAT problem * fixed build error * Revert "added map coloring SAT problem" This reverts commit 93af259. * Revert "fixed build error" This reverts commit 6641c2c. * added map coloring SAT problem * removed redundant parentheses * added Viterbi algorithm * added monkey & bananas planning problem * simplified condition in search.py * added tests for monkey & bananas planning problem * removed monkey & bananas planning problem * Revert "removed monkey & bananas planning problem" This reverts commit 9d37ae0. * Revert "added tests for monkey & bananas planning problem" This reverts commit 24041e9. * Revert "simplified condition in search.py" This reverts commit 6d229ce. * Revert "added monkey & bananas planning problem" This reverts commit c74933a. * defined the PlanningProblem as a specialization of a search.Problem & fixed typo errors * fixed doctest in logic.py * fixed doctest for cascade_distribution * added ForwardPlanner and tests * added __lt__ implementation for Expr * added more tests * renamed forward planner * Revert "renamed forward planner" This reverts commit c4139e5. * renamed forward planner class & added doc * added backward planner and tests * fixed mdp4e.py doctests * removed ignore_delete_lists_heuristic flag * fixed heuristic for forward and backward planners * added SATPlan and tests * fixed ignore delete lists heuristic in forward and backward planners * fixed backward planner and added tests * updated doc * added nary csp definition and examples * added CSPlan and tests * fixed CSPlan * added book's cryptarithmetic puzzle example * fixed typo errors in test_csp * fixed aimacode#1111 * added sortedcontainers to yml and doc to CSPlan * added tests for n-ary csp * fixed utils.extend * updated test_probability.py * converted static methods to functions * added AC3b and AC4 with heuristic and tests * added conflict-driven clause learning sat solver * added tests for cdcl and heuristics * fixed probability.py * fixed import * fixed kakuro
1 parent 440142c commit a23462f

8 files changed

Lines changed: 420 additions & 41 deletions

File tree

‎csp.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1248,24 +1248,24 @@ def display(self, assignment=None):
12481248

12491249

12501250
# ______________________________________________________________________________
1251-
# Karuko Problem
1251+
# Kakuro Problem
12521252

12531253

12541254
# difficulty 0
1255-
karuko1 = [['*', '*', '*', [6, ''], [3, '']],
1255+
kakuro1 = [['*', '*', '*', [6, ''], [3, '']],
12561256
['*', [4, ''], [3, 3], '_', '_'],
12571257
[['', 10], '_', '_', '_', '_'],
12581258
[['', 3], '_', '_', '*', '*']]
12591259

12601260
# difficulty 0
1261-
karuko2 = [
1261+
kakuro2 = [
12621262
['*', [10, ''], [13, ''], '*'],
12631263
[['', 3], '_', '_', [13, '']],
12641264
[['', 12], '_', '_', '_'],
12651265
[['', 21], '_', '_', '_']]
12661266

12671267
# difficulty 1
1268-
karuko3 = [
1268+
kakuro3 = [
12691269
['*', [17, ''], [28, ''], '*', [42, ''], [22, '']],
12701270
[['', 9], '_', '_', [31, 14], '_', '_'],
12711271
[['', 20], '_', '_', '_', '_', '_'],
@@ -1276,7 +1276,7 @@ def display(self, assignment=None):
12761276
[['', 14], '_', '_', ['', 17], '_', '_']]
12771277

12781278
# difficulty 2
1279-
karuko4 = [
1279+
kakuro4 = [
12801280
['*', '*', '*', '*', '*', [4, ''], [24, ''], [11, ''], '*', '*', '*', [11, ''], [17, ''], '*', '*'],
12811281
['*', '*', '*', [17, ''], [11, 12], '_', '_', '_', '*', '*', [24, 10], '_', '_', [11, ''], '*'],
12821282
['*', [4, ''], [16, 26], '_', '_', '_', '_', '_', '*', ['', 20], '_', '_', '_', '_', [16, '']],
@@ -1294,7 +1294,7 @@ def display(self, assignment=None):
12941294
['*', '*', ['', 6], '_', '_', '*', '*', ['', 15], '_', '_', '_', '*', '*', '*', '*']]
12951295

12961296

1297-
class Karuko(NaryCSP):
1297+
class Kakuro(NaryCSP):
12981298

12991299
def __init__(self, puzzle):
13001300
variables = []

0 commit comments

Comments
 (0)