N Queen

Updated meabed 0 Tallied Votes 892 Views Share

[edit] This code was originally posted here [/edit]

The problem is to find all ways of placing n non-taking queens on a n by n board. A queen attacks all cells in its same row, column, and either diagonal. Therefore, the objective is to place n queens on an n by n board in such a way that no two queens are on the same row, column or diagonal. really i sloved this proplem using AI and i did the project in VB.net and C++ ..

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<math.h>
#include<stdlib.h>
#include<DOS.h>
#include<graphics.h>
 
#define SQSIZE 30
#define DELAY 500
long count = 0;
void initialize_graphics(int&, int&);
int** MakeChessBoard(int);
int PlaceQueens(int**, int, int);
int CheckKill(int**, int, int, int);
void CreateChessBoard(int**, int);
void DeleteChessBoard(int**, int);
void PlaceQueen(int, int);
void RemoveQueen(int, int) ;
void HomeQueen(int);
 
int max_x, max_y;
 
void main()
{
int** chessboard;
int i, j, size;
cout << "N-Queen Problem" << endl;
cout << "Press any Key to continue...";
getch();
do
{
clrscr();
printf("Enter Size of chessBoard[Number of rows or columns ie. N]:");
scanf("%d", &size);
if (size < 4)
{
printf("\nThere is NO solution for N<4");
getch();
}
}
while (size < 4);
chessboard = MakeChessBoard(size);
initialize_graphics(max_x, max_y);
CreateChessBoard(chessboard, size);
PlaceQueens(chessboard, size, 0);
getch();
DeleteChessBoard(chessboard, size);
}
int** MakeChessBoard(int size)
{
int** chessboard;
int i, j;
/*Allocate Double Dimention Array*/
chessboard = (int * *) malloc(sizeof(int) * size);
for (i = 0; i < size; i++)
chessboard[i] = (int *) malloc(sizeof(int) * size);
/*Initialize Double Dimention Array*/
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
chessboard[i][j] = 0;
return chessboard;
}
int PlaceQueens(int** chessboard, int size, int level)
{
count++;
int Q_placed = 0; /*
	 Q_placed is a flag reflecting that whether a Queen
	 is placed on the current level or not.
	 This value is returned to preceeding levels.
	 */
int QNextLevel; /*
	 QNextLevel is a flag reflecting that whether a Queen
	 is placed on the next level or not.
	 During recurssion this Flag will allow recurssion
	 */
 
int flag;	/*
	 Determines whether a Queen can be placed at current
	 position or not.
	 */
int i;
for (i = 0; i < size; i++)
{
/*Breaks the loops after all the Queens have been placed*/
if (Q_placed == 1)
break;
/*Check whether Queen can be placed or not*/
flag = CheckKill(chessboard, size, level, i);
/*If Queen can be placed*/
if (flag == 0)
{
/*Queen Placed. This will be changed if Next level Queen is
	 not placed succesfully*/
Q_placed = 1;
/*Queen Placed. */
chessboard[level][i] = 1;
PlaceQueen(level, i);
/*Check for Last level*/
if (level == size - 1)
	;
else /*Place a next level Queen*/
{
	QNextLevel = PlaceQueens(chessboard, size, level + 1);
	/*If next level Queen is not Placed.*/
	if (QNextLevel == 0)
	{
	 /*Mark this level Queen as Not Placed*/
	 Q_placed = 0;
	 chessboard[level][i] = 0;
	 RemoveQueen(level, i);
	 if (i == size - 1)
	 HomeQueen(level);
	}
}
}
else if (flag == 1)
{
PlaceQueen(level, i);
RemoveQueen(level, i);
if (i == size - 1)
	HomeQueen(level);
}
}
return Q_placed;
}
int CheckKill(int** chessboard, int size, int row, int column)
{
int i, j;
for (i = 0; i < row; i++)/*ROW Loop: Only From 0 to (Current Level - 1) */
for (j = 0; j < size; j++)/*COLUMN Loop:From 0 to ChessBoardsize */
if (chessboard[i][j] == 1)/*If there is a Queen*/
	if (j == column)
	 return 1; /*If Queen is in the same column*/
	else if (abs(i - row) == abs(j - column))
	 return 1;/*If it is Diagonal*/
return 0;
}
void CreateChessBoard(int** chessboard, int size)
{
setfillstyle(SOLID_FILL, LIGHTBLUE);
setcolor(RED);
bar(0, 0, max_x, max_y);
for (int i = 0; i < size; i++)
{
for (int j = 1; j <= size; j++)
{
if (i % 2 == j % 2)
	setfillstyle(SOLID_FILL, WHITE);
else
	setfillstyle(SOLID_FILL, YELLOW);
bar(j * SQSIZE, i * SQSIZE, (j + 1) * SQSIZE, (i + 1) * SQSIZE);
}
}
settextstyle(DEFAULT_FONT, HORIZ_DIR, 2);
setcolor(WHITE);
outtextxy(max_x - 300, max_y - 50, "N Queen -PCD-");
setcolor(RED);
setlinestyle(SOLID_LINE, 0, 1);
for (int p = 0; p <= max_x; p += SQSIZE)
line(p, 0, p, max_y);
for (p = 0; p <= max_x; p += SQSIZE)
line(0, p, max_x, p);
}
void DeleteChessBoard(int** chessboard, int size)
{
int i;
for (i = 0; i < size; i++)
free(chessboard[i]);
free(chessboard);
}
void initialize_graphics(int& max_x, int& max_y)
{
/*
initialize_graphics() function initializes the graphic enviroment.
*/
int gdriver = DETECT, gmode, errorcode;
 
initgraph(&gdriver, &gmode, NULL);
 
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk) /* an error occurred */
{
cout << "Graphics error:" << grapherrormsg(errorcode) << endl;
cout << "Press any key to halt:";
getch();
exit(1); /* terminate with an error code */
}
max_x = getmaxx();
max_y = getmaxy();
}
 
