Question

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.

Question: Does Simulated Annealing (SA) algorithms (with 10 iterations) solve the 14-Queens Problem? What about Simulated Annealing (SA) algorithms (with 50 iterations). Show your answer.

Answer 1

NAVIE ALGORITHM:

while there are untried configurations
{
   generate the next configuration
   if queens don't attack in this configuration then
   {
      print this configuration;
   }
}

BACKTRACKING ALGORITHM:

1) Start in the leftmost column
2) If all queens are placed
    return true
3) Try all rows in the current column. 
   Do following for every tried row.
    a) If the queen can be placed safely in this row 
       then mark this [row, column] as part of the 
       solution and recursively check if placing
       queen here leads to a solution.
    b) If placing the queen in [row, column] leads to
       a solution then return true.
    c) If placing queen doesn't lead to a solution then
       unmark this [row, column] (Backtrack) and go to 
       step (a) to try other rows.
3) If all rows have been tried and nothing worked,
   return false to trigger backtracking.

C# PROGRAM FOR SOLVING QUEEN PROBLEM

using System;

     

class GFG

{

    readonly int N = 4;

void printSolution(int [,]board)

    {

        for (int i = 0; i < N; i++)

        {

            for (int j = 0; j < N; j++)

                Console.Write(" " + board[i, j]

                                  + " ");

            Console.WriteLine();

        }

    }

bool isSafe(int [,]board, int row, int col)     {         int i, j; for (i = 0; i < col; i++)             if (board[row,i] == 1)                 return false;         for (i = row, j = col; i >= 0 &&              j >= 0; i--, j--)             if (board[i,j] == 1)                 return false;         for (i = row, j = col; j >= 0 &&                       i < N; i++, j--)             if (board[i, j] == 1)                 return false;         return true;     }     bool solveNQUtil(int [,]board, int col)     {         if (col >= N)             return i;         for (int i = 0; i < N; i++) {             if (isSafe(board, i, col))             {                 /* Place this queen in board[i,col] */                 board[i, col] = 1;                 if (solveNQUtil(board, col + 1) == true)                     return true; board[i, col] = 0; // BACKTRACK             }         }         return false;     }     bool solveNQ()     {         int [,]board = {{ 0, 0, 0, 0 },                         { 0, 0, 0, 0 },                         { 0, 0, 0, 0 },                         { 0, 0, 0, 0 }}; if (solveNQUtil(board, 0) == false)         {             Console.Write("Solution does not exist");             return false;         }         printSolution(board);         return true;     }     public static void Main(String []args)     {         GFG Queen = new GFG();         Queen.solveNQ();     } }