<s> import random <EOL> from copy import deepcopy , copy <EOL> from itertools import product <EOL> from utils import argmin <EOL> MOST_CONSTRAINED_VARIABLE = '<STR_LIT>' <EOL> HIGHEST_DEGREE_VARIABLE = '<STR_LIT>' <EOL> LEAST_CONSTRAINING_VALUE = '<STR_LIT>' <EOL> def backtrack ( problem , variable_heuristic = '<STR_LIT>' , value_heuristic = '<STR_LIT>' , inference = True ) : <EOL> '''<STR_LIT>''' <EOL> assignment = { } <EOL> domains = deepcopy ( problem . domains ) <EOL> if variable_heuristic == MOST_CONSTRAINED_VARIABLE : <EOL> variable_chooser = _most_constrained_variable_chooser <EOL> elif variable_heuristic == HIGHEST_DEGREE_VARIABLE : <EOL> variable_chooser = _highest_degree_variable_chooser <EOL> else : <EOL> variable_chooser = _basic_variable_chooser <EOL> if value_heuristic == LEAST_CONSTRAINING_VALUE : <EOL> values_sorter = _least_constraining_values_sorter <EOL> else : <EOL> values_sorter = _basic_values_sorter <EOL> return _backtracking ( problem , <EOL> assignment , <EOL> domains , <EOL> variable_chooser , <EOL> values_sorter , <EOL> inference = inference ) <EOL> def _basic_variable_chooser ( problem , variables , domains ) : <EOL> '''<STR_LIT>''' <EOL> return variables [ <NUM_LIT:0> ] <EOL> def _most_constrained_variable_chooser ( problem , variables , domains ) : <EOL> '''<STR_LIT>''' <EOL> return sorted ( variables , key = lambda v : len ( domains [ v ] ) ) [ <NUM_LIT:0> ] <EOL> def _highest_degree_variable_chooser ( problem , variables , domains ) : <EOL> '''<STR_LIT>''' <EOL> return sorted ( variables , key = lambda v : problem . var_degrees [ v ] , reverse = True ) [ <NUM_LIT:0> ] <EOL> def _count_conflicts ( problem , assignment , variable = None , value = None ) : <EOL> '''<STR_LIT>''' <EOL> return len ( _find_conflicts ( problem , assignment , variable , value ) ) <EOL> def _call_constraint ( assignment , neighbors , constraint ) : <EOL> variables , values = zip ( * [ ( n , assignment [ n ] ) <EOL> for n in neighbors ] ) <EOL> return constraint ( variables , values ) <EOL> def _find_conflicts ( problem , assignment , variable = None , value = None ) : <EOL> '''<STR_LIT>''' <EOL> if variable is not None and value is not None : <EOL> assignment = deepcopy ( assignment ) <EOL> assignment [ variable ] = value <EOL> conflicts = [ ] <EOL> for neighbors , constraint in problem . constraints : <EOL> if all ( n in assignment for n in neighbors ) : <EOL> if not _call_constraint ( assignment , neighbors , constraint ) : <EOL> conflicts . append ( ( neighbors , constraint ) ) <EOL> return conflicts <EOL> def _basic_values_sorter ( problem , assignment , variable , domains ) : <EOL> '''<STR_LIT>''' <EOL> return domains [ variable ] [ : ] <EOL> def _least_constraining_values_sorter ( problem , assignment , variable , domains ) : <EOL> '''<STR_LIT>''' <EOL> def update_assignment ( value ) : <EOL> new_assignment = deepcopy ( assignment ) <EOL> new_assignment [ variable ] = value <EOL> return new_assignment <EOL> values = sorted ( domains [ variable ] [ : ] , <EOL> key = lambda v : _count_conflicts ( problem , assignment , <EOL> variable , v ) ) <EOL> return values <EOL> def _backtracking ( problem , assignment , domains , variable_chooser , values_sorter , inference = True ) : <EOL> '''<STR_LIT>''' <EOL> from arc import arc_consistency_3 <EOL> if len ( assignment ) == len ( problem . variables ) : <EOL> return assignment <EOL> pending = [ v for v in problem . variables <EOL> if v not in assignment ] <EOL> variable = variable_chooser ( problem , pending , domains ) <EOL> values = values_sorter ( problem , assignment , variable , domains ) <EOL> for value in values : <EOL> new_assignment = deepcopy ( assignment ) <EOL> new_assignment [ variable ] = value <EOL> if not _count_conflicts ( problem , new_assignment ) : <EOL> new_domains = deepcopy ( domains ) <EOL> new_domains [ variable ] = [ value ] <EOL> if not inference or arc_consistency_3 ( new_domains , problem . constraints ) : <EOL> result = _backtracking ( problem , <EOL> new_assignment , <EOL> new_domains , <EOL> variable_chooser , <EOL> values_sorter , <EOL> inference = inference ) <EOL> if result : <EOL> return result <EOL> return None <EOL> def _min_conflicts_value ( problem , assignment , variable ) : <EOL> '''<STR_LIT>''' <EOL> return argmin ( problem . domains [ variable ] , lambda x : _count_conflicts ( problem , assignment , variable , x ) ) <EOL> def min_conflicts ( problem , initial_assignment = None , iterations_limit = <NUM_LIT:0> ) : <EOL> """<STR_LIT>""" <EOL> assignment = { } <EOL> if initial_assignment : <EOL> assignment . update ( initial_assignment ) <EOL> else : <EOL> for variable in problem . variables : <EOL> value = _min_conflicts_value ( problem , assignment , variable ) <EOL> assignment [ variable ] = value <EOL> iteration = <NUM_LIT:0> <EOL> run = True <EOL> while run : <EOL> conflicts = _find_conflicts ( problem , assignment ) <EOL> conflict_variables = [ v for v in problem . variables <EOL> if any ( v in conflict [ <NUM_LIT:0> ] for conflict in conflicts ) ] <EOL> if conflict_variables : <EOL> variable = random . choice ( conflict_variables ) <EOL> value = _min_conflicts_value ( problem , assignment , variable ) <EOL> assignment [ variable ] = value <EOL> iteration += <NUM_LIT:1> <EOL> if iterations_limit and iteration >= iterations_limit : <EOL> run = False <EOL> elif not _count_conflicts ( problem , assignment ) : <EOL> run = False <EOL> return assignment <EOL> def convert_to_binary ( variables , domains , constraints ) : <EOL> """<STR_LIT>""" <EOL> def wdiff ( vars_ ) : <EOL> def diff ( variables , values ) : <EOL> hidden , other = variables <EOL> if hidden . startswith ( '<STR_LIT>' ) : <EOL> idx = vars_ . index ( other ) <EOL> return values [ <NUM_LIT:1> ] == values [ <NUM_LIT:0> ] [ idx ] <EOL> else : <EOL> idx = vars_ . index ( hidden ) <EOL> return values [ <NUM_LIT:0> ] == values [ <NUM_LIT:1> ] [ idx ] <EOL> diff . no_wrap = True <EOL> return diff <EOL> new_constraints = [ ] <EOL> new_domains = copy ( domains ) <EOL> new_variables = list ( variables ) <EOL> last = <NUM_LIT:0> <EOL> for vars_ , const in constraints : <EOL> if len ( vars_ ) == <NUM_LIT:2> : <EOL> new_constraints . append ( ( vars_ , const ) ) <EOL> continue <EOL> hidden = '<STR_LIT>' % last <EOL> new_variables . append ( hidden ) <EOL> last += <NUM_LIT:1> <EOL> new_domains [ hidden ] = [ t for t in product ( * map ( domains . get , vars_ ) ) if const ( vars_ , t ) ] <EOL> for var in vars_ : <EOL> new_constraints . append ( ( ( hidden , var ) , wdiff ( vars_ ) ) ) <EOL> return new_variables , new_domains , new_constraints </s>
