Question

Q7. Does Simulated Anealing (with 10 iterations) solve the 14-Queens Problem? What about SA (with 50 iterations). Show your answer.

Answer 1

Lets see the answer:-

Lets see 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();

    }

}

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.