This program will use arc-consistency to remove the invalid values from the variable
domain and generate the permutations for the 8 queen problem.

Here is the source code with the make file.

chessboard.h

#include <iostream>		// uses std::cout std::cin
#include <stdlib.h>
#include <stdio.h>		// uses exit(0) and fprintf
#include <stack>                // uses std::stack 
#include <vector>
#ifndef CHESSBOARD_H
#define CHESSBOARD_H

class ChessBoard
{
public:
 void PutQueen(int pos);
 void TakeQueen(int pos);
 void GetAvaliablePositions(std::vector<int>&);

 //!constructor
 ChessBoard();
 ~ChessBoard();
private:
 int lastAvaliablePosition;
 enum CellState
 {
    CELL_AVALIABLE ,
    CELL_NOT_AVALIABLE
 };

 CellState cells[64];
 std::stack<int> undo_stack;
};


#endif

chessboard.cpp

#include "chessboard.h"
#include <stdio.h>
#include <stdlib.h>
#include <vector>		// uses std::vector

/* macros for the debug purposes */
#define PRINT_VECTOR(vector) for(int i=0;i<vector.size();i++)std::cout<<vector[i]<<" ";

// !constructor
ChessBoard::ChessBoard()
{
  // set all the cells to avaliable
 for(int i=0;i<64;i++)
  cells[i]=CELL_AVALIABLE;

  lastAvaliablePosition=0;
 // we don't need to clear the stack since when the constructor is called it's cleared.
}

// ! destructor 
ChessBoard::~ChessBoard()
{
 // ~ Do nothing here.
}

void ChessBoard::PutQueen(int pos)
{
 int undo_count=0;
 
 // set the pos unavaliable.
 cells[pos-1]=CELL_NOT_AVALIABLE;
 undo_stack.push(pos);
 undo_count++;

 // horizontally,
 int i=pos;
 while(i>8)
  {
   i=i-8;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
  }
 i=pos;
 while(i<57)
 {
  i=i+8;
  if(cells[i-1]!= CELL_NOT_AVALIABLE)
  {
   cells[i-1] = CELL_NOT_AVALIABLE;
   undo_stack.push(i);
   undo_count++;
  }
 }
 
 i=pos;
 while(i%8!=0)
 {
   i++;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1]=CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=1)
 {
   i--;
   if(cells[i-1]!=CELL_NOT_AVALIABLE)
   {
    cells[i-1]=CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=0&&i<57)
 {
  i=i+9;
  if(cells[i-1]!= CELL_NOT_AVALIABLE)
  {
   cells[i-1] = CELL_NOT_AVALIABLE;
   undo_stack.push(i);
   undo_count++;
  }
 }
 i=pos;
 while(i%8!=1&&i>8)
 {
  i=i-9;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=1&&i<57)
 {
  i=i+7;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }  
 }
 
 i=pos;
 while(i%8!=0&&i>8)
 {
   i=i-7;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 // now push the undo_count.
 undo_stack.push(undo_count);
}

void ChessBoard::TakeQueen(int pos)
{
 // get the undo_count
 int undo_count=undo_stack.top();
 undo_stack.pop();
 for(;undo_count>0;undo_count--)
 {
  int undo_pos=undo_stack.top();
  undo_stack.pop();
  cells[undo_pos-1]=CELL_AVALIABLE;
 }
}

void ChessBoard::GetAvaliablePositions(std::vector<int>& _input)
{
 lastAvaliablePosition=-1;
 while(cells[++lastAvaliablePosition] != CELL_AVALIABLE&& lastAvaliablePosition<65);
 while(lastAvaliablePosition<65)
 {
  _input.push_back(lastAvaliablePosition+1);
  while(cells[++lastAvaliablePosition] != CELL_AVALIABLE&& lastAvaliablePosition<65);
 }
 //PRINT_VECTOR(_input);

}

search.cpp

/* Author : M Sandun Dhammika Perera.(sandundhammikaperera@yahoo.com PS:-communication dev ideas only).
 * License: GNU GPL
 * purpose: To demonstrate 8-queen problem.
 * :NOTE: This program will generate all the premutations of the 8th queen problem but not the combinations.
 */

