0

[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++ ..

Edited by Nick Evan: Added backlink

#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);
}
5
Contributors
5
Replies
8
Views
13 Years
Discussion Span
Last Post by bangonkali
0

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

0

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.

Edited by bangonkali: n/a

0

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

0

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.

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.