8 Queen problem

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