#include <iostream>		//uses std:;cin std::cout
#include <stdio.h>
#include <stdlib.h>
#include "chessboard.h"
#include <vector>			// uses std::vector

void search(int(&)[8],ChessBoard& ,int);
void print_queen_locations(int(&)[8]);
int queens[8];

int main(int argc,char argv[])
{
 ChessBoard chess_board;
 search(queens,chess_board,1);
 return 0;
}

void search(int(&queens)[8],ChessBoard& chess_board,int queen)
{
 if(queen==8)
 {
  std::vector<int> avaliable_positions;
  avaliable_positions.clear();
  chess_board.GetAvaliablePositions(avaliable_positions);
  for(int i=0;i<avaliable_positions.size();i++)
  {
    queens[7]=avaliable_positions[i];
    print_queen_locations(queens);
  }
 }else
 {
  std::vector<int> avaliable_positions;
  avaliable_positions.clear();
  chess_board.GetAvaliablePositions(avaliable_positions);
  for (int i=0;i<avaliable_positions.size();i++)
  {
    int pos=avaliable_positions[i];
    chess_board.PutQueen(pos);
    queens[queen-1]=pos;
    search(queens,chess_board,queen+1);
    chess_board.TakeQueen(pos);
  }
 }
}

void print_queen_locations(int(& queen)[8])
{
 std::cout<<'<';
 for(int i=0;i<8;i++)
   std::cout<<queen[i]<<" ";
 std::cout<<'>'<<'\n';
}

Makefile

CC=g++

all:queen

queen:chessboard.o search.o 
	$(CC) -o queen chessboard.o search.o -g

chessboard.o:chessboard.cpp
	$(CC) -c chessboard.cpp -g

search.o:search.cpp
	$(CC) -c search.cpp -g

clean: 
	rm -f *.o queen
450 Views
chessboard.h
[code]
#include <iostream>		// uses std::cout std::cin
#include <stdlib.h>
#include <stdio.h>		// uses exit(0) and fprintf
#include <stack>                // uses std::stack 
#include <vector>
#ifndef CHESSBOARD_H
#define CHESSBOARD_H

class ChessBoard
{
public:
 void PutQueen(int pos);
 void TakeQueen(int pos);
 void GetAvaliablePositions(std::vector<int>&);

 //!constructor
 ChessBoard();
 ~ChessBoard();
private:
 int lastAvaliablePosition;
 enum CellState
 {
    CELL_AVALIABLE ,
    CELL_NOT_AVALIABLE
 };

 CellState cells[64];
 std::stack<int> undo_stack;
};


#endif
[/code]

chessboard.cpp
[code]
#include "chessboard.h"
#include <stdio.h>
#include <stdlib.h>
#include <vector>		// uses std::vector

/* macros for the debug purposes */
#define PRINT_VECTOR(vector) for(int i=0;i<vector.size();i++)std::cout<<vector[i]<<" ";

// !constructor
ChessBoard::ChessBoard()
{
  // set all the cells to avaliable
 for(int i=0;i<64;i++)
  cells[i]=CELL_AVALIABLE;

  lastAvaliablePosition=0;
 // we don't need to clear the stack since when the constructor is called it's cleared.
}

// ! destructor 
ChessBoard::~ChessBoard()
{
 // ~ Do nothing here.
}

void ChessBoard::PutQueen(int pos)
{
 int undo_count=0;
 
 // set the pos unavaliable.
 cells[pos-1]=CELL_NOT_AVALIABLE;
 undo_stack.push(pos);
 undo_count++;

 // horizontally,
 int i=pos;
 while(i>8)
  {
   i=i-8;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
  }
 i=pos;
 while(i<57)
 {
  i=i+8;
  if(cells[i-1]!= CELL_NOT_AVALIABLE)
  {
   cells[i-1] = CELL_NOT_AVALIABLE;
   undo_stack.push(i);
   undo_count++;
  }
 }
 
 i=pos;
 while(i%8!=0)
 {
   i++;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1]=CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=1)
 {
   i--;
   if(cells[i-1]!=CELL_NOT_AVALIABLE)
   {
    cells[i-1]=CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=0&&i<57)
 {
  i=i+9;
  if(cells[i-1]!= CELL_NOT_AVALIABLE)
  {
   cells[i-1] = CELL_NOT_AVALIABLE;
   undo_stack.push(i);
   undo_count++;
  }
 }
 i=pos;
 while(i%8!=1&&i>8)
 {
  i=i-9;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 i=pos;
 while(i%8!=1&&i<57)
 {
  i=i+7;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }  
 }
 
 i=pos;
 while(i%8!=0&&i>8)
 {
   i=i-7;
   if(cells[i-1]!= CELL_NOT_AVALIABLE)
   {
    cells[i-1] = CELL_NOT_AVALIABLE;
    undo_stack.push(i);
    undo_count++;
   }
 }
 // now push the undo_count.
 undo_stack.push(undo_count);
}

