Parallelizing the 8-Queen solution using Hill Climbing Search You are provided with the Java code implementing a solution for the 8-Queen puzzle using a search method called Hill Climbing. Upon execution of the Java code, the user is prompted to enter the value of n which is the chess board dimension that can be any natural number except for 2 and 3. The run Search () method of HillClimbingSearch is then called to compute a solution and the board solution is printed if/when it is found. Try to execute the code for various values of n and check the time it takes to compute a solution. Hill Climbing search works by randomly selecting a solution to a problem and iteratively improving the solution until it satisfies the desired constraints. In order to find solutions to n- Queen problem faster as n increases, we can run several threads of HillClimbing Search concurrently. Each thread will start from a randomly selected point in the search space and the threads will explore different parts of the search space concurrently until one of them finds a solution. This can considerably improve the time required to find a solution for large values of n (e.g., n > 40). Your task is to modify Main.java and HillClimbing Search.java so that you create several threads each running one instance of HillClimbing Search. Create a ThreadGroup to keep track of all your threads. You stop all the threads as soon as one of them finds a solution. The number of threads you create is optional. You only need to modify Main.java and HillClimbingSearch.java. In the latter, you only need to modify the run Seach () method, and there is no need to touch any other methods in that file. Hint: You might want to take a look at the ThreadGroup Javadoc: http://docs.oracle.com/javase/7/docs/api/java/lang/ThreadGroup.html To stop the threads, you can use the interrupt mechanism in Java. You may find the discussion on this webpage helpful in implementing your interrupt mechanism for stopping all the threads as soon as one thread finds a solution: https://stackoverflow.com/questions/31895612/how-to- stop-a-thread-with-thread-interrupt-method. Good Luck! HillClimbingSearch.java /Program to implement Hill Climbing with random restart to solve N-queens problem import java.util.Random; 1 2 12345 5 6 7 public class HillClimbing Search { private int n; private int heuristic = 0; 8 private int presentHeuristic; 9 private NQueen [] finalSolution; 10 11 12 13 public HillClimbing Search (int size) { n = size; finalSolution null; 14 } 15 16 17 public NQueen () getFinalSolution() { return finalSolution; 18 } 19 20 21 22 23 24 25 26 } 27 //Method to create a new random board public NQueen [] generateBoard() { NQueen [] startBoard = new NQueen [n]; Random rndm = new Random(); for(int i=0; i 39 40 41 42 } 43 HillClimbingSearch.java for (int i=0; i 78 79 80 81 82 83 84 85 86 87 88 89 } 90 91 HillClimbingSearch.java // Iterate each row for (int j=0; j 114 115 116 117 } 118 119 120 } presentHeuristic = heuristic; } finalSolution = present Board; 123 4 4 567 8 9 10 Main.java import java.util.Scanner; public class Main { public static void main(String[] args) { int n = 0; try (Scanner s=new Scanner(System.in)) { while (true) { System.out.println("Enter the number of Queens :"); n = s.nextInt(); if ( n == 2 || n ==3) { System.out.println("No Solution possible for "+ n +" Queens. Please enter another number"); 11 12 13 } 14 else 15 break; 16 } 17 } 18 19 20 21 22 23 24 25 26 27 long timestamp1 = System.currentTimeMillis(); System.out.println("Solution to "+ n +" queens using hill climbing search: "); HillClimbingSearch hcs = new HillClimbingSearch(n); hcs.runSearch(); if (hcs.getFinalSolution() != null) hcs.printState(hcs.getFinalSolution()); 28 29 30 31 32 33 34 35 //Printing the solution long timestamp2 = System.currentTimeMillis(); long time Diff = timestamp2 - timestamp1; System.out.println("Execution Time: "+timeDiff+" ms"); 36 37 38 } 39 } ~/Downloads/Java Code 7/8-Queen Problem HC/Main.java* 5:42 LF UTF-8 Java GitHub Git (0) 123 4 567 NQueen.java //Class for N-queens Problem public class NQueen { private int row; private int column; public NQueen (int row, int column) { this.row = row; 7 8 this.column = column; 9 } 10 11 public void move () { 12 row++; 13 } 14 15 16 17 18 19 20 21 22 23 } 24 public boolean ifConflict (NQueen q) { // Check rows and columns if (row q.getRow() || column return true; // Check diagonals q.getColumn()) else if (Math.abs (column-q.getColumn()) return true; return false; public int getRow() { -- 25 return row; 26 } 27 88 28 29 30 public int getColumn() { return column; } 31 } Math.abs (row-q.getRow())) ~/Downloads/Java Code 7/8-Queen Problem HC/NQueen.java 2:14 (1,6) LF UTF-8 Java GitHub Git (0)