Parallelizing the 8-Queen solution using Hill Climbing Search You are provided with the Java code implementing...

Transcribed Image Text:

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<n; i++){ startBoard [i] = new NQueen (rndm.nextInt(n), i); return startBoard; 28 } 29 30 31 public void printState (NQueen [] state) { 32 33 34 35 36 37 } 38 39 //Method to print the Current State //Creating temporary board from the present board int[] [] tempBoard = new int[n] [n]; for (int i=0; i<n; i++) { //Get the positions of Queen from the Present board and set those positions as 1 in temp board tempBoard [state[i].getRow()] [state[i].getColumn()]=1; System.out.println(); for (int i=0; i<n; i++) { 40 for (int j = 0; j < n; j++) { ~/Downloads/JavaCode 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 LF UTF-8 Java GitHub Git (0) 39 40 41 42 } 43 HillClimbingSearch.java for (int i=0; i<n; i++) { for (int j = 0; j < n; j++) { System.out.print (tempBoard[i][j] + "); System.out.println(); 44 } 45 } 46 47 48 49 50 for (int i = 51 52 53 // Method to find Heuristics of a state public int findHeuristic (NQueen [] state) { int heuristic = 0; 0; i< state.length; i++) { for (int j=i+1; j<state.length; j++ ) { if (state[i].ifConflict (state[j])) { heuristic++; 54 } 55 } 56 } 57 return heuristic; 58 } 59 60 61 62 63 64 65 int bestHeuristic = // Method to get the next board with lower heuristic public NQueen () nextBoard (NQueen () presentBoard) { NQueen [] nextBoard = new NQueen [n]; NQueen [ ] tmpBoard = new NQueen [n]; int presentHeuristic = findHeuristic (present Board); presentHeuristic; 66 int tempH; 67 68 for (int i=0; i<n; i++) { 69 70 71 // Copy present board as best board and temp board nextBoard [i] = new NQueen (presentBoard[i].getRow(), presentBoard [i].getColumn() ); tmpBoard [i] = nextBoard [i]; 72 } 73 // Iterate each column 74 75 if (i>0) 76 77 78 for (int i=0; i<n; i++) { tmpBoard [i-1] = new NQueen (presentBoard [i-1].getRow(), presentBoard [i-1].getColumn() ); = new NQueen (0, tmpBoard [i].getColumn()); Iterate each row tmpBoard [i] // ~/Downloads/Java Code 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 LF UTF-8 Java GitHub Git (0) 78 79 80 81 82 83 84 85 86 87 88 89 } 90 91 HillClimbingSearch.java // Iterate each row for (int j=0; j<n; j++) { //Get the heuristic tempH = findHeuristic(tmpBoard); //Check if temp board better than best board if (tempH < bestHeuristic) { bestHeuristic = tempH; // Copy the temp board as best board for (int k=0; k<n; k++) { } nextBoard [k] = new NQueen(tmpBoard [k].getRow(), tmpBoard [k].getColumn()); //Move the queen if (tmpBoard[i].getRow() !=n-1) 92 tmpBoard[i].move(); 93 } 94 } 95 96 97 -- 98 nextBoard = //Check whether the present bord and the best board found have same heuristic //Then randomly generate new board and assign it to best board if (bestHeuristic presentHeuristic) { generateBoard(); 99 heuristic = findHeuristic (nextBoard); 100 } else 101 heuristic = bestHeuristic; 102 return nextBoard; 103 } 104 105 public void runSearch() { 106 107 NQueen [] presentBoard = 108 109 110 111 112 113 114 115 } 116 117 } presentHeuristic = generateBoard(); findHeuristic (presentBoard); // test if the present board is the solution board while (presentHeuristic != 0) { // Get the next board // printState(presentBoard); presentBoard = presentHeuristic = heuristic; finalSolution = presentBoard; ~/Downloads/JavaCode 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 nextBoard (presentBoard); LF UTF-8 Java GitHub Git (0) 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) 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<n; i++){ startBoard [i] = new NQueen (rndm.nextInt(n), i); return startBoard; 28 } 29 30 31 public void printState (NQueen [] state) { 32 33 34 35 36 37 } 38 39 //Method to print the Current State //Creating temporary board from the present board int[] [] tempBoard = new int[n] [n]; for (int i=0; i<n; i++) { //Get the positions of Queen from the Present board and set those positions as 1 in temp board tempBoard [state[i].getRow()] [state[i].getColumn()]=1; System.out.println(); for (int i=0; i<n; i++) { 40 for (int j = 0; j < n; j++) { ~/Downloads/JavaCode 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 LF UTF-8 Java GitHub Git (0) 39 40 41 42 } 43 HillClimbingSearch.java for (int i=0; i<n; i++) { for (int j = 0; j < n; j++) { System.out.print (tempBoard[i][j] + "); System.out.println(); 44 } 45 } 46 47 48 49 50 for (int i = 51 52 53 // Method to find Heuristics of a state public int findHeuristic (NQueen [] state) { int heuristic = 0; 0; i< state.length; i++) { for (int j=i+1; j<state.length; j++ ) { if (state[i].ifConflict (state[j])) { heuristic++; 54 } 55 } 56 } 57 return heuristic; 58 } 59 60 61 62 63 64 65 int bestHeuristic = // Method to get the next board with lower heuristic public NQueen () nextBoard (NQueen () presentBoard) { NQueen [] nextBoard = new NQueen [n]; NQueen [ ] tmpBoard = new NQueen [n]; int presentHeuristic = findHeuristic (present Board); presentHeuristic; 66 int tempH; 67 68 for (int i=0; i<n; i++) { 69 70 71 // Copy present board as best board and temp board nextBoard [i] = new NQueen (presentBoard[i].getRow(), presentBoard [i].getColumn() ); tmpBoard [i] = nextBoard [i]; 72 } 73 // Iterate each column 74 75 if (i>0) 76 77 78 for (int i=0; i<n; i++) { tmpBoard [i-1] = new NQueen (presentBoard [i-1].getRow(), presentBoard [i-1].getColumn() ); = new NQueen (0, tmpBoard [i].getColumn()); Iterate each row tmpBoard [i] // ~/Downloads/Java Code 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 LF UTF-8 Java GitHub Git (0) 78 79 80 81 82 83 84 85 86 87 88 89 } 90 91 HillClimbingSearch.java // Iterate each row for (int j=0; j<n; j++) { //Get the heuristic tempH = findHeuristic(tmpBoard); //Check if temp board better than best board if (tempH < bestHeuristic) { bestHeuristic = tempH; // Copy the temp board as best board for (int k=0; k<n; k++) { } nextBoard [k] = new NQueen(tmpBoard [k].getRow(), tmpBoard [k].getColumn()); //Move the queen if (tmpBoard[i].getRow() !=n-1) 92 tmpBoard[i].move(); 93 } 94 } 95 96 97 -- 98 nextBoard = //Check whether the present bord and the best board found have same heuristic //Then randomly generate new board and assign it to best board if (bestHeuristic presentHeuristic) { generateBoard(); 99 heuristic = findHeuristic (nextBoard); 100 } else 101 heuristic = bestHeuristic; 102 return nextBoard; 103 } 104 105 public void runSearch() { 106 107 NQueen [] presentBoard = 108 109 110 111 112 113 114 115 } 116 117 } presentHeuristic = generateBoard(); findHeuristic (presentBoard); // test if the present board is the solution board while (presentHeuristic != 0) { // Get the next board // printState(presentBoard); presentBoard = presentHeuristic = heuristic; finalSolution = presentBoard; ~/Downloads/JavaCode 7/8-Queen Problem HC/HillClimbingSearch.java 1:1 nextBoard (presentBoard); LF UTF-8 Java GitHub Git (0) 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)

Answer rating: 100% (QA)

Step1 The runSearch method in Java is a method that is used to search for a particular value in a collection of data The method takes two parameters the collection of data and the value that you are s... View the full answer