数据结构实验-八皇后问题

你的名字 2024-04-01 08:28 5阅读 0赞

> 八皇后问题

#include<iostream>
    #include<cstring>
    using namespace std;
    
    //八皇后问题
    
    class Queen {
    public:
    	Queen(int n);
    	~Queen();
    	void SetQueen();//填写n皇后
    	void PrintQeen();//打印皇后位置
    private:
    	int Place(int k);  //判断皇后K是否发生冲突
    	int* x;			  //皇后的位置
    	int num;		 //皇后的个数
    };
    
    Queen::Queen(int n) {
    	x = new int[n];
    	memset(x, -1, n);	//-1表示尚未摆放皇后
    	num = n;
    }
    Queen::~Queen() {
    	delete[] x;
    }
    void Queen::SetQueen() {
    	int k = 0, count = 0;	 //num储存解的个数
    	while (k >= 0)			//摆放皇后k，注意0<=k<=n
    	{
    		x[k]++;			  //在下一列摆放皇后k
    		while (x[k] < num && Place(k) == 1)	//发生冲突
    		{
    			x[k]++;					//皇后k试探下一列
    		}
    		if (x[k] < num && k == num - 1) {		//得到一个解，输出
    			cout << "第" << ++count << "个解是：";
    			PrintQeen();
    		}
    		else if (x[k] < num && k < num - 1)				//尚有皇后为摆放
    		{
    			k = k + 1;						//准备摆放下一个皇后
    		}
    		else
    		{
    			x[k--] = -1;			//重置x[k]，回溯，重新摆放皇后k
    		}
    	}
    }
    int Queen::Place(int k) {				//考察皇后k放置在x[k]是否发生冲突
    	for (int i = 0; i < k; i++) {
    		if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k]))	//违反约束条件
    			return 1;		//冲突，返回 1
    	}
    	return 0;			//不冲突，返回 0
    }
    void Queen::PrintQeen() {		//打印n皇后的一个解
    	for (int i = 0; i < num; i++) {
    		cout << x[i] + 1 << "\t";	//数组下标从0开始，打印的列号从1开始
    	}
    	cout << endl;
    }
    int main() {
    	int n;
    	cout << "请输入皇后的个数：";
    	cin >> n;
    
    	Queen Q(n);
    	//Q.PrintQeen();
    	Q.SetQueen();
    	return 0;
    }

> 递归算法解决

#include <iostream>
    using namespace std;
    //递归算法解决八皇后问题。总共有92种解法。
    int c[20], n = 8, cnt = 0;
    void print() {
    
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j == c[i]) cout << "1 ";
                else cout << "0 ";
            }
            cout << endl;
        }
        cout << endl;
    }
    void search(int r) {
        if (r == n) {
            print();
            ++cnt;
            return;
        }
        for (int i = 0; i < n; ++i) {
            c[r] = i;
            int ok = 1;
            for (int j = 0; j < r; ++j)
                if (c[r] == c[j] || r - j == c[r] - c[j] || r - j == c[j] - c[r]) {
                    ok = 0;
                    break;
                }
            if (ok) search(r + 1);
        }
    }
    int main() {
        search(0);
        cout << cnt << endl;
        return 0;
    }

> 递归解决

#include<iostream>
    #include<cstring>
    using namespace std;
    /*
    * 八皇后问题递归解法
    */
    
    class ChessBoard {
    private:
    	const bool available;//列，左斜线、右斜线数组是否可用的标志
    	const int squares, norm;
    	bool* column, * leftDiagonal, * rightDiagonal;
    	int* positionInRow, howMany;
    	void putQueen(int);
    	void printBoard(ostream&);
    	void initializeBoard();
    public:
    	ChessBoard();
    	ChessBoard(int);//这种可设置棋盘大小
    	void findSolutions();
    	//void printBoard(ostream);
    };
    ChessBoard::ChessBoard():available(true), squares(8), norm(squares - 1) {
    	initializeBoard();
    }
    ChessBoard::ChessBoard(int n) : available(true), squares(n), norm(squares - 1) {
    	initializeBoard();
    }
    
    void ChessBoard::initializeBoard() {
    	howMany = 0;
    	register int i;
    	column = new bool[squares];
    	positionInRow = new int[squares];
    	leftDiagonal = new bool[squares * 2 - 1];
    	rightDiagonal = new bool[squares * 2 - 1];
    	for (i = 0; i < squares; i++) {
    		positionInRow[i] = -1;
    	}
    	for (i = 0; i < squares; i++) {
    		column[i]=available;
    	}
    	for (i = 0; i < squares; i++) {
    		leftDiagonal[i] = rightDiagonal[i] = available;
    	}
    }
    
    void ChessBoard::putQueen(int row) {
    	for (int col = 0; col < squares; col++) {
    		if (column[col] == available && leftDiagonal[row + col] == available && rightDiagonal[row - col + norm] == available) {
    			positionInRow[row] = col;
    			column[col] = !available;
    			leftDiagonal[row + col] = !available;
    			rightDiagonal[row - col + norm] = !available;
    			if (row < squares - 1) {
    				putQueen(row + 1);
    			}
    			else
    			{
    				printBoard(cout);
    			}
    			column[col] = available;
    			leftDiagonal[row + col] = available;
    			rightDiagonal[row - col + norm] = available;
    		}
    	}
    }
    void ChessBoard::findSolutions() {
    	putQueen(0);
    	cout << howMany << "  solutions found.\n";
    }
    
    void ChessBoard::printBoard(ostream& cout)
    {
    	char* board = new char[squares * squares];//棋盘本是二维数组，这里简化为一维数组
    	memset(board, '0', squares * squares);
    	for (int i = 0; i < squares; i++) {
    		board[i * squares + positionInRow[i]] = '1';
    	}
    	for (int row = 0; row < squares; row++) {
    		for (int col = 0; col < squares; col++) {
    			cout << board[row * squares + col];
    		}
    		cout << endl;
    	}
    	cout << endl;
    	howMany++;
    }
    
    int main() {
    	//ChessBoard ch(8);
    	ChessBoard().findSolutions();
    	system("pause");
    	return 0;
    }