**Instructions**

Write a program that places 8 queens on an 8x8 board where none of
the queens are in conflict with each other. You are to
implement the solution by using the **Hill-Climbing algorithm
with random restarts**.

**Problem Overview & Algorithm Description**

The 8-Queens problem requires that 8 queens be placed on a board
with 8 rows and columns so that no queen occupies the same row,
column or diagonal as another queen. To solve this problem
using the Hill-Climbing with random restart algorithm, we must
first generate a random starting state which places a queen in a
random row of each column. From there, we first check to see
if the state is a goal state (no queens are in conflict). If not,
we evaluate all of the possible neighbor states by moving each
column’s queen through the rows of its column and generating a
heuristic value for each of those states. When all of the
neighbor states have been generated, we check to see if any states
were generated that have a lower heuristic value than the current
state. If a better state was not found, then we have reached
the local minima and must perform a random restart. If a
better (lower heuristic) state was found, then that state becomes
the current state and the above process is repeated on that
state.

**Remember:** your heuristic function is a
representation of how close you are to the goal state. Unlike
Pathfinding heuristics, we are not evaluating how close a
particular node is to the goal node, but rather how close the
current state (overall configuration) is to the goal state

**Program Requirements**

No graphics are required for this program. Instead, use a
series of 0s (empty) and 1s (queen) in a grid style to represent
each state. Every state generated should be output in this
manner along with the current state’s heuristic, the number of
neighboring states with lower heuristics, and the action taken
(restart or generate neighbor state). When a solution is
reached, your program should display the number of restarts and the
total number of state changes that have occurred. A sample
execution using 10 queens has been provided. Your
program output should match that format (except yours will be
8x8).

Community Answer

Honor CodeSolved 1 Answer

See More Answers for FREE

Enhance your learning with StudyX

Receive support from our dedicated community users and experts

See up to 20 answers per week for free

Experience reliable customer service

Get Started

