AI without Machine Learning

The ability of a computer (or machine) to mimic human intelligence and perform human-like tasks, does not always rely on machine learning.

Oftentimes, AI and ML are used within the same definition, but these two are not the same thing. Not all AI Agents rely on Machine Learning models to make decisions. This post is a display of that aspect, exploring the Constraint Satisfaction Problem approach using Python, to solve Sudoku boards, really fast. I will try to break down the pieces, the algorithms and the heuristics as much as needed, to avoid getting this writing on the long side. Nevertheless, you can find the complete implementation here.

Fan fact; My interest in how these kind of algorithms and heuristics work started when I miserably failed a coding interview years back. But what can you do, we either win or learn. 😬

What is an Intelligent Agent and what’s a Constraint Satisfaction Problem?

In Artificial Intelligence, the Agent is an autonomous entity that acts upon an environment (physical or virtual), using sensors (or something that absorbs changes in state), and actuators (ways to take action) to achieve its goals. In addition, an intelligent agent may learn from the environment to achieve those goals.

Constraint satisfaction is the process of finding a solution, given some conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfy all the constraints of a given problem. A Constraint satisfaction problem can be modelled as a type of optimization problem. Moreover, the existence of a solution to such problem, can be viewed as a decision problem, such that it can be posed as a yes-no question and processed by a set of algorithms.

Examples of problems that can be modelled as CSPs

1. Scheduling and timetabling for air tickets or travel planners.
2. Routing for a fleet of vehicles with capacities used for delivery and route optimization.
3. Bin-packing where items of different sizes must be packed into a finite number of bins. Can also be used in containerized environments where an auto-scaling entity tries to place containers to the correct worker nodes or tries to pick the right computing power to execute workloads.
4. Image recognition with constraint satisfaction neural networks for identifying “objects” of interest in an image (although in this case, we do have learning layers).

To convert a problem to a CSP, our AI Agent is required to:

1. Create a variable set: X={X1,X2,...,Xn}
2. Create a domain set: D={D1,D2,...,Dn}
3. Create a constraint set with variables and domains: C={C1,C2,...,Cm}
4. Find an optimal solution: Using Algorithms and Heuristics

To put the above into perspective for solving a Sudoku board, the squares in a 9x9 grid, can be thought as 81 variables
S[1,1], S[1,2], ..., S[9,8], S[9,9] where the columns, the rows and the block constraints, can be expressed with a single relation: DIFFERENT

Following the same thought process, we also have 81 domains

Each domain holds the possible values for each variable. For example, if we start with a board that has an empty square on the top-left corner, then the domain for that square can be represented as: A1: [1,2,3,4,5,6,7,8,9], hence all possible values. If we have the value 5, then the domain for that square is automatically limited to A1: [5]. If we have the value 5 and the value 3 next to it, then the domains starting representation is A1: [5] and A2: [3] and so on. In a sense, having a starting configuration for our Sudoku board, helps us narrow down the possible values for each domain, like you would do using a pen, keeping notes on the sides of the board.

Sudoku Board

We also have 27 constraints, that all must be satisfied:

1. 9 row constraints (values 1 to 9 must be unique for each row):
   DIFFERENT(S[i,1], S[i,2], ..., S[i,9])
2. 9 column constraints (values 1–9 must be unique for each column):
   DIFFERENT(S[1,j], S[2,j], ..., S[9,j])
3. 9 block constraints (values 1–9 must be unique for each block):
   DIFFERENT(S[1,1], S[1,2], S[1,3], S[2,1] ..., S[3,3])
DIFFERENT(S[1,4], S[1,5], S[1,6], S[2,4] ..., S[3,6])
...
DIFFERENT(S[7,7], S[7,8], S[7,9], S[8,7] ..., S[9,9])

Then for those 27 constraints, we keep track of ALL the possible combinations and permutations for each row, column and block, for example, DIFFERENT[[A1,B1], [A1,C1], [A1,D1],...,[A1,I1]],...
In a way, we are setting the stage for our Agent’s algorithms, to have a source of truth for all the impossible configurations of the board.

On top, we create a map of neighbours for every variable on the board, to keep an indexed “record of concerns” for each variable. We will use this map in the ARC consistency algorithm to examine if the arcs between pairs of variables are consistent, in order to reduce the number of available values in each of the domains. As a reference, neighbours will also be used as a map in many other places like the Forward Checking algorithm to reduce the search tree after picking a value and the Heuristics to speed up the process. Below is a depiction of the neighbours of one of the values (7).

AC-3 Algorithm

The ARC consistency algorithm will alone solve a board if there is an initial configuration with reduced enough domain values, meaning that the board has plenty of values already assigned to variables. Nevertheless, it works like a filtering/preprocessing algorithm, where right off the bat, we can reduce the possible values of each domain, before forwarding the flow to our Backtracking solver. The process of removing a value from a given domain happens on the revise function, when a domain value is not bound by a constraint. Then, if a domain “loses” a value, the neighbours need to be rechecked, hence appending back to the queue of constraints.

AC3-Memory Usage report

