Intro to A.I 8 Queens Programming Assignment using the Hill-Climbing algorithm w

Question

Intro to A.I 8 Queens Programming Assignment using the Hill-Climbing algorithm with random restarts using Java Programming.

I seriously need help understanding how to approach this programming assignment. It would really help if someone can help me walk through it step by step. It has been a few years since I used Java and I really want to make sure I understand what is going on with the process to program this.

Here are the requirements:

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).

Explanation / Answer

/**

solution code is given below:-

It contains 6 .java files. : -

codes of all files are given as per order mentioned here.

first compile all the 6 file and then run java EightQueens

* @file EightQueens.java

* Solves the eight queens problem using various AI techniques

*/

import java.util.*;

import java.text.NumberFormat;

public class EightQueens {

public EightQueens(){

}

public static void main(String[] args){

EightQueens board = new EightQueens();

int numberOfRuns = 2000;

int hillClimbNodes=0, randomRestartNodes=0, annealNodes=0;

int hillClimbSuccesses=0, randomRestartSuccesses=0, annealSuccesses=0;

for(int i=0; i<numberOfRuns; i++){

Queen[] startBoard = board.generateBoard();

//Node test = new Node();

//test.setState(startBoard);

//System.out.println(test);

HillClimbing hillClimber = new HillClimbing(startBoard);

RandomRestart randomRestart = new RandomRestart(startBoard);

SimulatedAnnealing anneal = new SimulatedAnnealing(startBoard);

Node hillSolved = hillClimber.hillClimbing();

Node randomSolved = randomRestart.randomRestart();

Node annealSolved = anneal.simulatedAnneal(28, 0.0001);

if(hillSolved.getHeuristic()==0){

//System.out.println("Hill Climbing Solved: "+hillSolved);

hillClimbSuccesses++;

}

if(randomSolved.getHeuristic()==0){

//System.out.println("Random Restart Solved: "+randomSolved);

randomRestartSuccesses++;

}

if(annealSolved.getHeuristic()==0){

//System.out.println("Anneal Solved: "+annealSolved);

annealSuccesses++;

}

hillClimbNodes += hillClimber.getNodesGenerated();

randomRestartNodes += randomRestart.getNodesGenerated();

annealNodes += anneal.getNodesGenerated();

}

System.out.println("Hill climb successes: "+hillClimbSuccesses);

System.out.println("Random restart successes: "+randomRestartSuccesses);

System.out.println("Simulated Annealing successes: "+annealSuccesses);

System.out.println();

double hillClimbPercent = (double)hillClimbSuccesses/(double)numberOfRuns;

System.out.println(hillClimbPercent);

double randomRestartPercent = (double)(randomRestartSuccesses/numberOfRuns);

double annealPercent = (double)(annealSuccesses/numberOfRuns);

NumberFormat fmt = NumberFormat.getPercentInstance();

System.out.println("Hill climbing: Nodes: "+hillClimbNodes);

System.out.println("Percent successes: "+fmt.format(hillClimbPercent));

System.out.println("Random Restart: Nodes: "+randomRestartNodes);

System.out.println("Percent successes: "+fmt.format(randomRestartPercent));

System.out.println("Simulated Annealing: Nodes: "+annealNodes);

System.out.println("Percent successes: "+fmt.format(annealPercent));

}

/**

* The starter board

* @return Queen[]

*/

public Queen[] generateBoard(){

Queen[] start = new Queen[8];

Random gen = new Random();

for(int i=0; i<8; i++){

start[i] = new Queen(gen.nextInt(8),i);

}

return start;

}

}

//

/**
* @file HillClimbing.java
* @author Natasha Squires <nsquires@upei.ca>
* Implementation of the hill climbing algorithm
*/
import java.util.*;

