2.3.
4 8 queens problem
The problem is to place 8 queens on a chessboard so that no two queens are in the same
row, column or diagonal
The picture below on the left shows a solution of the 8-queens problem. The picture on
the right is not a correct solution, because some of the queens are attacking each other.
Figure 18
How do we formulate this in terms of a state space search problem? The problem
formulation involves deciding the representation of the states, selecting the initial state
representation, the description of the operators, and the successor states. We will now
show that we can formulate the search problem in several different ways for this problem.
N queens problem formulation 1
States: Any arrangement of 0 to 8 queens on the board
Initial state: 0 queens on the board
Successor function: Add a queen in any square
Goal test: 8 queens on the board, none are attacked
The initial state has 64 successors. Each of the states at the next level have 63 successors,
and so on. We can restrict the search tree somewhat by considering only those successors
where no queen is attacking each other. To do that we have to check the new queen
against all existing queens on the board. The solutions are found at a depth of 8.
63 successors
...
..
64 successors
Figure 19
N queens problem formulation 2
States: Any arrangement of 8 queens on the board
Initial state: All queens are at column 1
Successor function: Change the position of any one queen
Goal test: 8 queens on the board, none are attacked
Figure 20
If we consider moving the queen at column 1, it may move to any of the seven remaining
columns.
N queens problem formulation 3
States: Any arrangement of k queens in the first k rows such that none are attacked
Initial state: 0 queens on the board
Successor function: Add a queen to the (k+1)th row so that none are attacked.
Goal test : 8 queens on the board, none are attacked
Figure 21
We will now take up yet another search problem, the 8 puzzle.
2.3.5 Problem Definition - Example, 8 puzzle
5 4 1 42 73
6 1 8 248 5 864
7 3 2 37 68 5
Initial State Goal State
Figure 22
In the 8-puzzle problem we have a 3 3 square board and 8 numbered tiles. The board has
one blank position. Bocks can be slid to adjacent blank positions. We can alternatively
and equivalently look upon this as the movement of the blank position up, down, left or
right. The objective of this puzzle is to move the tiles starting from an initial position and
arrive at a given goal configuration.
The 15-puzzle problems is similar to the 8-puzzle. It has a 4 4 square board and 15
numbered tiles
The state space representation for this problem is summarized below:
States: A state is a description of each of the eight tiles in each location that it can
occupy.
Operators/Action: The blank moves left, right, up or down
Goal Test: The current state matches a certain state (e.g. one of the ones shown on
previous slide)
Path Cost: Each move of the blank costs 1
A small portion of the state space of 8-puzzle is shown below. Note that we do not need
to generate all the states before the search begins. The states can be generated when
required.
5 4
6 1 8
7 3 2
5 4 5 4 8
6 1 8 6 1
7 3 2 7 3 2
5 4
6 1 8 5 4 8 5 4 8
7 3 2 5 1 4 6 1
6 1
6 8 7 3 2
7 3 2
7 3 2
Figure 23
8-puzzle partial state space
2.3.6 Problem Definition - Example, tic-tac-toe
Another example we will consider now is the game of tic-tac-toe. This is a game that
involves two players who play alternately. Player one puts a X in an empty position.
Player 2 places an O in an unoccupied position. The player who can first get three of his
symbols in the same row, column or diagonal wins. A portion of the state space of tic-tac-
toe is depicted below.
x
ox
xo
ox x
x x x
xo xx o x x x ox
o ox x x
o
o
x
………..
xx x
xx
x
x xx oo
o o
Figure 24
Now that we have looked at the state space representations of various search problems,
we will now explore briefly the search algorithms.
2.3.7 Water jug problem
You have three jugs measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet.
You need to measure out exactly one gallon.
Initial state: All three jugs are empty
Goal test: Some jug contains exactly one gallon.
Successor function:Applying the
o action tranfer to jugs i and j with capacities Ci and Cj and containing
Gi and Gj gallons of water, respectively, leaves jug i with max(0,
Gi (Cj Gj)) gallons of water and jug j with min(Cj, Gi+ Gj) gallons
of water.
o Applying the action fill to jug i leaves it with Ci gallons of water.
Cost function: Charge one point for each gallon of water transferred and
each gallon of water filled
Explicit vs Implicit state space
The state space may be explicitly represented by a graph. But more typically the state
space can be implicitly represented and generated when required. To generate the state
space implicitly, the agent needs to know
the initial state
The operators and a description of the effects of the operators
An operator is a function which "expands" a node and computes the successor node(s). In
the various formulations of the N-queens problem, note that if we know the effects of the
operators, we do not need to keep an explicit representation of all the possible states,
which may be quite large.
