import?copy
from?csp?import?CSP


def?create_n_queens_csp（n=8）:
????“““Create?an?N-Queen?problem?on?the?board?of?size?n?*?n.

????You?should?call?csp.add_variable（）?and?csp.add_binary_factor（）.

????Args:
????????n:?int?number?of?queens?or?the?size?of?one?dimension?of?the?board.

????Returns
????????csp:?A?CSP?problem?with?correctly?configured?factor?tables
????????such?that?it?can?be?solved?by?a?weighted?CSP?solver
????“““
????csp?=?CSP（）
????#?TODO:?Problem?b
????#?TODO:?BEGIN_YOUR_CODE
????variables?=?[]
????for?i?in?range（n）:
????????#?name?variables?from?y1?to?yn
????????var?=?‘y{}‘.format（i+1）?
????????#?assign?values?to?variables
????????csp.add_variable（varrange（1n+1））
????????variables.append（var）
????for?i?in?range（len（variables））:
????????for?j?in?range（len（variables））:
????????????if?variables[i]?!=?variables[j]:
????????????????distance?=?abs（i-j）
????????????????#?Generate?binary?constraints?between?queens
????????????????csp.add_binary_factor（variables[i]?variables[j]?lambda?y1?y2:?y1?!=?y2?and?distance?!=?abs（y1-y2））
????#raise?NotImplementedError
????#?TODO:?END_YOUR_CODE
????return?csp


class?BacktrackingSearch:
????“““A?backtracking?algorithm?that?solves?CSP.

????Attributes:
????????num_assignments:?keep?track?of?the?number?of?assignments
????????????（identical?when?the?CSP?is?unweighted）
????????num_operations:?keep?track?of?number?of?times?backtrack（）?gets?called
????????first_assignment_num_operations:?keep?track?of?number?of?operations?to
????????????get?to?the?very?first?successful?assignment?（maybe?not?optimal）
????????all_assignments:?list?of?all?solutions?found

????????csp:?a?weighted?CSP?to?be?solved
????????mcv:?bool?if?True?use?Most?Constrained?Variable?heuristics
????????ac3:?bool?if?True?AC-3?will?be?used?after?each?variable?is?made
????????domains:?dictionary?of?domains?of?every?variable?in?the?CSP

????Usage:
????????search?=?BacktrackingSearch（）
????????search.solve（csp）
????“““

????def?__init__（self）:
????????self.num_assignments?=?0
????????self.num_operations?=?0
????????self.first_assignment_num_operations?=?0
????????self.all_assignments?=?[]

????????self.csp?=?None
????????self.mcv?=?False
????????self.ac3?=?False
????????self.domains?=?{}

????def?reset_results（self）:
????????“““Resets?the?statistics?of?the?different?aspects?of?the?CSP?solver.“““
????????self.num_assignments?=?0
????????self.num_operations?=?0
????????self.first_assignment_num_operations?=?0
????????self.all_assignments?=?[]

????def?check_factors（self?assignment?var?val）:
????????“““Check?consistency?between?current?assignment?and?a?new?variable.

????????Given?a?CSP?a?partial?assignment?and?a?proposed?new?value?for?a
????????variable?return?the?change?of?weights?after?assigning?the?variable
????????with?the?proposed?value.

????????Args:
????????????assignment:?A?dictionary?of?current?assignment.
????????????????Unassigned?variables?do?not?have?entries?while?an?assigned
????????????????variable?has?the?assigned?va