CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Constraint satisfaction problem - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"f3cab537-f449-43d7-9189-948039f8c3ff","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Constraint_satisfaction_problem","wgTitle":"Constraint satisfaction problem","wgCurRevisionId":1259275985,"wgRevisionId":1259275985,"wgArticleId":211652,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","Articles with short description","Short description is different from Wikidata","Articles needing additional references from November 2014","All articles needing additional references","Constraint programming","NP-complete problems"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Constraint_satisfaction_problem","wgRelevantArticleId":211652, "wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1128326","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"], "GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar", "ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Constraint satisfaction problem - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Constraint_satisfaction_problem"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Constraint_satisfaction_problem&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Constraint_satisfaction_problem rootpage-Constraint_satisfaction_problem skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Constraint+satisfaction+problem" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Constraint+satisfaction+problem" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Constraint+satisfaction+problem" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Constraint+satisfaction+problem" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Formal_definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formal_definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Formal definition</span> </div> </a> <ul id="toc-Formal_definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Solution" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Solution"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Solution</span> </div> </a> <ul id="toc-Solution-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Theoretical_aspects" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Theoretical_aspects"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Theoretical aspects</span> </div> </a> <button aria-controls="toc-Theoretical_aspects-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Theoretical aspects subsection</span> </button> <ul id="toc-Theoretical_aspects-sublist" class="vector-toc-list"> <li id="toc-Computational_Complexity" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Computational_Complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Computational Complexity</span> </div> </a> <ul id="toc-Computational_Complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Function_problems" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Function_problems"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Function problems</span> </div> </a> <ul id="toc-Function_problems-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Variants" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Variants"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Variants</span> </div> </a> <button aria-controls="toc-Variants-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Variants subsection</span> </button> <ul id="toc-Variants-sublist" class="vector-toc-list"> <li id="toc-Dynamic_CSPs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Dynamic_CSPs"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Dynamic CSPs</span> </div> </a> <ul id="toc-Dynamic_CSPs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Flexible_CSPs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Flexible_CSPs"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Flexible CSPs</span> </div> </a> <ul id="toc-Flexible_CSPs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Decentralized_CSPs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Decentralized_CSPs"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Decentralized CSPs</span> </div> </a> <ul id="toc-Decentralized_CSPs-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Constraint satisfaction problem</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 13 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-13" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">13 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Constraint-Satisfaction-Problem" title="Constraint-Satisfaction-Problem – German" lang="de" hreflang="de" data-title="Constraint-Satisfaction-Problem" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Problema_de_satisfacci%C3%B3n_de_restricciones" title="Problema de satisfacción de restricciones – Spanish" lang="es" hreflang="es" data-title="Problema de satisfacción de restricciones" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A7%D8%B1%D8%B6%D8%A7%DB%8C_%D9%85%D8%AD%D8%AF%D9%88%D8%AF%DB%8C%D8%AA" title="مسئله ارضای محدودیت – Persian" lang="fa" hreflang="fa" data-title="مسئله ارضای محدودیت" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_satisfaction_de_contraintes" title="Problème de satisfaction de contraintes – French" lang="fr" hreflang="fr" data-title="Problème de satisfaction de contraintes" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%A0%9C%EC%95%BD_%EC%B6%A9%EC%A1%B1_%EB%AC%B8%EC%A0%9C" title="제약 충족 문제 – Korean" lang="ko" hreflang="ko" data-title="제약 충족 문제" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%AC%E0%A4%BE%E0%A4%A7%E0%A4%BE_%E0%A4%B8%E0%A4%82%E0%A4%A4%E0%A5%81%E0%A4%B7%E0%A5%8D%E0%A4%9F%E0%A4%BF_%E0%A4%95%E0%A5%80_%E0%A4%B8%E0%A4%AE%E0%A4%B8%E0%A5%8D%E0%A4%AF%E0%A4%BE" title="बाधा संतुष्टि की समस्या – Hindi" lang="hi" hreflang="hi" data-title="बाधा संतुष्टि की समस्या" data-language-autonym="हिन्दी" data-language-local-name="Hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Problema_di_soddisfacimento_di_vincoli" title="Problema di soddisfacimento di vincoli – Italian" lang="it" hreflang="it" data-title="Problema di soddisfacimento di vincoli" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%91%D7%A2%D7%99%D7%99%D7%AA_%D7%A1%D7%99%D7%A4%D7%95%D7%A7_%D7%90%D7%99%D7%9C%D7%95%D7%A6%D7%99%D7%9D" title="בעיית סיפוק אילוצים – Hebrew" lang="he" hreflang="he" data-title="בעיית סיפוק אילוצים" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E5%88%B6%E7%B4%84%E5%85%85%E8%B6%B3%E5%95%8F%E9%A1%8C" title="制約充足問題 – Japanese" lang="ja" hreflang="ja" data-title="制約充足問題" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Problema_da_satisfa%C3%A7%C3%A3o_de_restri%C3%A7%C3%B5es" title="Problema da satisfação de restrições – Portuguese" lang="pt" hreflang="pt" data-title="Problema da satisfação de restrições" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A3%D0%B4%D0%BE%D0%B2%D0%BB%D0%B5%D1%82%D0%B2%D0%BE%D1%80%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%87%D0%B5%D0%BD%D0%B8%D0%B9" title="Удовлетворение ограничений – Russian" lang="ru" hreflang="ru" data-title="Удовлетворение ограничений" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%BA%D0%BE%D0%BD%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BE%D0%B1%D0%BC%D0%B5%D0%B6%D0%B5%D0%BD%D1%8C" title="Задача виконання обмежень – Ukrainian" lang="uk" hreflang="uk" data-title="Задача виконання обмежень" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E7%B4%84%E6%9D%9F%E6%BB%BF%E8%B6%B3%E5%95%8F%E9%A1%8C" title="約束滿足問題 – Chinese" lang="zh" hreflang="zh" data-title="約束滿足問題" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1128326#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Constraint_satisfaction_problem" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Constraint_satisfaction_problem" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Constraint_satisfaction_problem"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Constraint_satisfaction_problem"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Constraint_satisfaction_problem" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Constraint_satisfaction_problem" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&oldid=1259275985" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Constraint_satisfaction_problem&id=1259275985&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FConstraint_satisfaction_problem"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FConstraint_satisfaction_problem"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Constraint_satisfaction_problem&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Constraint_satisfaction_problem&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Constraint_satisfaction" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1128326" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Set of objects whose state must satisfy limits</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="/wiki/Communicating_sequential_processes" title="Communicating sequential processes">Communicating sequential processes</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Constraint_satisfaction_problem" title="Special:EditPage/Constraint satisfaction problem">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Constraint+satisfaction+problem%22">"Constraint satisfaction problem"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Constraint+satisfaction+problem%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Constraint+satisfaction+problem%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Constraint+satisfaction+problem%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Constraint+satisfaction+problem%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Constraint+satisfaction+problem%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">November 2014</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p><b>Constraint satisfaction problems</b> (<b>CSPs</b>) are mathematical questions defined as a set of objects whose <a href="/wiki/State_(computer_science)" title="State (computer science)">state</a> must satisfy a number of <a href="/wiki/Constraint_(mathematics)" title="Constraint (mathematics)">constraints</a> or <a href="/wiki/Limit_(mathematics)" title="Limit (mathematics)">limitations</a>. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over <a href="/wiki/Variable_(mathematics)" title="Variable (mathematics)">variables</a>, which is solved by <a href="/wiki/Constraint_satisfaction" title="Constraint satisfaction">constraint satisfaction</a> methods. CSPs are the subject of research in both <a href="/wiki/Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a> and <a href="/wiki/Operations_research" title="Operations research">operations research</a>, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. <a href="/wiki/Complexity_of_constraint_satisfaction" title="Complexity of constraint satisfaction">CSPs often exhibit high complexity</a>, requiring a combination of <a href="/wiki/Heuristics" class="mw-redirect" title="Heuristics">heuristics</a> and <a href="/wiki/Combinatorial_search" title="Combinatorial search">combinatorial search</a> methods to be solved in a reasonable time. <a href="/wiki/Constraint_programming" title="Constraint programming">Constraint programming</a> (CP) is the field of research that specifically focuses on tackling these kinds of problems.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Additionally, the <a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> (SAT), <a href="/wiki/Satisfiability_modulo_theories" title="Satisfiability modulo theories">satisfiability modulo theories</a> (SMT), <a href="/wiki/Mixed_integer_programming" class="mw-redirect" title="Mixed integer programming">mixed integer programming</a> (MIP) and <a href="/wiki/Answer_set_programming" title="Answer set programming">answer set programming</a> (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem. </p><p>Examples of problems that can be modeled as a constraint satisfaction problem include: </p> <ul><li><a href="/wiki/Type_inference" title="Type inference">Type inference</a><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Eight_queens_puzzle" title="Eight queens puzzle">Eight queens puzzle</a></li> <li><a href="/wiki/Graph_coloring" title="Graph coloring">Map coloring problem</a></li> <li><a href="/wiki/Maximum_cut" title="Maximum cut">Maximum cut problem</a><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Sudoku" title="Sudoku">Sudoku</a>, <a href="/wiki/Crossword" title="Crossword">crosswords</a>, <a href="/wiki/Futoshiki" title="Futoshiki">futoshiki</a>, <a href="/wiki/Kakuro" title="Kakuro">Kakuro</a> (Cross Sums), <a href="/wiki/Numbrix" class="mw-redirect" title="Numbrix">Numbrix</a>/<a href="/wiki/Hidato" title="Hidato">Hidato</a> and many other <a href="/wiki/Logic_puzzle" title="Logic puzzle">logic puzzles</a></li></ul> <p>These are often provided with tutorials of <a href="/wiki/Constraint_programming" title="Constraint programming">CP</a>, ASP, Boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include <a href="/wiki/Automated_planning" class="mw-redirect" title="Automated planning">automated planning</a>,<sup id="cite_ref-GhallabNau2004_6-0" class="reference"><a href="#cite_note-GhallabNau2004-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Lexical_disambiguation" class="mw-redirect" title="Lexical disambiguation">lexical disambiguation</a>,<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Musicology" title="Musicology">musicology</a>,<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Configure,_price_and_quote" title="Configure, price and quote">product configuration</a><sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> and <a href="/wiki/Resource_allocation" title="Resource allocation">resource allocation</a>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p><p>The existence of a solution to a CSP can be viewed as a <a href="/wiki/Decision_problem" title="Decision problem">decision problem</a>. This can be decided by finding a solution, or failing to find a solution after exhaustive search (<a href="/wiki/Stochastic_algorithm" class="mw-redirect" title="Stochastic algorithm">stochastic algorithms</a> typically never reach an exhaustive conclusion, while directed searches often do, on sufficiently small problems). In some cases the CSP might be known to have solutions beforehand, through some other mathematical inference process. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=1" title="Edit section: Formal definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Formally, a constraint satisfaction problem is defined as a triple <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle X,D,C\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <mi>X</mi> <mo>,</mo> <mi>D</mi> <mo>,</mo> <mi>C</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle X,D,C\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2e74db7a51e7e2bd4993c61fc60fb5d2f23ef6f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.548ex; height:2.843ex;" alt="{\displaystyle \langle X,D,C\rangle }"></span>, where<sup id="cite_ref-Russell2010_13-0" class="reference"><a href="#cite_note-Russell2010-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=\{X_{1},\ldots ,X_{n}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X=\{X_{1},\ldots ,X_{n}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dcbf39e54811783de5bfd141d419c65a4845dde2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.703ex; height:2.843ex;" alt="{\displaystyle X=\{X_{1},\ldots ,X_{n}\}}"></span> is a set of variables,</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=\{D_{1},\ldots ,D_{n}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D=\{D_{1},\ldots ,D_{n}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/169fc4f57811304de0d1efffd1e4dba3152eba91" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.647ex; height:2.843ex;" alt="{\displaystyle D=\{D_{1},\ldots ,D_{n}\}}"></span> is a set of their respective domains of values, and</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=\{C_{1},\ldots ,C_{m}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C=\{C_{1},\ldots ,C_{m}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d49c92e67face9fb811ad2f10c6bb1ce1804a6cd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.421ex; height:2.843ex;" alt="{\displaystyle C=\{C_{1},\ldots ,C_{m}\}}"></span> is a set of constraints.</li></ul> <p>Each variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af4a0955af42beb5f85aa05fb8c07abedc13990d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle X_{i}}"></span> can take on the values in the nonempty domain <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f07b53d3212e08ca316a536c8aac0bbefa79ee1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.724ex; height:2.509ex;" alt="{\displaystyle D_{i}}"></span>. Every constraint <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{j}\in C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>∈</mo> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{j}\in C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0fb599c15e70abc26200f17997299d3e935befaa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.179ex; height:2.843ex;" alt="{\displaystyle C_{j}\in C}"></span> is in turn a pair <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle t_{j},R_{j}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle t_{j},R_{j}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/668bed52faba4d03b23bb64891c65ce024da7017" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.266ex; height:3.009ex;" alt="{\displaystyle \langle t_{j},R_{j}\rangle }"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>⊆</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3061f944959af2bd28b9efac4d621723398faac3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.104ex; height:3.009ex;" alt="{\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}"></span> is a set of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> indices and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6bc93d61e1436bb2c2fb771a13d0892784754998" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.674ex; height:2.843ex;" alt="{\displaystyle R_{j}}"></span> is a <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span>-ary <a href="/wiki/Relation_(mathematics)" title="Relation (mathematics)">relation</a> on the corresponding product of domains <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \times _{i\in t_{j}}D_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>∈</mo> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mrow> </msub> <msub> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \times _{i\in t_{j}}D_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f24422ad0e18a56db579bdaae8aca1b95bff71fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.736ex; height:3.009ex;" alt="{\displaystyle \times _{i\in t_{j}}D_{i}}"></span> where the product is taken with indices in ascending order. An <i>evaluation</i> of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> satisfies a constraint <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle t_{j},R_{j}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle t_{j},R_{j}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/668bed52faba4d03b23bb64891c65ce024da7017" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.266ex; height:3.009ex;" alt="{\displaystyle \langle t_{j},R_{j}\rangle }"></span> if the values assigned to the variables <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/53942a7888623b7eff84a0e43183e046c9f66d65" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.749ex; height:2.676ex;" alt="{\displaystyle t_{j}}"></span> satisfy the relation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6bc93d61e1436bb2c2fb771a13d0892784754998" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.674ex; height:2.843ex;" alt="{\displaystyle R_{j}}"></span>. </p><p>An evaluation is <i>consistent</i> if it does not violate any of the constraints. An evaluation is <i>complete</i> if it includes all variables. An evaluation is a <i>solution</i> if it is consistent and complete; such an evaluation is said to <i>solve</i> the constraint satisfaction problem. </p> <div class="mw-heading mw-heading2"><h2 id="Solution">Solution</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=2" title="Edit section: Solution"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Constraint satisfaction problems on finite domains are typically solved using a form of <a href="/wiki/Search_algorithm" title="Search algorithm">search</a>. The most used techniques are variants of <a href="/wiki/Backtracking" title="Backtracking">backtracking</a>, <a href="/wiki/Constraint_propagation" class="mw-redirect" title="Constraint propagation">constraint propagation</a>, and <a href="/wiki/Local_search_(optimization)" title="Local search (optimization)">local search</a>. These techniques are also often combined, as in the <a href="/wiki/Very_large-scale_neighborhood_search" title="Very large-scale neighborhood search">VLNS</a> method, and current research involves other technologies such as <a href="/wiki/Linear_programming" title="Linear programming">linear programming</a>.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p><p><a href="/wiki/Backtracking" title="Backtracking">Backtracking</a> is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a <a href="/wiki/Recursion" title="Recursion">recursive</a> call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. <a href="/wiki/Backmarking" title="Backmarking">Backmarking</a> improves the efficiency of checking consistency. <a href="/wiki/Backjumping" title="Backjumping">Backjumping</a> allows saving part of the search by backtracking "more than one variable" in some cases. <a href="/wiki/Constraint_learning" title="Constraint learning">Constraint learning</a> infers and saves new constraints that can be later used to avoid part of the search. <a href="/wiki/Look-ahead_(backtracking)" title="Look-ahead (backtracking)">Look-ahead</a> is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable. </p><p><a href="/wiki/Constraint_propagation" class="mw-redirect" title="Constraint propagation">Constraint propagation</a> techniques are methods used to modify a constraint satisfaction problem. More precisely, they are methods that enforce a form of <a href="/wiki/Local_consistency" title="Local consistency">local consistency</a>, which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are <a href="/wiki/Arc_consistency" class="mw-redirect" title="Arc consistency">arc consistency</a>, <a href="/wiki/Hyper-arc_consistency" class="mw-redirect" title="Hyper-arc consistency">hyper-arc consistency</a>, and <a href="/wiki/Path_consistency" class="mw-redirect" title="Path consistency">path consistency</a>. The most popular constraint propagation method is the <a href="/wiki/AC-3_algorithm" title="AC-3 algorithm">AC-3 algorithm</a>, which enforces arc consistency. </p><p><a href="/wiki/Local_search_(optimization)" title="Local search (optimization)">Local search</a> methods are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment. The <a href="/wiki/Min-conflicts_algorithm" title="Min-conflicts algorithm">min-conflicts algorithm</a> is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to <a href="/wiki/Hybrid_algorithm_(constraint_satisfaction)" title="Hybrid algorithm (constraint satisfaction)">hybrid algorithms</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Theoretical_aspects">Theoretical aspects</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=3" title="Edit section: Theoretical aspects"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Computational_Complexity">Computational Complexity</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=4" title="Edit section: Computational Complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>CSPs are also studied in <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, <a href="/wiki/Finite_model_theory" title="Finite model theory">finite model theory</a> and <a href="/wiki/Universal_algebra" title="Universal algebra">universal algebra</a>. It turned out that questions about the complexity of CSPs translate into important universal-algebraic questions about underlying algebras. This approach is known as the <i>algebraic approach</i> to CSPs.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p>Since every computational decision problem is <a href="/wiki/Polynomial-time_reduction" title="Polynomial-time reduction">polynomial-time equivalent</a> to a CSP with an infinite template,<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> general CSPs can have arbitrary complexity. In particular, there are also CSPs within the class of <a href="/wiki/NP-intermediate" title="NP-intermediate">NP-intermediate</a> problems, whose existence was demonstrated by <a href="/wiki/NP-intermediate" title="NP-intermediate">Ladner</a>, under the assumption that <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P ≠ NP</a>. </p><p>However, a large class of CSPs arising from natural applications satisfy a complexity dichotomy, meaning that every CSP within that class is either in <a href="/wiki/P_(complexity)" title="P (complexity)">P</a> or <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>. These CSPs thus provide one of the largest known subsets of <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a> which avoids <a href="/wiki/NP-intermediate" title="NP-intermediate">NP-intermediate</a> problems. A complexity dichotomy was first proven by <a href="/wiki/Schaefer%27s_dichotomy_theorem" title="Schaefer's dichotomy theorem">Schaefer</a> for Boolean CSPs, i.e. CSPs over a 2-element domain and where all the available relations are <a href="/wiki/Boolean_operator_(Boolean_algebra)" class="mw-redirect" title="Boolean operator (Boolean algebra)">Boolean operators</a>. This result has been generalized for various classes of CSPs, most notably for all CSPs over finite domains. This <i>finite-domain dichotomy conjecture</i> was first formulated by Tomás Feder and Moshe Vardi,<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> and finally proven independently by Andrei Bulatov<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> and Dmitriy Zhuk in 2017.<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p><p>Other classes for which a complexity dichotomy has been confirmed are </p> <ul><li>all <a href="/wiki/First-order_logic" title="First-order logic">first-order</a> <a href="/wiki/Reduct" title="Reduct">reducts</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Q} ,<)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Q</mi> </mrow> <mo>,</mo> <mo><</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Q} ,<)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43c487a052f5cefd2a85361e480e641af11aabb3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.46ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Q} ,<)}"></span>,<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup></li> <li>all first-order reducts of the <a href="/wiki/Rado_graph" title="Rado graph">countable random graph</a>,<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup></li> <li>all first-order reducts of the <a href="/wiki/Model_companion" class="mw-redirect" title="Model companion">model companion</a> of the class of all C-relations,<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup></li> <li>all first-order reducts of the universal homogenous <a href="/wiki/Partially_ordered_set" title="Partially ordered set">poset</a>,<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup></li> <li>all first-order reducts of homogenous undirected graphs,<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup></li> <li>all first-order reducts of all unary structures,<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup></li> <li>all CSPs in the complexity class MMSNP.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup></li></ul> <p>Most classes of CSPs that are known to be tractable are those where the <a href="/wiki/Hypergraph" title="Hypergraph">hypergraph</a> of constraints has bounded <a href="/wiki/Treewidth" title="Treewidth">treewidth</a>,<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> or where the constraints have arbitrary form but there exist equationally non-trivial polymorphisms of the set of constraint relations.<sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> </p><p>An <i>infinite-domain dichotomy conjecture</i><sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> has been formulated for all CSPs of reducts of finitely bounded homogenous structures, stating that the CSP of such a structure is in P if and only if its <a href="/wiki/Clone_(algebra)" title="Clone (algebra)">polymorphism clone</a> is equationally non-trivial, and NP-hard otherwise. </p><p>The complexity of such infinite-domain CSPs as well as of other generalisations (Valued CSPs, Quantified CSPs, Promise CSPs) is still an area of active research.<sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup><a rel="nofollow" class="external autonumber" href="https://tu-dresden.de/tu-dresden/newsportal/news/erc-synergy-grant-fuer-pococop-komplexitaet-von-berechnungen?set_language=en">[1]</a><a rel="nofollow" class="external autonumber" href="https://www.tuwien.at/tu-wien/aktuelles/news/erc-synergy-grant-die-komplexitaet-von-berechnungen">[2]</a> </p><p>Every CSP can also be considered as a <a href="/wiki/Conjunctive_query" title="Conjunctive query">conjunctive query</a> containment problem.<sup id="cite_ref-31" class="reference"><a href="#cite_note-31"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Function_problems">Function problems</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=5" title="Edit section: Function problems"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A similar situation exists between the functional classes <a href="/wiki/FP_(complexity)" title="FP (complexity)">FP</a> and <a href="/wiki/Sharp-P" class="mw-redirect" title="Sharp-P">#P</a>. By a generalization of <a href="/wiki/Ladner%27s_theorem" class="mw-redirect" title="Ladner's theorem">Ladner's theorem</a>, there are also problems in neither FP nor <a href="/wiki/Sharp-P-complete" class="mw-redirect" title="Sharp-P-complete">#P-complete</a> as long as FP ≠ #P. As in the decision case, a problem in the #CSP is defined by a set of relations. Each problem takes a <a href="/wiki/Boolean_logic" class="mw-redirect" title="Boolean logic">Boolean</a> formula as input and the task is to compute the number of satisfying assignments. This can be further generalized by using larger domain sizes and attaching a weight to each satisfying assignment and computing the sum of these weights. It is known that any complex weighted #CSP problem is either in FP or #P-hard.<sup id="cite_ref-32" class="reference"><a href="#cite_note-32"><span class="cite-bracket">[</span>32<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=6" title="Edit section: Variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The classic model of Constraint Satisfaction Problem defines a model of static, inflexible constraints. This rigid model is a shortcoming that makes it difficult to represent problems easily.<sup id="cite_ref-33" class="reference"><a href="#cite_note-33"><span class="cite-bracket">[</span>33<span class="cite-bracket">]</span></a></sup> Several modifications of the basic CSP definition have been proposed to adapt the model to a wide variety of problems. </p> <div class="mw-heading mw-heading3"><h3 id="Dynamic_CSPs">Dynamic CSPs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=7" title="Edit section: Dynamic CSPs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Dynamic CSPs</b><sup id="cite_ref-34" class="reference"><a href="#cite_note-34"><span class="cite-bracket">[</span>34<span class="cite-bracket">]</span></a></sup> (<i>DCSP</i>s) are useful when the original formulation of a problem is altered in some way, typically because the set of constraints to consider evolves because of the environment.<sup id="cite_ref-35" class="reference"><a href="#cite_note-35"><span class="cite-bracket">[</span>35<span class="cite-bracket">]</span></a></sup> DCSPs are viewed as a sequence of static CSPs, each one a transformation of the previous one in which variables and constraints can be added (restriction) or removed (relaxation). Information found in the initial formulations of the problem can be used to refine the next ones. The solving method can be classified according to the way in which information is transferred: </p> <ul><li><a href="/wiki/Oracle_machine" title="Oracle machine">Oracles</a>: the solution found to previous CSPs in the sequence are used as heuristics to guide the resolution of the current CSP from scratch.</li> <li>Local repair: each CSP is calculated starting from the partial solution of the previous one and repairing the inconsistent constraints with <a href="/wiki/Local_search_(optimization)" title="Local search (optimization)">local search</a>.</li> <li>Constraint recording: new constraints are defined in each stage of the search to represent the learning of inconsistent group of decisions. Those constraints are carried over to the new CSP problems.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Flexible_CSPs">Flexible CSPs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=8" title="Edit section: Flexible CSPs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Classic CSPs treat constraints as hard, meaning that they are <i>imperative</i> (each solution must satisfy all of them) and <i>inflexible</i> (in the sense that they must be completely satisfied or else they are completely violated). <b>Flexible CSP</b>s relax those assumptions, partially <i>relaxing</i> the constraints and allowing the solution to not comply with all of them. This is similar to preferences in <a href="/wiki/Preference-based_planning" title="Preference-based planning">preference-based planning</a>. Some types of flexible CSPs include: </p> <ul><li>MAX-CSP, where a number of constraints are allowed to be violated, and the quality of a solution is measured by the number of satisfied constraints.</li> <li><a href="/wiki/Weighted_constraint_satisfaction_problem" title="Weighted constraint satisfaction problem">Weighted CSP</a>, a MAX-CSP in which each violation of a constraint is weighted according to a predefined preference. Thus satisfying constraint with more weight is preferred.</li> <li>Fuzzy CSP model constraints as <a href="/wiki/Fuzzy_logic" title="Fuzzy logic">fuzzy</a> relations in which the satisfaction of a constraint is a continuous function of its variables' values, going from fully satisfied to fully violated.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Decentralized_CSPs">Decentralized CSPs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=9" title="Edit section: Decentralized CSPs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In DCSPs<sup id="cite_ref-cfl_36-0" class="reference"><a href="#cite_note-cfl-36"><span class="cite-bracket">[</span>36<span class="cite-bracket">]</span></a></sup> each constraint variable is thought of as having a separate geographic location. Strong constraints are placed on information exchange between variables, requiring the use of fully distributed algorithms to solve the constraint satisfaction problem. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=10" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Constraint_composite_graph" title="Constraint composite graph">Constraint composite graph</a></li> <li><a href="/wiki/Constraint_programming" title="Constraint programming">Constraint programming</a></li> <li><a href="/wiki/Declarative_programming" title="Declarative programming">Declarative programming</a></li> <li><a href="/wiki/Constrained_optimization" title="Constrained optimization">Constrained optimization</a> (COP)</li> <li><a href="/wiki/Distributed_constraint_optimization" title="Distributed constraint optimization">Distributed constraint optimization</a></li> <li><a href="/wiki/Graph_homomorphism" title="Graph homomorphism">Graph homomorphism</a></li> <li><a href="/wiki/Unique_games_conjecture" title="Unique games conjecture">Unique games conjecture</a></li> <li><a href="/wiki/Weighted_constraint_satisfaction_problem" title="Weighted constraint satisfaction problem">Weighted constraint satisfaction problem</a> (WCSP)</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=11" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFLecoutre2013" class="citation book cs1">Lecoutre, Christophe (2013). <i>Constraint Networks: Techniques and Algorithms</i>. Wiley. p. 26. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-118-61791-5" title="Special:BookSources/978-1-118-61791-5"><bdi>978-1-118-61791-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Constraint+Networks%3A+Techniques+and+Algorithms&rft.pages=26&rft.pub=Wiley&rft.date=2013&rft.isbn=978-1-118-61791-5&rft.aulast=Lecoutre&rft.aufirst=Christophe&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.springer.com/computer/ai/journal/10601">"Constraints – incl. option to publish open access"</a>. <i>springer.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-03</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=springer.com&rft.atitle=Constraints+%E2%80%93+incl.+option+to+publish+open+access&rft_id=http%3A%2F%2Fwww.springer.com%2Fcomputer%2Fai%2Fjournal%2F10601&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChandraGordonJeanninSchlesinger2016" class="citation book cs1">Chandra, Satish; Gordon, Colin S.; Jeannin, Jean-Baptiste; Schlesinger, Cole; Sridharan, Manu; Tip, Frank; Choi, Youngil (2016). <a rel="nofollow" class="external text" href="https://cs.drexel.edu/~csgordon/papers/oopsla16.pdf">"Type inference for static compilation of JavaScript"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications</i>. pp. 410–429. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2983990.2984017">10.1145/2983990.2984017</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-4444-9" title="Special:BookSources/978-1-4503-4444-9"><bdi>978-1-4503-4444-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Type+inference+for+static+compilation+of+JavaScript&rft.btitle=Proceedings+of+the+2016+ACM+SIGPLAN+International+Conference+on+Object-Oriented+Programming%2C+Systems%2C+Languages%2C+and+Applications&rft.pages=410-429&rft.date=2016&rft_id=info%3Adoi%2F10.1145%2F2983990.2984017&rft.isbn=978-1-4503-4444-9&rft.aulast=Chandra&rft.aufirst=Satish&rft.au=Gordon%2C+Colin+S.&rft.au=Jeannin%2C+Jean-Baptiste&rft.au=Schlesinger%2C+Cole&rft.au=Sridharan%2C+Manu&rft.au=Tip%2C+Frank&rft.au=Choi%2C+Youngil&rft_id=https%3A%2F%2Fcs.drexel.edu%2F~csgordon%2Fpapers%2Foopsla16.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Jim, Trevor, and Jens Palsberg. "<a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.886&rep=rep1&type=pdf">Type inference in systems of recursive types with subtyping</a>." Available on authors' web page (1999).</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFarhiAram_W_Harrow2016" class="citation arxiv cs1">Farhi, Edward; Aram W Harrow (2016). "Quantum Supremacy through the Quantum Approximate Optimization Algorithm". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.07674">1602.07674</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/quant-ph">quant-ph</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Quantum+Supremacy+through+the+Quantum+Approximate+Optimization+Algorithm&rft.date=2016&rft_id=info%3Aarxiv%2F1602.07674&rft.aulast=Farhi&rft.aufirst=Edward&rft.au=Aram+W+Harrow&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-GhallabNau2004-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-GhallabNau2004_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMalik_GhallabDana_NauPaolo_Traverso2004" class="citation book cs1">Malik Ghallab; Dana Nau; Paolo Traverso (21 May 2004). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=uYnpze57MSgC&q=%22constraint+satisfaction%22&pg=PP1"><i>Automated Planning: Theory and Practice</i></a>. Elsevier. pp. 1–. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-08-049051-9" title="Special:BookSources/978-0-08-049051-9"><bdi>978-0-08-049051-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Automated+Planning%3A+Theory+and+Practice&rft.pages=1-&rft.pub=Elsevier&rft.date=2004-05-21&rft.isbn=978-0-08-049051-9&rft.au=Malik+Ghallab&rft.au=Dana+Nau&rft.au=Paolo+Traverso&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DuYnpze57MSgC%26q%3D%2522constraint%2Bsatisfaction%2522%26pg%3DPP1&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt">Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning</a>, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt">Archived</a> 2009-02-06 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> Ian Miguel – slides.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Demetriou, George C. "<a rel="nofollow" class="external text" href="http://www.aclweb.org/anthology/E93-1051">Lexical disambiguation using constraint handling in Prolog (CHIP)</a>." Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics, 1993.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">MacDonald, Maryellen C., and Mark S. Seidenberg. "<a rel="nofollow" class="external text" href="https://web.archive.org/web/20180325105726/https://pdfs.semanticscholar.org/a73e/53c44f1e998c5a03b9cbac9e0e16d5b09e77.pdf">Constraint satisfaction accounts of lexical and sentence comprehension</a>." Handbook of Psycholinguistics (Second Edition). 2006. 581–611.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "<a rel="nofollow" class="external text" href="http://www.jatit.org/volumes/Vol86No2/17Vol86No2.pdf">GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES</a>." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327–331.</span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><i>Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules</i>, Dong Yang & Ming Dong, <a href="/w/index.php?title=Journal_of_Intelligent_Manufacturing&action=edit&redlink=1" class="new" title="Journal of Intelligent Manufacturing (page does not exist)">Journal of Intelligent Manufacturing</a> volume 24, pages99–111 (2013)</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">Modi, Pragnesh Jay, et al. "<a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8697&rep=rep1&type=pdf">A dynamic distributed constraint satisfaction approach to resource allocation</a>." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2001.</span> </li> <li id="cite_note-Russell2010-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-Russell2010_13-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStuart_Jonathan_RussellPeter_Norvig2010" class="citation book cs1">Stuart Jonathan Russell; Peter Norvig (2010). <i>Artificial Intelligence: A Modern Approach</i>. Prentice Hall. p. Chapter 6. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780136042594" title="Special:BookSources/9780136042594"><bdi>9780136042594</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Artificial+Intelligence%3A+A+Modern+Approach&rft.pages=Chapter+6&rft.pub=Prentice+Hall&rft.date=2010&rft.isbn=9780136042594&rft.au=Stuart+Jonathan+Russell&rft.au=Peter+Norvig&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMilano,_MichelaVan_Hentenryck,_Pascal2011" class="citation conference cs1"><a href="/wiki/Michela_Milano" title="Michela Milano">Milano, Michela</a>; Van Hentenryck, Pascal, eds. (2011). <i>Hybrid optimization : the ten years of CPAIOR</i>. International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems. New York: Springer. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781441916440" title="Special:BookSources/9781441916440"><bdi>9781441916440</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/695387020">695387020</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Hybrid+optimization+%3A+the+ten+years+of+CPAIOR&rft.place=New+York&rft.pub=Springer&rft.date=2011&rft_id=info%3Aoclcnum%2F695387020&rft.isbn=9781441916440&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBartoBradyBulatovKozik2024" class="citation journal cs1">Barto, Libor; Brady, Zarathustra; Bulatov, Andrei; Kozik, Marcin; Zhuk, Dmitriy (2024-05-15). "Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras". <i>TheoretiCS</i>. <b>3</b>: 11361. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2104.11808">2104.11808</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.46298%2Ftheoretics.24.14">10.46298/theoretics.24.14</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2751-4838">2751-4838</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=TheoretiCS&rft.atitle=Unifying+the+Three+Algebraic+Approaches+to+the+CSP+via+Minimal+Taylor+Algebras&rft.volume=3&rft.pages=11361&rft.date=2024-05-15&rft_id=info%3Aarxiv%2F2104.11808&rft.issn=2751-4838&rft_id=info%3Adoi%2F10.46298%2Ftheoretics.24.14&rft.aulast=Barto&rft.aufirst=Libor&rft.au=Brady%2C+Zarathustra&rft.au=Bulatov%2C+Andrei&rft.au=Kozik%2C+Marcin&rft.au=Zhuk%2C+Dmitriy&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyGrohe2008" class="citation book cs1">Bodirsky, Manuel; Grohe, Martin (2008). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-540-70583-3_16">"Non-dichotomies in Constraint Satisfaction Complexity"</a>. In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). <i>Automata, Languages and Programming</i>. Lecture Notes in Computer Science. Vol. 5126. Berlin, Heidelberg: Springer. pp. 184–196. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-70583-3_16">10.1007/978-3-540-70583-3_16</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-70583-3" title="Special:BookSources/978-3-540-70583-3"><bdi>978-3-540-70583-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Non-dichotomies+in+Constraint+Satisfaction+Complexity&rft.btitle=Automata%2C+Languages+and+Programming&rft.place=Berlin%2C+Heidelberg&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=184-196&rft.pub=Springer&rft.date=2008&rft_id=info%3Adoi%2F10.1007%2F978-3-540-70583-3_16&rft.isbn=978-3-540-70583-3&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Grohe%2C+Martin&rft_id=https%3A%2F%2Flink.springer.com%2Fchapter%2F10.1007%2F978-3-540-70583-3_16&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFederVardi1998" class="citation journal cs1">Feder, Tomás; <a href="/wiki/Moshe_Vardi" title="Moshe Vardi">Vardi, Moshe Y.</a> (1998). <a rel="nofollow" class="external text" href="http://epubs.siam.org/doi/10.1137/S0097539794266766">"The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory"</a>. <i>SIAM Journal on Computing</i>. <b>28</b> (1): 57–104. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539794266766">10.1137/S0097539794266766</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=The+Computational+Structure+of+Monotone+Monadic+SNP+and+Constraint+Satisfaction%3A+A+Study+through+Datalog+and+Group+Theory&rft.volume=28&rft.issue=1&rft.pages=57-104&rft.date=1998&rft_id=info%3Adoi%2F10.1137%2FS0097539794266766&rft.issn=0097-5397&rft.aulast=Feder&rft.aufirst=Tom%C3%A1s&rft.au=Vardi%2C+Moshe+Y.&rft_id=http%3A%2F%2Fepubs.siam.org%2Fdoi%2F10.1137%2FS0097539794266766&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBulatov2017" class="citation book cs1">Bulatov, Andrei (2017). "A Dichotomy Theorem for Nonuniform CSPs". <i>Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017</i>. IEEE Computer Society. pp. 319–330. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1703.03021">1703.03021</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2017.37">10.1109/FOCS.2017.37</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-5386-3464-6" title="Special:BookSources/978-1-5386-3464-6"><bdi>978-1-5386-3464-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=A+Dichotomy+Theorem+for+Nonuniform+CSPs&rft.btitle=Proceedings+of+the+58th+IEEE+Annual+Symposium+on+Foundations+of+Computer+Science%2C+FOCS+2017&rft.pages=319-330&rft.pub=IEEE+Computer+Society&rft.date=2017&rft_id=info%3Aarxiv%2F1703.03021&rft_id=info%3Adoi%2F10.1109%2FFOCS.2017.37&rft.isbn=978-1-5386-3464-6&rft.aulast=Bulatov&rft.aufirst=Andrei&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFZhuk2020" class="citation journal cs1">Zhuk, Dmitriy (2020). "A Proof of the CSP Dichotomy Conjecture". <i>Journal of the ACM</i>. <b>67</b> (5): 1–78. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1704.01914">1704.01914</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3402029">10.1145/3402029</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=A+Proof+of+the+CSP+Dichotomy+Conjecture&rft.volume=67&rft.issue=5&rft.pages=1-78&rft.date=2020&rft_id=info%3Aarxiv%2F1704.01914&rft_id=info%3Adoi%2F10.1145%2F3402029&rft.aulast=Zhuk&rft.aufirst=Dmitriy&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyKára2010" class="citation journal cs1">Bodirsky, Manuel; Kára, Jan (2010-02-08). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/1667053.1667058">"The complexity of temporal constraint satisfaction problems"</a>. <i>J. ACM</i>. <b>57</b> (2): 9:1–9:41. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1667053.1667058">10.1145/1667053.1667058</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+ACM&rft.atitle=The+complexity+of+temporal+constraint+satisfaction+problems&rft.volume=57&rft.issue=2&rft.pages=9%3A1-9%3A41&rft.date=2010-02-08&rft_id=info%3Adoi%2F10.1145%2F1667053.1667058&rft.issn=0004-5411&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=K%C3%A1ra%2C+Jan&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F1667053.1667058&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyPinsker2011" class="citation book cs1">Bodirsky, Manuel; Pinsker, Michael (2011). "Schaefer's theorem for graphs". <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing"><i>Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)</i></a>. <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>. pp. 655–664. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1011.2894">1011.2894</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1993636.1993724">10.1145/1993636.1993724</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-0691-1" title="Special:BookSources/978-1-4503-0691-1"><bdi>978-1-4503-0691-1</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:47097319">47097319</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Schaefer%27s+theorem+for+graphs&rft.btitle=Proceedings+of+the+43rd+Annual+Symposium+on+Theory+of+Computing+%28STOC+%2711%29&rft.pages=655-664&rft.pub=Association+for+Computing+Machinery&rft.date=2011&rft_id=info%3Aarxiv%2F1011.2894&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A47097319%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F1993636.1993724&rft.isbn=978-1-4503-0691-1&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Pinsker%2C+Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyJonssonPham2017" class="citation journal cs1">Bodirsky, Manuel; Jonsson, Peter; Pham, Trung Van (2017-08-02). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3105907">"The Complexity of Phylogeny Constraint Satisfaction Problems"</a>. <i>ACM Trans. Comput. Logic</i>. <b>18</b> (3): 23:1–23:42. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1503.07310">1503.07310</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3105907">10.1145/3105907</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1529-3785">1529-3785</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Trans.+Comput.+Logic&rft.atitle=The+Complexity+of+Phylogeny+Constraint+Satisfaction+Problems&rft.volume=18&rft.issue=3&rft.pages=23%3A1-23%3A42&rft.date=2017-08-02&rft_id=info%3Aarxiv%2F1503.07310&rft.issn=1529-3785&rft_id=info%3Adoi%2F10.1145%2F3105907&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Jonsson%2C+Peter&rft.au=Pham%2C+Trung+Van&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F3105907&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKompatscherPham2017" class="citation book cs1">Kompatscher, Michael; Pham, Trung Van (2017). "A Complexity Dichotomy for Poset Constraint Satisfaction". <i>34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)</i>. Leibniz International Proceedings in Informatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 47:1–47:12. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.STACS.2017.47">10.4230/LIPIcs.STACS.2017.47</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=A+Complexity+Dichotomy+for+Poset+Constraint+Satisfaction&rft.btitle=34th+Symposium+on+Theoretical+Aspects+of+Computer+Science+%28STACS+2017%29&rft.series=Leibniz+International+Proceedings+in+Informatics&rft.pages=47%3A1-47%3A12&rft.pub=Schloss+Dagstuhl+%E2%80%93+Leibniz-Zentrum+f%C3%BCr+Informatik&rft.date=2017&rft_id=info%3Adoi%2F10.4230%2FLIPIcs.STACS.2017.47&rft.aulast=Kompatscher&rft.aufirst=Michael&rft.au=Pham%2C+Trung+Van&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyMartinPinskerPongrácz2019" class="citation journal cs1">Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongrácz, András (January 2019). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/16M1082974">"Constraint Satisfaction Problems for Reducts of Homogeneous Graphs"</a>. <i>SIAM Journal on Computing</i>. <b>48</b> (4): 1224–1264. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.05819">1602.05819</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F16M1082974">10.1137/16M1082974</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Constraint+Satisfaction+Problems+for+Reducts+of+Homogeneous+Graphs&rft.volume=48&rft.issue=4&rft.pages=1224-1264&rft.date=2019-01&rft_id=info%3Aarxiv%2F1602.05819&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F16M1082974&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Martin%2C+Barnaby&rft.au=Pinsker%2C+Michael&rft.au=Pongr%C3%A1cz%2C+Andr%C3%A1s&rft_id=https%3A%2F%2Fepubs.siam.org%2Fdoi%2F10.1137%2F16M1082974&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyMottet2018" class="citation cs2">Bodirsky, Manuel; Mottet, Antoine (2018-05-20), "A Dichotomy for First-Order Reducts of Unary Structures", <i>Logical Methods in Computer Science</i>, <b>14</b> (2), <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1601.04520">1601.04520</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.23638%2FLMCS-14%282%3A13%292018">10.23638/LMCS-14(2:13)2018</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Logical+Methods+in+Computer+Science&rft.atitle=A+Dichotomy+for+First-Order+Reducts+of+Unary+Structures&rft.volume=14&rft.issue=2&rft.date=2018-05-20&rft_id=info%3Aarxiv%2F1601.04520&rft_id=info%3Adoi%2F10.23638%2FLMCS-14%282%3A13%292018&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Mottet%2C+Antoine&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyMadelaineMottet2018" class="citation book cs1">Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine (2018-07-09). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3209108.3209156">"A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP"</a>. <i>Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science</i>. LICS '18. New York, NY, USA: Association for Computing Machinery. pp. 105–114. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1802.03255">1802.03255</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3209108.3209156">10.1145/3209108.3209156</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-5583-4" title="Special:BookSources/978-1-4503-5583-4"><bdi>978-1-4503-5583-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=A+universal-algebraic+proof+of+the+complexity+dichotomy+for+Monotone+Monadic+SNP&rft.btitle=Proceedings+of+the+33rd+Annual+ACM%2FIEEE+Symposium+on+Logic+in+Computer+Science&rft.place=New+York%2C+NY%2C+USA&rft.series=LICS+%2718&rft.pages=105-114&rft.pub=Association+for+Computing+Machinery&rft.date=2018-07-09&rft_id=info%3Aarxiv%2F1802.03255&rft_id=info%3Adoi%2F10.1145%2F3209108.3209156&rft.isbn=978-1-4503-5583-4&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Madelaine%2C+Florent&rft.au=Mottet%2C+Antoine&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F3209108.3209156&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBartoKozik2014" class="citation journal cs1">Barto, Libor; Kozik, Marcin (2014-01-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/2556646">"Constraint Satisfaction Problems Solvable by Local Consistency Methods"</a>. <i>J. ACM</i>. <b>61</b> (1): 3:1–3:19. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2556646">10.1145/2556646</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+ACM&rft.atitle=Constraint+Satisfaction+Problems+Solvable+by+Local+Consistency+Methods&rft.volume=61&rft.issue=1&rft.pages=3%3A1-3%3A19&rft.date=2014-01-01&rft_id=info%3Adoi%2F10.1145%2F2556646&rft.issn=0004-5411&rft.aulast=Barto&rft.aufirst=Libor&rft.au=Kozik%2C+Marcin&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F2556646&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirsky2021" class="citation book cs1">Bodirsky, Manuel (2021). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/complexity-of-infinitedomain-constraint-satisfaction/8E6E86C8F8C5C534440266EFB9E584D3"><i>Complexity of Infinite-Domain Constraint Satisfaction</i></a>. Lecture Notes in Logic. Cambridge: Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-107-04284-1" title="Special:BookSources/978-1-107-04284-1"><bdi>978-1-107-04284-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Complexity+of+Infinite-Domain+Constraint+Satisfaction&rft.place=Cambridge&rft.series=Lecture+Notes+in+Logic&rft.pub=Cambridge+University+Press&rft.date=2021&rft.isbn=978-1-107-04284-1&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft_id=https%3A%2F%2Fwww.cambridge.org%2Fcore%2Fbooks%2Fcomplexity-of-infinitedomain-constraint-satisfaction%2F8E6E86C8F8C5C534440266EFB9E584D3&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBodirskyPinskerPongrácz2021" class="citation journal cs1">Bodirsky, Manuel; Pinsker, Michael; Pongrácz, András (March 2021). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/projective-clone-homomorphisms/3654D0B62D3C45DF6DBD93DDC57B8B02">"Projective Clone Homomorphisms"</a>. <i>The Journal of Symbolic Logic</i>. <b>86</b> (1): 148–161. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1409.4601">1409.4601</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2Fjsl.2019.23">10.1017/jsl.2019.23</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-4812">0022-4812</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Journal+of+Symbolic+Logic&rft.atitle=Projective+Clone+Homomorphisms&rft.volume=86&rft.issue=1&rft.pages=148-161&rft.date=2021-03&rft_id=info%3Aarxiv%2F1409.4601&rft.issn=0022-4812&rft_id=info%3Adoi%2F10.1017%2Fjsl.2019.23&rft.aulast=Bodirsky&rft.aufirst=Manuel&rft.au=Pinsker%2C+Michael&rft.au=Pongr%C3%A1cz%2C+Andr%C3%A1s&rft_id=https%3A%2F%2Fwww.cambridge.org%2Fcore%2Fjournals%2Fjournal-of-symbolic-logic%2Farticle%2Fabs%2Fprojective-clone-homomorphisms%2F3654D0B62D3C45DF6DBD93DDC57B8B02&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPinsker2022" class="citation arxiv cs1">Pinsker, Michael (2022-03-31). "Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2203.17182">2203.17182</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.LO">cs.LO</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Current+Challenges+in+Infinite-Domain+Constraint+Satisfaction%3A+Dilemmas+of+the+Infinite+Sheep&rft.date=2022-03-31&rft_id=info%3Aarxiv%2F2203.17182&rft.aulast=Pinsker&rft.aufirst=Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-31">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKolaitisVardi2000" class="citation journal cs1">Kolaitis, Phokion G.; <a href="/wiki/Moshe_Y._Vardi" class="mw-redirect" title="Moshe Y. Vardi">Vardi, Moshe Y.</a> (2000). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2000.1713">"Conjunctive-Query Containment and Constraint Satisfaction"</a>. <i><a href="/wiki/Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>. <b>61</b> (2): 302–332. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.2000.1713">10.1006/jcss.2000.1713</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Conjunctive-Query+Containment+and+Constraint+Satisfaction&rft.volume=61&rft.issue=2&rft.pages=302-332&rft.date=2000&rft_id=info%3Adoi%2F10.1006%2Fjcss.2000.1713&rft.aulast=Kolaitis&rft.aufirst=Phokion+G.&rft.au=Vardi%2C+Moshe+Y.&rft_id=https%3A%2F%2Fdoi.org%2F10.1006%252Fjcss.2000.1713&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-32"><span class="mw-cite-backlink"><b><a href="#cite_ref-32">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCaiChen2012" class="citation conference cs1">Cai, Jin-Yi; Chen, Xi (2012). "Complexity of counting CSP with complex weights". <i><a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12)</a></i>. pp. 909–920. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1111.2384">1111.2384</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2213977.2214059">10.1145/2213977.2214059</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-1245-5" title="Special:BookSources/978-1-4503-1245-5"><bdi>978-1-4503-1245-5</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:53245129">53245129</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Complexity+of+counting+CSP+with+complex+weights&rft.btitle=Proceedings+of+the+Forty-Fourth+Annual+ACM+Symposium+on+Theory+of+Computing+%28STOC+%2712%29&rft.pages=909-920&rft.date=2012&rft_id=info%3Aarxiv%2F1111.2384&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A53245129%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F2213977.2214059&rft.isbn=978-1-4503-1245-5&rft.aulast=Cai&rft.aufirst=Jin-Yi&rft.au=Chen%2C+Xi&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-33"><span class="mw-cite-backlink"><b><a href="#cite_ref-33">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMiguel2001" class="citation thesis cs1">Miguel, Ian (July 2001). <i>Dynamic Flexible Constraint Satisfaction and its Application to AI Planning</i> (Ph.D. thesis). <a href="/wiki/University_of_Edinburgh_School_of_Informatics" class="mw-redirect" title="University of Edinburgh School of Informatics">University of Edinburgh School of Informatics</a>. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.6733">10.1.1.9.6733</a></span>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1842%2F326">1842/326</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Dynamic+Flexible+Constraint+Satisfaction+and+its+Application+to+AI+Planning&rft.degree=Ph.D.&rft.inst=University+of+Edinburgh+School+of+Informatics&rft.date=2001-07&rft_id=info%3Ahdl%2F1842%2F326&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.9.6733%23id-name%3DCiteSeerX&rft.aulast=Miguel&rft.aufirst=Ian&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> <li id="cite_note-34"><span class="mw-cite-backlink"><b><a href="#cite_ref-34">^</a></b></span> <span class="reference-text">Dechter, R. and Dechter, A., <a rel="nofollow" class="external text" href="http://www.ics.uci.edu/%7Ecsp/r5.pdf">Belief Maintenance in Dynamic Constraint Networks</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20121117042241/http://www.ics.uci.edu/%7Ecsp/r5.pdf">Archived</a> 2012-11-17 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> In Proc. of AAAI-88, 37–42.</span> </li> <li id="cite_note-35"><span class="mw-cite-backlink"><b><a href="#cite_ref-35">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf">Solution reuse in dynamic constraint satisfaction problems</a>, Thomas Schiex</span> </li> <li id="cite_note-cfl-36"><span class="mw-cite-backlink"><b><a href="#cite_ref-cfl_36-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDuffyLeith2013" class="citation cs2">Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", <i>IEEE/ACM Transactions on Networking, 21(4)</i>, vol. 21, pp. 1298–1308, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1103.3240">1103.3240</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTNET.2012.2222923">10.1109/TNET.2012.2222923</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11504393">11504393</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Decentralized+Constraint+Satisfaction&rft.btitle=IEEE%2FACM+Transactions+on+Networking%2C+21%284%29&rft.pages=1298-1308&rft.date=2013-08&rft_id=info%3Aarxiv%2F1103.3240&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11504393%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FTNET.2012.2222923&rft.aulast=Duffy&rft.aufirst=K.R.&rft.au=Leith%2C+D.J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Constraint_satisfaction_problem&action=edit&section=12" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=wrs6Lvo5LZM">A quick introduction to constraint satisfaction on YouTube</a></li> <li>Manuel Bodirsky (2021). <i>Complexity of Infinite-Domain Constraint Satisfaction</i>. Cambridge University Press. <a rel="nofollow" class="external free" href="https://doi.org/10.1017/9781107337534">https://doi.org/10.1017/9781107337534</a></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSteven_MintonAndy_PhilipsMark_D._JohnstonPhilip_Laird1993" class="citation journal cs1">Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems". <i>Journal of Artificial Intelligence Research</i>. <b>58</b> (1–3): 161–205. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.6637">10.1.1.308.6637</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0004-3702%2892%2990007-k">10.1016/0004-3702(92)90007-k</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14830518">14830518</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Artificial+Intelligence+Research&rft.atitle=Minimizing+Conflicts%3A+A+Heuristic+Repair+Method+for+Constraint-Satisfaction+and+Scheduling+Problems&rft.volume=58&rft.issue=1%E2%80%933&rft.pages=161-205&rft.date=1993&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.308.6637%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A14830518%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2F0004-3702%2892%2990007-k&rft.au=Steven+Minton&rft.au=Andy+Philips&rft.au=Mark+D.+Johnston&rft.au=Philip+Laird&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTsang1993" class="citation book cs1">Tsang, Edward (1993). <a rel="nofollow" class="external text" href="http://www.bracil.net/edward/FCS.html"><i>Foundations of Constraint Satisfaction</i></a>. Academic Press.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Foundations+of+Constraint+Satisfaction&rft.pub=Academic+Press&rft.date=1993&rft.aulast=Tsang&rft.aufirst=Edward&rft_id=http%3A%2F%2Fwww.bracil.net%2Fedward%2FFCS.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-12-701610-4" title="Special:BookSources/0-12-701610-4">0-12-701610-4</a></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChen2009" class="citation journal cs1">Chen, Hubie (December 2009). "A Rendezvous of Logic, Complexity, and Algebra". <i>ACM Computing Surveys</i>. <b>42</b> (1): 1–32. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0611018">cs/0611018</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1592451.1592453">10.1145/1592451.1592453</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11975818">11975818</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Computing+Surveys&rft.atitle=A+Rendezvous+of+Logic%2C+Complexity%2C+and+Algebra&rft.volume=42&rft.issue=1&rft.pages=1-32&rft.date=2009-12&rft_id=info%3Aarxiv%2Fcs%2F0611018&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11975818%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F1592451.1592453&rft.aulast=Chen&rft.aufirst=Hubie&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDechter2003" class="citation book cs1">Dechter, Rina (2003). <a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~dechter/books/index.html"><i>Constraint processing</i></a>. Morgan Kaufmann.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Constraint+processing&rft.pub=Morgan+Kaufmann&rft.date=2003&rft.aulast=Dechter&rft.aufirst=Rina&rft_id=http%3A%2F%2Fwww.ics.uci.edu%2F~dechter%2Fbooks%2Findex.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/1-55860-890-7" title="Special:BookSources/1-55860-890-7">1-55860-890-7</a></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFApt2003" class="citation book cs1"><a href="/wiki/Krzysztof_R._Apt" title="Krzysztof R. Apt">Apt, Krzysztof</a> (2003). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/principlesofcons0000aptk"><i>Principles of constraint programming</i></a></span>. Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521825832" title="Special:BookSources/9780521825832"><bdi>9780521825832</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Principles+of+constraint+programming&rft.pub=Cambridge+University+Press&rft.date=2003&rft.isbn=9780521825832&rft.aulast=Apt&rft.aufirst=Krzysztof&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fprinciplesofcons0000aptk&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-82583-0" title="Special:BookSources/0-521-82583-0">0-521-82583-0</a></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLecoutre2009" class="citation book cs1">Lecoutre, Christophe (2009). <a rel="nofollow" class="external text" href="http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250"><i>Constraint Networks: Techniques and Algorithms</i></a>. ISTE/Wiley.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Constraint+Networks%3A+Techniques+and+Algorithms&rft.pub=ISTE%2FWiley&rft.date=2009&rft.aulast=Lecoutre&rft.aufirst=Christophe&rft_id=http%3A%2F%2Fwww.iste.co.uk%2Findex.php%3Ff%3Da%26ACTION%3DView%26id%3D250&rfr_id=info%3Asid%2Fen.wikipedia.org%3AConstraint+satisfaction+problem" class="Z3988"></span> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-84821-106-3" title="Special:BookSources/978-1-84821-106-3">978-1-84821-106-3</a></li> <li>Tomás Feder, <a rel="nofollow" class="external text" href="http://theory.stanford.edu/~tomas/consmod.pdf"><i>Constraint satisfaction: a personal perspective</i></a>, manuscript.</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060213071549/http://4c.ucc.ie/web/archive/index.jsp">Constraints archive</a></li> <li><a rel="nofollow" class="external text" href="http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm">Forced Satisfiable CSP Benchmarks of Model RB</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210125071920/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm">Archived</a> 2021-01-25 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060813201559/http://www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html">Benchmarks – XML representation of CSP instances</a></li> <li><a rel="nofollow" class="external text" href="http://xcsp.org">XCSP3 – An XML-based format designed to represent CSP instances</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20090419182234/http://www.ps.uni-sb.de/Papers/abstracts/tackDiss.html">Constraint Propagation</a> – Dissertation by Guido Tack giving a good survey of theory and implementation issues</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Industrial_and_applied_mathematics" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Industrial_and_applied_mathematics" title="Template:Industrial and applied mathematics"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Industrial_and_applied_mathematics" title="Template talk:Industrial and applied mathematics"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Industrial_and_applied_mathematics" title="Special:EditPage/Template:Industrial and applied mathematics"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Industrial_and_applied_mathematics" style="font-size:114%;margin:0 4em"><a href="/wiki/Applied_mathematics" title="Applied mathematics">Industrial and applied mathematics</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computational_mathematics" title="Computational mathematics">Computational</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Algorithm" title="Algorithm">Algorithms</a> <ul><li><a href="/wiki/Algorithm_design" class="mw-redirect" title="Algorithm design">design</a></li> <li><a href="/wiki/Analysis_of_algorithms" title="Analysis of algorithms">analysis</a></li></ul></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata theory</a></li> <li><a href="/wiki/Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li> <li><a href="/wiki/Coding_theory" title="Coding theory">Coding theory</a></li> <li><a href="/wiki/Computational_geometry" title="Computational geometry">Computational geometry</a></li> <li><a class="mw-selflink selflink">Constraint satisfaction</a> <ul><li><a href="/wiki/Constraint_programming" title="Constraint programming">Constraint programming</a></li></ul></li> <li><a href="/wiki/Logic_in_computer_science" title="Logic in computer science">Computational logic</a></li> <li><a href="/wiki/Cryptography" title="Cryptography">Cryptography</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a></li> <li><a href="/wiki/Computational_statistics" title="Computational statistics">Statistics</a></li></ul> </div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Mathematical_software" scope="row" class="navbox-group" style="width:1%;font-weight:normal;"><a href="/wiki/Mathematical_software" title="Mathematical software">Mathematical software</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/List_of_arbitrary-precision_arithmetic_software" title="List of arbitrary-precision arithmetic software">Arbitrary-precision arithmetic</a></li> <li><a href="/wiki/List_of_finite_element_software_packages" title="List of finite element software packages">Finite element analysis</a></li> <li><a href="/wiki/Tensor_software" title="Tensor software">Tensor software</a></li> <li><a href="/wiki/List_of_interactive_geometry_software" title="List of interactive geometry software">Interactive geometry software</a></li> <li><a href="/wiki/List_of_optimization_software" title="List of optimization software">Optimization software</a></li> <li><a href="/wiki/List_of_statistical_software" title="List of statistical software">Statistical software</a></li> <li><a href="/wiki/List_of_numerical-analysis_software" title="List of numerical-analysis software">Numerical-analysis software</a></li> <li><a href="/wiki/List_of_numerical-analysis_software" title="List of numerical-analysis software">Numerical libraries</a></li> <li><a href="/wiki/Solver" title="Solver">Solvers</a></li></ul> </div></td></tr></tbody></table><div> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Discrete_mathematics" title="Discrete mathematics">Discrete</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Computer_algebra" title="Computer algebra">Computer algebra</a></li> <li><a href="/wiki/Computational_number_theory" title="Computational number theory">Computational number theory</a></li> <li><a href="/wiki/Combinatorics" title="Combinatorics">Combinatorics</a></li> <li><a href="/wiki/Graph_theory" title="Graph theory">Graph theory</a></li> <li><a href="/wiki/Discrete_geometry" title="Discrete geometry">Discrete geometry</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Mathematical_analysis" title="Mathematical analysis">Analysis</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Approximation_theory" title="Approximation theory">Approximation theory</a></li> <li><a href="/wiki/Clifford_analysis" title="Clifford analysis">Clifford analysis</a> <ul><li><a href="/wiki/Clifford_algebra" title="Clifford algebra">Clifford algebra</a></li></ul></li> <li><a href="/wiki/Differential_equation" title="Differential equation">Differential equations</a> <ul><li><a href="/wiki/Ordinary_differential_equation" title="Ordinary differential equation">Ordinary differential equations</a></li> <li><a href="/wiki/Partial_differential_equation" title="Partial differential equation">Partial differential equations</a></li> <li><a href="/wiki/Stochastic_differential_equation" title="Stochastic differential equation">Stochastic differential equations</a></li></ul></li> <li><a href="/wiki/Differential_geometry" title="Differential geometry">Differential geometry</a> <ul><li><a href="/wiki/Differential_form" title="Differential form">Differential forms</a></li> <li><a href="/wiki/Gauge_theory_(mathematics)" title="Gauge theory (mathematics)">Gauge theory</a></li> <li><a href="/wiki/Geometric_analysis" title="Geometric analysis">Geometric analysis</a></li></ul></li> <li><a href="/wiki/Dynamical_system" title="Dynamical system">Dynamical systems</a> <ul><li><a href="/wiki/Chaos_theory" title="Chaos theory">Chaos theory</a></li> <li><a href="/wiki/Control_theory" title="Control theory">Control theory</a></li></ul></li> <li><a href="/wiki/Functional_analysis" title="Functional analysis">Functional analysis</a> <ul><li><a href="/wiki/Operator_algebra" title="Operator algebra">Operator algebra</a></li> <li><a href="/wiki/Operator_theory" title="Operator theory">Operator theory</a></li></ul></li> <li><a href="/wiki/Harmonic_analysis_(mathematics)" class="mw-redirect" title="Harmonic analysis (mathematics)">Harmonic analysis</a> <ul><li><a href="/wiki/Fourier_analysis" title="Fourier analysis">Fourier analysis</a></li></ul></li> <li><a href="/wiki/Multilinear_algebra" title="Multilinear algebra">Multilinear algebra</a> <ul><li><a href="/wiki/Exterior_algebra" title="Exterior algebra">Exterior</a></li> <li><a href="/wiki/Geometric_algebra" title="Geometric algebra">Geometric</a></li> <li><a href="/wiki/Tensor" title="Tensor">Tensor</a></li> <li><a href="/wiki/Vector_calculus#Vector_algebra" title="Vector calculus">Vector</a></li></ul></li> <li><a href="/wiki/Multivariable_calculus" title="Multivariable calculus">Multivariable calculus</a> <ul><li><a href="/wiki/Exterior_calculus" class="mw-redirect" title="Exterior calculus">Exterior</a></li> <li><a href="/wiki/Geometric_calculus" title="Geometric calculus">Geometric</a></li> <li><a href="/wiki/Tensor_calculus" class="mw-redirect" title="Tensor calculus">Tensor</a></li> <li><a href="/wiki/Vector_calculus" title="Vector calculus">Vector</a></li></ul></li> <li><a href="/wiki/Numerical_analysis" title="Numerical analysis">Numerical analysis</a> <ul><li><a href="/wiki/Numerical_linear_algebra" title="Numerical linear algebra">Numerical linear algebra</a></li> <li><a href="/wiki/Numerical_methods_for_ordinary_differential_equations" title="Numerical methods for ordinary differential equations">Numerical methods for ordinary differential equations</a></li> <li><a href="/wiki/Numerical_methods_for_partial_differential_equations" title="Numerical methods for partial differential equations">Numerical methods for partial differential equations</a></li> <li><a href="/wiki/Validated_numerics" title="Validated numerics">Validated numerics</a></li></ul></li> <li><a href="/wiki/Calculus_of_variations" title="Calculus of variations">Variational calculus</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Probability_theory" title="Probability theory">Probability theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Probability_distribution" title="Probability distribution">Distributions</a> (<a href="/wiki/Random_variable" title="Random variable">random variables</a>)</li> <li><a href="/wiki/Stochastic_process" title="Stochastic process">Stochastic processes</a> / <a href="/wiki/Stochastic_calculus" title="Stochastic calculus">analysis</a></li> <li><a href="/wiki/Functional_integration" title="Functional integration">Path integral</a></li> <li><a href="/wiki/Malliavin_calculus" title="Malliavin calculus">Stochastic variational calculus</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Mathematical_physics" title="Mathematical physics">Mathematical<br />physics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Analytical_mechanics" title="Analytical mechanics">Analytical mechanics</a> <ul><li><a href="/wiki/Lagrangian_mechanics" title="Lagrangian mechanics">Lagrangian</a></li> <li><a href="/wiki/Hamiltonian_mechanics" title="Hamiltonian mechanics">Hamiltonian</a></li></ul></li> <li><a href="/wiki/Field_theory_(physics)" class="mw-redirect" title="Field theory (physics)">Field theory</a> <ul><li><a href="/wiki/Classical_field_theory" title="Classical field theory">Classical</a></li> <li><a href="/wiki/Conformal_field_theory" title="Conformal field theory">Conformal</a></li> <li><a href="/wiki/Effective_field_theory" title="Effective field theory">Effective</a></li> <li><a href="/wiki/Gauge_theory" title="Gauge theory">Gauge</a></li> <li><a href="/wiki/Quantum_field_theory" title="Quantum field theory">Quantum</a></li> <li><a href="/wiki/Statistical_field_theory" title="Statistical field theory">Statistical</a></li> <li><a href="/wiki/Topological_field_theory" class="mw-redirect" title="Topological field theory">Topological</a></li></ul></li> <li><a href="/wiki/Perturbation_theory" title="Perturbation theory">Perturbation theory</a> <ul><li><a href="/wiki/Perturbation_theory_(quantum_mechanics)" title="Perturbation theory (quantum mechanics)">in quantum mechanics</a></li></ul></li> <li><a href="/wiki/Potential_theory" title="Potential theory">Potential theory</a></li> <li><a href="/wiki/String_theory" title="String theory">String theory</a> <ul><li><a href="/wiki/Bosonic_string_theory" title="Bosonic string theory">Bosonic</a></li> <li><a href="/wiki/Topological_string_theory" title="Topological string theory">Topological</a></li></ul></li> <li><a href="/wiki/Supersymmetry" title="Supersymmetry">Supersymmetry</a> <ul><li><a href="/wiki/Supersymmetric_quantum_mechanics" title="Supersymmetric quantum mechanics">Supersymmetric quantum mechanics</a></li> <li><a href="/wiki/Supersymmetric_theory_of_stochastic_dynamics" title="Supersymmetric theory of stochastic dynamics">Supersymmetric theory of stochastic dynamics</a></li></ul></li></ul> </div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Algebraic_structures" scope="row" class="navbox-group" style="width:1%;font-weight:normal;"><a href="/wiki/Algebraic_structures" class="mw-redirect" title="Algebraic structures">Algebraic structures</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Algebra_of_physical_space" title="Algebra of physical space">Algebra of physical space</a></li> <li><a href="/wiki/Path_integral_formulation" title="Path integral formulation">Feynman integral</a></li> <li><a href="/wiki/Poisson_algebra" title="Poisson algebra">Poisson algebra</a></li> <li><a href="/wiki/Quantum_group" title="Quantum group">Quantum group</a></li> <li><a href="/wiki/Renormalization_group" title="Renormalization group">Renormalization group</a></li> <li><a href="/wiki/Particle_physics_and_representation_theory" title="Particle physics and representation theory">Representation theory</a></li> <li><a href="/wiki/Spacetime_algebra" title="Spacetime algebra">Spacetime algebra</a></li> <li><a href="/wiki/Superalgebra" title="Superalgebra">Superalgebra</a></li> <li><a href="/wiki/Supersymmetry_algebra" title="Supersymmetry algebra">Supersymmetry algebra</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Decision_theory" title="Decision theory">Decision sciences</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Game_theory" title="Game theory">Game theory</a></li> <li><a href="/wiki/Operations_research" title="Operations research">Operations research</a></li> <li><a href="/wiki/Mathematical_optimization" title="Mathematical optimization">Optimization</a></li> <li><a href="/wiki/Social_choice_theory" title="Social choice theory">Social choice theory</a></li> <li><a href="/wiki/Statistics" title="Statistics">Statistics</a></li> <li><a href="/wiki/Mathematical_economics" title="Mathematical economics">Mathematical economics</a></li> <li><a href="/wiki/Mathematical_finance" title="Mathematical finance">Mathematical finance</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other applications</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Mathematical_and_theoretical_biology" title="Mathematical and theoretical biology">Biology</a></li> <li><a href="/wiki/Mathematical_chemistry" title="Mathematical chemistry">Chemistry</a></li> <li><a href="/wiki/Mathematical_psychology" title="Mathematical psychology">Psychology</a></li> <li><a href="/wiki/Mathematical_sociology" title="Mathematical sociology">Sociology</a></li> <li>"<a href="/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences" title="The Unreasonable Effectiveness of Mathematics in the Natural Sciences">The Unreasonable Effectiveness of Mathematics in the Natural Sciences</a>"</li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Mathematics" title="Mathematics">Mathematics</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Organizations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a> <ul><li><a href="/wiki/Japan_Society_for_Industrial_and_Applied_Mathematics" title="Japan Society for Industrial and Applied Mathematics">Japan Society for Industrial and Applied Mathematics</a></li></ul></li> <li><a href="/wiki/Soci%C3%A9t%C3%A9_de_Math%C3%A9matiques_Appliqu%C3%A9es_et_Industrielles" title="Société de Mathématiques Appliquées et Industrielles">Société de Mathématiques Appliquées et Industrielles</a></li> <li><a href="/wiki/International_Council_for_Industrial_and_Applied_Mathematics" title="International Council for Industrial and Applied Mathematics">International Council for Industrial and Applied Mathematics</a></li> <li><a href="/w/index.php?title=European_Community_on_Computational_Methods_in_Applied_Sciences&action=edit&redlink=1" class="new" title="European Community on Computational Methods in Applied Sciences (page does not exist)">European Community on Computational Methods in Applied Sciences</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><b><a href="/wiki/Category:Mathematics" title="Category:Mathematics">Category</a></b></li> <li><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a> / <a href="/wiki/Topic_outline_of_mathematics" class="mw-redirect" title="Topic outline of mathematics">outline</a> / <a href="/wiki/List_of_mathematics_topics" class="mw-redirect" title="List of mathematics topics">topics list</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Constraint_satisfaction_problem&oldid=1259275985">https://en.wikipedia.org/w/index.php?title=Constraint_satisfaction_problem&oldid=1259275985</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Constraint_programming" title="Category:Constraint programming">Constraint programming</a></li><li><a href="/wiki/Category:NP-complete_problems" title="Category:NP-complete problems">NP-complete problems</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_November_2014" title="Category:Articles needing additional references from November 2014">Articles needing additional references from November 2014</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 24 November 2024, at 08:19<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Constraint_satisfaction_problem&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-w8xh7","wgBackendResponseTime":125,"wgPageParseReport":{"limitreport":{"cputime":"0.565","walltime":"0.755","ppvisitednodes":{"value":3189,"limit":1000000},"postexpandincludesize":{"value":117956,"limit":2097152},"templateargumentsize":{"value":1424,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":141260,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 593.827 1 -total"," 45.24% 268.630 1 Template:Reflist"," 24.42% 145.028 14 Template:Cite_book"," 18.27% 108.500 3 Template:Navbox"," 18.10% 107.491 1 Template:Industrial_and_applied_mathematics"," 10.58% 62.805 1 Template:Short_description"," 9.90% 58.768 1 Template:More_citations_needed"," 9.16% 54.380 11 Template:Cite_journal"," 9.10% 54.019 1 Template:Ambox"," 6.66% 39.537 2 Template:Pagetype"]},"scribunto":{"limitreport-timeusage":{"value":"0.360","limit":"10.000"},"limitreport-memusage":{"value":6933477,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-w5j95","timestamp":"20241124081930","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Constraint satisfaction problem","url":"https:\/\/en.wikipedia.org\/wiki\/Constraint_satisfaction_problem","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1128326","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1128326","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-04-16T22:07:27Z","dateModified":"2024-11-24T08:19:27Z","headline":"mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations"}</script> </body> </html>