Leveraging Constraints: A Problem-Solving Strategy from Sudoku to Artificial Intelligence

Let’s begin with understanding the notion of constraints. In a problem-solving scenario, constraints are conditions or limitations that our solution must adhere to. Often, they are seen as barriers to solving the problem, but in many situations, they help in simplifying the problem by limiting the solution space.

Take the example of the game Sudoku, which is a prime example of a constraint satisfaction problem. In Sudoku, the constraint is that every row, column, and 3x3 box must contain all the digits from 1 to 9 with no repetition. This might seem like it makes the puzzle more difficult initially, but it’s these constraints that help us eliminate incorrect numbers from the possible solutions.

In Sudoku, the common strategy is to focus first on the squares, rows, or columns that are the most filled in. These areas are the “most constrained” because they have fewer options available for the remaining spots. By working on the most constrained areas first, we are more likely to find a clear path forward without hitting as many dead-ends or needing to backtrack.

This concept is also widely used in the field of artificial intelligence, where it’s known as the “Most Constrained Variable” or the “Minimum Remaining Values Heuristic.” For instance, let’s say you’re writing an AI program for a color-mapping problem - you want to color a map so that no adjacent regions have the same color. The Most Constrained Variable principle suggests that you should start by coloring the region with the most neighbors. By doing so, you’ll minimize the possibilities for the remaining regions and thus simplify the problem-solving process.

In general, working on the most constrained or the most obvious part of the problem first can lead to significant progress. It also helps in developing an understanding of the problem and can potentially stimulate the development of a complete solution. Solving the apparent parts often sheds light on the hidden aspects of the problem, providing the much-needed insight for the remaining parts.

The main lesson from sudoku is that we should look for the most constrained part of the problem. While constraints often make the problem difficult, they may also simplify our thinking about the solution because they eliminate choices.

There is a rule for solving certain types of problems in artificial intelligence called the Most Constrained Variable. This is also called the minimum remaining values heuristic. It means that in a problem where we are trying to assign different values to different variables to meet constraints, we should start with the variable that has the most constraints. We choose the variable with the most constraints on the remaining variable, the variable that has the lowest number of possible values.

If one part of the problem is heavily constrained, that’s a great place to start because you can make progress without worrying that you are spending time on work that will later be ignored. A related corollary is that you should start with the part that is obvious. If you can solve part of the problem, you can learn something from seeing your own code that will stimulate your imagination to solve the rest.