ANSWER : import java.util.*; public class EightQueens {        final private int [][] map = new int[8][8];     final private int [][] testMap = new int[8][8];     private int heuristic = 0;     private int queenLocs = 0;     private int restarts = 0;     private int moves = 0;     private boolean newMap = true;     private int neighbors = 8;           public EightQueens( ){ //initializes the map         for(int i = 0; i < 8; i++){             for(int j = 0; j < 8; j++){                 map[i][j] = 0;             }         }     }           public void randomizeMap( ){ //randomizes the map       Random rand = new Random( );       int num;              while(queenLocs < 8){             for(int i = 0; i < 8; i++){                 map[rand.nextInt(7)][i] = 1;                 queenLocs++;                 }             }       heuristic = heuristic(map);     }        //***************************Heuristic****************************//        public boolean findRowEx(int [][] test, int a){ //determines row conflicts         boolean exFound = false;         int count = 0;                for(int i = 0; i < 8; i++){             if(test[i][a] == 1){                 count++;             }         }         if(count > 1){             exFound = true;         }         return exFound;     }     public boolean findColEx(int [][] test, int j){ //determines column conflicts         boolean exFound = false;         int count = 0;         for(int i = 0; i < 8; i++){             if(test[j][i] == 1){                 count++;             }         }         if(count > 1){           exFound = true;         }         return exFound;     }        public boolean findDiaEx(int [][] test, int a, int b){//determines diagonal conflicts         boolean diaFound = false;                for(int i = 1; i < 8; i++){             if(diaFound){                 break;             }             if((a+i < 8)&&(b+i < 8)){                 if(test[a+i][b+i] == 1){                     diaFound = true;                 }             }             if((a-i >= 0)&&(b-i >= 0)){                 if(test[a-i][b-i] == 1){                     diaFound = true;                 }             }             if((a+i < 8)&&(b-i >= 0)){                 if(test[a+i][b-i] == 1){                     diaFound = true;                 }             }               if((a-i >= 0)&&(b+i < 8)){                 if(test[a-i][b+i] == 1){                     diaFound = true;                 }             }           }         return diaFound;     }        public int heuristic(int [][] test){//Counts the number of queens in conflict     int count = 0;     boolean rowEx;     boolean colEx;     boolean diaEx;                for(int i = 0; i < 8; i++){             for(int j= 0; j < 8; j++){                 if(test[i][j] == 1){                     rowEx = findRowEx(test, j);                     colEx = findColEx(test, i);                     diaEx = findDiaEx(test, i, j);                                        if(rowEx || colEx || diaEx){                         count++;                     }                 }             }         }         return count;     }     //***********************Move Queen***********************//     public void moveQueen( ){ //moves a queen and determines whether to continue to a new state or restart or to summarize solution         int[][] hArray = new int[8][8];         int colCount;         int minCol;         int minRow;         int prevColQueen = 0;         newMap = false;                while(true){             colCount = 0;                    for(int i = 0; i < 8; i++){                 System.arraycopy(map[i], 0, testMap[i], 0, 8);             }             while(colCount < 8){                 for(int i = 0; i < 8;i++){                     testMap[i][colCount] = 0;                 }                 for(int i = 0; i < 8; i++){                     if(map[i][colCount] == 1){                         prevColQueen = i;                     }                     testMap[i][colCount] = 1;                     hArray[i][colCount] = heuristic(testMap);                     testMap[i][colCount] = 0;                 }                 testMap[prevColQueen][colCount] = 1;                 colCount++;             }                        if(determineRestart(hArray)){                 queenLocs = 0;                 for(int i = 0; i < 8; i++){                     for(int j = 0; j < 8; j++){                         map[i][j] = 0;                     }                 }                 randomizeMap( );                 System.out.println("RESTART");                 restarts++;             }                    minCol = findMinCol(hArray);             minRow = findMinRow(hArray);                    for(int i = 0; i < 8; i++){                 map[i][minCol] = 0;             }                    map[minRow][minCol] = 1;             moves++;             heuristic = heuristic(map);                        if(heuristic(map) == 0){                 System.out.println("nCurrent State");                 for(int i = 0; i < 8; i++){                     for(int j = 0; j < 8; j++){                         System.out.print(map[i][j] + " ");                     }                     System.out.print("n");                 }             System.out.println("Solution Found!");             System.out.println("State changes: " + moves);             System.out.println("Restarts: " + restarts);             break;             }             System.out.println("n");             System.out.println("Current h: " + heuristic);             System.out.println("Current State");             for(int i = 0; i < 8; i++){                 for(int j = 0; j < 8; j++){                     System.out.print(map[i][j] + " ");                 }                 System.out.print("n");             }             System.out.println("Neighbors found with lower h: " + neighbors);             System.out.println("Setting new current State");         }     }     public int findMinCol(int[][] test){ //finds column of minimum neighbor state         int minCol = 8;         int minVal = 8;         int count = 0;                for(int i = 0; i < 8; i++){           for(int j = 0; j < 8; j++){               if(test[i][j] < minVal){                   minVal = test[i][j];                   minCol = j;               }               if(test[i][j] < heuristic){                   count++;               }           }         }         neighbors = count;         return minCol;     }     public int findMinRow(int[][] test){ //finds row of minimum neighbor state         int minRow = 8;         int minVal = 8;                for(int i = 0; i < 8; i++){           for(int j = 0; j < 8; j++){               if(test[i][j] < minVal){                   minVal = test[i][j];                   minRow = i;               }           }         }         return minRow;     }     public boolean determineRestart(int [][] test){// determines whether restart is necessary         int minVal = 8;         boolean restart = false;                for(int i = 0; i < 8; i++){             for(int j = 0; j < 8; j++){                 if(test[i][j] < minVal){                     minVal = test[i][j];                 }             }         }         if(neighbors == 0){             restart = true;         }         return restart;     }     /************************* Main **********************/     public static void main(String[] args) {// creates object, creates initial random map, then initiates state change      EightQueens one = new EightQueens( );      one.randomizeMap();      one.moveQueen();     } }   Sample run :- Problems (a) Javadoc 虫 Declaration 튼 Cole is<terminated> EightQueens [Java Application] Ci\Program Files\Javaljdk1.8.0_131\binไjavaw.exe (Jul 9, 2017, 8:20:43 AM)\begin{array}{lllllllll}1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \text { Neighbors found with lower h: } 7 \\ \text { Setting } \\ & & & & & & \\ \text { Current current State }\end{array}001000000000001001000000000000000000000010000000000001000Neighbors found with lower h: 7Setting new current StateCurrent h: 2Current State1000010000100000000000100100000000010000000000010000000000001000Neighbors found with lower h: 2Setting new current StateCurrent State0000010000100000000000100100000000010000000000011000000000001000Solution Found!State changes: 31Restarts: 5   Hope it helps... please give an upvote. It's very important to me... thank you:) ...