My goal in this program is to solve for the 12 unique solutions for the 8 queens problem. All the below posted is my code. I believe that my findSolutions function is capable of finding the first solution but I have a couple issues from that point. If the user wants to see a different solution it needs to find a different one, currently mine finds the same one over and over. I suppose I need to use a random starting point for the new solution. Will that work and if so any recomendations on doing that would be nice. Also once the first solution is found or second, etc., I need to eliminate its symmetric solutions so I am only producing 12 in total. I think I have the proper algorithms to check for them but unsure how to implement them so they aren't provided as solutions. I am sure my post is somewhat confusing, as I am confused. Any advice would be appreciated. Please don't post the code as I am a student, but any psuedocode and tips would be excellent. Thanks in advance.
#include <iostream>
#include <stack>
#include<vector>
using namespace std;
const int QUEEN_NUM = 8;
struct Position{
int column,
row;
};
class Board {
private:
int** board; // NxN matrix which represents the board
stack<Position> queens; //A stack that holds the current solution queen positions
public:
vector<stack<Position>> solutions;
Board();
~Board();
bool qCheck(int**, int, int); // checks invalid queen positions for a single queen
void findSolutions(); //Searches for a single solution
void putQueen(int, int); // places a queen on the board, in position (i,j);
void printBoard(); // prints the board configurations
stack<Position> getQueens();
int getBoard();
};
#include "queens.h"
Board::Board()
{
board=new int*[QUEEN_NUM];
for(int i=0; i < QUEEN_NUM; i++) {
board[i]=new int[QUEEN_NUM];
}
for(int rows=0; rows < QUEEN_NUM; rows++) {
for(int col=0; col < QUEEN_NUM; col++) {
board[col][rows] = 0;
}
}
}
Board::~Board()
{
for(int i = 0; i < QUEEN_NUM; i++) {
delete [] board[i];
}
delete [] board;
}
bool Board::qCheck(int** board, int col, int rows )
{
////////////Check for invalid position///////////////
//Checks the current spot
if(board[col][rows])
return false;
// checks horizontal right movement
for(int b=(col+1); b < QUEEN_NUM; b++) {
if(board[b][rows]) {
return false;
}
}
// checks horizontal left movement
for(int b=(col-1); b >= 0; b--) {
if(board[b][rows]) {
return false;
}
}
// checks vertical up movement
for(int a=(rows-1); a >= 0; a--) {
if(board[col][a]) {
return false;
}
}
// checks vertical down movement
for(int a=(rows+1); a < QUEEN_NUM; a++) {
if(board[col][a]) {
return false;
}
}
// checks diagonal down-right movement
for(int a=(rows+1), b=(col+1); a < QUEEN_NUM && b < QUEEN_NUM; a++, b++) {
if(board[b][a]) {
return false;
}
}
// checks diagonal up-right movement
for(int a=(rows-1), b=(col+1); a >= 0 && b < QUEEN_NUM; a--, b++) {
if(board[b][a]) {
return false;
}
}
// checks diagonal up-left movement
for(int a=(rows-1), b=(col-1); a >= 0 && b >= 0; a--, b--) {
if(board[b][a]) {
return false;
}
}
// checks diagonal down-left movement
for(int a=(rows+1), b=(col-1); a < QUEEN_NUM && b >= 0; a++, b--) {
if(board[b][a]) {
return false;
}
}
return true;
}
void Board::printBoard()
{
cout << endl << endl;
for(int i=0; i < QUEEN_NUM; i++) { //Top border of board
cout << " _";
}
cout << endl;
for(int rows=0; rows < QUEEN_NUM; rows++) { //The left side of each square
cout << "|";
for(int col=0; col < QUEEN_NUM; col++) {
if(board[col][rows]==0) { //If no queen in this position
cout << "_"; //Draw an empty square
cout << "|";
}
else if(board[col][rows]==1) { //If there is a queen in position
cout << "Q"; //Display Queen symbol
cout << "|"; //and right side of square
}
}
cout << endl;
}
}
void Board::findSolutions()
{
Position temp;
int rows = 0, col = 0;
while(queens.size()!= QUEEN_NUM){
if(qCheck(board,col,rows)){ //If this is a valid position
putQueen(col,rows); //Put the queen here
rows++;
col = 0;
}
if(col==QUEEN_NUM-1){ //If on the last space of the board
if(!queens.empty()){
temp = queens.top(); //gain access to position on top of stack
rows = temp.row; //set variable x
col = temp.column; //and y to the position from top of stack.
board[col][rows] = 0;
queens.pop(); //Remove position from top of stack
}
}
if (col < QUEEN_NUM-1)
col++;
else if (col >= QUEEN_NUM-1&& rows <QUEEN_NUM-1){
col = 0;
rows++;
}
}
printBoard(); //show the solution
}
void Board::putQueen(int col, int rows)
{
Position temp;
board[col][rows] = 1; //Assign 1 to queens position
temp.column = col; //give the coordinates to a temp position object
temp.row = rows;
queens.push(temp); //Store the position in stack
}
stack<Position> Board::getQueens()
{
return queens;
}
/*
int Board::getBoard()
{
return board;
}*/
void main()
{
Board board;
board.findSolutions();
}
#pragma once
#include <vector>
#include <stack>
#include <iostream>
#include "queens.h"
using namespace std;
class Interface
{
private:
/*vector<stack<Position>> allSolutions;
vector<int **> uniqueSolutions;
int** singleSolution;
int** rotate(int**);
int** invert(int**);
void findUnique();*/
public:
vector<int**> allSolutions;
int** singleSolution;
int** rotate(int**);
int** invert(int**);
void findUnique();
Interface();
~Interface();
void menu();
void symmetricSolutions();
};
#include "Interface.h"
Interface::Interface(void)
{
singleSolution =new int*[QUEEN_NUM];
for(int i=0; i < QUEEN_NUM; i++) {
singleSolution[i]=new int[QUEEN_NUM];
}
for(int rows=0; rows < QUEEN_NUM; rows++) {
for(int col=0; col < QUEEN_NUM; col++) {
singleSolution[col][rows] = 0;
}
}
}
Interface::~Interface(void)
{
for(int i = 0; i < QUEEN_NUM; i++) {
delete [] singleSolution[i];
}
delete [] singleSolution;
}
void Interface::menu()
{
int choice;
Board temp;
cout<< "8 Queens" << endl;
cout<< "Please make a choice" << endl;
cout<< "1: See a unique solution" << endl;
cout<< "2: See already found solutions" << endl;
cout<< "3: Exit Program" << endl;
cin >> choice;
switch(choice){
case 1:{
temp.findSolutions();
//allSolutions.push_back();
menu();
}break;
case 2:{
for(int j = 0;j<QUEEN_NUM;j++)
for(int i = 0;i<QUEEN_NUM;i++)
cout << allSolutions[i][j] << endl;
}break;
case 3:return;
default:{
cout << "Improper entry, try again." << endl;
menu();
break;
}
}
}
/*
int** Interface::rotate(int** boardIn)
{
int** boardOut;
boardOut = new int*[QUEEN_NUM];
for(int i=0; i < QUEEN_NUM; i++) {
boardOut[i]=new int[QUEEN_NUM];
}
for(int i=0; i < QUEEN_NUM; i++)
for(int j=0; j < QUEEN_NUM; j++)
boardOut[i][j]= boardIn[7-j][i];
return boardOut;
}
int** Interface::invert(int** boardIn)
{
int** boardOut;
boardOut = new int*[QUEEN_NUM];
for(int i=0; i < QUEEN_NUM; i++) {
boardOut[i]=new int[QUEEN_NUM];
}
for(int j=0; j < QUEEN_NUM; j++)
for(int i=0; i < QUEEN_NUM; i++)
boardOut[i][j]= boardIn[7-i][j];
return boardOut;
}*/
/*
void Interface::findUnique()
{
Board temp;
//temp.findSolutions();
int i = 0;
while(allSolutions[i]!=allSolutions.end()){
temp.findSolutions();
uniqueSolutions.push_back(temp.getQueens());
//if(temp.getQueens()= allSolutions[i])
// break;
i++;
}
}
*/
void Interface::symmetricSolutions(){}
/*{
Board temp;
temp.findSolutions(); ///Need to use findUnique here but it isnt functioning yet
allSolutions.push_back(temp.getBoard()); //1
singleSolution = rotate(temp.getBoard());//rotate 1
allSolutions.push_back(singleSolution); //2
singleSolution = invert(singleSolution); //invert 1
allSolutions.push_back(singleSolution); //3
singleSolution = rotate(singleSolution); //rotate 2
allSolutions.push_back(singleSolution); //4
singleSolution = invert(singleSolution); //invert 2
allSolutions.push_back(singleSolution); //5
singleSolution = rotate(singleSolution); //rotate 3
allSolutions.push_back(singleSolution); //6
singleSolution = invert(singleSolution); //invert 3
allSolutions.push_back(singleSolution); //7
singleSolution = invert(singleSolution); //invert 4
allSolutions.push_back(singleSolution); //8
}*/
/*
void main(){
Interface inter;
inter.menu();
}
*/