N Queen Problem

The N Queen, also known as eight queens puzzle, is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

									/*****Please include following header files*****/
// iostream
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

#define N 4

static void PrintSolution(int board[N][N])
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
			cout << " " << board[i][j] << " ";

		cout << endl;
	}
}

static bool IsSafe(int board[N][N], int row, int col)
{
	int i, j;

	for (i = 0; i < col; ++i)
		if (board[row][i])
			return false;

	for (i = row, j = col; i >= 0 && j >= 0; --i, --j)
		if (board[i][j])
			return false;

	for (i = row, j = col; j >= 0 && i < N; ++i, --j)
		if (board[i][j])
			return false;

	return true;
}

static bool SolveNQ(int board[N][N], int col)
{
	if (col >= N)
		return true;

	for (int i = 0; i < N; ++i)
	{
		if (IsSafe(board, i, col))
		{
			board[i][col] = 1;

			if (SolveNQ(board, col + 1))
				return true;

			board[i][col] = 0;
		}
	}

	return false;
}

static bool Solve()
{
	int board[N][N] = { 
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 },
		{ 0, 0, 0, 0 }
	};

	if (SolveNQ(board, 0) == false)
		return false;

	PrintSolution(board);
	return true;
}

Example

									bool isSolved = Solve();

Output

									isSolved: true

Output of Solve function:
 0  0  1  0
 1  0  0  0
 0  0  0  1
 0  1  0  0