八皇后问题，普通遍历与标记优化

        八皇后问题，就是在8*8的棋盘上防止八个皇后，使他们不能互相攻击（横、竖、两个对角线都不能存在另一个棋子）。

        八皇后问题的高效解法，可以维护一个左右对角线的数组，用于查找对角线是否有攻击的棋子。但是这种解法理解成本较高，不够直观。笔者一般采用维护一个二维数组用于模拟真实情况。

        解法一：模拟二维数组，每次放置一个皇后前，遍历查找她的横、竖、对角线均不存在其他皇后。这种解法，代码非常简单易于理解。但是有一个小问题，即每次需要扫描位置的横、竖、对角线，平白无故会多扫描很多次。

bool eight_check(int iPos, int k, vector<vector<int>> &veBoard)
{
	if (iPos >= 8 || k >= 8) return false;
	for (int i = 0; i < 8; ++i)
	{
		if (veBoard[i][k] == 1)
			return false;
		if (veBoard[iPos][i] == 1)
			return false;
	}
	int i = iPos;
	int j = k;
	while (i >= 0 && j >= 0)
	{
		if (veBoard[i--][j--] == 1)
			return false;
	}
	i = iPos;
	j = k;
	while (i >= 0 && j < 8)
	{
		if (veBoard[i--][j++] == 1)
			return false;
	}
	i = iPos;
	j = k;
	while (i < 8 && j >= 0)
	{
		if (veBoard[i++][j--] == 1)
			return false;
	}
	i = iPos;
	j = k;
	while (i < 8 && j < 8)
	{
		if (veBoard[i++][j++] == 1)
			return false;
	}
	return true;
}
int iTotalCountQueen = 0;
void eight_queen(int iPos, vector<vector<int>> &veBoard)
{
	if (iPos >= 8)
	{
		for (int i = 0; i < 8; ++i)
		{
			for (int j = 0; j < 8; ++j)
			{
				cout << veBoard[i][j] << " ";
			}
			cout << endl;
		}
		cout << "-------------------------" << ++iTotalCountQueen << endl;
		return;
	}
	for (int i = 0; i < 8; ++i)
	{
		if (eight_check(iPos, i, veBoard))
		{
			veBoard[iPos][i] = 1;
			eight_queen(iPos + 1, veBoard);
			veBoard[iPos][i] = 0;
		}
	}
}
void eight_queen()
{
	std::vector<vector<int>> veBoard;
	veBoard.resize(8);
	for (int i = 0; i < 8; ++i)
	{
		veBoard[i].resize(8);
	}
	eight_queen(0, veBoard);
}

       解法二：针对解法一，每个位置都需要扫描一遍横、竖、对角线带来的不必要遍历，可以针对性进行优化。将他们的先后顺序进行调整。开始时先扫描后放置，这次先放置，然后将放置位置的横、竖、对角线都进行标记，下次只需要判断某个格子是否存在值就可以。这样只需要在放置和回收的时候进行两次横、竖、对角线的标记与删除标记即可。

bool eight_check_two(int iPos, int k, vector<vector<int>> &veBoard)
{
	if (iPos >= 8 || k >= 8) return false;
	return veBoard[iPos][k] == 0;
}
void eight_setval_two(int iPos, int k, vector<vector<int>> &veBoard, int iFlag)
{
	for (int i = 0; i < 8; ++i)
	{
		veBoard[iPos][i] += iFlag;
		veBoard[i][k] += iFlag;
	}
	int i = iPos;
	int j = k;
	while (i >= 0 && j >= 0) veBoard[i--][j--] += iFlag;
	i = iPos;
	j = k;
	while (i >= 0 && j < 8) veBoard[i--][j++] += iFlag;
	i = iPos;
	j = k;
	while (i < 8 && j >= 0) veBoard[i++][j--] += iFlag;
	i = iPos;
	j = k;
	while (i < 8 && j < 8) veBoard[i++][j++] += iFlag;
}
void eight_queen_two(int iPos, vector<vector<int>> &veBoard)
{
	if (iPos >= 8)
	{
		for (int i = 0; i < 8; ++i)
		{
			for (int j = 0; j < 8; ++j)
			{
				cout << veBoard[i][j] << " ";
			}
			cout << endl;
		}
		cout << "two-------------------------" << ++iTotalCountQueen << endl;
		return;
	}
	for (int i = 0; i < 8; ++i)
	{
		if (eight_check_two(iPos, i, veBoard))
		{
			eight_setval_two(iPos, i, veBoard, 1);
			eight_queen_two(iPos + 1, veBoard);
			eight_setval_two(iPos, i, veBoard, -1);
		}
	}
}
void eight_queen()
{
	std::vector<vector<int>> veBoard;
	veBoard.resize(8);
	for (int i = 0; i < 8; ++i)
	{
		veBoard[i].resize(8);
	}
	eight_queen_two(0, veBoard);
}

这样效率比方法一高效一些些，但是却不方便查看。再拿一个数组用于保存结果就可以了

bool eight_check_two(int iPos, int k, vector<vector<int>> &veBoard)
{
	if (iPos >= 8 || k >= 8) return false;
	return veBoard[iPos][k] == 0;
}
void eight_setval_two(int iPos, int k, vector<vector<int>> &veBoard, int iFlag)
{
	for (int i = 0; i < 8; ++i)
	{
		veBoard[iPos][i] += iFlag;
		veBoard[i][k] += iFlag;
	}
	int i = iPos;
	int j = k;
	while (i >= 0 && j >= 0) veBoard[i--][j--] += iFlag;
	i = iPos;
	j = k;
	while (i >= 0 && j < 8) veBoard[i--][j++] += iFlag;
	i = iPos;
	j = k;
	while (i < 8 && j >= 0) veBoard[i++][j--] += iFlag;
	i = iPos;
	j = k;
	while (i < 8 && j < 8) veBoard[i++][j++] += iFlag;
}
std::vector<int> veEnd;
void eight_queen_two(int iPos, vector<vector<int>> &veBoard)
{
	if (iPos >= 8)
	{
		/*for (int i = 0; i < 8; ++i)
		{
			for (int j = 0; j < 8; ++j)
			{
				cout << veBoard[i][j] << " ";
			}
			cout << endl;
		}*/
		//for (auto &it : veEnd)
			cout << it << " ";
		cout << "two-------------------------" << ++iTotalCountQueen << endl;
		return;
	}
	for (int i = 0; i < 8; ++i)
	{
		if (eight_check_two(iPos, i, veBoard))
		{
			eight_setval_two(iPos, i, veBoard, 1);
			veEnd.push_back(i);
			eight_queen_two(iPos + 1, veBoard);
			veEnd.pop_back();
			eight_setval_two(iPos, i, veBoard, -1);
		}
	}
}
void eight_queen()
{
	std::vector<vector<int>> veBoard;
	veBoard.resize(8);
	for (int i = 0; i < 8; ++i)
	{
		veBoard[i].resize(8);
	}
	//eight_queen(0, veBoard);
	eight_queen_two(0, veBoard);
}

        效率并不是最高的解法，但是确实是相当容易理解的写法。