5 CONSTRAINT SATISFACTION PROBLEMS

1 5 CONSTRAINTSATISFACTIONPROBLEMSI nwhich weseehowtreatingstatesasmore thanjustlittleblack boxesleadsto theinventionofa range ofpowerfulnew search methodsanda deeperunderstandingofproblemstructure and4 exploredtheideathatproblemscanbesolvedby searchinginaspaceofstates. Thesestatescanbeevaluatedbydomain-specif icheuristicsandtestedtoseewhetherthey ,however,eachstateis is representedbyanarbi-BLACKBOX trarydatastructurethatcanbeaccessedonlyb ytheproblem-specificroutines thesuccessorfunction,heuristicfunction, , whosestatesandgoaltestconformtoa standard,structured,andverysimplereprese ntation( ).Searchal-REPRESENTATION gorithmscanbedefinedthattake advantageofthestructureofstatesandusegen eral-purposeratherthanproblem-specifiche uristicsto enablethesolutionoflargeproblems( ).Perhapsmostimportantly, thestandardrepresentationofthegoaltestre vealsthestruc-tureoftheproblemitself( ).Thisleadstomethodsforproblemdecomposit ionandtoanunderstandingoftheintimateconn ectionbetweenthestructureofa ,aconstraintsatisfactionproblem(orCSP)is definedbya setofvari-CONSTRAINTSATISFACTIONPROBLEM ables,X1; X2; : : : ; Xn, anda setofconstraints,C1; C2; : : : ; Cm.

2 EachvariableXihasaVARIABLESCONSTRAINTS nonemptydomainDiofpossiblevalues. definedbyanassignmentofvaluesto someorallofthevariables,fXi=vi; Xj=ASSIGNMENTvj; : : :g. Anassignmentthatdoesnotviolateany constraintsis oneinwhicheveryvariableis mentioned,andaso-lutiontoa CSPis a solutionthatmaximizesanobjective ,havingtiredofRomania,wearelookingata mapofAustraliashowingeachofitsstatesandt erritories, (a),andthatwearegiventhetaskofcoloringea chregioneitherred,green,orblueinsucha waythatnoneighboringregionshave thesamecolor. To formulatethisasa CSP, wedefinethevariablestobetheregions:WA,NT ,Q,NSW,V,SA, andT. Thedomainofeachvariableis thesetfred;green;blueg. Theconstraintsrequireneighboringregionst ohave distinctcolors;forexample,theallowableco mbinationsforWAandNTarethepairsf(red;gre en);(red;blue);(green;red);(green;blue); (blue;red);(blue;green)g:(Theconstraintc analsoberepresentedmoresuccinctlyasthein equalityWA6=NT, pro-videdtheconstraintsatisfactionalgori thmhassomewayto evaluatesuchexpressions.)

3 Therearemany possiblesolutions,suchasfWA=red;NT=green ; Q=red;NSW=green; V=red;SA=blue; T=redg:It is helpfultovisualizea CSPasaconstraintgraph, (b). problemasa a CSPconformsto astandardpattern thatis,a setofvariableswithassignedvalues thesuccessorfunctionandgoaltestcanwritte nina ,wecandevelopeffective,genericheuristics thatrequirenoadditional, , thestructureoftheconstraintgraphcanbeuse dtosim-plifythesolutionprocess,insomecas esgivinganexponentialreductionincomplexi ty. TheCSPrepresentationis thefirst,andsimplest,ina South WalesVictoriaTasmaniaWANTSAQNSWVT(a)(b)F igure (a) toassigncolorstoeachregionsothatnoneighb oringregionshave thesamecolor. (b)Themap-coloringproblemrepresentedasa is fairlyeasyto seethata CSPcanbegivenanincrementalformulationasa standardsearchproblemasfollows:}Initials tate: theemptyassignmentfg, inwhichallvariablesareunassigned.}Succes sorfunction: a valuecanbeassignedtoany unassignedvariable,providedthatit doesnotconflictwithpreviouslyassignedvar iables.

