Here is a project that I did for Computer Science 472 - Foundations of Aritificial Intelligence. The goal of this project was to investigate search strategies. Here is the report, followed by the applet.

The set up of the propblem is that you need to color a grid so that each row and column has one of each color. Not hard to do from the begining, but you much harder if you pre-set colors. For refernece, chronological backtracking is just sequentially trying each next color and backtracking whenever there is no color. Foward checking is to check the most constrained squares first, which more rapidly discovers conflicts, and you can move on faster. Local Search is randomly setting colors, then finding conflicting squares and changing them until it works.

The source.

Geoffrey Hoffman

Stephen Ostermiller

October 20, 1997

Assignment 3

Documentation:

First a word on the features, and how to use the applet. Basically, to assign colors, click a square, an “x” will appear, then click a color. As you fill in the grid, the palette will reflect which are valid colors, and which are not. Colors may also be selected by press the numbers 0-9 and “-” for clear.

Buttons

• Clear Grid: Clears the entire grid, and all locks.
• Clear New Squares: Squares added manually or with the random fill or preset patterns are locked, so that when you press Clear New Squares, it will return you to your starting state.
• Percentage Fill Choice and Button: This will attempt to fill the grid with random (yet still valid) colors up to a specified percentage. These colors will be locked.
• Preset Pattern Choice and Button: This will set the grid up in a preset pattern, and the message box will contain the statistics about the patterns results. (More detailed statistics are below)
• Easy Solve: Just shows a trivial solution that Human Logic can easily find.
• A: Backtracking: Attempts to fill the grid with chronological backtracking. It will either 1) succeed, 2) time out after a set number of backtracks, or 3) will search the entire space and determine pattern is unsolvable.
• B: Forward Checking: Attempts to fill the grid with backtracking with forward checking. It will either 1) succeed, 2) time out after a set number of backtracks, or 3) will search the entire space and determine pattern is unsolvable.
• C: Local Search: Attempts to fill the grid with a local search. It will either 1) succeed or 2) time out after a set number of flips.
• Lock Color: Specifies whether you want it to assert only valid color choices, or it is de-selected, it will allow free placement of the colors.

Local Search Strategy

We tried a number of various strategies, and the final one is the one you see here. The applet first fills the remainder of the array randomly. It then scans the entire array, generating a list of squares that have conflicts (number of squares in it's row or column with the same color) that are equal to an updating Max. number of conflicts. It then chooses one of these nodes randomly. It then tries to find a safe color, i.e. one that is not in its row or column somewhere else. If not, then it sets it to the color that has the least number of occurrences in its row and column. It then repeats. It will repeat for a set number of times (at the moment, 500) and then it will randomly change some of the grid (the squares that were not preset). It first does it with 10 squares, then after another loop. 20. then 30. This way, if it keeps falling into a local minimum, it will keep putting it farther and farther away.

Forward Checking vs. Chronological Backtracking:

As far as we can tell, forward checking improves searches dramatically in all cases that we saw. (We ran several other tests not here). The logic behind this is that even though it is searching a similar space as the backtracking, instead of just expanding the next node in order, it expands the most constrained, which allows it to eliminate bad combinations a lot faster. The game here is that we are not looking for the optimal state, we are just looking for one solution.

Comments on Local Search

Due to the randomness of the Local Search, its results were all over the place, with very large standard deviations. The mean times were generally better than backtracking, and usually better than forward checking, though not always.

Pattern 1 was just a random assignment that happened to work. So, backtracking and local search ended up being very close, yet forward checking was substantially faster. Pattern 2 was made to be a little bit tougher for the organized searches, and forward checking took a little more time. Pattern 3 was specifically designed to make the order searches backtrack a lot, and it made both back tracking and forward checking take a lot more time, with only a few squares being preset.

From what we could tell, the run time of the local search was roughly dependent on the number of squares pre-assigned. The less that were pre-assigned, the better it did. We figure this has to do with the fact that there are far more solutions when there are less pre-assigned squares, and since it is searching some what randomly, and we only need to find one of any valid solution, it is more likely to stumble on one in a less constrained space. We did not test it, but we figure that there is a point where it will reverse, and get easier, as the space gets more and more constrained. (We did not have enough time to do a full statistical analysis on the algorithm)

More detailed analysis of the 3 preset patterns is in the table following.

Statistical Data On the Searches

The applet. (there are some re-draw bugs that have come out as Java went to newer versions, so if you see nothing, resize the window to see the result)

<---Return to Hoffy's Page

Last Modified: