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 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;
}

{
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();
}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;
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;
}
*/``````

What I would do is whether you find a solution or not, just keep looking.

IOW, when you find the first solution, save it in a file. Then just continue looking as if you didn't find a solution. Eventually, you should find them all.

Ya, that would be a great start though will eventually need to find only the unique solutions meaning if you were to rotate the board 4 times and their reflections. The first problem I am working on though is to just find the different solutions. With my code it always starts the same way, therefore comes up with the same solution each time. I guess rather then just incrementing the columns each time and starting at 0,0, just iteratively check random columns in each row. Hope this makes sense. Whats your thoughts?

Well, I'm not crazy about the way you approached the problem. I liked the wikipedia entry on this problem: http://en.wikipedia.org/wiki/Eight_queens, where it mentions:

"Most often, it is used as an example of a problem which can be solved with a recursive algorithm, by phrasing the n queens problem inductively in terms of adding a single queen to any solution to the problem of placing n−1 queens on an n-by-n chessboard. The induction bottoms out with the solution to the 'problem' of placing 0 queens on an n-by-n chessboard, which is the empty chessboard."

As you're a student, I'm assuming you're probably still a bit uncomfortable with recursion, which is why you're kind of simulating it here instead of using the real thing? Anyhow, I think a good start would be to push out some code for checking the symmetric/rotated solutions. Functions like:
GetRotated90(...), GetRotated180(...), GetRotated270(...), GetSymmetric(...), for example, would be helpful.

Right now, your findSolutions function is problematic because its "end-case" (i.e the point it identifies something as a solution) is when all 8 queens are out. Because of that, no matter how you randomize the starting point, you're never going to be guaranteed that your 2nd run, for example, will return a unique solution. Eventually, your end case should be that all 8 queens are out AND its a unique solution (which you get with the help of the functions listed above).

To do that, you're going to have to restructure that while loop a bit, but I'll leave that to you.

thaks for you information..

I actually did try recursion initially, but got the dreaded stack overflow:( It was something along these lines.

``````void Board::findSolutions(int col, int rows){
Position temp;

if (queens.size()== QUEEN_NUM)//A solution found
return;

else if (col == QUEEN_NUM && y == QUEEN_NUM){//if position is last on board
if(!queens.empty()){
temp = queens.top();
rows = temp.row
col = temp.column;
board[col][rows] = 0;
queens.pop();
}
}
else if(qCheck(board, col, rows))//If position is valid
putQueen(col, rows);

if(col < QUEEN_NUM-1) //if not the last column in the row
return findSolutions(col+1, rows); //go to next column

else if (col >= QUEEN_NUM-1)//if the last column in the row
return findSolutions(0, rows+1);//start in the first column on next row
}``````

After looking at this code for a moment, I guess once a valid position is found on a row I should just look on the next row instead of continuing to search every position. Something like...

``````else if(qCheck(board, col, rows)){//If position is valid
putQueen(col, rows);
return findSolutions(0, rows+1);
}``````

I do not know if this is doing enough to stop the overflow though. Appreciate the above help, keep it coming :)

Ok so after a few days, I finally got the 8 queens problem solved. After having so much trouble I decided to practice recursion by doing the same problem but with 32 knights. 8x8 board, place 32 knights without them attacking one another. I am using a 1d array. When calling the program I get a heap corruption error. I am not sure why but recursion is really escaping me. Please help. I can provide other pieces of the code if requested. Thanks

``````void Board::findSolutions(bool *board, int col, int rows, int spacesLeft)
{
if(kCheck(board, col, rows)){//Checks the 8 positions around the knight that he can attack
board[col+rows*WIDTH] = true;// If he can be placed set the position to true
knightTracker++;
}

if (knightTracker == KNIGHTS){//if all knights are placed
bool *boardN = new bool[SIZE];
for (int i = 0; i < SIZE; i++)
boardN[i] = board[i];
solutions.push_back(boardN);//Put into a solutions vector to find the unique solutions
return;
}
/////////////////////I think this base case is not working right/////////////////////
//if Last position    or how many knights left  is greater than spaces left
if((col+rows*WIDTH == SIZE)||(KNIGHTS-knightTracker > spacesLeft)){
return;
}

//copy the board and recursively check next position
for(int i = 0; i < WIDTH; i++){
bool *boardN = new bool[SIZE];
for (int j = 0; j < SIZE; j++)
boardN[j] = board[j];

findSolutions(boardN, col+1, i,SIZE-(col+rows*WIDTH));
delete[] boardN;
}
}

//Primer function to begin to find solutions
void Board::findSolutions()
{
//Create the board with all squares set to false
for(int i = 0, j = WIDTH-(WIDTH>>1); i < j; i++){
bool *boardN = new bool[SIZE];
for (int x = 0; x < SIZE; boardN[x++] = false);
//Call the overloaded findSolutions o being the process
findSolutions(boardN, 0, i, SIZE-1);
delete[] boardN;
}
}``````

Ok so after a few days, I finally got the 8 queens problem solved. After having so much trouble I decided to practice recursion by doing the same problem but with 32 knights. 8x8 board, place 32 knights without them attacking one another.

A bit off topic so apologies :)

EDIT this is an extremely wrong comment - you would not believe how good I am at games and missed this, sorry :( Obvious diagonals only solutions.

``````/*
but a knight in the corner attacks 2 squares.
A knight on the edge 3 - 4 squares
so it is not possible to place 32 knights without attacking a knight

so i would not recommend a recursive function for this.

You could try a recursive traverse shape function where you paint an area with in lines. If you have a board this is a small step up
*/``````

Actually it is possible to place 32 knights onto a chess board. A knights attack only lands on the opposite color of what they are one. So if you put a knight on every light square or on every dark square you can place 32 knights. I know the solution to the puzzle. The idea is to do this using recursion and not just program it to place on every other square. After running the debugger some more I see my columns just keep getting higher over 8.

You are going to have to avoid some pitfalls with te 32 Knights problem

first is that as a brute force search it will often fail to find a solution

There are only two solutions: as you pointed out.

If you step in a vertical line it will not fail until the 24th piece is down.

This makes it much higher order complexity than the queens problem and you need to check that your code is going to complete rather than run for years.

having said that:

Ok so after a few days, I finally got the 8 queens problem solved. After having so much trouble I decided to practice recursion by doing the same problem but with 32 knights. 8x8 board, place 32 knights without them attacking one another. I am using a 1d array. When calling the program I get a heap corruption error. I am not sure why but recursion is really escaping me. Please help. I can provide other pieces of the code if requested. Thanks

``````void Board::findSolutions(bool *board, int col, int rows, int spacesLeft)
{
if(kCheck(board, col, rows)){//Checks the 8 positions around the knight that he can attack
board[col+rows*WIDTH] = true;// If he can be placed set the position to true
knightTracker++;``````

should there be `--spaces_left` what is happening on the else where the knight is being attacked?

spacesLeft is updated to stay SIZE(64) - col+row*WIDTH(8) so it is a constant subtracted by the current position, so it increments and decrements as the position moves. Or at least thats the idea I am going for.

EDIT: I would like to post the entire code, but don't want to help anyone who is just looking for quick answers to homework or something. I have done that a couple times and realized that is what is probably happening.
If youd like I could send the rest via pm or something.

Friendly bump
My newest attempt at it. No solutions are being found, but there are no overflows and when watching autos while debugging it seems things are acting properly. I am definately missign something though and unsure what it is.

``````void Board::findSolutions(bool *board, int col, int rows, int spacesLeft)
{
knightTracker = 0;

if(kCheck(board, col, rows)){//Checks the 8 positions around the knight that it can attack
board[col+rows*WIDTH] = true;// If knight can be placed, set the position to true
//knightTracker++;
}
//loop goes through board and counts number of placed knights
for(int i=0; i<SIZE; i++){
if(board[i]==true)
knightTracker++;
}

if (knightTracker == KNIGHTS){  //If all knights are placed
bool *boardN = new bool[SIZE];
for (int i = 0; i < SIZE; i++)
boardN[i] = board[i];
solutions.push_back(boardN);//put into a solutions vector to find the unique solutions
return;
}
//if on the last position or the number of knights left is greater than spaces left
if((col+rows*WIDTH == SIZE)||(KNIGHTS-knightTracker > spacesLeft)){
//knightTracker--;
return;
}

//copy the board and recursively check next position
for(int i = 0; i < WIDTH; i++){
bool *boardN = new bool[SIZE];
for (int j = 0; j < SIZE; j++)
boardN[j] = board[j];
///Columns are incrementing too far
if (col >= 7)
return;
//	findSolutions(boardN, 0, i,SIZE-(col+rows*WIDTH));
else
findSolutions(boardN, col+1, i,SIZE-(col+rows*WIDTH));

delete[] boardN;
}
}``````

My comment in my last post was concerned with the following condition.

if `(kCheck` is false this second condition:

``)||(KNIGHTS-knightTracker > spacesLeft)``

is unaltered as the number of knights remaining is the same so
unless spaces remaining are reduced this will not fire.

As for finding no solutions...
This is a more complex issue and as I expressed badly before the order of complexity of the problem is such that a brute force recursive function might fail to find one of the two solutions.

If I was doing this recursively, my logic would be every time I add a knight to the board I would add all the squares that are attacked by it. Then every attacked square I would add an attack too reducing the number of spaces left at the same time.

This uses an int for each square rather than a bool so that the move can be unwound easily when removing the last knight placed.

so I would consider the logic of `kCheck` as it should adjust the spaces left.

The other line that I find confusing without running it is as follows:

``findSolutions(boardN, col+1, i,SIZE-(col+rows*WIDTH));``

Now this might be corret to give a solution.
What i read this as doing is:
1 - you are stepping horizontally along the row
2 - stepping along each column
3 - reducing the number of spaces left to reflect squares untested by latest run
4 - setting the value for board of 64 values for each iteration

Now when you find a solution you still have to continue through the entire iteration to check for other solutions.
my concern is that this appears to be the order of 64! times that the function can get called. and creating a new board every time.

Assuming I haven't got your iteration wrong ;)
I think you need to dramatically reduce your calculations.
If this is a project to test recursive functions rather than building towards a chess AI. It is best to avoid recursive functions for tree logic patterns as it is trickier to put in overflow safeguards.

Problems such as the knight's tour or painting a shape are both better suited to recursion.

if `(kCheck` is false this second condition:

is unaltered as the number of knights remaining is the same so
unless spaces remaining are reduced this will not fire.
.

That is the idea, though it occurs if it is true or false it's not an else statement. I think I read what you said right anyway.
1)It does find the current number of knights placed

``````for(int i=0; i<SIZE; i++){
boardN[i] = board[i];
if(board[i]== 1)
knightTracker++;
}``````

2)Also decrements the spacesleft by subtracting the current array element(position) from total size.

