|
|
by Marko Riedel
The n-queens problem consists in placing n non-attacking queens on an n-by-n chess board. A queen can attack another queen vertically, horizontally, or diagonally. E.g. placing a queen on a central square of the board blocks the row and column where it is placed, as well as the two diagonals (rising and falling) at whose intersection the queen was placed.
The algorithm to solve this problem uses backtracking, but we will unroll the recursion. The basic idea is to place queens column by column, starting at the left. New queens must not be attacked by the ones to the left that have already been placed on the board. We place another queen in the next column if a consistent position is found. All rows in the current column are checked. We have found a solution if we placed a queen in the rightmost column. A solution to the five-queens problem is shown in Figure 4.
Recursion is the obvious choice to implement this algorithm. We have an additional requirement, however. The user should be able to run the search step by step as well as automatically. E.g. she may want to halt the search at the middle column and observe how subsequent queens are placed. We would have to somehow stop and restart a sequence of nested calls if recursion were used. We record the state of the search instead. First, we record where queens have so far been placed on the board. Second, we record which row of the rightmost column we are currently checking.
The GUI is simple. We draw the board and the queens that have so far been placed. Placed queens are drawn in black. The board is drawn in blue during backtracking and in green if a solution was found. The queen that we are currently trying to place is drawn in red. The application’s menu lets the user single-step through the search or choose to run it automatically. The algorithm returns to the initial position after all positions have been searched.
The application’s structure is straightforward. There are two classes: a controller and a subclass of NSView. The controller is the application’s delegate. It parses command-line arguments, sets up and responds to the main menu and controls the timer that is used during automated searches. The view draws the board and knows how to move from one state of the search to the next.
We start by including the usual headers and define a constant that determines the width in pixels of a single cell of the board. The class QView:NSView represents and draws the board. Its instance variables store the size of the board, the number of solutions found during the current run and the state of the search. The latter is determined by the array board, whose indices correspond to columns and values to rows. It records where queens have been placed. The value of candidate records where in the rightmost empty column we are trying to place the next queen.
There are only a few methods in the implementation of QView. The initializer creates a view of the right size for the given dimension (width/height). The method drawRect: is where the view draws itself. The most important method is next, which advances from one state of the search to the next. There is a method that returns a boolean that indicates whether the current state of the board represents a solution.
The initializer is straighforward. It invokes the initializer of its superclass NSView with a rectangle of the appropriate dimensions. It creates the mutable array that holds the board. It is empty because initially there is no queen on the board. We start at column zero, with the bottom position being the first of d positions that must be checked, hence the value of candidate is zero. The counter for the number of solutions that have been found is set to zero.
The method drawRect is NSView’s designated draw method where the view draws itself. The background of the board is green if the current state of the board represents a solution and blue otherwise. The variable mx holds the width and height of the view in pixels.
The next step is to draw the grid, which consists of 2n + 2 lines, n + 1 horizontal ones and n + 1 vertical ones. The loop draws the lines in pairs, moving in parallel from bottom to top and from left to right.
We now draw the queens using the data stored in the array board. A queen is represented by a black filled circle whose radius is a quarter of the cell size. The queen is centered in the respective cell.
It remains to draw the queen that is currently being checked. It is farthest to the right and hence its column index is the number of queens already placed. The value of candidate determines the row.
We move on to the most important part of this recipe, i.e. the method that takes the search from one state to the next. We first extract the number of queens that have been placed on the board. The current candidate resides in the column to the right of the rightmost queen, where candidate determines in what row the candidate is placed. The latter value increases during the search. It starts at the bottom row and is incremented until the top row is reached, one increment per state change.
The candidate is admissible only if it is consistent with the queens that are already on the board, i.e. if it is not attacked by/does not attack any of these queens. We check each of them in turn. If the candidate is in the same row or column or diagonal then the position is not consistent. Rows and columns are easy to check. Use the following observation for diagonals. A falling diagonal has the equation y = -x + p. Two queens that lie on the same falling diagonal have the same value for y + x. A rising diagonal has the equation y = x + p. Two queens that lie on the same rising diagonal have the same value for y - x. A candidate is consistent if it passes the check for all queens that are already on the board.
If the candidate’s position is consistent, then we place a queen on the board and position the next candidate at the very bottom of the next column. The consistency check is also run if a solution has been found. It fails in this case because all available rows are blocked. Hence no new extra queen is ever added to the right of the right side of the board, and a solution leads to the else clause, where we increment the solution count, remove the rightmost successfully placed queen and make the cell just above it the new candidate we must check. We move the candidate up one cell otherwise, i.e. when the position is not consistent.
We backtrack to the rightmost column that has not been checked completely. A row value of d indicates that a column has been checked. We move backwards from the right to the left, eliminating columns that we have checked. The new candidate position in a given column is one cell above the previous position, hence the increment.
There remains some housekeeping to do. We can detect the transition from the last state to the first by checking whether the previous state was the top position of the first column. If this is the case, then we can output the number of solutions found and reset the solution counter to zero.
The method triggers a redisplay at the end since the state of the board has certainly changed.
Sometimes the controller needs to know whether the current state of the board represents a solution or not. This is the purpose of isSolution. We have a solution if the number of queens on the board equals the number of rows/columns of the board.
We are now ready to move on to the controller. Recall that the user may step through a search or run it automatically. The latter case requires a timer. We define two constants that determine how much time elapses between firings of the timer. It fires quickly (after 0.15 seconds) if the current position does not represent a solution, and waits a full five seconds otherwise.
The controller obviously needs to keep track of the QView. It also stores whether the search is currently running automatically or not. There is an invocation for use with the timer (we use the same invocation again and again). The controller also stores the timer.
The controller is the application’s delegate and applicationDidFinishLaunching: is its most important method, where it initializes the menu, creates the window with the board and prepares for use of the timer. The three methods runSearch:, haltSearch: and next: are invoked through clicks on the application’s main menu. They run the search, halt it or advance it by a single step, respectively. The method validateMenuItem: enables and disables the corresponding entries on the main menu according to the run state of the application. The method tick is invoked when the timer fires.
The method validateMenuItem: recognizes menu items by tags. This is recommended for large applications where internationalization plays a role; i.e. we do not want to depend on the title of an item, as it may change. (Thanks Fabien Vallon for the hint.)
The first thing applicationDidFinishLaunching: does is to query the command line arguments. The second argument contains the size of the board.
The next step is to build the application’s menu and set the tags of each item. There are three entries to control the search: run, halt and next. The fourth entry of the menu quits the application. We assign and display the menu.
We require exactly one argument, namely the size of the board.
The command line argument is a string. We require a scanner to retrieve the integer value from the string. We throw an exception if the scanner fails or the board is to small (min. is a two by two).
The intial state is step mode, i.e. we are not running.
We are ready to instantiate the QView that will perform the search and display the board.
The next step is to build the window. The size of the content rectangle is equal to the size of the view, since it will be the content view of the window. We allocate and initialize the window, which is titled, but not resizable. The title of the window indicates what size of queens problem we are solving.
We place the view in the window, center it and make it appear on screen.
The last step is to create the one invocation that will be used with all timers. It captures the target object (the controller) and the selector (tick). It is retained because it must persist throughout the lifetime of the application.
The method runSearch: is invoked via the main menu. It sets the internal state to “running” and schedules a timer that fires at FAIL_PAUSE intervals.
The method haltSearch: resets the internal state to “halted” and invalidates the timer, which stops firing and is autoreleased.
