插座黑白墙画:求八皇后问题C++程序设计

#ifndef _QUEENBOARD_H_
#define _QUEENBOARD_H_

const int BOARDSIZE = 8;

using namespace std;

class Queenboard {

private:
bool board[BOARDSIZE][BOARDSIZE];

public:
Queenboard();
bool is_space_under_attack(int, int) const;
void occupy_space(int, int);
void clear_column(int);

friend ostream& operator<<(ostream& out, const Queenboard& cb);
};

Queenboard::Queenboard() {
// Initialize the board to contain zero queens.
for (int row = 0; row < BOARDSIZE; row++) {
for (int col = 0; col < BOARDSIZE; col++) {
board[row][col] = false;
}
}
}

ostream& operator<<(ostream& out, const Queenboard& cb) {

// output the board
for (int row = 0; row < BOARDSIZE; row++) {

out << "---------------------------------" << endl;
for (int col = 0; col < BOARDSIZE; col++) {
out << "|";
if ( cb.board[row][col]) {
out << " Q ";
}
else {
out << " ";
}
}
out << "|" << endl;
}
out << "---------------------------------" << endl;
return out;
}

void Queenboard::clear_column(int col) {

if (col >= BOARDSIZE || col < 0) {
throw out_of_range("Queenboard::clear_column()");
}

for (int row = 0; row < BOARDSIZE; row++) {
board[row][col] = false;
}
}

void Queenboard::occupy_space(int row, int col) {

if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::occupy_space()");
}

// places a queen on the board
board[row][col] = true;
}

bool Queenboard::is_space_under_attack(int row, int col) const {

if (col >= BOARDSIZE || col < 0 ||
row >= BOARDSIZE || row < 0) {
throw out_of_range("Queenboard::is_space_under_attack()");
}

// check to the left
int i = col - 1;
while (i >= 0) {
if (board[row][i]) return true;
i--;
}

// check diagonal up and left
int j = row - 1;
int k = col - 1;
while (j >= 0 && k >= 0) {
if (board[j][k]) return true;
j--; k--;
}

// check diagonal down and left
j = row + 1;
k = col - 1;
while (j < BOARDSIZE && k >= 0) {
if (board[j][k]) return true;
j++; k--;
}

return false;
}

#endif

#include <iostream>
#include <cstdlib>
#include <stdexcept>

#include "Queenboard.h"

using namespace std;

bool place_queens(Queenboard& qb, int col);

int main(int argc, char* argv[]) {

try {

Queenboard qb;
if (! place_queens(qb, 0)) {
cout << "No solution found.\n";
}
return EXIT_SUCCESS;
}
catch (exception& e) {
cerr << e.what() << "\n";
}
catch (...) {
cerr << "Unknown exception caught.\n";
}

return EXIT_FAILURE;
}

bool place_queens(Queenboard& qb, int col) {

bool inserted = false;
for (int row = 0; row < BOARDSIZE; row++) {

if (! qb.is_space_under_attack(row, col)) {

// insert a queen
qb.occupy_space(row, col);
inserted = true;

if (col == BOARDSIZE - 1) {
// solution found!
cout << qb << "\n";
return true;

}
else {
// place a queen in the next column
if (place_queens(qb, col + 1)) {
return true;
}
else {
inserted = false;
}
}
}
}

if (! inserted) {
// backtrack to previous column
qb.clear_column(col - 1);
return false;
}
}

课本上应该有吧
找本C++的书看看行了

没想法了

这样算是最佳解

class Queen8{

static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];

public static void main(String args[]){
for (int i=0;i<QueenMax;i++)chess[i]=-1;
placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"个解法 made by yifi 2003");
}

public static void placequeen(int num)
{
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i<QueenMax;i++) qsave[i]=true;

i=0;
while (i<num){
qsave[chess[i]]=false;
int k=num-i;
if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false;
if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false;
i++;
}
for(i=0;i<QueenMax;i++){
if (qsave[i]==false)continue;
if (num<QueenMax-1){
chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("这是第"+oktimes+"个解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");

for (i=0;i<QueenMax;i++){
String row="第"+(i+1)+"行: ";
if (chess[i]==0);
else
for(int j=0;j<chess[i];j++) row+="--";
row+="++";
int j = chess[i];
while(j<QueenMax-1){row+="--";j++;}
System.out.println(row);
}
}
}
}
}