CareerCup

dono :(

backtracking

Place them diagonally

Put the other queen in L shape of each queen (like how the knight moves). I beleive this solves it

There is a simple algorithm yielding a solution to the n queens puzzle for n = 1 or any n = 4:

1. Divide n by 12. Remember the remainder (n is 8 for the eight queens puzzle).
2. Write a list of the even numbers from 2 to n in order.
3. If the remainder is 3 or 9, move 2 to the end of the list.
4. Append the odd numbers from 1 to n in order, but, if the remainder is 8, switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the end of the list.
6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
7. Place the first-column queen in the row with the first number in the list, place the second-column queen in the row with the second number in the list, etc.

A1, B3, C5, D7, E2, F4, G6, H8

Do not agree METU`s answer. A1 and H8 are on the same diagnal.

A1,B5,C8,D6,E3,F7,G2,H4

how about this?

A4, B1, C7, D2, E6, F8, G5, H3

Do interviewers really expect a solution to a problem such as this when experts have worked on it for years?

Not so hard... Its just a recursive approach (experts worked on how to compute this for N=24 & stuff which yields enormous amounts of solutions). 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;
}

package com.example;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class NQueenProblem {
	public Map<Integer, Integer> calculatePositions(int n) {
		Map<Integer, Integer> finalMap = new HashMap<Integer, Integer>();

		calculatePositions(0, n, finalMap, new HashSet<Integer>(), new HashSet<Integer>(), new HashSet<Integer>());

		return finalMap;
	}

	
	private boolean  calculatePositions(int row, int n, Map<Integer, Integer> finalMap, Set<Integer> usedColumnsSet,
										Set<Integer> lowerPositionsSet, Set<Integer> upperPositionsSet) {
		for (int column = 0; column < n; column++) {
			if (usedColumnsSet.contains(column)) {
				continue;
			}

			int lower = row + column;
			if (lowerPositionsSet.contains(lower)) {
				continue;
			}

			int subtracter = 2*column + n - 1;
			int upper = subtracter - lower;
			if (upperPositionsSet.contains(upper)) {
				continue;
			}

			if (row == (n - 1)) {
				finalMap.put(row, column);
				return true;
			}

			usedColumnsSet.add(column);
			lowerPositionsSet.add(lower);
			upperPositionsSet.add(upper);

			boolean result = calculatePositions(row + 1, n, finalMap, usedColumnsSet, lowerPositionsSet, upperPositionsSet);

			if (result) {
				finalMap.put(row, column);
				return true;
			} else {
				usedColumnsSet.remove(column);
				lowerPositionsSet.remove(lower);
				upperPositionsSet.remove(upper);
			}
		}

		return false;
	}

	public static void main(String[] args) {
		NQueenProblem nQueenProblem = new NQueenProblem();
		System.out.println(nQueenProblem.calculatePositions(4));
	}
}