6-Constraint Satisfaction Problems

[Rishav159]

We can discuss the development in chapter 6 here.

[Rishav159]

I want to improve the already implemented AC-3 diagram. It's quite difficult to understand what is happening in it without imagining the constraint queue in the mind. Also, there seems to be a few JS errors associated with the implementation. The console shows Cannot read property '0' of undefined after the algorithm is completed. I thought maybe create a new issue to address this problem, but I will be replacing it anyways so decided against it.

My initial thoughts to improve the diagram:

• The last 2 constraints W != Y and W != Z seems useless. A diffconstraint rarely manages to reduce the domain of variable (it does that only if the domain of the target variable has already reduced to 1 value). So I suggest replacing them with some other constraints.
• The yellow coloring shows which 2 values are being considered but does not show for which constraint is it being considered. This lefts the reader to take a guess on what constraint is being checked. Maybe we can apply a different color to the constraint as well to indicate it is being checked.
• Since there is no queue shown, it is hard to see why and when some constraints are reconsidered. But, I believe even if we show the queue, it will be hard for the user to observe since the size will be very large. I am not sure what to do about this yet.
• Maybe in the end we can show the difference between the sizes of the state space that AC-3 reduced. For example in the current CSP, the original CSP had 9*5*7*6 = 1890 possible solutions. After AC-3, the reduced CSP has 4*4*5*6 = 480 possible solutions. That is a 74% reduction!

What are your thoughts ? @redblobgames

[redblobgames]

The existing diagram seems more of a “this demonstrates to the reader that we implemented the algorithm” (which was the goal last year) and not “this demonstrates to the reader how the algorithm works” (which is the goal this year). I think you should feel free to improve, reimplement, replace, or remove it. What are the concepts to show?

• Arcs
• Queue
• Constraint checking

Would the sudoku diagram be able to demonstrate these concepts? I think the reader might have an easier time with sudoku than with the abstract problem. I'm not sure.

[Rishav159]

Would the sudoku diagram be able to demonstrate these concepts? I think the reader might have an easier time with sudoku than with the abstract problem. I'm not sure.

I agree with this. I believe the important concept to show here is the algorithm itself; ie, why the algorithm is what it is. More specifically, it should show why the arcs associated with a node is re-added back to the queue if the domain reduces (because it may cause further reductions in other variables).

[Rishav159]

I have been thinking about this concept and it doesn't strike a chord on how should i approach it. I want to demonstrate the working of the AC-3 algorithm. The sudoku problem could work, but I am speculating that the queue will be too large for the reader to understand what is happening. Also, sudoku is a specific case where there is only one valid assignment which is the solution as compared to the map coloring problem where multiple solutions and assignments exists. I can't clearly grasp how a visualization focused on the AC-3 should be. I would like to know your thoughts on this @redblobgames. If this still doesn't sound convincing to us, maybe we should skip this one and come back later.

[redblobgames]

It happens. I recommend moving on to the next thing. Sometimes our brains will come up with ideas while we are working on other things. And sometimes there just isn't a good diagram for a concept.

[Rishav159]

Okay. I will move on to the next concept.

[redblobgames]

(Random thoughts to save for later) I guess what's nice about the Australia graph is that it's small and we're hoping that would allow for more detailed visualizations (such as showing all arcs). But AC-3 can't solve it (if I understand correctly). And what's nice about Sudoku is that it's something many readers will already understand the rules for. But it might be too big, and it might not show what AC-3 is capable of. For Sudoku though the diagram right now lets you click on a domain X and then it runs consistency with all other domains Y. We could show the arc consistency concept by going through the other (24?) domains Y one by one (with a timer/animation) and show the domain X being reduced. However it seems impractical to show the queue. But that might be ok — maybe we can show the arc consistency concept with sudoku and leave the queue for a different diagram.

[redblobgames]

This page has some constraint satisfaction problems other than what's in the AIMA textbook. I don't know whether they're good matches for AC-3 though http://www.teach.cs.toronto.edu/~csc384h/summer/Project/Project_ideas.html

• Gardening (wet/dry, shade/sunny, native/exotic)
• Stock investments (income, growth, risk)
• Meal plans (protein, carbs, calories)

[Ghost---Shadow]

For gardening, the equations can be modified

Y = X + 1
Z >= Y + 1
W != Y
W != Z

to

// Meet water requirements
Water Required For Plant A > Cell Water Capacity
Water Required For Plant B > Cell Water Capacity

// Soil type
Soil needed for A = Cell Type
Soil needed for B = Cell Type

// Cell id constraint
A cell id which meets water requirement = cell id which meets soil requirement

Then some sprites can be added to show which type of plants are placed where.

[redblobgames]

@Rishav159's list of more things that could be done for chapter 6:

• A diagram to demonstrate k-consistency
• Min-Conflicts algorithm for solving CSP by local search
• Topological Sort
• Tree-CSP-Solver