Question

Generate a large number of instances of the following problems: 8 × 8 Puzzle and 8-Queens Problem and solve these problems (if possible) using different local search algorithms (Hill Climbing Algorithm, Random Restart Hill Climbing Algorithm and Simulated annealing). Measure the cost of each search and the percentage of problems solved and make a graphical representation of these values based on the optimal cost. Comment on your results.

Programming language can be either Python, C++ or Java. + code comments are necessary

Answer 1

package DS;

import java.util.*;

// Class NQueenAllSolutions definition

public class NQueenAllSolutions

{

// Defines a constant for N x N chess board

public static final int BOARDSIZE = 8;

// Static method to return true if a queen is in safe state otherwise returns false

private static boolean checkSafe(char chessBoard[][], int row, int col)

{

// Returns false if two queens are available in the same column

// Loops till row value

for (int r = 0; r < row; r++)

// Checks if r and col index position of the matrix chessBoard contains character 'Q'

// then returns false

if (chessBoard[r][col] == 'Q')

return false;

// Return false if two queens are available in the same left diagonal

  

// Loops till either row and column is grater than or equals to zero

for (int r = row, c = col; r >= 0 && c >= 0; r--, c--)

// Checks if r and c index position of the matrix chessBoard contains character 'Q'

// then returns false

if (chessBoard[r][c] == 'Q')

return false;

// Return false if two queens are available in the same right diagonal

  

// Loops till either row is greater than or equals to zero and column is less than board size

for (int r = row, c = col; r >= 0 && c < BOARDSIZE; r--, c++)

// Checks if r and c index position of the matrix chessBoard contains character 'Q'

// then returns false

if (chessBoard[r][c] == 'Q')

return false;

  

// Otherwise return true. Queen is in safe place

return true;

}// End of method

// Static method to find solution to N queen problem and prints the solution

private static void nQueenSolution(char chessBoard[][], int row)

{

// Checks if N queens are placed successfully, then print the solution

// Checks if parameter row value is equals to board size

if (row == BOARDSIZE)

{

// Loops till board size for number of rows

for (int r = 0; r < BOARDSIZE; r++)

{

// Loops till board size for number of columns

for (int c = 0; c < BOARDSIZE; c++)

// Displays each cell value

System.out.print(chessBoard[r][c] + " ");

System.out.println();

}// End of for loop

System.out.println();

  

return;   

}// End of if condition

  

// Otherwise place queen at every square in current row r and recurse for each valid movement

for (int c = 0; c < BOARDSIZE; c++)

{

// Checks if no two queens threaten each other

if (checkSafe(chessBoard, row, c))

{

// Assigns character 'Q' for queen on current square

chessBoard[row][c] = 'Q';

// Recursively calls the method for next row

nQueenSolution(chessBoard, row + 1);

// Backtrack and remove queen from current square by replacing character'-'

chessBoard[row][c] = '-';

}// End of if condition

}// End of for loop

  

}// End of method

// main method definition

public static void main(String[] args)

{

// Creates a matrix for chess board with row and column size as BOARDSIZE

char[][] chessBoard = new char[BOARDSIZE][BOARDSIZE];

// Loops till number of rows to initialize chess board by character '-'

for (int r = 0; r < BOARDSIZE; r++)

Arrays.fill(chessBoard[r], '-');

  

// Calls the method to find and print the N queen solution

nQueenSolution(chessBoard, 0);

}// End of main method

}// End of class

Sample Output:

Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -

- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -
- - - - Q - - -

- Q - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -

- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -

- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -

- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -

- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -

- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -

- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -

- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -

- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -

- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -

- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -

- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -

- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -

- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - Q -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -

- - - Q - - - -
- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -

- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -

- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -

- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -

- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q

- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -

- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -

- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -

- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -

- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -

- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -

- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -

- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -

- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -

- - - - Q - - -
- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -

- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -

- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -

- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- Q - - - - - -

- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -

- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -

- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -

- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -

- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q

- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -

- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -

- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -

- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q

- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -

- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -

- - - - - - Q -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -

- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -
- - - Q - - - -

- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -

- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -

- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -

- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -

- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -