This is a classic needing (almost) no further introduction.

Given a N x N chess board, place N queens on it so none can attack another: I.e. no other queens can be found horizontally, vertically or diagonally to the current.

On the board below, no further queens can be positioned.

+-+-+
|Q| |
+-+-+
| | |
+-+-+

In this example a queen can be located in position a or position b - but not in both, thereby making (0,0) an invalid first position:
+-+-+-+
|Q| | |
+-+-+-+
| | |a|
+-+-+-+
| |b| |
+-+-+-+


Return value must by an array of N x-positions. That is, the y position is given by the index. For following board, expected answer is `[1, 3, 0, 2]`:

+-+-+-+-+
| |X| | |    x=1, y=0
+-+-+-+-+
| | | |X|    x=3, y=1
+-+-+-+-+
|X| | | |    x=0, y=2
+-+-+-+-+
| | |X| |    x=2, y=3
+-+-+-+-+

Only one solution per N is expected. If no solution can be found, return an empty array. That is, for a 1 x 1 board, the output is [0].

Input is a value positive number (N>0) and can be quite large, so try to make your solution efficient. See sample tests to check how large `N` can be.

Have fun :)

----
Next steps:
 - [N queens puzzle (with one mandatory queen position)](https://www.codewars.com/kata/561bed6a31daa8df7400000e)
 - [N queens problem (with one mandatory queen position) - challenge version](https://www.codewars.com/kata/5985ea20695be6079e000003)

Source: codewars | Difficulty: MEDIUM

Starter code: def nQueen(n):
	

Solutions:
def nQueen(n):
	if n == 2 or n == 3:
		return []
	(r, odds, evens) = (n % 6, list(range(1, n, 2)), list(range(0, n, 2)))
	if r == 2:
		evens[:2] = evens[:2][::-1]
		evens.append(evens.pop(2))
	if r == 3:
		odds.append(odds.pop(0))
		evens.extend(evens[:2])
		del evens[:2]
	return odds + evens


def nQueen(n):
	if n == 1:
		return [0]
	if n <= 3:
		return []
	evens = [i for i in range(2, n + 1, 2)]
	odds = [i for i in range(1, n + 1, 2)]
	if n % 6 == 3:
		evens.remove(2)
		evens.append(2)
		odds.remove(1)
		odds.remove(3)
		odds.append(1)
		odds.append(3)
	elif n % 6 == 2:
		(odds[0], odds[1]) = (3, 1)
		odds.remove(5)
		odds.append(5)
	return [a - 1 for a in evens + odds]


def nQueen(n):
	if n <= 3:
		return [[], [0], [], []][n]
	odds = list(range(1, n + 1, 2))
	evens = list(range(2, n + 1, 2))
	if n % 6 == 2:
		(p1, p3) = (odds.index(1), odds.index(3))
		(odds[p1], odds[p3]) = (odds[p3], odds[p1])
		odds.remove(5)
		odds.append(5)
	elif n % 6 == 3:
		evens.remove(2)
		evens.append(2)
		odds.remove(1)
		odds.remove(3)
		odds.extend([1, 3])
	return [n - a for a in evens + odds]


def nQueen(n):
	if n <= 3:
		return [[], [0]][n == 1]
	mod = n % 6
	odd = list(range(1, n + 1, 2))
	even = list(range(2, n + 1, 2))
	if mod == 2:
		odd[:2] = odd[:2][::-1]
		odd.append(odd.pop(2))
	elif mod == 3:
		even.append(even.pop(0))
		odd.extend([odd.pop(0), odd.pop(0)])
	return [i - 1 for i in even + odd]


def nQueen(n):
	if 2 <= n <= 3:
		return []
	sol = list(range(n))
	(even, odd) = (sol[::2], sol[1::2])
	if n % 6 == 2:
		even = even[1::-1] + even[3:] + even[2:3]
	if n % 6 == 3:
		(even, odd) = (even[2:] + even[:2], odd[1:] + odd[:1])
	return odd + even


def nQueen(n):
	if n == 2 or n == 3:
		return []
	r = n % 12
	L = [2 * i for i in range(1, n // 2 + 1)]
	if r == 3 or r == 9:
		L = L[1:] + [2]
	if n % 2 == 0:
		L1 = [2 * i - 1 for i in range(1, n // 2 + 1)]
	else:
		L1 = [2 * i - 1 for i in range(1, n // 2 + 2)]
	if r == 8:
		for i in range(1, len(L1), 2):
			(L1[i - 1], L1[i]) = (L1[i], L1[i - 1])
	if r == 2:
		(L1[0], L1[1]) = (L1[1], L1[0])
		L1.remove(5)
		L1.append(5)
	if r == 3 or r == 9:
		L1.remove(1)
		L1.append(1)
		L1.remove(3)
		L1.append(3)
	L = L + L1
	return [t - 1 for t in L]


def nQueen(n):
	if n in [2, 3]:
		return []
	odds = [*range(1, n, 2)]
	evens = [*range(0, n, 2)]
	if n % 6 == 2:
		evens[:2] = evens[:2][::-1]
		evens.append(evens.pop(2))
	elif n % 6 == 3:
		odds.append(odds.pop(0))
		evens += evens[:2]
		del evens[:2]
	return odds + evens


from typing import List

def nQueen(n: int) -> List[int]:
	if n in {2, 3}:
		return []
	odds = [*range(1, n, 2)]
	evens = [*range(0, n, 2)]
	if n % 6 == 2:
		evens[:2] = evens[:2][::-1]
		evens.append(evens.pop(2))
	elif n % 6 == 3:
		odds.append(odds.pop(0))
		evens += evens[:2]
		del evens[:2]
	return [*odds, *evens]


from random import shuffle
from typing import List
from concurrent.futures import ProcessPoolExecutor

def is_under_attack(queens: List[int], queen: int) -> bool:
	(x, y) = (queens.index(queen), queen)
	return any((x == xx or y == yy or abs(xx - x) == abs(yy - y) for (xx, yy) in enumerate(queens) if xx != x and yy != y))

def _nQueen(n: int) -> List[int]:
	if n in {2, 3}:
		return []
	queens = [*list(range(n))]
	shuffle(queens)
	swapped = True
	while swapped:
		swapped = False
		for i in range(n):
			for j in range(i + 1, n):
				if is_under_attack(queens, queens[i]) or is_under_attack(queens, queens[j]):
					(queens[i], queens[j]) = (queens[j], queens[i])
					if is_under_attack(queens, queens[i]) and is_under_attack(queens, queens[j]):
						(queens[i], queens[j]) = (queens[j], queens[i])
					else:
						swapped = True
	return queens
_solutions = []

def nQueen(n: int) -> List[int]:
	if not _solutions:
		with ProcessPoolExecutor() as pool:
			_solutions[:] = [*pool.map(_nQueen, list(range(51)))]
	return _solutions[n]


from copy import deepcopy

def nQueen(size):
	for y in range((size + 1) // 2):
		board = tuple((set(range(size)) for _ in range(size)))
		if solve(board, set(), size, 0, y):
			return [s.pop() for s in board]
	return []

def solve(board, placed, size, sx, sy):
	board[sx].intersection_update({sy})
	placed.add(sx)
	for x in range(size):
		if x == sx:
			continue
		board[x].difference_update({sy, sy + sx - x, sy + x - sx})
		if not board[x]:
			return False
	if len(placed) == size:
		return True
	min_v = size
	min_x = None
	for x in range(size):
		if x in placed:
			continue
		lx = len(board[x])
		if lx == 1:
			return solve(board, placed, size, x, next(iter(board[x])))
		if lx < min_v:
			min_v = lx
			min_x = x
	for y in board[min_x]:
		new_board = deepcopy(board)
		new_placed = placed.copy()
		if solve(new_board, new_placed, size, min_x, y):
			update(board, new_board)
			return True
	return False

def update(board, new_board):
	for (s, ns) in zip(board, new_board):
		s.clear()
		s.update(ns)