课程设计---八皇后问题 设在初始状态下在国际象棋棋盘上没有任何棋子(这里的棋子指皇后棋子).然后顺序在第1行,第2行,...,第8行上布放棋子.在每一行中共有8个可选择位置,但在任一个时刻棋盘的合法布局都必须满足3个限制条件: (1)任意两个棋子不得放在同一行上; (2)任意两个棋子不得放在同一列上; (3)任意两个棋子不得放在同一正斜线和反斜线上.年、编写求解并输出此问题的一个合法布局的程序.

using System;

public class NQueensPuzzle { private int noOfSolutions; private int noOfQueens; private int[] queensInRow;

//default constructor //Postcondition: noOfSolutions = 0; noOfQueens = 8; // The array queensInRow is instantiated to // store the 8-tuple public NQueensPuzzle() { noOfQueens = 8; queensInRow = new int[8]; noOfSolutions = 0; }

//constructor //Postcondition: noOfSolutions = 0; noOfQueens = queens; // The array queensInRow is instantiated to // store the n-tuple public NQueensPuzzle(int queens) { noOfQueens = queens; queensInRow = new int[noOfQueens]; noOfSolutions = 0; }

//Method to determine if a queen can be placed //in row k and column i. //Postcondition: returns true if a queen can be placed in // row k and column i; otherwise it returns // false public bool canPlaceQueen(int k, int i) { for(int j = 0; j < k; j++) if((queensInRow[j] == i) || (Math.Abs(queensInRow[j] - i) == Math.Abs(j-k))) return false; return true; }

//Method to determine all solutions to the n-queens //puzzle using backtracking //The method is called with the value 0 //Postcondition: All n-tuples representing solutions of // n-queens puzzle are generated and printed public void queensConfiguration(int k) { for(int i = 0; i < noOfQueens; i++) { if(canPlaceQueen(k, i)) { queensInRow[k] = i; //place the kth queen in column i

if(k == noOfQueens - 1) //all queens are placed printConfiguration(); //print the n-tuple else queensConfiguration(k + 1); //determine the place for //the (k+1)th queen } } }

//Method to output an n-tuple containing a solution //to the n-queens puzzle public void printConfiguration() { noOfSolutions++; Console.Write("("); for(int i = 0; i < noOfQueens - 1; i++) Console.Write(queensInRow[i] + ", ");

Console.WriteLine(queensInRow[noOfQueens - 1] + ")"); }

//Method to return the total number of solutions //Postcondition: The value of noOfSolution is returned public int solutionsCount() { return noOfSolutions; } }

[CODE]
#include "SStack.h"
using namespace std;

const int N = 8;

struct Position
{
int x, y;
};
Stack<Position*> s;
Position *p = new Position[N];

// Test Function
int test();

int main()
{
p->x = p->y = 1;
int count = 1;

s.push(p);
bool done = true;
while (1)
{
if (s.top()->y > N)
{
if (s.top()->x == 1)
break;
if (s.top()->x == 2)
{
s.pop();
s.pop();
(p->y)++;
s.push(p);
continue;
}
s.pop();
s.pop();
((p + s.top()->x)->y)++;
s.push((p + s.top()->x));
continue;
}

if (test() && s.top()->x == N)
{
cout << "第" << count++ << "种: ";
for (int i = 0; i < N; i++)
cout /*<< (p + i)->x << ' '*/ << (p + i)->y /*<< endl*/;
cout << endl;
//system("pause");
}

if (test() && s.top()->x != N)
{
(p + s.top()->x)->x = s.top()->x + 1;
(p + s.top()->x)->y = 1;
s.push((p + s.top()->x));
}
else
{
s.pop();
((p + s.top()->x)->y)++;
s.push((p + s.top()->x));
}

}

system("pause");
return 0;
}

int test()
{
if (s.top()->x == 1)
return 1;
for (int i = 0; i < s.top()->x - 1; i++)
{
if ((p+i)->y == s.top()->y)
return 0;
else if (s.top()->x - (p+i)->x == s.top()->y - (p+i)->y)
return 0;
else if (s.top()->x - (p+i)->x == (p+i)->y - s.top()->y)
return 0;
}
return 1;
}



[/CODE]

#ifndef SStack_H
#define SStack_H
// 版权没有。。。。欢迎盗版.... -_-ii
// Made By [Stupid.ET] Cedric Porter
#include <iostream>
#include <cassert>
using namespace std;

template<class T>
class Stack;

template<class T>
class Node
{
T data;
Node *next;
public:
Node(T d, Node<T>* n) { data = d; next = n;}
friend class Stack<T>;
};

template<class T>
class Stack
{
Node<T> *head, *iter;
unsigned long sz;
public:
Stack() {head = iter = NULL; sz = 0;}
~Stack() {empty();}
void empty();
void push(T);
void pop();
T top();
unsigned long size();
};

template<class T>
void Stack<T>::empty()
{
while (head != NULL)
{
iter = head;
head = head->next;
delete head;
}
sz = 0;
}
template<class T>
void Stack<T>::push(T d)
{
if (head == NULL)
head = new Node<T>(d, NULL);
else
head = new Node<T>(d, head);
sz++;
}

template<class T>
void Stack<T>::pop()
{
assert(head != NULL);
sz--;
if (head->next == NULL)
{
delete head;
head = NULL;
return;
}

iter = head;
head = head->next;
delete iter;
}

template<class T>
T Stack<T>::top()
{
assert(head != NULL);
return head->data;
}

template<class T>
unsigned long Stack<T>::size()
{
return sz;
}
#endif