Question 1
For the search problem with the following state space graph and heuristics, give the solution found by the A* search as well as the order of the states that the algorithm expands. Let us assume the tie is broken alphabetically.
Node
S
D
E
P
Q
B
A
C
H
R
F
G
Heuristic
11
7
6
9
8
4
2
3
5
4
2
0
4+4
6+2
D 3+7 9+6 E 11+3 5+6
1+9 P
S
0+11
Solution: S D E R F G
Nodes to be expanded: S D B A P E R F G
11+3 C
G 10+0
BCE Q
A* search expands the nodes by f(n) = g(n) + h(n), where g(n) is the cost of the path from the start to node n and h(n) is the heuristic of n
A 13+5H R7+4
16+8
F
8+2
Question 2
For the N-Queens problem, apart from the representation given in the lecture, please give another representation?
Variables:
, ,…, (where denotes the position (column) of a queen on row i of the chessboard)
Q1
Q2
Q3
Q4
Domain: Constraints:
One queen each column:
One queen each diagonal:
, e.g. when Q1 on column 2 ( ),Q2 cannotbeon3nor1 ()
Question 3
Consider the following 4×4 Sudoku problem, where each column, each row, and each of the four regions contain all of the digits from 1 to 4. Use backtracking search with forward checking and ordering to solve this problem. Give the order of all states to be visited. Let us assume that tie of cells is broken first from top to bottom and then from left to right, and tie of numbers is broken numerically.
Backtracking:
Check constraints as you go
Consider one variable at a layer
Forward Checking:
When assigning a variable, cross off anything that is now violated on all of its neighbours’ domains.
Ordering:
hoose the variable with the fewest legal values left in its domain.
3
4
2
4
Question 3
Consider the following the 4×4 Sudoku problem, where each column, each row, and each of the four regions contain all of the digits from 1 to 4. Use backtracking search with forward checking and ordering to solve this problem. Give the order of all states to be visited. Let us assume that tie of cells is broken first from top to bottom and then from left to right, and tie of numbers is broken numerically.
3
4
{1,2}
{1,2}
{1}
2
{1,3}
{1,3,4}
{1,2,4}
{1,3}
{1,2,3}
{1,2,3}
{1,2}
{1,3}
4
{1,2,3}
3
4
{1,2}
{1,2}
1
2
{3}
{3,4}
{2,4}
{1,3}
{1,2,3}
{1,2,3}
{2}
{1,3}
4
{1,2,3}
3
4
{1,2}
{1,2}
1
2
3
{4}
{2,4}
{1,3}
{1,2}
{1,2,3}
{2}
{1,3}
4
{1,2,3}
3
4
{1,2}
{1,2}
1
2
3
4
4
{1,3}
{1,2}
{1,2,3}
2
{1,3}
4
{1,3}
3
4
{1,2}
{1,2}
1
2
3
4
{4}
{1,3}
{1,2}
{1,2,3}
2
{1,3}
4
{1,3}
3
4
{1,2}
{1,2}
1
2
3
4
{2,4}
{1,3}
{1,2}
{1,2,3}
{2}
{1,3}
4
{1,2,3}
Question 3
Consider the following the 4×4 Sudoku problem, where each column, each row, and each of the four regions contain all of the digits from 1 to 4. Use backtracking search with forward checking and ordering to solve this problem. Give the order of all states to be visited. Let us assume that tie of cells is broken first from top to bottom and then from left to right, and tie of numbers is broken numerically.
3
4
1
{2}
1
2
3
4
4
{1,3}
{2}
{1,2,3}
2
{1,3}
4
{1,3}
3
4
1
2
1
2
3
4
4
{1,3}
{2}
{1,3}
2
{1,3}
4
{1,3}
3
4
1
2
1
2
3
4
4
{1,3}
2
{1,3}
2
{1,3}
4
{1,3}
3
4
1
2
1
2
3
4
4
1
2
3
2
3
4
{1}
3
4
1
2
1
2
3
4
4
1
2
3
2
{3}
4
{1}
3
4
1
2
1
2
3
4
4
1
2
{3}
2
{3}
4
{1,3}
Question 3
Consider the following the 4×4 Sudoku problem, where each column, each row, and each of the four regions contain all of the digits from 1 to 4. Use backtracking search with forward checking and ordering to solve this problem. Give the order of all states to be visited. Let us assume that tie of cells is broken first from top to bottom and then from left to right, and tie of numbers is broken numerically.
3
4
1
2
1
2
3
4
4
1
2
3
2
3
4
1
The order of states to be visited:
Cell21=1 Cell23 =3 Cell24 =4 Cell41 =2 Cell31 =4 Cell13 =1 Cell14 =2 Cell32 =1 Cell34 =3 Cell42 =3 Cell44 =1
Cell33 =2