``````if (col < WIDTH-1)
findSolutions(boardN, col+1, rows,SIZE-(col+rows*WIDTH));
if (col >= WIDTH-1)
findSolutions(boardN, 0, rows+1,SIZE-(col+rows*WIDTH));``````

As you see in the top two recursive calls I changed how I was doing them and unsure if it is correct, but its ever changing atm. I took your advice and marked all squares attack by the current knight as wel, let me show you the few functions I think are valid. And remember at the same time I have functions and stuff in place that will check all solutions symmetry to ensure only uniques are found. When ran I get:

Windows has triggered a breakpoint in project1_cs232.exe.
This may be due to a corruption of the heap, which indicates a bug in project1_cs232.exe or any of the DLLs it has loaded.
This may also be due to the user pressing F12 while project1_cs232.exe has focus.
The output window may have more diagnostic information.

Sorry in advance for the messy, odd wall of code.

``````bool Board::kCheck(int *board, int col, int rows)
{
int pos = col+rows*WIDTH ;
///incrementing columns before incrementing rows
//short up left
if(col>=2&& rows>=1){
if(board[pos-10]==1)
return false;
}
//far up left
if(col>=1&&rows>=2){
if(board[pos-17]==1)
return false;
}
//short down left
if(col>=2 && rows<=6){
if(board[pos+6]==1)
return false;
}
//far down left
if(col>=1 && rows<=5){
if(board[pos+15]==1)
return false;
}
//short up right
if(col<=5&&rows<=1){
if(board[pos-6]==1)
return false;
}
//far up right
if(col<=6 && rows<=2){
if(board[pos-15]==1)
return false;
}
//short down right
if(col<=5 && rows<=6){
if(board[pos+10]==1)
return false;
}
//far down right
if(col<=6 && rows<=5){
if(board[pos+17]==1)
return false;
}
return true;
}

