Algorithm Design and Evaluation

x i = j means that the queen of row i is placed in column j. The candidate values for x i are from 1 to 8. The value j is accepted if the square (i, j) is not under any queen's attack (a queen can capture horizontally, vertically, and diagonally). To control for this, we need to record the state of the board before and after a queen is placed.

Horizontal control is unnecessary because each row is assigned exactly one queen. Vertical control is achieved by the array of variables aj with the convention that aj is equal to 1 if column j is empty. The two diagonals passing through cell (i, j) have one diagonal consisting of cells where i + j is constant, and the other diagonal consisting of cells where i - j is constant (2  i+j  16, -7  ij  7).

From there the first diagonal is recorded by the variable sequence bj (2  j  16) and the second diagonal is recorded by the variable sequence c j (-7  j  7) with the convention that these lines are also

empty if the corresponding variable has the value 1.

The state variables a j , b j , c j are initialized to the value 1 in the Init() function. Thus, the value j is accepted if and only if all three variables a i , b i+j , c i-j have the value 1. These variables must be reassigned to the value 0 when the ith queen is arranged and returned to the value 1 after calling Result() or Try(i+1).

Data organization:

- Array x to store the arrangement of the 8 queens found.

- Array c with elements c[j] to record the state of column j (c[j]=1 then column j has no queens lined up, c[j]=0 then column j has queens lined up)

- Array ct to record the state of total diagonal i+j:

+ ct[i+j]=1 then diagonal i+j has no queen touching it

+ ct[i+j]=0 then diagonal i+j has a queen pointing to it

- Array ch to record the state of the diagonal difference ij: To let the index of the array run from 1, so with ij running from -7 to 7, we set it to i-j+8 running from 1 to 15.

+ ct[i-j+8]=1 then diagonal ij has no queen touching it

+ ct[i-j+8]=0 then diagonal ij has a queen pointing to it

Functions:

init() //Initialization function

{

for(i=1;i<=8;i++) c[i]=1;

for(i=2;i<=2*8;i++) ct[i]=1;

for(i=1;i<=2*8-1;i++) ch[i]=1;

}

try(i) // Arrange the queen in row i;

{

for(j=1;j<=8;j++) if(c[j]&&ct[i+j]&&ch[i-j+8])

{

x[i]=j;

c[j]=0;

ct[i+j]=0; ch[i-j+8]=0; if(i==8)

ht(); // Function to return the found arrangement else try(i+1);

c[j]=1;

ct[i+j]=1; ch[i-j+8]=1;

}

main()

{

init();

try(1);

}

4.2.5. Find a path on the graph

1) Problem

G = (V, E) is a simple graph (directed or undirected). V = {1,. ., n} is the set of vertices, E is the set of edges (arcs). With s, t  V, find all paths from s to t.

Basic search algorithms:

DFS algorithm: Depth-first search. BFS algorithm: Breadth-first search.

2) Algorithm design

* The DFS algorithm searches the graph in depth. The algorithm visits all vertices that can be reached up to vertex t from a given vertex s. The later the vertex is visited, the sooner it will be finished (LIFO mechanism). So the algorithm can be organized by a recursive procedure.

Input: G = (V,E), s, t

Output: All paths from s to t (if any). DFS(s)

