The Problem
The 8-queens problem can be defined as follows: Place 8 queens on an (8 by 8) chess board such that none of the queens attacks any of the others. A configuration of 8 queens on the board is shown in figure 1, but this does not represent a solution as the queen in the first column is on the same diagonal as the queen in the last column.
Figure 1: Almost a solution of the 8-queens problem
Searching for a Solution
This problem can be solved by searching for a solution. The initial state is given by the empty chess board. Placing a queen on the board represents an action in the search problem. A goal state is a configuration where none of the queens attacks any of the others. Note that every goal state is reached after exactly 8 actions.
This formulation as a search problem can be improved when we realize that, in any solution, there must be exactly one queen in each of the columns. Thus, the possible actions can be restricted to placing a queen in the next column that does not yet contain a queen. This reduces the branching factor from (initially) 64 to 8.
Furthermore, we need only consider those rows in the next column that are not already attacked by a queen that was previously on the board. This is because the placing of further queens on the board can never remove the mutual attack and turn the configuration into a solution.
The EightQueensApp Java Application
EightQueensApp.jar is a Java application that explores the above search space using a number of (uninformed) search strategies. Download the application and double-click it. Alternatively, run the command "java -jar EightQueensApp.jar" from the command line. Either should bring up a window that looks essentially like the one shown in figure 2.
Figure 2: The window of the application
To search for a solution, first select a search strategy. Next, there are some configuration options for the search process. If the search space is to be searched as a graph, multiple paths leading to the same node will usually only be explored once. In a tree, search states that can be reached by multiple paths will also be explored multiple times. However, given our formulation of the search problem, there can only be one path to every state. The number of states to be generated can be limited to the given value, resulting in the search being abandoned at that point. For a depth-first search it is also possible to set a depth limit, meaning no states at a greater depth will be explored.
Finally, a trace of the search can be written to the window and/or a text file. The operation performed by a search engine consists of selecting a current search node and generating its successors, and the trace reflects this process. For example, the line:
current state: 11: <State (2qs): 7 3 0 0 0 0 0 0>>
indicates that the selected node contains the given state. In this state 2 queens are on the board. The following numbers then indicate the positions of all queens on the board, starting with the first column. In the example, the first queen is in row 7 (numbering of rows starts from 0 here), and the second queen is in row 3. The remaining zeros can be ignored as there are only two queens on the board.
The lines following this one in the trace describe the successor states that have been generated, for example:
successor state: 59: <State (3qs): 7 3 6 0 0 0 0 0>successor state: 60: <State (3qs): 7 3 1 0 0 0 0 0>successor state: 61: <State (3qs): 7 3 0 0 0 0 0 0>
So, expanding the given search node (11) resulted in three new search nodes (59, 60 and 61).
Even with tracing off the window will display some information about the search (which is not part of the trace). It will show how many states have been explored (the goal test has been performed and successors have been generated) and how many states have been generated (explored states plus fringe nodes). If a solution is found this will also be printed. Finally, the elapsed time taken to perform the search is printed. Note that writing the trace usually takes more time than searching itself.
References
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach, chapter 3. Prentice Hall, 2nd edition, 2003.