void Board::placeKnight(int *board, int col, int rows)
{
int pos = col+rows*WIDTH ;

//Everywhere the knight can attack is set to 2
//short up left
if(col>=2&& rows>=1)
board[pos-10]=2;
//far up left
if(col>=1&&rows>=2)
board[pos-17]=2;
//short down left
if(col>=2 && rows<=6)
board[pos+6]=2;
//far down left
if(col>=1 && rows<=5)
board[pos+15]=2;
//short up right
if(col<=5&&rows<=1)
board[pos-6]=2;
//far up right
if(col<=6 && rows<=2)
board[pos-15]=2;
//short down right
if(col<=5 && rows<=6)
board[pos+10]=2;
//far down right
if(col<=6 && rows<=5)
board[pos+17]=2;

//Set knight as 1
board[pos]=1;
}

void Board::findSolutions(int *board, int col, int rows, int spacesLeft)
{
//cout <<"Working \n";
knightTracker = 0;

if(kCheck(board, col, rows)){//Checks the 8 positions around the knight that it can attack
//board[col+rows*WIDTH] = 1;// If knight can be placed, set the position to true
placeKnight(board,col,rows);
}

int *boardN = new int[SIZE];
//loop goes through board, copies it to a temp board and counts number of placed knights
for(int i=0; i<SIZE; i++){
boardN[i] = board[i];
if(board[i]== 1)
knightTracker++;
}
//base case 1
if (knightTracker == KNIGHTS){  //If all knights are placed
solutions.push_back(boardN);//put into a solutions vector to find the unique solutions
printBoard(boardN);//testing findsolution
return;
}
//base case 2
//if on the last position or the number of knights left is greater than spaces left
if((col+rows*WIDTH == SIZE)||(KNIGHTS-knightTracker > spacesLeft))
return;

for(int i = 0; i < SIZE; i++){
if(board[i]==0){
if (col < WIDTH-1)
findSolutions(boardN, col+1, rows,SIZE-(col+rows*WIDTH));
if (col >= WIDTH-1)
findSolutions(boardN, 0, rows+1,SIZE-(col+rows*WIDTH));
delete[] boardN;
}
}
}``````

minor issue in you check position in that are you checking the current position is empty as well as not attacked?

There are some maintenance issues creeping-in and these are being exagerated by changing design half way throuh

you might want some methods or classes that hide some of the magic numbers

``````int get_ind(int row, int col)
{
int ret(-1);
if(row >= 0 && row < width)
{
int ret = row + col *width;
if(ret >= size)
{
ret = -1;
}
}
return ret;
}``````
``````bool is_knight(bool * board, int row, int col)
{
bool ret(false);
int ind = get_ind(row, col);
if(ind != -1)
{
ret = board[ind];
}
return ret;
}``````
``````bool am_I_attacked(int row, int col)
{
bool ret(false);
int ind = get_ind(row, col);
if(ind != -1)
{
if(is_knight(row + 1, col + 2))
{
ret = true;
}
//etc
}
}``````

this makes it easier to see rather than the -17 and col >2

although I think from number of steps you might need to completely change board `int board[width * height];`

``````void add_knight(int * board, int row, int col)
{
//just set inds greater than current pos
set_board(board, row + 1, col + 2);
set_board(board, row - 1, col + 2);
set_board(board, row - 2, col + 1);
set_board(board, row + 2, col + 1);
++knightTracker;
}

void set_board(int * board, int row, int col, bool b /*=true*/)
{
int ind = get_ind(row, col);
if(ind != -1)
{
if(b == true)
{
board[ind] += 1;
}
else
{
board[ind] -= 1;
}
}
}``````

