2N皇后问题

红太狼 2022-04-23 09:30 181阅读 0赞

**题目描述**  
*给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。\*

#include<iostream>
    #include<string>
    #include<vector>
    #include<queue>
    #include<list>
    #include<map>
    #include<cmath>
    
    using namespace std;
    
    int n;
    int board[8][8];
    int result = 0;
    int queen_w[8];
    int queen_b[8];
    
    int valid_w(int row, int line)
    { 
    	for (int i = 0; i < row; i++){ 
    		if (line == queen_w[i] || abs(row - i) == abs(line - queen_w[i])) //abs():求整数的绝对值
    			return 0;
    	}
    	return 1;
    }
    
    int valid_b(int row, int line)
    { 
    	for (int i = 0; i < row; i++){ 
    		if (line == queen_b[i] || abs(row - i) == abs(line - queen_b[i])) //abs():求整数的绝对值
    			return 0;
    	}
    		return 1;
    }
    
    void Queen_w(int row)
    { 
    	if (row == n)
    	{ 
    		result++;
    	}
    	else{ 
    		for (int line = 0; line < n; line++)
    		{ 
    			if (queen_b[row]==line||board[row][line] == 0)
    				continue;
    			else if (valid_w(row, line) == 1)
    			{ 
    				queen_w[row] = line;//表示row行的皇后在第line列
    				Queen_w(row + 1);
    			}
    		}
    	}
    }
    
    void Queen_b(int row)
    { 
    	if (row == n)
    	{ 
    		Queen_w(0);
    	}
    	else{ 
    		for (int line = 0; line < n; line++)
    		{ 
    			if (board[row][line] == 0)
    				continue;
    			else if (valid_b(row, line) == 1)
    			{ 
    				queen_b[row] = line;//表示row行的皇后在第line列
    				Queen_b(row + 1);
    			}
    		}
    	}
    }
    
    int main()
    { 
    	cout << "请输入棋盘的长度（宽度）：" << endl;
    	cin >> n;
    	cout << "请输入棋盘可放置的位置："<<endl;
    	for (int i = 0; i < n; i++)
    	{ 
    		for (int j = 0; j < n; j++)
    		{ 
    			cin >> board[i][j];
    		}
    	}
    	Queen_b(0);
    	cout << result << endl;
    	system("pause");
    	return 0;
    }