4 }Goaltest: thecurrentassignmentis complete.}Pathcost: a constantcost( ,1) completeassignmentandthereforeappearsatd epthnif ,thesearchtreeextendsonlytodepthn. Forthesereasons,depth-firstsearchalgorit hmsarepopularforCSPs.( )It is alsothecasethatthepathbywhich a solutionis reachedis ,wecanalsouseacomplete-stateformulation, inwhicheverystateis a ( ) canalsobeviewedasa finite-domainCSP, wherethevariablesQ1; : : : ; Q8arethepositionsofeachqueenincolumns1; : : : ;8andeachvariablehasthedomainf1;2;3;4;5; 6;7;8g. If themaximumdomainsizeofany variableina CSPisd, thenthenumberofpossiblecompleteassignmen tsisO(dn) thatis, , whosevariablescanbeeithertrueorfalse. BooleanCSPsincludeBOOLEANCSPS asspecialcasessomeNP-completeproblems,su chas3 SAT. (SeeChapter7.)Intheworstcase,therefore,w ecannotexpecttosolve ,however, general-purposeCSPalgorithmscansolve problemsorders ofmagnitudelargerthanthosesolvableviathe general-purposesearchalgorithmsthatwesaw forexample, ,whenschedulingconstructionjobsontoa calendar, eachjob sstartdateis a ,it is , ,ifJob1, whichtakesfive days,mustprecedeJob3, thenwewouldneeda constraintlanguageofalgebraicinequalitie ssuchasStartJob1+ 5 StartJob3.

5 It is alsonolongerpossibletosolve suchconstraintsbyenumeratingallpossiblea ssignments,becausethereareinfinitelymany (whichwewillnotdiscusshere)existforlinea rconstraintsonintegervariables thatis, constraints ,suchastheonejustgiven , , ,ina schedulingproblem, , ;thestartandfinishofeachobservationandma neuverarecontinuous-valuedvariablesthatm ustobey a varietyofastronomical,precedence, thatoflinearprogrammingproblems, timepolynomialin functionshave alsobeenstudied quadraticprogramming,second-orderconicpr ogramming, ,it is usefultolookat theunaryconstraint, whichrestrictstheUNARY CONSTRAINT valueofa ,it couldbethecasethatSouthAustraliansactive lydislike thecolorgreen. Everyunaryconstraintcanbeeliminatedsimpl ybypreprocessingthedomainofthecorrespond ingvariabletoremove any ,SA6=NSWis a CONSTRAINT binaryCSPis onewithonlybinaryconstraints;it canberepresentedasa constraintgraph, (b).Higher-orderconstraintsinvolve ( (a).)

6 It is usualtoinsistthateachletterinCRYPTARITHM ETICa cryptarithmeticpuzzlerepresenta (a)),thiswouldberepresentedasthesix-vari ableconstraintAlldi (F; T; U; W; R; O). Alternatively, it canberepresentedbya collectionofbinaryconstraintssuchasF6=T. Theadditionconstraintsonthefourcolumnsof thepuzzlealsoinvolve severalvariablesandcanbewrittenasO+O=R+ 10 X1X1+W+W=U+ 10 X2X2+T+T=O+ 10 X3X3=FwhereX1,X2, andX3areauxiliaryvariablesrepresentingth edigit(0or1)carriedover , (b).Thesharp-eyedreaderwillhave noticedthattheAlldi constraintcanbebrokendownintobinaryconst raints F6=T,F6=U, , , everyhigher-order, finite-domainconstraintcanbereducedto a setofbinaryconstraintsif , describedsofarhave allbeenabsoluteconstraints,violationofwh ichrulesouta ,ina universitytimetablingproblem, teachingat 2 solution( ), forexample, pointsagainsttheoverallobjective function, , (a)OWTFUR(b)+FTTOWWUOORX3X1X2 Figure (a)A distinctdigit;theaimistofinda substitutionofdigitsforletterssuchthatth eresultingsumis arithmeticallycorrect,withtheaddedrestri ctionthatnoleadingzeroesareallowed.