public class HillClimbing {
private final static int N=8;
private Queen[] startState;
private Node start; //start state
private int nodesGenerated;

/**
* Constructor
*/
public HillClimbing(){
start = new Node(); //empty start node
startState = new Queen[N]; //empty start state
startState();
nodesGenerated=0;
}

/**
* Constructs HillClimbing with a starting board
* @param s
*/
public HillClimbing(Queen[] s){
start = new Node();
startState = new Queen[N];
for(int i=0; i<s.length; i++){
startState[i] = new Queen(s[i].getRow(), s[i].getColumn());
}
start.setState(startState);
start.computeHeuristic();

nodesGenerated=0;
}

/**
* Sets the starting state
*/
public void startState(){
//sets up a pseudo random start state
Random gen = new Random();
for(int i=0; i<N; i++){
startState[i] = new Queen(gen.nextInt(N), i);
}
start.setState(startState);
start.computeHeuristic();
// System.out.println("start: "+start);
}

/**
* The hill climbing algorithm
* @return Node
*/
public Node hillClimbing(){
Node currentNode = start;

while(true){
ArrayList<Node> successors = currentNode.generateNeighbours(currentNode);
nodesGenerated+=successors.size();

Node nextNode = null;

for(int i=0; i<successors.size(); i++){
if(successors.get(i).compareTo(currentNode) < 0){
nextNode = successors.get(i);
}
}

if(nextNode==null)
return currentNode;

currentNode = nextNode;
}
}

/**
* Returns the Node's state
* @return Node
*/
public Node getStartNode(){
return start;
}

/**
* Returns amount of nodes generated
* @return int
*/
public int getNodesGenerated(){
return nodesGenerated;
}
}

//

/**
* @file Node.java
* @author Natasha Squires <nsquires@upei.ca>
* Represents a Queen
*/
import java.util.*;

public class Node implements Comparable<Node>{
private static final int N=8; //8 queens
public Queen[] state; //the node's state
private ArrayList<Node> neighbours;
private int hn; //heuristic score

/**
* Constructor
*/
public Node(){
state = new Queen[N]; //empty state
neighbours = new ArrayList<Node>(); //empty neighbour list
}

/**
* Constructor which creates a copy of a node's state
* @param n
*/
public Node(Node n){
state = new Queen[N];
neighbours = new ArrayList<Node>();
for(int i=0; i<N; i++)
state[i] = new Queen(n.state[i].getRow(), n.state[i].getColumn());
hn=0;
}

/**
* Generates the possible chess board configurations given a
* specific board state
* @param startState
*/
public ArrayList<Node> generateNeighbours(Node startState){
int count=0;

if(startState==null)
System.out.println("warning");
else{
// System.out.println("hmm?");
// System.out.println(startState);
}

for(int i=0; i<N; i++){
for(int j=1; j<N; j++){
neighbours.add(count, new Node(startState));
neighbours.get(count).state[i].moveDown(j);
//make sure to compute its hn value
neighbours.get(count).computeHeuristic();

count++;
}
}

return neighbours;
}

/**
* Returns a randomly generated neighbour of a given state
* @param startState
* @return
*/
public Node getRandomNeighbour(Node startState){
Random gen = new Random();

int col = gen.nextInt(N);
int d = gen.nextInt(N-1)+1;

Node neighbour = new Node(startState);
neighbour.state[col].moveDown(d);
neighbour.computeHeuristic();

return neighbour;
}

/**
* computes the heuristic, which is the number of
* pieces that can attack each other
* @return int
*/
public int computeHeuristic(){

for(int i=0; i<N-1; i++){
for(int j=i+1; j<N; j++){
if(state[i].canAttack(state[j])){
hn++;
}
}
}

return hn;
}

/**
* Hn getter
* @return
*/
public int getHeuristic(){
return hn;
}

/**
* Implements Comparable method compareTo, judges a comparison
* on the basis of a Node's heuristic value
* @param n
* @return int
*/
public int compareTo(Node n){
if(this.hn < n.getHeuristic())
return -1;
else if(this.hn > n.getHeuristic())
return 1;
else
return 0;
}

/**
* state setter
* @param s
*/
public void setState(Queen[] s){
for(int i=0; i<N; i++){
state[i]= new Queen(s[i].getRow(), s[i].getColumn());
}
}

/**
* state getter
* @return
*/
public Queen[] getState(){
return state;
}

/**
* toString method prints out Node's state
* @return String
*/
public String toString(){
String result="";
String[][] board = new String[N][N];

//initialise board with X's to indicate empty spaces
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
board[i][j]="X ";

//place the queens on the board
for(int i=0; i<N; i++){
board[state[i].getRow()][state[i].getColumn()]="Q ";
}

//feed values into the result string
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
result+=board[i][j];
}
result+=" ";
}

return result;
}
}

//

/**
* @file Queen.java
*
* A Queen chess piece
*/

public class Queen {
private int row;
private int column;

/**
* Constructor. Sets Queen's row and column
* @param r
* @param c
*/
public Queen(int r, int c){
row = r;
column = c;
}

/**
* Determines whether this queen can attack another
* @param q
* @return boolean
*/
public boolean canAttack(Queen q){
boolean canAttack=false;

//test rows and columns
if(row==q.getRow() || column==q.getColumn())
canAttack=true;
//test diagonal
else if(Math.abs(column-q.getColumn()) == Math.abs(row-q.getRow()))
canAttack=true;

return canAttack;
}

/**
* moves the piece down
* @param spaces
*/
public void moveDown(int spaces){
row+=spaces;

//bound check/reset
if(row>7 && row%7!=0){
row=(row%7)-1;
}
else if(row>7 && row%7==0){
row=7;
}
}

/**
* row setter
* @param r
*/
public void setRow(int r){
row = r;
}

/**
* row getter
* @return int
*/
public int getRow(){
return row;
}

/**
* column setter
* @param c
*/
public void setColumn(int c){
column = c;
}

/**
* column getter
* @return int
*/
public int getColumn(){
return column;
}

public String toString(){
return "("+row+", "+column+")";
}
}

///

/**
* @file RandomRestart.java

* Implements the random restart hill climbing algorithm
*/
public class RandomRestart {
private HillClimbing hillClimber;
private int nodesGenerated;
private Node start;

/**
* Constructor
*/
public RandomRestart(Queen[] startBoard){
hillClimber = new HillClimbing(startBoard);
nodesGenerated = 0;
}

/**
* The random restart hill climbing algorithm
* @return
*/
public Node randomRestart(){
Node currentNode = hillClimber.getStartNode();
setStartNode(currentNode);
int heuristic = currentNode.getHeuristic();

while(heuristic!=0){
Node nextNode = hillClimber.hillClimbing();
nodesGenerated+=hillClimber.getNodesGenerated();
heuristic = nextNode.getHeuristic();

if(heuristic!=0){ //restart
hillClimber = new HillClimbing();
}else
currentNode = nextNode;
}
return currentNode;
}

/**
* Sets the initial board
* @param n
*/
public void setStartNode(Node n){
start = n;
}

/**
* Start set getter
* @return Node
*/
public Node getStartNode(){
return start;
}

/**
* Returns the amount of nodes generated during the
* random restart algorithm
* @return int
*/
public int getNodesGenerated(){
return nodesGenerated;
}
}

/**
* @file SimulatedAnnealing.java
* @author nsquires
* Implements the Simulated Annealing algorithm
*/
import java.util.*;

public class SimulatedAnnealing {
private final static int N=8;
int nodesGenerated;
private Queen[] startState;
private Node start;

/**
* Constructor
*/
public SimulatedAnnealing(Queen[] s){
nodesGenerated = 0;
start = new Node();
startState = new Queen[N];

for(int i=0; i<N; i++){
startState[i] = new Queen(s[i].getRow(), s[i].getColumn());
}
start.setState(startState);
start.computeHeuristic();
// startState();
}

/**
* Initializes a pseudorandom configuration of queens on
* a board
*/
public void startState(){
start = new Node();
startState = new Queen[N];
Random gen = new Random();

for(int i=0; i<N; i++){
startState[i] = new Queen(gen.nextInt(N), i);
}
start.setState(startState);
start.computeHeuristic();
}

/**
* The simulated annealing algorithm
* @param initialTemp
* @param step
* @return Node
*/
public Node simulatedAnneal(double initialTemp, double step){
Node currentNode = start;
double temperature = initialTemp;
double val = step;
double probability;
int delta;
double determine;

Node nextNode = new Node();

while(currentNode.getHeuristic()!=0 && temperature > 0){
//select a random neighbour from currentNode
nextNode = currentNode.getRandomNeighbour(currentNode);
nodesGenerated++;

if(nextNode.getHeuristic()==0)
return nextNode;

delta = currentNode.getHeuristic() - nextNode.getHeuristic();

if(delta > 0){ //currentNode has a higher heuristic
currentNode = nextNode;
}else{
probability = Math.exp(delta/temperature);
//Do we want to choose nextNode or stick with currentNode?
determine = Math.random();

if(determine <= probability){ //choose nextNode
currentNode = nextNode;
}
}
temperature = temperature - val;
}

return currentNode;
}

/**
* nodesGenerated getter
* @return
*/
public int getNodesGenerated(){
return nodesGenerated;
}

/**
* start getter
* @return
*/
public Node getStartNode(){
return start;
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.