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)

Difficulty: interview

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]

# https://en.wikipedia.org/wiki/Eight_queens_puzzle#Existence_of_solutions
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)