Discovery can be used to analyze and explain program traces, either for didactic or debugging purposes. This project shows the progress of two backtracking algorithms during their search for a solution of the n-queens problem. You need some computer science background in order to understand it.

The n-queens problem

The n-queens problem consists of placing n queens on an nxn checker board in such a way that they do not threaten each other, according to the rules of the game of chess. Every queen on a checker square can reach the other squares that are located on the same horizontal, vertical, and diagonal line. So there can be at most one queen at each horizontal line, at most one queen at each vertical line, and at most one queen at each of the 4n-2 diagonal lines. Furthermore, since we want to place as many queens as possible, namely exactly n queens, there must be exactly one queen at each horizontal line and at each vertical line.

A common way to solve this problem consists in trying to put the queens on the board squares one after the other. If one queen threatens the newly introduced queen, we withdraw the queen and search for another position. If we cannot find a solution, we choose to remove a queen already positioned, assign it another position that has not yet been used, and start the search again. This last operation is called a backtrack, and the whole strategy is called a trial-and-error algorithm. It is known that for n = 8, there are exactly 92 solutions, or less if you consider symmetric solutions as equal.

Here we analyze the internal working of a trial-and-error algorithm that was run for n=39.

The backtracking algorithms

This sample data comes from two algorithms that have been tested for this problem.

Both algorithms try to put a queen at the square (x,y) for various x, y between 1 and n, one after the other. (x denotes a vertical line on the chessboard, and y denotes a horizontal line.) They do so according to a fixed order for x, x₁, x₂, ... x_n, say using different y values for each one of them. After a queen has been set, the next one is tried, and so on. When no queen can be positioned, that is, when no value of y is available for it due to horizontal and diagonal threats of already positioned queens, the algorithm unsettles the last previously positioned queen; this is called backtracking. When a queen is positioned, its effect on the other (not yet filled) horizontal lines is computed; this is called constraint propagation.

The difference between the algorithms lies in the sequence of x_i. The algorithm called firstfail uses the sequence 1, 2, ..., n, that is, it attempts to position the first queens near the border. The algorithm called firstmid uses the sequence (n+1)/2, (n-1)/2, (n+3)/2, (n-3)/2, (n+3)/2, ..., 1, n, that is, it attempts to position the first queens near the center of the board.

We can easily guess that firstmid will find a solution earlier than firstfail, but it is hard to understand why. This is where ILOG Discovery comes in.

The data tables

Each algorithm produces one record of output each time it positions a queen on the checker board to try. So the minimum number of records is equal to the number of columns and rows of the board. Sometimes, positioning the queen will prevent positioning the remaining queens (a backtrack). In this case, one row is added to try to position the same queen on another column.

Each record consists of:

Path

This is a string indicating the current position in the search space. The length of the string denotes the number of queens already positioned. The number at each step indicates the number of trials that have been made to position the queen at the current location. For example, the string /0/1/1/4/2/7 denotes that 5 queens have been positioned so far (omit the leading 0), that the first and second queens are currently in their first tried position, that the third one is in its 4th attempt, the fourth queen in its 2nd attempt, and that for the fifth queen the 7th attempt is currently being tried.

NodeNb

The node number, also denoted by "RowNumber" in the ILOG Discovery GUI. This is a number which is incremented each time, for each record. So this number provides a discrete timescale, which allows us to look at the progress of the backtracking algorithm.

Var

The "variable" number. This is the x coordinate at which a queen is positioned.

Val

The "value". This is the y coordinate at which a queen is positioned. In terms of constraint notation, it is the value of an x variable.

Kind

This is an indication of what is going on in the algorithm. There are three possible values: choice, which means that the search continues with the next queen, failure, which means that the search continues with a new position for the last queen, and finally solution.

PropNb

Number of propagation events. This is the number of value reduction attempts on a variable performed at this step.

EvtNb

Number of events. This is a combination of the other types of events.

RedNb

Number of reductions. This is the number of variables whose possible value set becomes more constrained than it was before this step.

WakNb

Number of wakeups. This is the number of constraints that are marked as "interesting" for the following steps.

NbFail

Number of failures that will occur starting from the current position. This is computed a posteriori; this value is obviously not known at the time the algorithm reaches this step.

NbSol

Number of solutions that will be found starting from the current position. This is always 0 or 1, since the algorithms stop searching when they have found a solution. This value too is obviously not known at the time the algorithm reaches this step.

SolPerCent

Percentage of solution. This is computed as NbSol / (NbSol + NbFail) * 100. The higher this value, the "nearer" the algorithm is coming to the solution.

The Variable/Value diagrams

The two first views represent a (x,y) diagram of the progress of each algorithm. Each record label, size and color has been set to "Node Number", that is, to the order in which the queens are placed on the checker board. So, large and dark circles represent the first queens positioned on the board, while clear and small ones represent queens positioned late in the process.

first fail strategy	first mid-mid strategy

