CareerCup

1st queen-4th row,1st column
2nd quenn-6th row,2nd column
3rd quenn-3rd row,3rd column
4th quenn-5th row,4th column
5th quenn-7th row,5th column
6th quenn-2nd row,6th column
7th quenn-8th row,7th column
8th quenn-1sr row,8th column

http://en.wikipedia.org/wiki/Eight_queens_puzzle

durangobill.com/N_Queens.html

easy

1st queen-4th row,1st column
2nd quenn-6th row,2nd column
3rd quenn-3rd row,3rd column
4th quenn-5th row,4th column
5th quenn-7th row,5th column
6th quenn-2nd row,6th column
7th quenn-8th row,7th column
8th quenn-1sr row,8th column

Place one queen. Place another so they can't beat each other and recursively go on like this. Hard part is to figure out how to optimize the naive approach so you don't enumerate solutions twice and also don't do unnecessary work in general...

This is just a bit over the top for an interview but I am quite happy with it:

#include "stdafx.h"
#include <stdint.h>
#include <vector>
#include <unordered_set>
#include <iostream>
#include <future>

struct Position
{
	int32_t x, y;

	Position() : x(0), y(0) {}
	Position(int32_t x, int32_t y) : x(x), y(y) {}
};

template<class TCallback>
void asyncNextQueen(std::vector<std::future<void>>& tasks, std::vector<Position>& queens, const int N, int pass, const TCallback& callback)
{
	tasks.push_back(std::async([=, &tasks, &callback]()
	{
		std::vector<Position> copy = queens;
		nextQueen(tasks, copy, N, pass, callback);
	}));
}

template<class TCallback>
void nextQueen(std::vector<std::future<void>>& tasks, std::vector<Position>& queens, const int N, int pass, const TCallback& callback)
{
	if (queens.size() == N)
	{
		callback(queens);
		return;
	}

	for (int y = 0; y < N; y++)
	{
		Position pos = { pass, y };

		if (!canPlaceQueen(queens, pos))
			continue;

		queens.push_back(pos);

		if (pass == 1)
			asyncNextQueen(tasks, queens, N, pass + 1, callback);
		else
			nextQueen(tasks, queens, N, pass + 1, callback);

		queens.pop_back();
	}
}

bool canPlaceQueen(std::vector<Position>& queens, Position pos)
{
	for (auto q : queens)
	{
		if ((q.x == pos.x) || (q.y == pos.y) || (std::abs(q.x - pos.x) == std::abs(q.y - pos.y)))
			return false;
	}

	return true;
}

template<class TCallback>
void solveNQueens(const int N, const TCallback& callback)
{
	std::vector<Position> queens;
	std::vector<std::future<void>> tasks;
	queens.reserve(N);
	nextQueen(tasks, queens, N, 0, callback);

	for (auto& task : tasks) task.wait();
}

int main(int argc, char** argv)
{
	int count = 0;

	solveNQueens(16, [&](std::vector<Position>& queens)
	{
		count++;
	});

	std::cout << "DONE (" << count << ")!";
	std::cin.ignore();
	return 0;
}