In: Computer Science
In this case study, your task is to study different search algorithms to solve the N-Queens Problem which has been presented in class. We will focus on the incremental formulation in which we add a queen to any square in the leftmost empty column that is not attacked by any other queen. We will compare the following algorithms:
1- Breadth-first Seatch (BFS)
2- Depth-first Search (DFS)
3- Simulated Annealing (SA)
4- Hill Climbing (HC)
Question is:. Using any of the mentioned algorithims, is there a solution for the 4-Queens Problem? Demonsrate your answer.
N-Queen Problem using Hill climbing algorithm
The N Queen is the problem in which we have to place N chess queens on an N×N chessboard so that no two queens may be able to attack each other.
Scenario
1: N = 4
Queens
Output by applying Hill
Climbing Algorithm:
0 1 0
0
0 0 0
1
1 0 0
0
0 0 1
0
Explanation:
The
Position of queens are:
1 – {1,
2}
2 – {2,
4}
3 – {3,
1}
4 – {4,
3}
In the
example mentioned above we have placed all 4 queens in that manner
that no two queens are attacking each other. Therefore, we will
able to solve the problem using Hill Climbing
Algorithm.
Scenario
: N = 8
Queens
Output by applying Hill
Climbing Algorithm: 0 0 0 0 0 0 1
0
0 1 0 0 0 0
0 0
0 0 0 0 0 1
0 0
0 0 1 0 0 0
0 0
1 0 0 0 0 0
0 0
0 0 0 1 0 0
0 0
0 0 0 0 0 0
0 1
0 0 0 0 1 0
0 0
The most popular algorithm - Backtracking to the most popular algorithm to solve N Queen problem,
We will use to Hill climbing Algorithm to with AI approach to solve the problem.
Various terminologies used in the problem are as follows –
· Notion of a State – A state in N queen problem is any configuration of the N queens on the N X N board. Also, to decrease the search space we can add an additional constraint that there can only be a single queen in a particular column. A state in the program is implemented using an array of length N, such that if state[i]=j then there is a queen at column index i and row index j.
· Notion of Neighbours – Neighbours of a state are other states with board layout that vary from the present state’s board layout with consideration to the position of any of a single queen. That queen differs a state from its neighbour may be evacuated anywhere in the same column.
· Function proposed for optimization
– Local search is an optimization
algorithm that searches the local space to enhance a function that
takes the state as input and gives some value as an output. The
value of the objective function of a state related to that context
is the number of duos of queens attacking each other. Our Goal
should be to find a state with the minimum objective value. This
function must has a maximum & minimum value of NC2 and 0
respectivily.
Algorithm:
1. We start with a random state(i.e, assuming arbitrary configuration of the board).
2. Firstly we Scan through all possible adjutants neighbours of the current state and shift to the neighbour with the highest objective value, if we found any. And if there is no one exist, i.e. a neighbour, with objective strictly higher than the current state but exists one with equal then shift to any random neighbour.
3. We will repeat step 2, until the state whose objective is strictly higher than all it’s neighbour’s objectives, is found and then go to step 4.
4. The state identified after the local search is either the local best or the global best. There is no way of avoidance of local goals but adding a random neighbour or a random restart each time a local best is come across thus increases the chances of achieving global best.
5. Output the state and return.
Observation - It is easily noticeable that the global best in our case is 0 since it is the minimum number of pairs of queens that can attack each other. The random restart has a higher chance of reaching global best but we can still use chance neighbour because problem of N queens does not has a high number of local best and random neighbour is faster than random restart.
· Findings in the END after applying the algorithm:
1. Random Neighbour which outflows shoulders but only has less chance of escaping local best for sure.
2. Random Restart in which both escapes shoulders and has a high chance of escaping local best for sure.
// Code for
solving N Queen Problem using Hill climbing Algorithm in C++
Language
#include
<iostream>
#include <math.h>
#define
N 4
using namespace std;
// A
utility function that configures the 2D array "board" and array
"state" randomly to provide a starting point for the
algorithm
void configureRandom(int board[][N], int* state)
{
// Seed
for the random function
srand(time(0));
//
Iterating through the
// column indices
for (int i = 0; i < N; i++) {
// Getting a random row index
state[i] = rand() % N;
// Placing a queen on the
// obtained place in
// chessboard.
board[state[i]][i] = 1;
}
}
// A
utility function that prints
// the 2D array "board".
void printqboard(int board[][N])
{
for (int i
= 0; i < N; i++) {
cout << " ";
for (int j = 0; j < N; j++)
{
cout <<
board[i][j] << " ";
}
cout << "\n";
}
}
// A
utility function that prints
// the array "state".
void printqstate(int* state)
{
for (int i
= 0; i < N; i++) {
cout << " " << state[i]
<< " ";
}
cout << endl;
}
//
Function to compare
// two arrays, state1 and state2 and
// returns true if equal
// and false otherwise.
bool comparestate(int* state1, int* state2)
{
for (int i
= 0; i < N; i++) {
if (state1[i] != state2[i]) {
return
false;
}
}
return true;
}
//
Function that fills
// the 2D array "board" with
// values "value"
void fill(int board[][N], int value)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
{
board[i][j] =
value;
}
}
}
//
Function that calculates the
// objective value of the
// state(queens attacking to ach other)
// using the board by the
// following logic.
int calculateobj(int board[][N],
int* state)
{
// For
each queen in a column, we check
// for other queens falling in the line
// of our current queen and if found,
// any, then we increment the variable
// attacking count.
// Number
of queens attacking each other,
// initially zero.
int attacking = 0;
//
Variables to index a particular
// row and column on board.
int row, col;
for (int i = 0; i < N; i++) {
// At each column 'i', the queen is
// placed at row 'state[i]', by
the
// definition of our
state.
// To the left of same row
// (row remains constant
// and col decreases)
row = state[i], col = i - 1;
while (col >= 0
&&
board[row][col] != 1) {
col--;
}
if (col >= 0
&&
board[row][col] == 1) {
attacking++;
}
// To the right of same row
// (row remains constant
// and col increases)
row = state[i], col = i + 1;
while (col < N
&&
board[row][col] != 1) {
col++;
}
if (col < N
&&
board[row][col] == 1) {
attacking++;
}
// Diagonally to the left up
// (row and col
simoultaneously
// decrease)
row = state[i] - 1, col = i -
1;
while (col >= 0 && row
>= 0
&&
board[row][col] != 1) {
col--;
row--;
}
if (col >= 0 && row
>= 0
&&
board[row][col] == 1) {
attacking++;
}
// Diagonally to the right down
// (row and col
simoultaneously
// increase)
row = state[i] + 1, col = i +
1;
while (col < N && row
< N
&&
board[row][col] != 1) {
col++;
row++;
}
if (col < N && row <
N
&&
board[row][col] == 1) {
attacking++;
}
// Diagonally to the left down
// (col decreases and row
// increases)
row = state[i] + 1, col = i -
1;
while (col >= 0 && row
< N
&&
board[row][col] != 1) {
col--;
row++;
}
if (col >= 0 && row <
N
&&
board[row][col] == 1) {
attacking++;
}
// Diagonally to the right up
// (col increases and row
// decreases)
row = state[i] - 1, col = i +
1;
while (col < N && row
>= 0
&&
board[row][col] != 1) {
col++;
row--;
}
if (col < N && row >=
0
&&
board[row][col] == 1) {
attacking++;
}
}
// Return
pairs.
return (int)(attacking / 2);
}
//
function that
// generates a board configuration
// given the state.
void genboard(int board[][N],
int* state)
{
fill(board, 0);
for (int i = 0; i < N; i++) {
board[state[i]][i] = 1;
}
}
//
Function that copies
// contents of state2 to state1.
void copythestate(int* state1, int* state2)
{
for (int i
= 0; i < N; i++) {
state1[i] = state2[i];
}
}
//
Function gets the neighbour
// of the current state having
// the least objective value
// amongst all neighbours as
// well as the current state.
void getnbour(int board[][N],
int* state)
{
// Declaring and initializing the
// optimal board and state with
// the current board and the state
// as the starting point.
int
opBoard[N][N];
int opState[N];
copythestate(opState,
state);
genboard(opBoard,
opState);
//
Initializing the optimal
// objective value
int
opObjective
= calculateobj(opBoard,
opState);
//
Declaring and initializing
// the temporary board and
// state for the purpose
// of computation.
int
NeighbourBoard[N][N];
int NeighbourState[N];
copythestate(NeighbourState,
state);
genboard(NeighbourBoard,
NeighbourState);
//
Iterating through all
// possible neighbours
// of the board.
for (int i
= 0; i < N; i++) {
for (int j = 0; j < N; j++)
{
// Condition for skipping
the
// current
state
if (j != state[i]) {
//
Initializing temporary
// neighbour with the
// current neighbour.
NeighbourState[i] = j;
NeighbourBoard[NeighbourState[i]][i]
= 1;
NeighbourBoard[state[i]][i]
= 0;
//
Calculating the objective
// value of the neighbour.
int
temp
= calculateobj(
NeighbourBoard,
NeighbourState);
//
Comparing temporary and optimal
// neighbour objectives and if
// temporary is less than optimal
// then updating accordingly.
if (temp
<= opObjective) {
opObjective = temp;
copythestate(opState,
NeighbourState);
genboard(opBoard,
opState);
}
// Going
back to the original
// configuration for the next
// iteration.
NeighbourBoard[NeighbourState[i]][i]
= 0;
NeighbourState[i] = state[i];
NeighbourBoard[state[i]][i] = 1;
}
}
}
// Copy
the optimal board and
// state thus found to the current
// board and, state since c++ doesn't
// allow returning multiple values.
copythestate(state, opState);
fill(board, 0);
genboard(board, state);
}
void
hillClimbing(int board[][N],
int* state)
{
//
Declaring and initializing the
// neighbour board and state with
// the current board and the state
// as the starting point.
int
neighbourBoard[N][N] = {};
int neighbourState[N];
copythestate(neighbourState, state);
genboard(neighbourBoard,
neighbourState);
do {
// Copying the neighbour board and
// state to the current board
and
// state, since a neighbour
// becomes current after the
jump.
copythestate(state, neighbourState);
genboard(board, state);
// Getting the optimal neighbour
getnbour(neighbourBoard,
neighbourState);
if (comparestate(state,
neighbourState)) {
// If neighbour and current
are
// equal then no
optimal neighbour
// exists and
therefore output the
// result and
break the loop.
printqboard(board);
break;
}
else if (calculateobj(board,
state)
== calculateobj(
neighbourBoard,
neighbourState)) {
// If neighbour and current
are
// not equal but
their objectives
// are equal
then we are either
// approaching a
shoulder or a
// local
optimum, in any case,
// jump to a
random neighbour
// to escape
it.
// Random neighbour
neighbourState[rand() % N]
= rand() % N;
genboard(neighbourBoard,
neighbourState);
}
} while
(true);
}
//
Driver code
int main()
{
int
state[N] = {};
int board[N][N] = {};
// Getting
a starting point by
// randomly configuring the board
ly(board, state);
// Do hill
climbing on the
// board obtained
hillClimbing(board, state);
return
0;
}