Eight queens of recursion

Eight queens question: put eight queens on the 8 × 8 grid chess, so that they can't attack each other, that is, any two Queens can't be on the same line, column or diagonal line, and ask how many kinds of placement there are.

Solution: carefully analyze the problem and find that in order to meet the requirements, each time you place a piece, you must place it in a different line. Then you can simplify the problem as follows: starting from the first line, first place the piece in a certain position in the first line, second place it in a certain position in the second line... And so on, then place the piece in a certain position in the eighth line (such as If there is such a position. Therefore, we can use the similar recursive method to solve this problem. We define an eightQueen function, whose parameter is the current number of lines where the chessmen are placed. All the solutions can be easily obtained through the recursive call.

Judge whether it can be placed in a certain position: when judging, it needs to judge the column and diagonal of a certain point position (x, y), so it needs 5 judgments. (you don't need to judge rows here because each placement is in a new row, and there is no duplication problem!).

The final complete procedure is:

#include <iostream>
using namespace std;

int EQMap[8][8] = {0};
int counter = 1;

bool isThisPlaceOK(int x, int y)
{
	// check if position(x, y) is safe in col.
	for(int i = 0; i < 8; i++)
	{
		if(EQMap[i][y] == 1)
		{
			return false;
		}
	}

	// west-north
	for(int i = x, j = y; i >= 0 && j >= 0; i--, j--)
	{
		if(EQMap[i][j] == 1)
		{
			return false;
		}
	}

	// west-south
	for(int i = x, j = y; i < 8 && j >= 0; i++, j--)
	{
		if(EQMap[i][j] == 1)
		{
			return false;
		}
	}

	// east-south
	for(int i = x, j = y; i < 8 && j < 8; i++, j++)
	{
		if(EQMap[i][j] == 1)
		{
			return false;
		}
	}

	// east-north
	for(int i = x, j = y; i >= 0 && j < 8; i--, j++)
	{
		if(EQMap[i][j] == 1)
		{
			return false;
		}
	}
	return true;
}

void printMap()
{
	for(int i = 0; i < 8; i++)
	{
		for(int j = 0; j < 8; j++)
		{
			cout << EQMap[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void eightQueen(int curRow)
{
	if(curRow == 8)
	{
		cout << "map " << counter++ <<endl;
		printMap();		
		return;
	}

	for(int j = 0; j < 8; j++)
	{
		if(isThisPlaceOK(curRow, j))
		{
			EQMap[curRow][j] = 1;
			eightQueen(curRow + 1);
		}
		EQMap[curRow][j] = 0;
	}
	return;
}

int main()
{
	eightQueen(0);
	return 0;
}

 

 

Posted on Fri, 31 Jan 2020 00:56:11 -0800 by whare