the reason for this is then you can keep track of your current position once you add a knight to the free empty slot
you check your knightTraker and then go from current pos

until size

``````int pos = get_ind(row, col);
if(pos > = 0 && pos < SIZE && board[pos] == 0)
{
v_pos.push_back(pos);
//check total knights here

//if not find next position to test
++pos;
while(pos < SIZE)
{
if(board[pos] >= 0)
{
++row;
if(row >width)
{
++col;
row -= width;
}
++pos;
}
else
{
break;
}
}
}``````

that will move to the next empty pos now you can just check the empty squares iteratively and if you start with a small board say 5*5 you can judge how long it will take to run.

using both pos and row and col is a bit of an overhead but it keeps the design closer to what you have already

now you only need one board as you can unwind moves if you wish.

although I would test with a small board as this still could prove too big for recursion.

Ok I will give this a try. One question currently though. what is v_pos ?
The vector I use in my code stores the solution once found, and from there is put into a function that chekcs and eliminates all symmetric solutions. The vector? variable name you use leads me to believe its a vector of individual positions? BTW thanks a bunch for the pointers and advice already given. Also Basically the functions you gave will replace my overloaded findsolutions function as well as the position checker and place knight functions? Thats what it looks like, but just to clarify.

Ok I will give this a try. One question currently though. what is v_pos ?

What I was giving as an alternative design had `v_pos` as a `std::vector<int>` the idea is that the last item is the last move tried.
so pos is just an index, on reflection this might have been better wrapped in side a coord class in the first place.

Now it is not necessary to change your entire design over at this point as it should work for small boards.

If you use the functions to remove the magic numbers then you can alter the , width & height of your board. This might indicate if my worries about your code taking too long to run will be addressed.

I would first check that al the solutions are being found with 4x4 and 8 knights and 5 x 5 with 13 knights

and then try increasing the size gradually.

I have not tested this to see if there is an issue but my concern is that, in effect, you are trying to think 31 moves ahead and even with 2 or three options a turn this is getting close to being too big to solve iteratively.

I know in a game a PC can take 45 minutes for 10 move depth with a heuristic algorithm for some games.

If I was doing this without iteration I would make the algorithm learn the shapes of placing the knights, In this instance, you know the density of Knights early on and it will not take long to find the solution.

so my design for an iterative solution may still prove to slow.

- the idea is:

1. you start at the smallest available pos.
2. you never place a new knight at an index smaller than the last knight was placed
3. add a knight to the next free pos (no knight + no attack)
--squaresLeft, ++knightTracker, store this free_pos)
4. add new attacks from the current knight
check for each

if was 0 ,
--squaresLeft
+= 1 to each square above current pos.

5. check remaining squares and knights for stop conditions
6. if no more combinations, undo last stored move advance to next free pos. (this is an unwind followed by an iterative call with pos increased) I will come back to this
7. else repeat for pos = free_pos + 1.

the find solution method

``bool find_solution(int * board, int cur_pos, int squares_left, int knights_left);``

so step 6.
removes cur_pos.

``````//reduces squares left
remove_knight(board, cur_pos, squares_left);
++knights_left;
v_pos.pop_back();``````

calls

``````++cur_pos;
if(cur_pos < size)
{
return find_solution(board, cur_pos, squares_left, knights_left);
}
else
{
return false;
}``````

and step 7:

``````add_knight(board, pos, squares_left);
--knights_left;
v_pos.push_back(next_pos);
cur_pos = next_pos + 1;
return find_solution(board, cur_pos, squares_left, knights_left);``````

the stage I haven't included is the stop condition which is the same as you were using before.
How to store a knight does not matter unless you change the iteration only the attacks on suares yet to be considered

to find the free position

``````int next_pos(cur_pos);
while(next_pos < size)
{
if(board[next_pos]  == 0)
{
//placed knight
break;
}
++next_pos;
}``````

This is obviously, only one approach, and you want to stop as soon as you find any solution for now.

Well I spent many hours this weekend and finally found a solution around five this monring!!! Thanks tetron for the help. My design just needed some minor tweaks in part thanks to you, and in part thanks to my inability to sleep with something like this bugging me. :)