//Nqueen.cpp
#include <iostream.h>
#include <stdlib.h>
class chess
{
public:
int x, y;
void set(int i, int j) {x = i; y = j;}
bool test(int r, int p, int m)
{ return (r==x || (x+y)==p || (x-y)==m);}
};
class cb
{
private:
int n; //棋盤大小
char *board;
chess *queens;
bool place(int); //放置第n個皇后
bool blocked(int, int, int);
public:
cb (int);
~cb ();
void display ();
};
cb::cb (int s)
{
n = s;
board = new char[n * n];
if (!board)
{
cout << "Can't create board" << endl;
exit(1);
}
queens = new chess [n];
if (!queens)
{
cout << "Can't create chesses" << endl;
exit(1);
}
cout << "Successful getting memory spaces for "
<< n << " queens\n";
for (int i=0; i < n * n; i++)
board[i] = ' ';
}
cb::~cb()
{
cout << "returning memory spaces for "
<< n << " queens." << endl;
delete [] board;
delete [] queens;
}
bool cb::blocked(int ith, int r, int c)
{
for (int k=0; k < ith; k++)
if (queens[k].test(r, r+c, r-c))
return true;
return false;
}
bool cb::place(int ith)
{
if (ith >= n)
return true;
for (int r=0; r < n; r++)
{
queens[ith].set(r, ith);
if (!blocked(ith, r, ith) && place(ith+1))
return true;
}
return false;
}
void cb::display ()
{
place (0);
for (int i=0; i< n; i++)
board[queens[i].x * n + queens[i].y] = 'x';
for (int j=0; j < n; j++)
{
for (int k=0; k < n; k++)
cout << board[j*n+k];
cout << endl;
}
}
void main(void)
{
cb *cbp;
cbp = new cb(8);
cbp->display();
delete cbp;
cbp = new cb(12);
cbp->display();
delete cbp;
}
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: terminal20.mba.ntu.edu.tw