{

for ( u = 1; u <= n; u++)

{

if (acceptable)

{

Note it; if (u  t)

DFS(u);

else

Print path; skip recording;

}

We need to describe the graph data and the statements stated in the model. The graph will be represented by an adjacency matrix: a =(a ij ) 1<=i, j<=n and:

a ij = 1 if (i, j )  E

aij = 0 if (i, j )  E

Record visited vertices to avoid duplication when backtracking by marking.

We use a one-dimensional array Daxet[] with the convention:

Daxet[u] = 1 , u has been visited. Daxet[u] = 0 , u has not been visited.

The Daxet[] array is initially initialized to all 0.

The admissibility conditions for vertex u are that u is adjacent to v (a vu = 1) and u has not been visited ( Daxet[u] = 0).

To record the vertices in the path, we use a one-dimensional array Preoc[ ], with the convention:

Prior[u] = v where v is the vertex before u, and u is adjacent to v. We initialize the Prior[] array with all 0's.

The algorithm is further refined: Input G = (aij) nxn , s, t

Output All paths from s to t (if any).

DFS(s)

{

data[s] = 1;

for( u = 1;u <= n; u++)

{

if( a[s][u] && !data[u])

{

Before[u] = s; if ( u == t )

path();

else

DFS(u);

data[u] = 0;

}

The array previous[ ] stores the vertices on the path. If at the end of the algorithm, Daxet[t] = 0 ( Previous[t] = 0 ) then there is no path from s to t.

In case a path exists, exporting the path is exporting the array Prev[].

This operation can be written as duongdi()

{

printf(t,"<--"); j = t;

while (before[j] != s)

{

printf(pre[j],"<--"); j = pre[j];

}

printf(s);

}

* The BFS algorithm searches the graph breadth-first. The algorithm visits all vertices that can be reached up to vertex t from a given vertex s at each level of adjacency. The sooner a vertex is visited, the sooner it will be traversed (FIFO mechanism - First In First Out).

Input G = (V,E),

s, t  V;

Output

Path from s to t.

Describe :

Step 0 : A 0 = {s}.

Step 1: A 1 = {x  VA 0 : ( s, x)  E}.

Step 2: A 2 = {x ? V {A 0 ?A 1 } : ?y  A 1 , ( y, x)  E}.

....



i  1

Step i: A i = {x  V/ A k :  y  A i-1 , (y,x)  E} .

k  0

…

The algorithm has no more than n iterations, one of the following two cases occurs:

- If for all i, t  A i : there is no path from s to t;

- Conversely, t  A m for some m. Then there exists a path from s to t, and that is a shortest path from s to t.

In this case, we determine the vertices on the path by rotating

Backtrack from t to the vertices before t in each of the previous sets until s is encountered.

In BFS algorithm, the sooner a vertex is visited, the sooner it becomes visited, so visited vertices are stored in queue. A vertex becomes visited as soon as we have finished examining all of its adjacent vertices.

We use an array Daxet[] to mark the visited vertices, Daxet[i]=0 means vertex i has not been visited, Daxet[i]= means vertex i has been visited. This array is initialized with all 0s to indicate that at first no vertices have been visited.

An array before[ ] to store the vertices on the shortest path to be found (if any), meaning Before[i] is the vertex that comes before vertex i in the path. The array Before[ ] is initialized to all 0 to indicate that there are no vertices at the beginning.

The graph will be represented by the adjacency matrix: a =(a ij ) 1<=i, j<=n and: a ij = 1 if (i, j )  E

aij = 0 if (i, j )  E

Queue is organized as array. The algorithm can be written more elegantly as follows: BFS(s)

{

startingQ = 1, endingQ = 1; queue[cuoiQ] = s; Data[s] = 1;

while (headQ <= tailQ)

{

u = queue[dauQ]; dauQ++;

for ( j = 1; j <= n; j++)

if( a[u][j] == 1 && !Daxet[j] )

{

Comment :

cuoiQ++; queue[cuoiQ] = j; Daxet[j] = 1; Prev[j] = u;

}

We can see that each time we call DFS(s), BFS(s), every vertex belonging to the same connected component with s will be visited, so after executing the above function:

• Before[t] = 0 : there is no path from s to t,

• Conversely, there is a path from s to t. Then the solution is given by: t ← p1 = Prior[t] ← p2 = Prior[p1] ← … ← s .

4.2.6. The patrol horse problem

1) Problem

Given a chessboard with nxn squares. A horse is allowed to move according to the rules of chess, first placed at x 0 , y 0 . A horse's journey consists of going through all the squares of the board, each square exactly once. Give the journeys (if any) of the horse.

2) Algorithm design

The obvious solution is to consider whether a further move can be made. The first diagram might be sketched as follows:

Try(i)

{

for ( j = 1 -> k)

if ( xi accepts possibility j)

{

Determine xi according to ability j; Record state;

if( i < n 2 )

Try(i+1); else

Record test; Return status;

}

To describe an algorithm in detail, we must specify how to describe data and operations, that is:

- Chessboard performance.

- Options for xi

- How to determine xi according to j.

- How to get new state, return old state.

- Record the test.

* We will represent the chessboard with a square matrix of order n: h[n][n] where h[i][j] corresponds to the cell in row i, column j (1 ≤ i, j ≤ n) and use the elements of the matrix to record the horse's movement with the following convention:

h[x][y] = 0: The horse has not passed through cell <x,y>;

h[x][y] = i : Cell <x,y> the horse passed through at step i (1  i  n 2 ).

* What are the options for xi? These are the horse moves that xi can accept.

With starting square <x,y> as shown in the figure, there are a total of 8 squares <u,v> that the horse can go to. Suppose they are numbered from 0 to 7 as shown below:

(The cell with the asterisk * is the cell in row x column y where the horse is standing)