what we previously called cw_constraint is a directional arc constraint between two cw_variable. let us introduce a new kind of constraint, cw_cycle, which is a cycle of 4 cw_variable which intersect each other in a loop shape. in my M.Eng paper i proved that non-cycloidal constraints between more than 2 variables are redundant
move existing cw_constraint implementation to a new class cw_arc, which is a derived class of the now-abstract cw_constraint class
add cw_cycle class, which inherits from cw_constraint
add population of cw_cycle constraints and integrate them into cw_csp to be used alongside cw_arc in the initial call to cw_csp::ac3()
Details
to satisfy a cw_cycle, all letters at all intersection indices must lead to valid letter assignments that can satisfy all constraints between variables in the cycle simultaneously. in the implementation, this is done by representing letter placements with nodes and drawing edges between nodes that can coexist in the same word and detecting cycles in the resulting graph. nodes that cannot meet this requirement are pruned from the appropriate variables
major cleanup to all of cw_csp_data_types
clean up cw_constraint interface and formally define its dependents and dependencies
add utility script to create histogram of AC-3 execution time during performance investigation
Testing
update existing test suite, which now all passes
add passing tests for utility functions related to cw_cycle
unfortunately, using cw_cycle constraints led to significant performance dropoffs because of the large amount of execution time needed to verify each constraint. it seems like brute-forcing the dead ends that simple cw_arc constraints cannot detect is a more viable solution here, disproving the hypothesis in #19
however, using cw_cycle does seem to help in some niche cases when used in the initial AC-3 call in cw_csp where its pruning work won't be undone later during solving
Overview
cw_constraintis a directional arc constraint between twocw_variable. let us introduce a new kind of constraint,cw_cycle, which is a cycle of 4cw_variablewhich intersect each other in a loop shape. in my M.Eng paper i proved that non-cycloidal constraints between more than 2 variables are redundantcw_constraintimplementation to a new classcw_arc, which is a derived class of the now-abstractcw_constraintclasscw_cycleclass, which inherits fromcw_constraintcw_cycleconstraints and integrate them intocw_cspto be used alongside cw_arc in the initial call tocw_csp::ac3()Details
cw_cycle, all letters at all intersection indices must lead to valid letter assignments that can satisfy all constraints between variables in the cycle simultaneously. in the implementation, this is done by representing letter placements with nodes and drawing edges between nodes that can coexist in the same word and detecting cycles in the resulting graph. nodes that cannot meet this requirement are pruned from the appropriate variablescw_csp_data_typescw_constraintinterface and formally define its dependents and dependenciesTesting
cw_cyclecw_cycleconstraints led to significant performance dropoffs because of the large amount of execution time needed to verify each constraint. it seems like brute-forcing the dead ends that simplecw_arcconstraints cannot detect is a more viable solution here, disproving the hypothesis in #19cw_cycledoes seem to help in some niche cases when used in the initial AC-3 call incw_cspwhere its pruning work won't be undone later during solvingNotes