7 (b)Theconstrainthypergraphforthecryptari thmeticproblem,showingtheAlldi a squareboxconnectedtothevariablesit , donotdiscusssuchCSPsfurtherinthischapter , a ,any ofthesearchalgorithmsfromChapters3 and4 cansolve quicklynoticesomethingterrible:thebranch ingfactorat thetoplevel isnd, becauseanyofdvaluescanbeassignedtoany ,thebranchingfactoris(n 1)d, generatea treewithn! dnleaves,eventhoughthereareonlydnpossibl ecompleteassignments!Ourseeminglyreasona blebut na ve problemformulationhasignoreda crucialpropertycommontoallCSPs:commutati vity. A problemis commutative if theorderofapplicationCOMMUTATIVITY ofany ,whenassigningvaluestovariables,wereacht hesamepartialassignment,regardlessoforde r. Therefore,allCSPsearch algorithmsgeneratesuccessors byconsideringpossibleassignmentsforonlya singlevariableateach nodeinthesearch ,attherootnodeofa searchtreeforcoloringthemapofAustralia,w emighthave a choicebetweenSA=red,SA=green, andSA=blue, butwewouldneverchoosebetweenSA=redandWA= blue.

8 Withthisrestriction,thenumberofleavesisd n, usedfora depth-firstsearchthatchoosesvaluesforBAC KTRACKINGSEARCH onevariableat a timeandbacktrackswhena variablehasnolegal uses,ineffect, (csp)returnsa solution,orfailurereturnRECURSIVE-BACKTR ACKING(fg,csp)functionRECURSIVE-BACKTRAC KING(assignment,csp)returnsa solution,orfailureifassignmentis completethenreturnassignmentvar SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp ],assignment,csp)foreachvalueinORDER-DOM AIN-VALUES(var,assignment,csp)doifvaluei s consistentwithassignmentaccordingtoCONST RAINTS[csp]thenaddfvar=valuegtoassignmen tresult RECURSIVE-BACKTRACKING(assignment,csp)if result6=failurethenreturnresultremovefva r=valuegfromassignmentreturnfailureFigur e ,it extendsthecurrentassign-menttogeneratea successor, ,thereis noneedtosupplyBACKTRACKING-SEARCH witha domain-specificinitialstate,successorfun ction, ,wherewehave assignedvariablesintheorderWA;NT; Q.

9 Plainbacktrackingis anuninformedalgorithmintheterminologyofC hapter3,sowedonotexpectit to beveryeffective turnsoutthatwecansolve +MRVF orwardCheckingFC+MRVMin-ConflictsUSA(>1, 000K)(>1,000K)2K6064n-Queens(>40,000K)13 ,500K(>40,000K)817K4 KZebra3, ,aresimplebacktracking,backtrackingwitht heMRVheuristic,forwardchecking,forwardch eckingwithMRV, themediannumberofconsistency checks(overfive runs)requiredtosolve theprob-lem;notethatallentriesexceptthet wo intheupperrightareinthousands(K). findinga (1995), alln-Queensproblemsfornfrom2 the ZebraPuzzle, areartificialrandomproblems.(Min-conflic tswasnotrunonthese.)Theresultssuggesttha tforwardcheckingwiththeMRV heuristicis betteronalltheseproblemsthantheotherback trackingalgorithms, ,wefindgeneral- ,andinwhatordershoulditsvaluesbetried? pathfails thatis,a stateis reachedinwhicha variablehasnolegal values canthesearchavoidrepeatingthisfailureins ubsequentpaths?Thesubsectionsthatfollow SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp ],assignment,csp).

10 Bydefault,SELECT-UNASSIGNED-VARIABLE simplyselectsthenextunassignedvariablein theordergivenbythelistVARIABLES[csp]. ,aftertheassignmentsforWA=redandNT=green ,thereis onlyonepossiblevalueforSA, soit makessenseto assignSA=bluenext ratherthanassigningQ. Infact,afterSAis assigned,thechoicesforQ,NSW, idea choosingthevariablewiththefewest legal values iscalledtheminimumremainingvalues(MRV) alsohasbeencalledthe mostconstrainedvariable orMINIMUMREMAININGVALUES fail-first heuristic,thelatterbecauseit picksa variablethatis mostlikelytocausea failuresoon, thereis a variableXwithzerolegal valuesremain-ing,theMRVheuristicwillsele ctXandfailurewillbedetectedimmediately avoidingpointlesssearchesthroughothervar iableswhichalwayswillfailwhenXis ,labeledBT+MRV, 3 to3,000timesbetterthansimplebacktracking , ;thenextsubsectiondescribesa heuristicdoesn t helpat allinchoosingthefirstregiontocolorinAust ralia,becauseinitiallyeveryregionhasthre elegal ,thedegreeheuristiccomesDEGREEHEURISTIC inhandy.