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