Newer
Older
"# CONSTRAINT SATISFACTION PROBLEMS\n",
"This IPy notebook acts as supporting material for topics covered in **Chapter 6 Constraint Satisfaction Problems** of the book* Artificial Intelligence: A Modern Approach*. We make use of the implementations in **csp.py** module. Even though this notebook includes a brief summary of the main topics, familiarity with the material present in the book is expected. We will look at some visualizations and solve some of the CSP problems described in the book. Let us import everything from the csp module to get started."
{
"cell_type": "code",
"# Hide warnings in the matplotlib sections\n",
"import warnings\n",
"warnings.filterwarnings(\"ignore\")"
"* Overview\n",
"* Graph Coloring\n",
"* N-Queens\n",
"* Backtracking Search\n",
"* Tree CSP Solver\n",
"* Graph Coloring Visualization\n",
"* N-Queens Visualization"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## OVERVIEW\n",
"\n",
"CSPs are a special kind of search problems. Here we don't treat the space as a black box but the state has a particular form and we use that to our advantage to tweak our algorithms to be more suited to the problems. A CSP State is defined by a set of variables which can take values from corresponding domains. These variables can take only certain values in their domains to satisfy the constraints. A set of assignments which satisfies all constraints passes the goal test. Let us start by exploring the CSP class which we will use to model our CSPs. You can keep the popup open and read the main page to get a better idea of the code."
"metadata": {
"collapsed": true
},
"source": [
"The __ _ _init_ _ __ method parameters specify the CSP. Variable can be passed as a list of strings or integers. Domains are passed as dict where key specify the variables and value specify the domains. The variables are passed as an empty list. Variables are extracted from the keys of the domain dictionary. Neighbor is a dict of variables that essentially describes the constraint graph. Here each variable key has a list its value which are the variables that are constraint along with it. The constraint parameter should be a function **f(A, a, B, b**) that **returns true** if neighbors A, B **satisfy the constraint** when they have values **A=a, B=b**. We have additional parameters like nassings which is incremented each time an assignment is made when calling the assign method. You can read more about the methods and parameters in the class doc string. We will talk more about them as we encounter their use. Let us jump to an example."
]
},
{
"cell_type": "markdown",
"\n",
"We use the graph coloring problem as our running example for demonstrating the different algorithms in the **csp module**. The idea of map coloring problem is that the adjacent nodes (those connected by edges) should not have the same color throughout the graph. The graph can be colored using a fixed number of colors. Here each node is a variable and the values are the colors that can be assigned to them. Given that the domain will be the same for all our nodes we use a custom dict defined by the **UniversalDict** class. The **UniversalDict** Class takes in a parameter which it returns as value for all the keys of the dict. It is very similar to **defaultdict** in Python except that it does not support item assignment."
]
},
{
"cell_type": "code",
"outputs": [
{
"data": {
"text/plain": [
"['R', 'G', 'B']"
]
},
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"s = UniversalDict(['R','G','B'])\n",
"s[5]"
]
},
{
"cell_type": "markdown",
"source": [
"For our CSP we also need to define a constraint function **f(A, a, B, b)**. In this what we need is that the neighbors must not have the same color. This is defined in the function **different_values_constraint** of the module."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
]
},
{
"cell_type": "markdown",
"The CSP class takes neighbors in the form of a Dict. The module specifies a simple helper function named **parse_neighbors** which allows us to take input in the form of strings and return a Dict of a form compatible with the **CSP Class**."
{
"cell_type": "markdown",
"The **MapColoringCSP** function creates and returns a CSP with the above constraint function and states. The variables are the keys of the neighbors dict and the constraint is the one specified by the **different_values_constratint** function. **australia**, **usa** and **france** are three CSPs that have been created using **MapColoringCSP**. **australia** corresponds to ** Figure 6.1 ** in the book."
]
},
{
"cell_type": "code",
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(<csp.CSP at 0x7feb58e54390>,\n",
" <csp.CSP at 0x7feb58e7c080>,\n",
" <csp.CSP at 0x7feb58e7c160>)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"australia, usa, france"
]
},
"The N-queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Here N is a natural number. Like the graph coloring problem, NQueens is also implemented in the csp module. The **NQueensCSP** class inherits from the **CSP** class. It makes some modifications in the methods to suit the particular problem. The queens are assumed to be placed one per column, from left to right. That means position (x, y) represents (var, val) in the CSP. The constraint that needs to be passed on the CSP is defined in the **queen_constraint** function. The constraint is satisfied (true) if A, B are really the same variable, or if they are not in the same row, down diagonal, or up diagonal. "
]
},
{
"cell_type": "code",
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">queen_constraint</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">a</span><span class=\"p\">,</span> <span class=\"n\">B</span><span class=\"p\">,</span> <span class=\"n\">b</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Constraint is satisfied (true) if A, B are really the same variable,</span>\n",
"<span class=\"sd\"> or if they are not in the same row, down diagonal, or up diagonal."""</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">A</span> <span class=\"o\">==</span> <span class=\"n\">B</span> <span class=\"ow\">or</span> <span class=\"p\">(</span><span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">b</span> <span class=\"ow\">and</span> <span class=\"n\">A</span> <span class=\"o\">+</span> <span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">B</span> <span class=\"o\">+</span> <span class=\"n\">b</span> <span class=\"ow\">and</span> <span class=\"n\">A</span> <span class=\"o\">-</span> <span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"n\">B</span> <span class=\"o\">-</span> <span class=\"n\">b</span><span class=\"p\">)</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
]
},
{
"cell_type": "markdown",
"The **NQueensCSP** method implements methods that support solving the problem via **min_conflicts** which is one of the techniques for solving CSPs. Because **min_conflicts** hill climbs the number of conflicts to solve, the CSP **assign** and **unassign** are modified to record conflicts. More details about the structures **rows**, **downs**, **ups** which help in recording conflicts are explained in the docstring."
]
},
{
"cell_type": "code",
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">NQueensCSP</span><span class=\"p\">(</span><span class=\"n\">CSP</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Make a CSP for the nQueens problem for search with min_conflicts.</span>\n",
"<span class=\"sd\"> Suitable for large n, it uses only data structures of size O(n).</span>\n",
"<span class=\"sd\"> Think of placing queens one per column, from left to right.</span>\n",
"<span class=\"sd\"> That means position (x, y) represents (var, val) in the CSP.</span>\n",
"<span class=\"sd\"> The main structures are three arrays to count queens that could conflict:</span>\n",
"<span class=\"sd\"> rows[i] Number of queens in the ith row (i.e val == i)</span>\n",
"<span class=\"sd\"> downs[i] Number of queens in the \\ diagonal</span>\n",
"<span class=\"sd\"> such that their (x, y) coordinates sum to i</span>\n",
"<span class=\"sd\"> ups[i] Number of queens in the / diagonal</span>\n",
"<span class=\"sd\"> such that their (x, y) coordinates have x-y+n-1 = i</span>\n",
"<span class=\"sd\"> We increment/decrement these counts each time a queen is placed/moved from</span>\n",
"<span class=\"sd\"> a row/diagonal. So moving is O(1), as is nconflicts. But choosing</span>\n",
"<span class=\"sd\"> a variable, and a best value for the variable, are each O(n).</span>\n",
"<span class=\"sd\"> If you want, you can keep track of conflicted variables, then variable</span>\n",
"<span class=\"sd\"> selection will also be O(1).</span>\n",
"<span class=\"sd\"> >>> len(backtracking_search(NQueensCSP(8)))</span>\n",
"<span class=\"sd\"> 8</span>\n",
"<span class=\"sd\"> """</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">n</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Initialize data structures for n Queens."""</span>\n",
" <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">)),</span> <span class=\"n\">UniversalDict</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">))),</span>\n",
" <span class=\"n\">UniversalDict</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">))),</span> <span class=\"n\">queen_constraint</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"n\">n</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"o\">*</span><span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span><span class=\"o\">*</span><span class=\"p\">(</span><span class=\"mi\">2</span><span class=\"o\">*</span><span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">nconflicts</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""The number of conflicts, as recorded with each assignment.</span>\n",
"<span class=\"sd\"> Count conflicts in row and in up, down diagonals. If there</span>\n",
"<span class=\"sd\"> is a queen there, it can't conflict with itself, so subtract 3."""</span>\n",
" <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
" <span class=\"n\">c</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span><span class=\"p\">[</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"o\">+</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"o\">-</span><span class=\"n\">val</span><span class=\"o\">+</span><span class=\"n\">n</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
" <span class=\"n\">c</span> <span class=\"o\">-=</span> <span class=\"mi\">3</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">c</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">assign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Assign var, and keep track of conflicts."""</span>\n",
" <span class=\"n\">oldval</span> <span class=\"o\">=</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">val</span> <span class=\"o\">!=</span> <span class=\"n\">oldval</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">oldval</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span> <span class=\"c1\"># Remove old val if there was one</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">oldval</span><span class=\"p\">,</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"o\">+</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
" <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">unassign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Remove var from assignment (if it is there) and track conflicts."""</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"n\">assignment</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">record_conflict</span><span class=\"p\">(</span><span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">[</span><span class=\"n\">var</span><span class=\"p\">],</span> <span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">)</span>\n",
" <span class=\"n\">CSP</span><span class=\"o\">.</span><span class=\"n\">unassign</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">record_conflict</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">delta</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Record conflicts caused by addition or deletion of a Queen."""</span>\n",
" <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">rows</span><span class=\"p\">[</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">downs</span><span class=\"p\">[</span><span class=\"n\">var</span> <span class=\"o\">+</span> <span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">ups</span><span class=\"p\">[</span><span class=\"n\">var</span> <span class=\"o\">-</span> <span class=\"n\">val</span> <span class=\"o\">+</span> <span class=\"n\">n</span> <span class=\"o\">-</span> <span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"n\">delta</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">display</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Print the queens and the nconflicts values (for debugging)."""</span>\n",
" <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">val</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"s1\">''</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">'Q'</span>\n",
" <span class=\"k\">elif</span> <span class=\"p\">(</span><span class=\"n\">var</span> <span class=\"o\">+</span> <span class=\"n\">val</span><span class=\"p\">)</span> <span class=\"o\">%</span> <span class=\"mi\">2</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">'.'</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">'-'</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">ch</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">' '</span><span class=\"p\">)</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">' '</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">' '</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">n</span><span class=\"p\">):</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">assignment</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"s1\">''</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">val</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">'*'</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ch</span> <span class=\"o\">=</span> <span class=\"s1\">' '</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">nconflicts</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">assignment</span><span class=\"p\">))</span> <span class=\"o\">+</span> <span class=\"n\">ch</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">' '</span><span class=\"p\">)</span>\n",
" <span class=\"k\">print</span><span class=\"p\">()</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
]
},
{
"cell_type": "markdown",
"source": [
"The _ ___init___ _ method takes only one parameter **n** the size of the problem. To create an instance we just pass the required n into the constructor."
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"eight_queens = NQueensCSP(8)"
]
},
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have defined our CSP. \n",
"We now need to solve this.\n",
"\n",
"### Min-conflicts\n",
"As stated above, the `min_conflicts` algorithm is an efficient method to solve such a problem.\n",
"<br>\n",
"To begin with, all the variables of the CSP are _randomly_ initialized. \n",
"<br>\n",
"The algorithm then randomly selects a variable that has conflicts and violates some constraints of the CSP.\n",
"<br>\n",
"The selected variable is then assigned a value that _minimizes_ the number of conflicts.\n",
"<br>\n",
"This is a simple stochastic algorithm which works on a principle similar to **Hill-climbing**.\n",
"The conflicting state is repeatedly changed into a state with fewer conflicts in an attempt to reach an approximate solution.\n",
"<br>\n",
"This algorithm sometimes benefits from having a good initial assignment.\n",
"Using greedy techniques to get a good initial assignment and then using `min_conflicts` to solve the CSP can speed up the procedure dramatically, especially for CSPs with a large state space."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">min_conflicts</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">max_steps</span><span class=\"o\">=</span><span class=\"mi\">100000</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Solve a CSP by stochastic hillclimbing on the number of conflicts."""</span>\n",
" <span class=\"c1\"># Generate a complete assignment for all variables (probably with conflicts)</span>\n",
" <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"n\">current</span> <span class=\"o\">=</span> <span class=\"p\">{}</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">var</span> <span class=\"ow\">in</span> <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">variables</span><span class=\"p\">:</span>\n",
" <span class=\"n\">val</span> <span class=\"o\">=</span> <span class=\"n\">min_conflicts_value</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
" <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
" <span class=\"c1\"># Now repeatedly choose a random conflicted variable and change it</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">max_steps</span><span class=\"p\">):</span>\n",
" <span class=\"n\">conflicted</span> <span class=\"o\">=</span> <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">conflicted_vars</span><span class=\"p\">(</span><span class=\"n\">current</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">conflicted</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">current</span>\n",
" <span class=\"n\">var</span> <span class=\"o\">=</span> <span class=\"n\">random</span><span class=\"o\">.</span><span class=\"n\">choice</span><span class=\"p\">(</span><span class=\"n\">conflicted</span><span class=\"p\">)</span>\n",
" <span class=\"n\">val</span> <span class=\"o\">=</span> <span class=\"n\">min_conflicts_value</span><span class=\"p\">(</span><span class=\"n\">csp</span><span class=\"p\">,</span> <span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
" <span class=\"n\">csp</span><span class=\"o\">.</span><span class=\"n\">assign</span><span class=\"p\">(</span><span class=\"n\">var</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">current</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(min_conflicts)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's use this algorithm to solve the `eight_queens` CSP."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"solution = min_conflicts(eight_queens)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is indeed a valid solution. \n",
"Let's write a helper function to visualize the solution space."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"%matplotlib inline\n",
"\n",
"def display_NQueensCSP(solution):\n",
" n = len(solution)\n",
" board = np.array([2 * int((i + j) % 2) for j in range(n) for i in range(n)]).reshape((n, n))\n",
" \n",
" for (k, v) in solution.items():\n",
" board[k][v] = 1\n",
" \n",
" fig = plt.figure(figsize=(7, 7))\n",
" ax = fig.add_subplot(111)\n",
" ax.set_title(f'{n} Queens')\n",
" plt.imshow(board, cmap='binary', interpolation='nearest')\n",
" ax.set_aspect('equal')\n",
" fig.tight_layout()\n",
" plt.show()"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeAAAAHwCAYAAAB+ArwOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFZFJREFUeJzt3HuspAd53/HfE6+52DFxG7bUFwpE\njSxR1AB7IEWuaIshsQMlVS+SaYNCVNVpGxLcRk1J/tmlSqU2f0SkokXZGAhJAItrRRGYECU0RW0M\nZ40pGEMFxhGLcbxu4hpwg7Hz9I8zbpdllzPbzOzjM+fzkY58Zuad9zzj18ff815mqrsDAJxb3zE9\nAADsRwIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAYZzoKqeWlXvr6o/qqq7q+p1VXXg2yx/\ncVW9frHsA1X1yar60XM5M7BeAgznxn9Ick+SS5I8M8lfS/JPT7dgVT0myW8leUqS5yX5riT/Iskv\nVNVPnZNpgbUTYDg3npbk7d39x919d5KbkvylMyz78iR/Icnf6+4vdPc3uvumJD+V5Oer6qIkqaqu\nqr/4yJOq6ler6udPuv2Sqrq1qu6rqv9aVX/5pMcurap3VdWJqvrCyWGvqiNV9faq+rWq+kpV3VZV\nWyc9/i+r6kuLxz5bVVet5l8R7C8CDOfGLyW5tqouqKrLklyTnQifzouSfKC7v3bK/e9KckGSv7Lb\nD6uqZyd5Y5IfT/LdSX45yXur6rFV9R1J/lOSTyS5LMlVSa6vqh88aRUvTXJjkouTvDfJ6xbrvSLJ\nK5M8p7svSvKDSe7cbR7gWwkwnBv/OTt7vPcnOZ5kO8l/PMOyT0zy5VPv7O6Hktyb5OASP+8fJfnl\n7r65ux/u7jcn+Xp24v2cJAe7+19194PdfUeSX0ly7UnP/0h3v7+7H07y60m+b3H/w0kem+TpVXV+\nd9/Z3Z9fYh7gFAIMa7bY4/xgkncnuTA7gf0zSf7tGZ5yb3bOFZ+6ngOL555Y4sc+JclPLw4/31dV\n9yV5cpJLF49despjP5fkSSc9/+6Tvn8gyeOq6kB3fy7J9UmOJLmnqm6sqkuXmAc4hQDD+v3Z7MTv\ndd399e7+n0nelOSHzrD8byW5pqouPOX+v5PkG0k+urj9QHYOST/iz5/0/ReT/Ovuvvikrwu6+22L\nx75wymMXdfeZ5vkm3f3W7v6r2Ql558x/SADfhgDDmnX3vUm+kOSfVNWBqro4yY9m5xzs6fx6dg5T\nv2Px9qXzF+dn/12SX+ju/7VY7tYkf7+qzquqq7NzZfUjfiXJP66q768dF1bVixcXcH00yf2Li6ke\nv3j+M6rqObu9lqq6oqpeUFWPTfLHSf53dg5LA2dJgOHc+NtJrs7O4ePPJXkoyT873YLd/fUkL8zO\nnurN2YncTUlem+Q1Jy36qiR/M8l9Sf5BTjqn3N3b2TkP/Lokf7T4ma9YPPbw4nnPzM4fBvcmuSE7\nb3fazWOT/JvFc+5O8ueyc/gaOEvV3dMzAN9GVZ2f5ANJvpTkFe2XFjaCPWB4lOvub2Tn/O/nk1wx\nPA6wIvaAAWCAPWAAGHDGD4P/06iqjd6tPnTo0PQIa3Xs2LHpEdbONtzbbL+975JLvuWt7hvjvvvu\nywMPPFC7LbeWQ9CbHuBNP2xftet/N3uebbi32X573+HDh6dHWJujR4/mrrvu2nUjOgQNAAMEGAAG\nCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaA\nAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8CApQJcVVdX1Wer6nNV9ep1DwUAm27XAFfVeUn+\nfZJrkjw9ycuq6unrHgwANtkye8DPTfK57r6jux9McmOSH17vWACw2ZYJ8GVJvnjS7eOL+75JVV1X\nVdtVtb2q4QBgUx1YYpk6zX39LXd0H01yNEmq6lseBwD+n2X2gI8nefJJty9Pctd6xgGA/WGZAH8s\nyfdW1dOq6jFJrk3y3vWOBQCbbddD0N39UFW9MskHk5yX5I3dfdvaJwOADbbMOeB09/uTvH/NswDA\nvuGTsABggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYI\nMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMOLCOlR46dCjb29vrWPWjwpEjR6ZH\nWKvunh5h7apqeoS12vRtaPvtfZu+DZdhDxgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAAD\nBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPA\nAAEGgAECDAADdg1wVb2xqu6pqk+di4EAYD9YZg/4V5NcveY5AGBf2TXA3f27Sf7wHMwCAPuGc8AA\nMGBlAa6q66pqu6q2T5w4sarVAsBGWlmAu/tod29199bBgwdXtVoA2EgOQQPAgGXehvS2JP8tyRVV\ndbyq/uH6xwKAzXZgtwW6+2XnYhAA2E8cggaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AA\nAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAw\n4MA6Vnrs2LFU1TpW/ajQ3dMjrNUmb7tHbPo2PHLkyPQIa7Xp28/v4N62tbW11HL2gAFggAADwAAB\nBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBA\ngAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFgwK4BrqonV9XvVNXtVXVbVb3qXAwG\nAJvswBLLPJTkp7v7lqq6KMmxqvpQd396zbMBwMbadQ+4u7/c3bcsvv9KktuTXLbuwQBgky2zB/x/\nVdVTkzwryc2neey6JNetZCoA2HBLB7iqvjPJu5Jc3933n/p4dx9NcnSxbK9sQgDYQEtdBV1V52cn\nvm/p7nevdyQA2HzLXAVdSd6Q5Pbu/sX1jwQAm2+ZPeArk7w8yQuq6tbF1w+teS4A2Gi7ngPu7o8k\nqXMwCwDsGz4JCwAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAw\nQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8CAA+tY6aFDh7K9vb2OVT8q\nVNX0CGt1+PDh6RHWbtO3YXdPj7BWtt/et+nbcBn2gAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAA\nGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQY\nAAYIMAAMEGAAGCDAADBg1wBX1eOq6qNV9Ymquq2qXnMuBgOATXZgiWW+nuQF3f3Vqjo/yUeq6gPd\n/Xtrng0ANtauAe7uTvLVxc3zF1+9zqEAYNMtdQ64qs6rqluT3JPkQ91982mWua6qtqtq+8SJE6ue\nEwA2ylIB7u6Hu/uZSS5P8tyqesZpljna3VvdvXXw4MFVzwkAG+WsroLu7vuSfDjJ1WuZBgD2iWWu\ngj5YVRcvvn98khcm+cy6BwOATbbMVdCXJHlzVZ2XnWC/vbvft96xAGCzLXMV9H9P8qxzMAsA7Bs+\nCQsABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPA\nAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAgAPrWOldd92VI0eOrGPVjwrdPT3CWlXV\n9AhrZxvubbbf3rfJ23Bra2up5ewBA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AA\nAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAw\nQIABYMDSAa6q86rq41X1vnUOBAD7wdnsAb8qye3rGgQA9pOlAlxVlyd5cZIb1jsOAOwPy+4BvzbJ\nzyT5kzMtUFXXVdV2VW0/8MADKxkOADbVrgGuqpckuae7j3275br7aHdvdffWBRdcsLIBAWATLbMH\nfGWSl1bVnUluTPKCqvqNtU4FABtu1wB398929+Xd/dQk1yb57e7+kbVPBgAbzPuAAWDAgbNZuLs/\nnOTDa5kEAPYRe8AAMECAAWCAAAPAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEG\ngAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBgABhxYx0ovvfTSHDlyZB2r\nflSoqukR1qq7p0dYO9twb9v07Xf48OHpEdZu07fhMuwBA8AAAQaAAQIMAAMEGAAGCDAADBBgABgg\nwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAG\nCDAADBBgABggwAAwQIABYMCBZRaqqjuTfCXJw0ke6u6tdQ4FAJtuqQAv/I3uvndtkwDAPuIQNAAM\nWDbAneQ3q+pYVV13ugWq6rqq2q6q7RMnTqxuQgDYQMsG+MrufnaSa5L8RFU9/9QFuvtod29199bB\ngwdXOiQAbJqlAtzddy3+eU+S9yR57jqHAoBNt2uAq+rCqrroke+T/ECST617MADYZMtcBf2kJO+p\nqkeWf2t337TWqQBgw+0a4O6+I8n3nYNZAGDf8DYkABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAG\nCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaA\nAQIMAAMOrGOlx44dS1WtY9WPCt09PcJabfK2e8Thw4enR1irTd+Gfgf3vk3ehltbW0stZw8YAAYI\nMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoAB\nAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAA5YKcFVdXFXvrKrPVNXtVfW8dQ8G\nAJvswJLL/VKSm7r771bVY5JcsMaZAGDj7RrgqnpCkucneUWSdPeDSR5c71gAsNmWOQT9PUlOJHlT\nVX28qm6oqgvXPBcAbLRlAnwgybOTvL67n5Xka0lefepCVXVdVW1X1faKZwSAjbNMgI8nOd7dNy9u\nvzM7Qf4m3X20u7e6e2uVAwLAJto1wN19d5IvVtUVi7uuSvLptU4FABtu2augfzLJWxZXQN+R5MfW\nNxIAbL6lAtzdtyZxaBkAVsQnYQHAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEG\ngAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMODA\nOlZ66NChbG9vr2PVjwpVNT3CWnX39AhrZxvubUeOHJkeYa02ffslm/87uAx7wAAwQIABYIAAA8AA\nAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAw\nQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABiwa4Cr6oqquvWkr/ur6vpzMRwAbKoDuy3Q3Z9N\n8swkqarzknwpyXvWPBcAbLSzPQR9VZLPd/fvr2MYANgvzjbA1yZ52+keqKrrqmq7qrZPnDjxp58M\nADbY0gGuqsckeWmSd5zu8e4+2t1b3b118ODBVc0HABvpbPaAr0lyS3f/wbqGAYD94mwC/LKc4fAz\nAHB2lgpwVV2Q5EVJ3r3ecQBgf9j1bUhJ0t0PJPnuNc8CAPuGT8ICgAECDAADBBgABggwAAwQYAAY\nIMAAMECAAWCAAAPAAAEGgAECDAADBBgABggwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBgA\nBggwAAwQYAAYIMAAMKC6e/UrrTqR5PdXvuIze2KSe8/hzzvXvL69zevb+zb9NXp9q/WU7j6420Jr\nCfC5VlXb3b01Pce6eH17m9e39236a/T6ZjgEDQADBBgABmxKgI9OD7BmXt/e5vXtfZv+Gr2+ARtx\nDhgA9ppN2QMGgD1FgAFgwJ4OcFVdXVWfrarPVdWrp+dZtap6Y1XdU1Wfmp5lHarqyVX1O1V1e1Xd\nVlWvmp5plarqcVX10ar6xOL1vWZ6pnWoqvOq6uNV9b7pWVatqu6sqk9W1a1VtT09z6pV1cVV9c6q\n+szi9/B50zOtUlVdsdh2j3zdX1XXT8/1iD17DriqzkvyP5K8KMnxJB9L8rLu/vToYCtUVc9P8tUk\nv9bdz5ieZ9Wq6pIkl3T3LVV1UZJjSf7WpmzDqqokF3b3V6vq/CQfSfKq7v694dFWqqr+eZKtJE/o\n7pdMz7NKVXVnkq3u3sgPqaiqNyf5L919Q1U9JskF3X3f9FzrsGjGl5J8f3efyw+KOqO9vAf83CSf\n6+47uvvBJDcm+eHhmVaqu383yR9Oz7Eu3f3l7r5l8f1Xktye5LLZqVand3x1cfP8xdfe/Iv3DKrq\n8iQvTnLD9Cycnap6QpLnJ3lDknT3g5sa34Wrknz+0RLfZG8H+LIkXzzp9vFs0P+895uqemqSZyW5\neXaS1Vocnr01yT1JPtTdG/X6krw2yc8k+ZPpQdakk/xmVR2rquumh1mx70lyIsmbFqcQbqiqC6eH\nWqNrk7xteoiT7eUA12nu26i9i/2iqr4zybuSXN/d90/Ps0rd/XB3PzPJ5UmeW1Ubcyqhql6S5J7u\nPjY9yxpd2d3PTnJNkp9YnBbaFAeSPDvJ67v7WUm+lmTjrqVJksXh9Zcmecf0LCfbywE+nuTJJ92+\nPMldQ7Pw/2lxbvRdSd7S3e+enmddFof2Ppzk6uFRVunKJC9dnCe9MckLquo3Zkdare6+a/HPe5K8\nJzunvjbF8STHTzoq887sBHkTXZPklu7+g+lBTraXA/yxJN9bVU9b/HVzbZL3Ds/EWVhcpPSGJLd3\n9y9Oz7NqVXWwqi5efP/4JC9M8pnZqVanu3+2uy/v7qdm5/fvt7v7R4bHWpmqunBxcWAWh2Z/IMnG\nvCOhu+9O8sWqumJx11VJNuICyNN4WR5lh5+TnUMQe1J3P1RVr0zywSTnJXljd982PNZKVdXbkvz1\nJE+squNJDnf3G2anWqkrk7w8yScX50mT5Oe6+/2DM63SJUnevLj68juSvL27N+6tOhvsSUnes/N3\nYg4keWt33zQ70sr9ZJK3LHZi7kjyY8PzrFxVXZCdd8v8+PQsp9qzb0MCgL1sLx+CBoA9S4ABYIAA\nA8AAAQaAAQIMAAMEGAAGCDAADPg/v2hxZuiP1asAAAAASUVORK5CYII=\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x22baedf4588>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display_NQueensCSP(solution)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The gray cells indicate the positions of the queens."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lets' see if we can find a different solution."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeAAAAHwCAYAAAB+ArwOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFaFJREFUeJzt3G2spAd53+H/Ha95sWPiNmwptikQ\nNbJEUQPsgRS5oi2GxA6UVH2RTBsUoqpO25DgNmpK8mWXKpXafIhIRYviGAhJAIvXilpgQpTQFLUx\nnDWmYAwVGEcsi+N1E9eAG4ydux/OuF2WXc5sM7O3z5zrko72zMwzz7nHj8a/87zMqe4OAHBufcf0\nAACwHwkwAAwQYAAYIMAAMECAAWCAAAPAAAEGgAECDAADBBjOgap6WlW9v6r+qKrurqrXV9WBb7P8\nxVX1hsWyD1TVJ6vqR8/lzMB6CTCcG/8hyT1JnpzkWUn+WpJ/eroFq+oxSX4ryVOTPD/JdyX5F0l+\noap+6pxMC6ydAMO58fQk7+juP+7uu5PcnOQvnWHZVyT5C0n+Xnd/obu/0d03J/mpJD9fVRclSVV1\nVf3FR55UVb9aVT9/0u2XVtVtVXVfVf3XqvrLJz12SVW9u6pOVNUXTg57VR2pqndU1a9V1Veq6vaq\n2jrp8X9ZVV9aPPbZqrpyNf+JYH8RYDg3finJNVV1QVVdmuTq7ET4dF6c5APd/bVT7n93kguS/JXd\nflhVPSfJm5L8eJLvTvLLSd5XVY+tqu9I8p+SfCLJpUmuTHJdVf3gSat4WZIbk1yc5H1JXr9Y7+VJ\nXpXkud19UZIfTHLXbvMA30qA4dz4z9nZ470/ybEk20n+4xmWfWKSL596Z3c/lOTeJAeX+Hn/KMkv\nd/ct3f1wd78lydezE+/nJjnY3f+qux/s7juT/EqSa056/ke6+/3d/XCSX0/yfYv7H07y2CTPqKrz\nu/uu7v78EvMApxBgWLPFHucHk7wnyYXZCeyfSfJvz/CUe7NzrvjU9RxYPPfEEj/2qUl+enH4+b6q\nui/JU5JcsnjsklMe+7kkTzrp+Xef9P0DSR5XVQe6+3NJrktyJMk9VXVjVV2yxDzAKQQY1u/PZid+\nr+/ur3f3/0zy5iQ/dIblfyvJ1VV14Sn3/50k30jy0cXtB7JzSPoRf/6k77+Y5F9398UnfV3Q3W9f\nPPaFUx67qLvPNM836e63dfdfzU7IO2f+RQL4NgQY1qy7703yhST/pKoOVNXFSX40O+dgT+fXs3OY\n+p2Ljy+dvzg/+++S/EJ3/6/Fcrcl+ftVdV5VXZWdK6sf8StJ/nFVfX/tuLCqXrK4gOujSe5fXEz1\n+MXzn1lVz93ttVTV5VX1wqp6bJI/TvK/s3NYGjhLAgznxt9OclV2Dh9/LslDSf7Z6Rbs7q8neVF2\n9lRvyU7kbk7yuiSvPWnRVyf5m0nuS/IPctI55e7ezs554Ncn+aPFz3zl4rGHF897VnZ+Mbg3yQ3Z\n+bjTbh6b5N8snnN3kj+XncPXwFmq7p6eAfg2qur8JB9I8qUkr2xvWtgI9oDhUa67v5Gd87+fT3L5\n8DjAitgDBoAB9oABYMAZ/xj8n0ZVbfRu9aFDh6ZHWKvjx49Pj7B2l1yy2R9dPXr06PQIa7Xp78FN\n337JZm/Du+66K/fee2/tttxaDkFveoA3/bD9kSNHpkdYu01/jVW7vvf3tE1/D2769ks2extubW1l\ne3t7143oEDQADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAA\nA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAOWCnBVXVVVn62qz1XV\na9Y9FABsul0DXFXnJfn3Sa5O8owkL6+qZ6x7MADYZMvsAT8vyee6+87ufjDJjUl+eL1jAcBmWybA\nlyb54km3jy3u+yZVdW1VbVfV9qqGA4BNdWCJZeo09/W33NF9fZLrk6SqvuVxAOD/WWYP+FiSp5x0\n+7Ikx9czDgDsD8sE+GNJvreqnl5Vj0lyTZL3rXcsANhsux6C7u6HqupVST6Y5Lwkb+ru29c+GQBs\nsGXOAae735/k/WueBQD2DX8JCwAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAA\nDBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8CAA+tY6aFD\nh7K9vb2OVT8qVNX0CGvV3dMjrN2mb8PDhw9Pj7BWm779vAf3B3vAADBAgAFggAADwAABBoABAgwA\nAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAAD\nwAABBoABAgwAAwQYAAYIMAAMEGAAGLBrgKvqTVV1T1V96lwMBAD7wTJ7wL+a5Ko1zwEA+8quAe7u\n303yh+dgFgDYN5wDBoABKwtwVV1bVdtVtX3ixIlVrRYANtLKAtzd13f3VndvHTx4cFWrBYCN5BA0\nAAxY5mNIb0/y35JcXlXHquofrn8sANhsB3ZboLtffi4GAYD9xCFoABggwAAwQIABYIAAA8AAAQaA\nAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIAB\nYIAAA8AAAQaAAQIMAAMOrGOlR48eTVWtY9WPCocPH54eYa02eds9orunR1irTd+Gtt/et8nbcGtr\na6nl7AEDwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAM\nEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwIBdA1xVT6mq\n36mqO6rq9qp69bkYDAA22YEllnkoyU93961VdVGSo1X1oe7+9JpnA4CNtesecHd/ubtvXXz/lSR3\nJLl03YMBwCZbZg/4/6qqpyV5dpJbTvPYtUmuXclUALDhlg5wVX1nkncnua677z/18e6+Psn1i2V7\nZRMCwAZa6iroqjo/O/F9a3e/Z70jAcDmW+Yq6EryxiR3dPcvrn8kANh8y+wBX5HkFUleWFW3Lb5+\naM1zAcBG2/UccHd/JEmdg1kAYN/wl7AAYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIAB\nYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADDiw\njpUeOnQo29vb61j1o0JVTY+wVt09PcLa2YZ7m+239x05cmR6hLU5fvz4UsvZAwaAAQIMAAMEGAAG\nCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaA\nAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8CAXQNcVY+rqo9W1Seq6vaqeu25GAwANtmBJZb5\nepIXdvdXq+r8JB+pqg909++teTYA2Fi7Bri7O8lXFzfPX3z1OocCgE231Dngqjqvqm5Lck+SD3X3\nLadZ5tqq2q6q7RMnTqx6TgDYKEsFuLsf7u5nJbksyfOq6pmnWeb67t7q7q2DBw+uek4A2ChndRV0\nd9+X5MNJrlrLNACwTyxzFfTBqrp48f3jk7woyWfWPRgAbLJlroJ+cpK3VNV52Qn2O7r7pvWOBQCb\nbZmroP97kmefg1kAYN/wl7AAYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AA\nAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADDiwjpUeP348\nR44cWceqHxW6e3qEtaqq6RHWzjbc22y/vW+Tt+FNN9201HL2gAFggAADwAABBoABAgwAAwQYAAYI\nMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoAB\nAgwAAwQYAAYIMAAMEGAAGCDAADBg6QBX1XlV9fGqummdAwHAfnA2e8CvTnLHugYBgP1kqQBX1WVJ\nXpLkhvWOAwD7w7J7wK9L8jNJ/uRMC1TVtVW1XVXbDzzwwEqGA4BNtWuAq+qlSe7p7qPfbrnuvr67\nt7p764ILLljZgACwiZbZA74iycuq6q4kNyZ5YVX9xlqnAoANt2uAu/tnu/uy7n5akmuS/HZ3/8ja\nJwOADeZzwAAw4MDZLNzdH07y4bVMAgD7iD1gABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAA\nDBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIM\nAAMOrGOll1xySY4cObKOVT8qVNX0CGvV3dMjrJ1tuLdt+vY7fPjw9Ahrt+nbcBn2gAFggAADwAAB\nBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBA\ngAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADDgwDILVdVdSb6S5OEkD3X31jqHAoBNt1SA\nF/5Gd9+7tkkAYB9xCBoABiwb4E7ym1V1tKquPd0CVXVtVW1X1faJEydWNyEAbKBlA3xFdz8nydVJ\nfqKqXnDqAt19fXdvdffWwYMHVzokAGyapQLc3ccX/96T5L1JnrfOoQBg0+0a4Kq6sKoueuT7JD+Q\n5FPrHgwANtkyV0E/Kcl7q+qR5d/W3TevdSoA2HC7Bri770zyfedgFgDYN3wMCQAGCDAADBBgABgg\nwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAG\nCDAADBBgABggwAAwQIABYIAAA8CAA+tY6dGjR1NV61j1o0J3T4+wVpu87R5x+PDh6RHWatO3offg\n3rfJ23Bra2up5ewBA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAME\nGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYMBSAa6q\ni6vqXVX1maq6o6qev+7BAGCTHVhyuV9KcnN3/92qekySC9Y4EwBsvF0DXFVPSPKCJK9Mku5+MMmD\n6x0LADbbMoegvyfJiSRvrqqPV9UNVXXhmucCgI22TIAPJHlOkjd097OTfC3Ja05dqKqurartqtpe\n8YwAsHGWCfCxJMe6+5bF7XdlJ8jfpLuv7+6t7t5a5YAAsIl2DXB3353ki1V1+eKuK5N8eq1TAcCG\nW/Yq6J9M8tbFFdB3Jvmx9Y0EAJtvqQB3921JHFoGgBXxl7AAYIAAA8AAAQaAAQIMAAMEGAAGCDAA\nDBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIM\nAAMEGAAGCDAADBBgABhwYB0rPXToULa3t9ex6keFqpoeYa26e3qEtbMN97YjR45Mj7BWm779ks1/\nDy7DHjAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AA\nAQaAAQIMAAMEGAAGCDAADBBgABggwAAwQIABYIAAA8AAAQaAAQIMAAMEGAAG7Brgqrq8qm476ev+\nqrruXAwHAJvqwG4LdPdnkzwrSarqvCRfSvLeNc8FABvtbA9BX5nk8939++sYBgD2i7MN8DVJ3n66\nB6rq2qrarqrtEydO/OknA4ANtnSAq+oxSV6W5J2ne7y7r+/ure7eOnjw4KrmA4CNdDZ7wFcnubW7\n/2BdwwDAfnE2AX55znD4GQA4O0sFuKouSPLiJO9Z7zgAsD/s+jGkJOnuB5J895pnAYB9w1/CAoAB\nAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFggAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADBAgAFg\ngAADwAABBoABAgwAAwQYAAYIMAAMEGAAGCDAADCgunv1K606keT3V77iM3tiknvP4c8717y+vc3r\n2/s2/TV6fav11O4+uNtCawnwuVZV2929NT3Hunh9e5vXt/dt+mv0+mY4BA0AAwQYAAZsSoCvnx5g\nzby+vc3r2/s2/TV6fQM24hwwAOw1m7IHDAB7igADwIA9HeCquqqqPltVn6uq10zPs2pV9aaquqeq\nPjU9yzpU1VOq6neq6o6qur2qXj090ypV1eOq6qNV9YnF63vt9EzrUFXnVdXHq+qm6VlWraruqqpP\nVtVtVbU9Pc+qVdXFVfWuqvrM4n34/OmZVqmqLl9su0e+7q+q66bnesSePQdcVecl+R9JXpzkWJKP\nJXl5d396dLAVqqoXJPlqkl/r7mdOz7NqVfXkJE/u7lur6qIkR5P8rU3ZhlVVSS7s7q9W1flJPpLk\n1d39e8OjrVRV/fMkW0me0N0vnZ5nlarqriRb3b2Rf6Siqt6S5L909w1V9ZgkF3T3fdNzrcOiGV9K\n8v3dfS7/UNQZ7eU94Ocl+Vx339ndDya5MckPD8+0Ut39u0n+cHqOdenuL3f3rYvvv5LkjiSXzk61\nOr3jq4ub5y++9uZvvGdQVZcleUmSG6Zn4exU1ROSvCDJG5Okux/c1PguXJnk84+W+CZ7O8CXJvni\nSbePZYP+573fVNXTkjw7yS2zk6zW4vDsbUnuSfKh7t6o15fkdUl+JsmfTA+yJp3kN6vqaFVdOz3M\nin1PkhNJ3rw4hXBDVV04PdQaXZPk7dNDnGwvB7hOc99G7V3sF1X1nUneneS67r5/ep5V6u6Hu/tZ\nSS5L8ryq2phTCVX10iT3dPfR6VnW6Irufk6Sq5P8xOK00KY4kOQ5Sd7Q3c9O8rUkG3ctTZIsDq+/\nLMk7p2c52V4O8LEkTznp9mVJjg/Nwv+nxbnRdyd5a3e/Z3qedVkc2vtwkquGR1mlK5K8bHGe9MYk\nL6yq35gdabW6+/ji33uSvDc7p742xbEkx046KvOu7AR5E12d5Nbu/oPpQU62lwP8sSTfW1VPX/x2\nc02S9w3PxFlYXKT0xiR3dPcvTs+zalV1sKouXnz/+CQvSvKZ2alWp7t/trsv6+6nZef999vd/SPD\nY61MVV24uDgwi0OzP5BkYz6R0N13J/liVV2+uOvKJBtxAeRpvDyPssPPyc4hiD2pux+qqlcl+WCS\n85K8qbtvHx5rparq7Un+epInVtWxJIe7+42zU63UFUlekeSTi/OkSfJz3f3+wZlW6clJ3rK4+vI7\nkryjuzfuozob7ElJ3rvze2IOJHlbd988O9LK/WSSty52Yu5M8mPD86xcVV2QnU/L/Pj0LKfasx9D\nAoC9bC8fggaAPUuAAWCAAAPAAAEGgAECDAADBBgABggwAAz4PyWycpsM6xLVAAAAAElFTkSuQmCC\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x22baeec2ef0>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"eight_queens = NQueensCSP(8)\n",
"solution = min_conflicts(eight_queens)\n",
"display_NQueensCSP(solution)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The solution is a bit different this time. \n",
"Running the above cell several times should give you various valid solutions.\n",
"<br>\n",
"In the `search.ipynb` notebook, we will see how NQueensProblem can be solved using a heuristic search method such as `uniform_cost_search` and `astar_search`."
]
},
{
"cell_type": "markdown",
"source": [
"### Helper Functions\n",
"\n",
"We will now implement a few helper functions that will help us visualize the Coloring Problem. We will make some modifications to the existing Classes and Functions for additional book keeping. To begin we modify the **assign** and **unassign** methods in the **CSP** to add a copy of the assignment to the **assignment_history**. We call this new class **InstruCSP**. This will allow us to see how the assignment evolves over time."
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"import copy\n",
"class InstruCSP(CSP):\n",
" \n",
" def __init__(self, variables, domains, neighbors, constraints):\n",
" super().__init__(variables, domains, neighbors, constraints)\n",
" \n",
" def assign(self, var, val, assignment):\n",
" super().assign(var,val, assignment)\n",
" self.assignment_history.append(copy.deepcopy(assignment))\n",
" \n",
" def unassign(self, var, assignment):\n",
" super().unassign(var,assignment)\n",
" self.assignment_history.append(copy.deepcopy(assignment))"
]
},
{
"cell_type": "markdown",
Tarun Kumar Vangani
a validé
"Next, we define **make_instru** which takes an instance of **CSP** and returns a **InstruCSP** instance. "
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
Tarun Kumar Vangani
a validé
"def make_instru(csp):\n",
" return InstruCSP(csp.variables, csp.domains, csp.neighbors, csp.constraints)"
]
},
{
"cell_type": "markdown",
"We will now use a graph defined as a dictionary for plotting purposes in our Graph Coloring Problem. The keys are the nodes and their corresponding values are the nodes they are connected to."
{
"cell_type": "code",
},
"outputs": [],
Tarun Kumar Vangani
a validé
"neighbors = {\n",
" 0: [6, 11, 15, 18, 4, 11, 6, 15, 18, 4], \n",
" 1: [12, 12, 14, 14], \n",
" 2: [17, 6, 11, 6, 11, 10, 17, 14, 10, 14], \n",
" 3: [20, 8, 19, 12, 20, 19, 8, 12], \n",
" 4: [11, 0, 18, 5, 18, 5, 11, 0], \n",
" 5: [4, 4], \n",
" 6: [8, 15, 0, 11, 2, 14, 8, 11, 15, 2, 0, 14], \n",
" 7: [13, 16, 13, 16], \n",
" 8: [19, 15, 6, 14, 12, 3, 6, 15, 19, 12, 3, 14], \n",
" 9: [20, 15, 19, 16, 15, 19, 20, 16], \n",
" 10: [17, 11, 2, 11, 17, 2], \n",
" 11: [6, 0, 4, 10, 2, 6, 2, 0, 10, 4], \n",
" 12: [8, 3, 8, 14, 1, 3, 1, 14], \n",
" 13: [7, 15, 18, 15, 16, 7, 18, 16], \n",
" 14: [8, 6, 2, 12, 1, 8, 6, 2, 1, 12], \n",
" 15: [8, 6, 16, 13, 18, 0, 6, 8, 19, 9, 0, 19, 13, 18, 9, 16], \n",
" 16: [7, 15, 13, 9, 7, 13, 15, 9], \n",
" 17: [10, 2, 2, 10], \n",
" 18: [15, 0, 13, 4, 0, 15, 13, 4], \n",
" 19: [20, 8, 15, 9, 15, 8, 3, 20, 3, 9], \n",
" 20: [3, 19, 9, 19, 3, 9]\n",
"}"
]
},
{
"cell_type": "markdown",
Tarun Kumar Vangani
a validé
"Now we are ready to create an InstruCSP instance for our problem. We are doing this for an instance of **MapColoringProblem** class which inherits from the **CSP** Class. This means that our **make_instru** function will work perfectly for it."
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
Tarun Kumar Vangani
a validé
"coloring_problem = MapColoringCSP('RGBY', neighbors)"
]
},
{
"cell_type": "code",
Tarun Kumar Vangani
a validé
"metadata": {
Tarun Kumar Vangani
a validé
},
"outputs": [],
"source": [
"coloring_problem1 = make_instru(coloring_problem)"
]
},
{
"cell_type": "markdown",
"## BACKTRACKING SEARCH\n",
"For solving a CSP the main issue with Naive search algorithms is that they can continue expanding obviously wrong paths. In backtracking search, we check constraints as we go. Backtracking is just the above idea combined with the fact that we are dealing with one variable at a time. Backtracking Search is implemented in the repository as the function **backtracking_search**. This is the same as **Figure 6.5** in the book. The function takes as input a CSP and few other optional parameters which can be used to further speed it up. The function returns the correct assignment if it satisfies the goal. We will discuss these later. Let us solve our **coloring_problem1** with **backtracking_search**."
]
},
{
"cell_type": "code",
},
"outputs": [],
"source": [
"result = backtracking_search(coloring_problem1)"
]
},
{
"cell_type": "code",
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{0: 'R',\n",
" 1: 'R',\n",
" 2: 'R',\n",
" 3: 'R',\n",
" 4: 'G',\n",
" 5: 'R',\n",
" 6: 'G',\n",
" 7: 'R',\n",
" 8: 'B',\n",
" 9: 'R',\n",
" 10: 'G',\n",
" 11: 'B',\n",
" 12: 'G',\n",
" 13: 'G',\n",
" 14: 'Y',\n",
" 15: 'Y',\n",
" 16: 'B',\n",
" 17: 'B',\n",
" 18: 'B',\n",
" 19: 'G',\n",
" 20: 'B'}"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"result # A dictonary of assignments."
]
},
{
"cell_type": "markdown",
"Let us also check the number of assignments made."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"21"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"coloring_problem1.nassigns"
]
},
{
"cell_type": "markdown",
"Now let us check the total number of assignments and unassignments which is the length of our assignment history."
]
},
{
"cell_type": "code",