Question

In: Computer Science

In this case study, your task is to study different search algorithms to solve the N-Queens...

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.

Solutions

Expert Solution

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;
}


Related Solutions

CASE STUDY:                                         &n
CASE STUDY:                                           “THE CARPENTER” Chris is a shy, anxious-looking, 31-year old carpenter who has been hospitalized after making suicide attempt by putting his head in a plastic bag. He asks to meet with the psychiatrist in a darkened room. He is wearing a baseball cap pulled down over his forehead and partially covering his eyes. Looking down at the floor, Chris says he has no friends, has just been fired from his job, and was recently rejected by his...
Module 7 showed that one way of comparing different algorithms for accomplishing the same task is...
Module 7 showed that one way of comparing different algorithms for accomplishing the same task is complexity analysis. You will recall that in complexity analysis we express the time an algorithm takes to run as a function of the size of the input, and we used the big-Oh notation. For example, if an algorithm has a complexity of O(1), then it always runs in the same amount of time, no matter what the size of the input is; if it...
Using the case study below or your own health issue with goal and objective, your task...
Using the case study below or your own health issue with goal and objective, your task is to develop three outputs and one indicator for each output, considering the means of verification and assumptions for your indicators through completing the table below Goal: Decrease the complications of Hyperglycemia Objective: To maintain the blood glucose level within normal range Output Indicators (Measure to verify to what extent the goal is fulfilled – include targets and baseline data where possible) Means of...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and contrast the different methods.
CASE STUDY: THE CASE OF ROSA N.* In many parts of the world the kind of...
CASE STUDY: THE CASE OF ROSA N.* In many parts of the world the kind of blatant racism, sexism, and discrimination described in the denial section of this chapter is becoming less common. Two such places are The Netherlands and California, both of which have the reputation of being racially progressive and tolerant when compared to other European countries or U.S. states. People articulate the virtues of pluralism, deny the presence of racism in their communities, and condemn its presence...
Case study: Deciding what is effective from different perspectives The aim of this case study is...
Case study: Deciding what is effective from different perspectives The aim of this case study is to illustrate the sometimes competing demands of effectiveness, efficiency and equity. In particular, it should help you to: Explain what is meant by key terms such as ‘LYG’, ‘QALY’ and ‘ICER’ Use these terms and the information they represent in a decision-making scenario ?        Compare and contrast the demands of effectiveness from different perspectives Scenario You are a member of an area prescribing...
n this paper, please discuss the following case study. In doing so, explain your approach to...
n this paper, please discuss the following case study. In doing so, explain your approach to the problem, support your approach with references, and execute your approach. Provide an answer to the case study’s question with a recommendation. You are the owner of a parasailing company that is expanding operations to a new beachfront location, and you need to prepare a three-year analysis for the bank that may loan you the funds to purchase your boat and parasailing equipment. Because...
CASE STUDY Solve the case based on the following information: The comparative statements of financial position...
CASE STUDY Solve the case based on the following information: The comparative statements of financial position for Cactus Ltd, which is a merchandising business selling indoor plants, follows. Cactus Ltd Comparative Statement of Financial Position As at 31 December 2019 and 2018 2019 2018 Assets € € Current assets: Cash 195 800 15 000 Trade receivables 58 400 72 000 Inventory 59 800 53 000 Prepayments 2 300 5 000 Total current assets: 316 300 145 000 Non-current assets: Land...
CASE STUDY Solve the case based on the following information: The comparative statements of financial position...
CASE STUDY Solve the case based on the following information: The comparative statements of financial position for Cactus Ltd, which is a merchandising business selling indoor plants, follows. Cactus Ltd Comparative Statement of Financial Position As at 31 December 2019 and 2018 2019 2018 Assets € € Current assets: Cash 195 800 15 000 Trade receivables 58 400 72 000 Inventory 59 800 53 000 Prepayments 2 300 5 000 Total current assets: 316 300 145 000 Non-current assets: Land...
Please read the case study below and use the Codification Research System to search for the...
Please read the case study below and use the Codification Research System to search for the solution to the issues raised at the end of the discussion in the “Required” section. In formulating your response, please cut and paste those paragraphs noted above that you used to derive your answer. WHAT HAPPENS WHEN YOU BARTER WITH STOCK? Does It Matter Whether It’s Treasury Stock or Newly Issued Stock? Clyde:               I acquired this land for my business by issuing stock. I...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT