Program Assignment #1 (with Java) Instructions: Write a program that places 8 qu
ID: 3856221 • Letter: P
Question
Program Assignment #1 (with Java)
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).
The rubric below will be used in the grading of your program. Partial points may be awarded for each category.
Category Value Program is free of syntax and runtime errors / 10
Problem solved using the Hill-Climbing with random restarts algorithm / 10
Program successfully finds a solution / 40
Program outputs required information in the format described / 20
Program restarts when local minima is reached / 10
Program utilizes an appropriate heuristic /10
Total Points / 100
Sample Execution Program Output
Current h: 8
Current State
0,0,0,0,1,0,0,0,0,0
0,0,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
1,0,1,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,1,1,0
0,0,0,0,0,0,1,0,0,0
0,0,0,0,0,1,0,0,0,1
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 2
Setting new current state
Current h: 5
Current State
0,0,0,0,1,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
0,0,0,1,0,0,0,0,0,0
1,0,1,0,0,0,0,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,1,0,0,0
0,0,0,0,0,1,0,0,0,1
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 2
Setting new current state
Current h: 3
Current State
0,0,0,0,1,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
0,0,0,1,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,1,0,0,0
0,0,0,0,0,1,0,0,0,1
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 1
Setting new current state
Current h: 1
Current State
0,0,0,0,1,0,0,0,0,0
0,0,0,0,0,0,0,1,0,0
0,0,0,0,0,1,0,0,0,0
0,0,0,1,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,1,0,0,0
0,0,0,0,0,0,0,0,0,1
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 0
RESTART
Current h: 10
Current State
0,0,0,0,0,0,0,0,0,0
0,0,0,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,0,0,1,0,0,0,0,1,0
1,1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0,0,1
0,0,1,0,0,1,0,0,0,0
Neighbors found with lower h: 20
Setting new current state
Current h: 8
Current State
0,0,0,0,0,1,0,0,0,0
0,0,0,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,0,0,1,0,0,0,0,1,0
1,1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0,0,1
0,0,1,0,0,0,0,0,0,0
Neighbors found with lower h: 8
Setting new current state
Current h: 6
Current State
0,0,0,0,0,1,0,0,0,0
0,1,0,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,0,0,1,0,0,0,0,1,0
1,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0,0,1
0,0,1,0,0,0,0,0,0,0
Neighbors found with lower h: 3
Setting new current state
Current h: 4
Current State
0,0,0,0,0,1,0,0,0,0
0,1,0,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,0,0,1,0,0,0,0,1,0
1,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,1,0,0,0
0,0,1,0,0,0,0,0,0,0
Neighbors found with lower h: 1
Setting new current state
Current h: 2
Current State
0,0,0,0,0,1,0,0,0,0
0,1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,1,0,0,0,0,0
0,0,0,0,0,0,0,1,0,0
0,0,0,1,0,0,0,0,0,0
1,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,1,0,0,0
0,0,1,0,0,0,0,0,0,0
Neighbors found with lower h: 0
RESTART
Current h: 10
Current State
0,1,0,1,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,0,0,0,0,0,0
0,0,0,0,1,0,1,1,0,1
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
Neighbors found with lower h: 1
Setting new current state
Current h: 7
Current State
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,0,0,0,0,0,0
0,0,0,0,1,0,1,1,0,1
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,0,0,0,0
Neighbors found with lower h: 1
Setting new current state
Current h: 5
Current State
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,1,0,0,0,0,0
0,0,0,0,0,0,1,1,0,1
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,0,0,0,0
Neighbors found with lower h: 7
Setting new current state
Current h: 4
Current State
0,0,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,1,0,0,0,0,0
0,0,0,0,0,0,1,1,0,1
0,0,0,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 2
Setting new current state
Current h: 2
Current State
0,0,0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0,0,0
1,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,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,1,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 2
Setting new current state
Current h: 1
Current State
0,0,0,0,0,0,1,1,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,1,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,0,1,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0
Neighbors found with lower h: 1
Setting new current state
Current State
0,0,0,0,0,0,1,0,0,0
0,0,1,0,0,0,0,0,0,0
1,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,0,0,1,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,1,0,0
0,0,0,1,0,0,0,0,0,0
0,1,0,0,0,0,0,0,0,0
Solution Found!
State changes: 29
Restarts: 6
Explanation / Answer
C/C++ program to solve N Queen Problem using
backtracking */
#define N 4
#include<stdio.h>
/* A utility function to print solution */
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("n");
}
}
/* A utility function to check if a queen can
be placed on board[row][col]. Note that this
function is called when "col" queens are
already placed in columns from 0 to col -1.
So we need to check only left side for
attacking queens */
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i])
return false;
/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j])
return false;
/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j])
return false;
return true;
}
/* A recursive utility function to solve N
Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;
/* Consider this column and try placing
this queen in all rows one by one */
for (int i = 0; i < N; i++)
{
/* Check if queen can be placed on
board[i][col] */
if ( isSafe(board, i, col) )
{
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
if ( solveNQUtil(board, col + 1) )
return true;
/* If placing queen in board[i][col]
doesn't lead to a solution, then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* If queen can not be place in any row in
this colum col then return false */
return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQUtil() to
solve the problem. It returns false if queens
cannot be placed, otherwise return true and
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions.*/
bool solveNQ()
{
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if ( solveNQUtil(board, 0) == false )
{
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
// driver program to test above function
int main()
{
solveNQ();
return 0;
}
Run on IDE
Output: The 1 values indicate placements of queens
C/C++ program to solve N Queen Problem using
backtracking */
#define N 4
#include<stdio.h>
/* A utility function to print solution */
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("n");
}
}
/* A utility function to check if a queen can
be placed on board[row][col]. Note that this
function is called when "col" queens are
already placed in columns from 0 to col -1.
So we need to check only left side for
attacking queens */
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i])
return false;
/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j])
return false;
/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j])
return false;
return true;
}
/* A recursive utility function to solve N
Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;
/* Consider this column and try placing
this queen in all rows one by one */
for (int i = 0; i < N; i++)
{
/* Check if queen can be placed on
board[i][col] */
if ( isSafe(board, i, col) )
{
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
if ( solveNQUtil(board, col + 1) )
return true;
/* If placing queen in board[i][col]
doesn't lead to a solution, then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* If queen can not be place in any row in
this colum col then return false */
return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQUtil() to
solve the problem. It returns false if queens
cannot be placed, otherwise return true and
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions.*/
bool solveNQ()
{
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if ( solveNQUtil(board, 0) == false )
{
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
// driver program to test above function
int main()
{
solveNQ();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.