C++ or Java please Assignment #1 You are to write a program in the language of y
ID: 3756646 • Letter: C
Question
C++ or Java please
Assignment #1 You are to write a program in the language of your choice to find all 92 solutions to the eight queens problem. You should conceptualize the problem as a tree and traverse every distinct path in that tree to find the solutions. The example of a non-solution I demonstrated in class traversed one specific path. You should be able to convince me and your classmates that all solutions have been found and you should be able to read you program's output, choose an arbitrary solution (one picked randomly from your solution set), and draw it on the white board. You should explain data structures you used, how much total memory you needed and how long your algorithm needed to find 92 sclutions. Collaboration is permitted, even encouraged. Results will be presented in class.Explanation / Answer
package DS;
import java.util.*;
// Class NQueenAllSolutions definition
public class NQueenAllSolutions
{
// Defines a constant for N x N chess board
public static final int BOARDSIZE = 8;
// Static method to return true if a queen is in safe state otherwise returns false
private static boolean checkSafe(char chessBoard[][], int row, int col)
{
// Returns false if two queens are available in the same column
// Loops till row value
for (int r = 0; r < row; r++)
// Checks if r and col index position of the matrix chessBoard contains character 'Q'
// then returns false
if (chessBoard[r][col] == 'Q')
return false;
// Return false if two queens are available in the same left diagonal
// Loops till either row and column is grater than or equals to zero
for (int r = row, c = col; r >= 0 && c >= 0; r--, c--)
// Checks if r and c index position of the matrix chessBoard contains character 'Q'
// then returns false
if (chessBoard[r][c] == 'Q')
return false;
// Return false if two queens are available in the same right diagonal
// Loops till either row is greater than or equals to zero and column is less than board size
for (int r = row, c = col; r >= 0 && c < BOARDSIZE; r--, c++)
// Checks if r and c index position of the matrix chessBoard contains character 'Q'
// then returns false
if (chessBoard[r][c] == 'Q')
return false;
// Otherwise return true. Queen is in safe place
return true;
}// End of method
// Static method to find solution to N queen problem and prints the solution
private static void nQueenSolution(char chessBoard[][], int row)
{
// Checks if N queens are placed successfully, then print the solution
// Checks if parameter row value is equals to board size
if (row == BOARDSIZE)
{
// Loops till board size for number of rows
for (int r = 0; r < BOARDSIZE; r++)
{
// Loops till board size for number of columns
for (int c = 0; c < BOARDSIZE; c++)
// Displays each cell value
System.out.print(chessBoard[r][c] + " ");
System.out.println();
}// End of for loop
System.out.println();
return;
}// End of if condition
// Otherwise place queen at every square in current row r and recurse for each valid movement
for (int c = 0; c < BOARDSIZE; c++)
{
// Checks if no two queens threaten each other
if (checkSafe(chessBoard, row, c))
{
// Assigns character 'Q' for queen on current square
chessBoard[row][c] = 'Q';
// Recursively calls the method for next row
nQueenSolution(chessBoard, row + 1);
// Backtrack and remove queen from current square by replacing character'-'
chessBoard[row][c] = '-';
}// End of if condition
}// End of for loop
}// End of method
// main method definition
public static void main(String[] args)
{
// Creates a matrix for chess board with row and column size as BOARDSIZE
char[][] chessBoard = new char[BOARDSIZE][BOARDSIZE];
// Loops till number of rows to initialize chess board by character '-'
for (int r = 0; r < BOARDSIZE; r++)
Arrays.fill(chessBoard[r], '-');
// Calls the method to find and print the N queen solution
nQueenSolution(chessBoard, 0);
}// End of main method
}// End of class
Sample Output:
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- - - - Q - - -
- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.