Chapter 5 – Recursion as a Problem-Solving Technique
One
of the most famous problems (puzzles) in computer science is the “Eight Queens
Problem” In this problem you are given a chessboard and 8 queens and are asked to
place the queens on the chessboard so that no queen can attack any other queen.
Just
for the fun of it, try solving the problem below:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Can you determine a strategy
to solve the problem?
What if you placed a queen somewhere in column 1 and then placed the next queen in a “safe” spot in column 2, and so on? Will this work? Would it work if you “backtrack” a little when you run into a problem?
Many computer problems
(especially those is Artificial Intelligence) use a method called
“backtracking”. The program follows a path as long as it can, but when it hits
a snag or roadblock or problem, it backs up only to a position that will allow
it to follow another path. Sometimes it has to back up all the way to the
beginning. This backtracking idea is well suited to our concept of recursion.
To solve the Eight Queens
Problem we could try a recursive algorithm like the one that follows (which is
given in pseudo-code):
placeQueens(currColumn)
//places queens in columns
numbered currColumn through 8
if(currColumn >8)
The problem is solved
else
while(unconsidered squares exist in currColumn and
the
problem is unsolved) {
Determine the next square in column
currColumn that
Is not under attack by a queen in an
earlier column.
if(such a square exists)
Place a queen in the square
placeQueens(currColumn+1) //
Try next column
if(no queen is possible in
currColumn+1)
Remove queen from
currColumn and consider
the next square in that column
endif
endif
endwhile
endif
Do you see the recursion? Do
you see the backtracking?
A complete (almost complete)
class that could be used to solve the problem may look something like this:
public
class Queens {
// squares per row or column
public static final int BOARD_SIZE = 8;
// used to indicate an empty square
public static final int EMPTY = 0;
// used to indicate square contains a queen
public static final int QUEEN = 1;
private int board[][]; // chess board
public Queens() {
//
-------------------------------------------------
// Constructor: Creates an empty square
board.
//
-------------------------------------------------
board = new int[BOARD_SIZE][BOARD_SIZE];
} //
end constructor
public void clearBoard() {
//
-------------------------------------------------
// Clears the board.
// Precondition: None.
// Postcondition: Sets all squares to EMPTY.
//
-------------------------------------------------
// To be implemented in Programming
Problem 1
} //
end clearBoard
public void displayBoard() {
//
-------------------------------------------------
// Displays the board.
// Precondition: None.
// Postcondition: Board is written to
standard
// output; zero is an EMPTY square, one is a
square
// containing a queen (QUEEN).
//
-------------------------------------------------
// To be implemented in Programming
Problem 1
} // end displayBoard
public boolean placeQueens(int column) {
//
-------------------------------------------------
// Places queens in columns of the board
beginning
// at the column specified.
// Precondition: Queens are placed correctly
in
// columns 1 through column-1.
// Postcondition: If a solution is found,
each
// column of the board contains one queen
and method
// returns true; otherwise, returns false
(no
// solution exists for a queen anywhere in
column
// specified).
//
-------------------------------------------------
if (column > BOARD_SIZE) {
return true; // base case
}
else {
boolean queenPlaced = false;
int row = 1; // number of square in column
while ( !queenPlaced && (row
<= BOARD_SIZE) ) {
// if square can be attacked
if (isUnderAttack(row, column)) {
++row; // consider next square in column
} // end if
else { // place queen and consider
next column
setQueen(row, column);
queenPlaced = placeQueens(column+1);
// if no queen is possible in next
column,
if (!queenPlaced) {
// backtrack: remove queen placed
earlier
// and try next square in column
removeQueen(row, column);
++row;
} // end if
} // end if
} // end while
return queenPlaced;
} // end if
} // end placeQueens
private void setQueen(int row, int column) {
//
--------------------------------------------------
// Sets a queen at square indicated by row
and
// column.
// Precondition: None.
// Postcondition: Sets the square on the
board in a
// given row and column to QUEEN.
//
--------------------------------------------------
// To be implemented in Programming
Problem 1
} //
end setQueen
private void removeQueen(int row, int
column) {
//
--------------------------------------------------
// Removes a queen at square indicated by
row and
// column.
// Precondition: None.
// Postcondition: Sets the square on the board
in a
// given row and column to EMPTY.
//
--------------------------------------------------
// To be implemented in Programming
Problem 1
} //
end removeQueen
private boolean
isUnderAttack(int row, int column) {
// --------------------------------------------------
// Determines whether the square on the
board at a
// given row and column is under attack by
any queens
// in the columns 1 through column-1.
// Precondition: Each column between 1 and
column-1
// has a queen placed in a square at a
specific row.
// None of these queens can be attacked by
any other
// queen.
// Postcondition: If the designated square
is under
// attack, returns true; otherwise, returns
false.
// --------------------------------------------------
// To be implemented in Programming
Problem 1
} //
end isUnderAttack
private int index(int number) {
//
--------------------------------------------------
// Returns the array index that corresponds
to
// a row or column number.
// Precondition: 1 <= number <=
BOARD_SIZE.
// Postcondition: Returns adjusted index
value.
//
--------------------------------------------------
// To be implemented in Programming
Problem 1
} //
end index
}
// end Queens
Recursion
is important in languages as well. For example, suppose that Java identifiers
could only consist of letters and digits and that a letter must come first. One
way that computer scientists have of describing this rule is as follows:
<letter> = a|b|c…x|y|z|A|B|C…X|Y|Z
<digit> = 0|1|2|3|4|5|6|7|8|9
<identifier> = <letter> |
<identifier> <letter> | <identifier> <digit>
Notice that the definition of an identifier is
recursive.
In the Java compiler (javac) you may find a method
that may look something like the following. This method could be used to
determine if the identifier that a programmer entered follows the rules or not.
isId(w)
//returns true if w is a legal Java identifier
if(w is of length 1)
if(w
is a letter)
return
true
else
return
false
else if(the
last character of w is a letter or digit)
return
isId(w minus the last character)
else
return
false
Your textbook goes through other language examples
like palindromes (do you know what they are?) and languages of the form AnBn.
If any of you will be taking the automata course next semester, you’ll learn
about these general forms of languages.
This is all we’re going to do in Chapter 5 and there
are a few of, I hope, fun problems for you to work on. On page 236, try
problems 2 and 5 and 9
Extra BONUS POINTS if you do a decent job with
problem 5 on page 240.
You
have learned about the two most basic data structures, the array and the linked
list. Some of the other data structures you will now learn about are really
nothing but special cases of an array or list structure. Usually these new
structures will use our previous structures, but will add some restrictions on
them – in particular how the user is able to add or remove items from the
structure.
A
stack is nothing more than what is known as a FIFO structure. FIFO stands for
First-In-First-Out. In other words if a person removes an item from a stack, it
must be the most recent item that was added to it. It is like having a pile of
shirts in a drawer and you can only place one on the top of the others, or
remove one from the top. You are not allowed to dig down into the pile to get
others. It is also like having an array that is turned on its end – like so:
|
|
|
|
|
2 |
|
9 |
|
3 |
|
7 |
|
5 |
-
the 5 is in array index 0
In the above array, if it were a stack, I would only
be allowed to remove the ‘2’ or put something else on the ‘top’ of the array.
There are only a few methods that need to be defined
to create a “stack”
1.
createStack( ) – creates an empty stack
2.
isEmpty( ) – determines whether a stack is empty
3.
push(newItem) – adds a new item to the top of the stack and throws an
exception is the insertion is not successful
4.
pop( ) – retrieves and then removes the top of the stack (i.e. the item
that was added most recently) and throws an exception if the deletion was not
successful
5.
popAll( ) – removes all items from the stack
6.
peek( ) – retrieves the top item in the stack but does not remove it,
throws an exception if the retrieval was not successful.
Before we get into the implementation details for a stack, let’s look at a common usage. Again let’s consider javac, the Java compiler. One of the things it must do is determine if you, the programmer, have entered a program with a balanced number of open and close braces – { }
When you look at a program, you can consider it as
one long string of characters with some braces thrown in here and there. For
example:
hwop{hwhv;{
vwejvpwj{ vwj} wov{ vwj}wqeyq}oish{owhe}hwqeoh}}
So how could you use a stack to check to see if the
braces are balanced? Easy. Every time you see and open brace, you push it on
the stack and every time you see a closed brace you pop one of the open braces
off of the stack. If your braces are balanced, at the end your stack should be
empty and there will have been no errors along the way.
stack.createStack( )
balancedSoFar = true
i = 0
while(balancedSoFar and i < length of aString)
ch =
character at position i in aString
++i
if(
ch is ‘{‘)
stack.push(‘{‘)
else if(ch is ‘}’)
if(!stack.isEmpty(
) )
openBrace
= stack.pop( )
else
balancedSoFar
= false
endif
endif
endwhile
if(balancedSoFar and stack.isEmpty( ) )
aString
has balanced braces
else
aString
does not have balanced braces
endif
We’ll end here and save the implementation details for another day!