Several bugs in CSP.py, patch included

[GoogleCodeExporter]

Reproduce:
$ python
>>> from csp import *
>>> backtracking_search(australia, mcv=True, fc=True)
-> Results in wrong coloring 

Several issues:
- Forward checking and Arc Consistency are severely broken. The most severe
issue is in line 86, where information about pruned domains from previous
steps is wrongly discarded.
- Most constrained variable-heuristic has it backwards and orders the least
constrained variable first
- Least constraining value-heuristic fails to compile on modern python
- The map of USA is wrong (New York adjacent to California), some borders
missing

The included patch fixes the described issues plus adds
- The map of France by Regions
- Formulation of the Sudoku-Problem
- Some trivial testing code

Otherwise great book!

Original issue reported on code.google.com by edgar.ho...@gmail.com on 6 Jul 2009 at 12:17

Attachments:

• csp.py.diff

[GoogleCodeExporter]

I confirm these bugs (cost me some hair before I noticed them, having assumed 
the
code is correct) and Edgar's fixes work

Original comment by eliben on 25 Jul 2009 at 7:46

[GoogleCodeExporter]

Thanks for the fixes, Edgar, and sorry for the hair-loss.  I'll incorporate 
these
soon.  My dilemma: we're working on a 3rd edition of the text, and some code 
will be
different; I don't have time to write the text and maintain two versions of the 
code.
 But I'll have to come up with some solution soon...

Original comment by peter.no...@gmail.com on 5 Aug 2009 at 7:19

[GoogleCodeExporter]

This issue was closed by revision r81.

Original comment by wit...@gmail.com on 3 Oct 2011 at 11:02

• Changed state: Fixed