Loading ...
Sorry, an error occurred while loading the content.

865Aima-python, several issues in csp.py

Expand Messages
  • edgar.holleis
    Jul 6, 2009

      I found several issues with the code in csp.py, version aima-python.2007.06.15.zip:

      1) Forward Checking and Maintain Arc Consistency don't work because of a thinko in csp.unassign:

      def unassign(self, var, assignment):
      """Remove {var: val} from assignment; that is backtrack. (...) """
      if var in assignment:
      # Reset the curr_domain to be the full original domain
      if self.curr_domains:
      --> self.curr_domains[var] = self.domains[var][:]
      del assignment[var]

      That cannot work because it discards too much information. The assignments made in previous recursions can all potentially lead to prunings of the current node's domain. In the highlighted line, instead of carefully undoing of the effects a particular assignment, the domain is reset to its initial value, thereby throwing away knowledge of those earlier prunings.

      Both backtrackging_search(usa, fc=True) and backtracking_search(usa, mac=True) return incorrectly colored maps.

      2) The Most Constrained Variable heuristic has it backwards and prefers less constrained variables over more constrained variables. That's why backtracking_search(usa, mcv=True) is guaranteed to run for many hours, exploring the search tree in the most inefficient possible way.

      3) The Least Constraining Value heuristic fails to compile on modern python.

      I took the liberty of developing and testing a patch for the aforementioned issues. Furthermore, it contains a formulation of the Sudoku problem using the csp.py machinery.

      Please find it at:

      Edgar Holleis