void PlaceQueen(int row, int column)
{
if (column == 0)/*Queen was in HOme*/
{
setfillstyle(SOLID_FILL, LIGHTBLUE) ;
setcolor(LIGHTBLUE);
pieslice(SQSIZE / 2, row * SQSIZE + SQSIZE / 2, 0, 360, 4);
}
delay(100);sound(400);delay(DELAY);nosound();
setfillstyle(SOLID_FILL, BLUE) ;
setcolor(BLUE);
pieslice((column + 1) * SQSIZE + SQSIZE / 2, row * SQSIZE + SQSIZE / 2, 0,
360, 4);
}
void RemoveQueen(int row, int column)
{
delay(100);sound(200);delay(DELAY);nosound();
if (row % 2 != column % 2)
{
setcolor(WHITE); setfillstyle(SOLID_FILL, WHITE);
}
else
{
setcolor(YELLOW); setfillstyle(SOLID_FILL, YELLOW);
}
pieslice((column + 1) * SQSIZE + SQSIZE / 2, row * SQSIZE + SQSIZE / 2, 0,
360, 4);
}
void HomeQueen(int row)
{
setfillstyle(SOLID_FILL, BLUE) ;
setcolor(BLUE);
pieslice(SQSIZE / 2, row * SQSIZE + SQSIZE / 2, 0, 360, 4);
}
nictipoloi 0 Newbie Poster

It doesn't have a clean compilation under Borland C++ Builder standar; you have to tinker it

boobal.sachin 0 Newbie Poster

it's too large.....

bangonkali 0 Newbie Poster

you can try this one:

# include<stdio.h>
int v,i,j,k,l,s,a[99];
int main()
{
for(s=8;*a-s;v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!printf(2+"\n\n%c"-(!l<<!j)," #Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]);
printf("\n\n");

return 0;
}

or this one:

# include<stdio.h>
# define Q  9

struct POINT {int x,y;}; 
POINT q[Q];
int N;

bool chkAll(int x){
	for ( int i =x ; i >=0 ; i--)
		for(int j = i - 1; j >= 0 ; j--)
			if( q[i].x == q[j].x || q[i].y == q[j].y || 
				q[i].x + q[i].y == q[j].x + q[j].y || 
				q[i].x - q[j].x == q[i].y - q[j].y)
				return false; 
	return true;
}

void MoveQueen(int x)
{
	if(x >= Q)
	{	
		printf("\n\nSolution : %d \n\n\t",++N);
		for(int j=0;j<Q;printf("\n\t"),j++)
			for(int i=0;i<Q;((q[j].x==j) && (q[j].y==i))?printf("Q%c",179) : printf("_%c",179),i++);
				return;
	}	
	
	for (int j = 0; j < Q ;q[x].x = x,j++)
	{	
		q[x].y = j;
		  if(chkAll(x)) 
			  MoveQueen(x + 1);
	}
}

void main()
{for (int i = 0; i < Q; q[0].x = 0,q[0].y = i,MoveQueen(1),i++);}

i'm quite sure both of them works. i tried them on visual studio 2008. i also only found them in the internet. can't remember the original link though. but anyway. thanks to the original authors. the credit goes to them.

love_rap 0 Newbie Poster

Hi
I need n-queen problem source code with C/C++ using dfs ( depth first search ).
Please .

bangonkali 0 Newbie Poster

Hi
I need n-queen problem source code with C/C++ using dfs ( depth first search ).
Please .

I think the code I posted above are examples using Depth First Search and Backtracking already, as shown on Wikipedia.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.