The algorithm has a worst-case time complexity of O(A²D³) where A is the number of arcs and D is the size of the largest domain.

def ac3(sudoku):
    queue = list(sudoku.constraints)

    while queue:
        xi, xj = queue.pop(0)

        if revise(sudoku, xi, xj):
            if len(sudoku.domains[xi]) == 0:
                return False

            for xk in sudoku.neighbors[xi]:
                if xk != xi:
                    queue.append([xk, xi])

    return True

def revise(sudoku, xi, xj):
    revised = False

    for x in sudoku.domains[xi]:
        if not any([sudoku.constraint(x, y) for y in sudoku.domains[xj]]):
            sudoku.domains[xi].remove(x)
            revised = True

    return revised

Backtracking algorithm

In order to jump into our Backtracking algorithm, we need to quickly examine 2 heuristics and 1 algorithm that will help us speed up the process of searching for a solution in our decision tree. The MRV and LCV heuristics will help our Agent to select; the next best variables to examine, the proper ordering of the values to be tried, if any inferences can be made along the way (pruning) and if a failure can be detected early. Pruning is nothing more that a data compression technique that reduces the size of decision trees by removing sections of the tree, hence making our process smaller in size and more memory-efficient.

Most Constrained Variable heuristic (a.k.a. minimum remaining values)

This heuristic picks a variable that has no assignment of any value and has the fewest possible values remaining in its domain. Our goal using this heuristic is to take a fail-first approach, so we pick the variable most likely to cause a conflict. We want to have a fail-first approach when selecting variables to examine, in order to prune large portions of the search tree early.

def select_unassigned_variable(assignment, sudoku):
    unassigned = [v for v in sudoku.variables if v not in assignment]
    return min(unassigned, key=lambda var: len(sudoku.domains[var]))

Least Constraining Value heuristic

This heuristic prefers the value that rules out the fewest choices for the neighbouring variables in the constraint graph. It follows a fail-last approach where this time we select a value least likely to cause a conflict. We do that by sorting the possible values of a variable (domain), based on the number of conflicts that selecting a value might cause.

def order_domain_values(sudoku, var):
    if len(sudoku.domains[var]) == 1:
        return sudoku.domains[var]
    return sorted(sudoku.domains[var], key=lambda val: sudoku.conflicts(sudoku, var, val))

Forward checking algorithm

The idea behind injecting the forward-checking process into our backtracking algorithm, is to keep track of the remaining legal values for unassigned variables and to terminate searching, when any variable has no possible moves. Forward checking propagates information from assigned to unassigned variables. In a sense, it “looks” into the future and it provides an answer to what will happen to other variables, if we assign a value to one of them.

def forward_check(self, var, value, assignment):

        for neighbor in self.neighbors[var]:
            if neighbor not in assignment:
                if value in self.domains[neighbor]:
                    self.domains[neighbor].remove(value)
                    self.pruned[var].append((neighbor, value))

Backtracking search algorithm

This is our brute-force algorithm that our Agent uses to expand the tree of possible moves, while searching for a solution. Hence, its job is to build a set of all the solutions incrementally using a Depth-First approach, and with the help of our heuristics and forward checking algorithm above, it will do so, by cutting corners and “looking” into the future with improved efficiency.

Backtracking-Memory Usage report

The time complexity of backtracking can be defined as O(K^N), where K is the number of times the function calls itself. If the function calls itself two times, then its time complexity is O(2^N), and if it calls three times, then O(3^N) and so on.

def backtrack(assignment, sudoku):

    if len(assignment) == len(sudoku.variables):
        return assignment

    # Most Constrained Variable heuristic: select_unassigned_variables
    var = select_unassigned_variable(assignment, sudoku)

    # Least Constraining Value heuristic: order_domain_values
    for value in order_domain_values(sudoku, var):

        if sudoku.consistent(assignment, var, value):

            sudoku.assign(var, value, assignment)

            result = backtrack(assignment, sudoku)
            if result:
                return result

            sudoku.unassign(var, assignment)

    return False

Putting it all together

Running a sample of 400 Sudoku board configurations, our Agent was able to solve them in 26 seconds, with an average solving time of 66.25 ms, and with 3 of them solved by the AC-3 algorithm alone.

Final remarks:

How do you measure/visualize the memory used?

First, install the memory profiler: pip install -U memory_profiler
Then, install matplotlib to generate plots: pip install -U matplotlib
Next, add the @profile directive above a function that you want to measure:

from memory_profiler import profile

@profile
def backtrack(assignment, sudoku):
...

Then, run your script using the mprof run command to sample the memory usage:

mprof run driver.py 000530000005000600000190503000004000000000164100370800008000040010000008004700921

And last, plot the result of the generated .dat file using:

mprof plot --output=backtracking-plot.png

Interested in another example of an Intelligent Agent?

Take a look at my 2048-puzzle solver here, which uses the minimax algorithm with ab-pruning and iterative deepening to solve the 2048 game, along with multiple heuristics to inject different strategies for the Agent to follow.

Famous last words: People that worry a lot about AI today, are people with college smartness.