void ChessBoard::TakeQueen(int pos)
{
 // get the undo_count
 int undo_count=undo_stack.top();
 undo_stack.pop();
 for(;undo_count>0;undo_count--)
 {
  int undo_pos=undo_stack.top();
  undo_stack.pop();
  cells[undo_pos-1]=CELL_AVALIABLE;
 }
}

void ChessBoard::GetAvaliablePositions(std::vector<int>& _input)
{
 lastAvaliablePosition=-1;
 while(cells[++lastAvaliablePosition] != CELL_AVALIABLE&& lastAvaliablePosition<65);
 while(lastAvaliablePosition<65)
 {
  _input.push_back(lastAvaliablePosition+1);
  while(cells[++lastAvaliablePosition] != CELL_AVALIABLE&& lastAvaliablePosition<65);
 }
 //PRINT_VECTOR(_input);

}

[/code]

search.cpp
[code]
eam>		//uses std:;cin std::cout
#include <stdio.h>
#include <stdlib.h>
#include "chessboard.h"
#include <vector>			// uses std::vector

void search(int(&)[8],ChessBoard& ,int);
void print_queen_locations(int(&)[8]);
int queens[8];

int main(int argc,char argv[])
{
 ChessBoard chess_board;
 search(queens,chess_board,1);
 return 0;
}

void search(int(&queens)[8],ChessBoard& chess_board,int queen)
{
 if(queen==8)
 {
  std::vector<int> avaliable_positions;
  avaliable_positions.clear();
  chess_board.GetAvaliablePositions(avaliable_positions);
  for(int i=0;i<avaliable_positions.size();i++)
  {
    queens[7]=avaliable_positions[i];
    print_queen_locations(queens);
  }
 }else
 {
  std::vector<int> avaliable_positions;
  avaliable_positions.clear();
  chess_board.GetAvaliablePositions(avaliable_positions);
  for (int i=0;i<avaliable_positions.size();i++)
  {
    int pos=avaliable_positions[i];
    chess_board.PutQueen(pos);
    queens[queen-1]=pos;
    search(queens,chess_board,queen+1);
    chess_board.TakeQueen(pos);
  }
 }
}

void print_queen_locations(int(& queen)[8])
{
 std::cout<<'<';
 for(int i=0;i<8;i++)
   std::cout<<queen[i]<<" ";
 std::cout<<'>'<<'\n';
}



[/code]

Makefile
[code]
CC=g++

all:queen

queen:chessboard.o search.o 
	$(CC) -o queen chessboard.o search.o -g

chessboard.o:chessboard.cpp
	$(CC) -c chessboard.cpp -g

search.o:search.cpp
	$(CC) -c search.cpp -g

clean: 
	rm -f *.o queen

[/code]
About the Author
Member Avatar NicAx64 Posting Pro

well I love technology and want to implement new and make the human life easy.ppl say I am kind thanks and I love to hear that.In programming I am not a expert , but love expertise advice , I want to listen and debug and read than code.My #1 programming language is C++. and I love VLSI and FPGA electronic subjects too.Currently I am a 3rd year student of BIT externaland I just completing my degree in informationtechnology. My favourate linux distro is slax. (there is an old story if you know RH you know RH ,if you know slax you know linux) and I love programming with the xlib and still learning it.In this semester we have a compiler theory , AI as subjects. I love those subjects. and Open,and want to think and implement something new. and my idea about the technology is Technologyshould be easily accessible , low cost , and reliable and should make the human life easy.and I living in the bambalapitiya city north colombo sri lanka.where is a best place to learn electronics. :S

Ancient Dragon 5,243

WinZip can not read that *.zip file.