These two visualizations explain clearly the difference between the strategies, and why the first-mid-mid strategy is more efficient.

At a first glance, you see that there are more points in the first view, especially in the top-left corner. This indicates that more trials have been made in the first case to position queens and reposition them. You see also that the points in the second view are more spread, providing a good hint as to why this algorithm is more successful: by spreading the queens as much as possible, the chances of a conflict are reduced.

You also see that repositioned queens are mostly represented by small and clear spots, indicating that the algorithms try to keep queens placed early in the process and reposition those that have been placed late, rather than choosing at random a queen to reposition when a conflict occurs (depth-first strategy).

Finally, by following the increments in the number, you get a good understanding of how each algorithm chooses to position queens one after the other: the first-fail strategy starts in the bottom left corner, then proceeds with "knights steps" toward the right. At some point (around 19), it cannot go further right, and tries to fill the gaps. This is where the algorithm starts to fail numerous times (after step 27), because the space left is confined to small holes in the top-left corner.

The first mid-mid strategy starts instead from the center, and proceeds in a spiral-like fashion, spreading queens as much as possible. We can see that this strategy is quite successful, as only a few backtracks are needed at the very end.

Multiple bar charts

The next two views are bar charts of all fields of the records. Although less didactic, they show more of the inner details of the algorithms. Therefore, they should be more useful to the trained eye that wants to find out quickly some pathological behavior of the algorithms.

first mid-mid strategy
first fail strategy

The views are sorted by node number (order of the search tree, visible by the growing area in the first column).

You can first get a good notion of the two differing strategies by observing columns 2 and 3 (Var and Val), similar to the variable/value diagram. You notice that in the first strategy, the Val column increases steadily, up to the first 25% of the exploration. Then the chosen values stay more or less in the upper range, while the corresponding variables (Var rows) stay in the bottom range (corresponding to a search concentrated on the top-left corner of the checker board). Conversely, the first mid-mid strategy spreads the values and chosen variables much more evenly.

By observing the Kind and NbFails column, you notice much more failures occurring in the first fail strategy, and the failures happen very early in the process (just after the first 25% of the process).

The PropNb column shows that, after the first fails (first 25% in the first fail, last 25% in the first mid-mid strategies), the number of constraints and tests, which was slowly decreasing, becomes much more variable: this is because each backtrack has a lot of consequences on the available space to put the queens.

The EvtNb, RedNb, and WakNb columns are particularly significant as to why the first fail strategy is inefficient: in the first part of the first fail process, a lot of wakeups and reductions occur, meaning the available choices are restricted: there is far less room available to position other queens. Although reducing the search space very rapidly is a good thing if the process only eliminates invalid positions, it is a bad thing in heuristic based searches: many positions that could be valid are eliminated. After the first massive reductions, almost no events and no reductions are performed at each step. Thus, the search space is not reduced anymore, and the algorithm has to backtrack, as no solution can be found in the few remaining possibilities. By contrast, wakeups and reductions decrease much more evenly in the first mid-mid strategy, showing that the search domain is reduced in an orderly fashion.

Many more observations can be achieved with this view, for instance by sorting on the Kind column to notice that fails produce much more wakeups and propagations than choice nodes, or by sorting by variable and value to get a sense of how each algorithm explores the search space.

While it is not always possible to readily see all interesting properties in a parallel histogram, this type of visualization usually provides very good hints about other aspects of a process that should be studied with care. Hence, parallel histograms are a very good visualization to use to start exploring the behavior of a process.

Treemaps

The last two views are treemaps of the first fail process, showing the search tree structure and where most choices and processing is performed.

packed map of the search tree (focused on the lower levels of the tree)	treemap of the search tree (focused on the lower levels of the tree)

On the first view, we see the node levels in a packed map, colored according to whether the node is a choice or a fail. We can notice that at depth 27, numerous trials have been made to place the queen: steps 27, 28, 46, 47, 77, 78, 88 and 89 are trials to place a queen on the same row at a different column. The algorithm has spend most of its time trying to position this queen. The second view presents the same tree, but laid out as a treemap. While the order in which nodes follow each other is less readable, more room is available to show each step of the process. The labels on the nodes help remember the order in which steps are performed. It becomes possible to associate further attributes with each node, showing for instance which variable or value has been assigned at each step.

Finally, with some practice at viewing treemaps and parallel histograms, it becomes possible to use much more sophisticated views that show both detail and structure information at the same time. The following view displays both the search tree and the values at each level:

Parallel histograms embedded in treemap (focused on the lower levels of the tree)

What's next

We hope this tour of a simple problem has given you ideas as to how Discovery can be used to debug and optimize programs by analyzing their traces. Instrumenting code to output meaningful statistics is usually done often and easily, but rarely are the generated traces used in a quantitative and structural manner to observe the overall behavior of a program. Discovery, being quite flexible, enables you to read traces for nearly any kind of program.

Up to Data Sets.