Based on the well known ['Eight Queens' problem](https://en.wikipedia.org/wiki/Eight_queens_puzzle).

#### Summary
Your challenge is to place N queens on a chess board such that none of the queens are attacking each other.

#### Details
A standard 8x8 chess board has its rows (aka ranks) labelled 1-8 from bottom to top, and its columns (aka files) labelled a-h from left to right. Any square can be denoted by a combination of letter and number. For example, the top left square is a8. A queen may attack any square on its rank or file. It may also attack any square diagonally.

In this kata, chessboard may have any size from 1 to 10. Columns are marked with letters a-j, and rows with single digit from 1 to 0 (first row is marked with 1, ninth row is marked with 9, and tenth row is marked with 0, so `a1` denotes bottom left field of the chessboard, and `j0` - top right field on a 10x10 board).

You will be given the position of one queen on the board (e.g. `'c3'`). Your challenge is to compute the position of the remaining queens and return the full solution (including the original input) as a comma-separated string (e.g. `'d8,a7,e6,h5,b4,g3,c2,f1'`). Fields do not have to be sorted in any particular way, but you have to adhere to above format (lowercase letters, no spaces, fields separated with commas).

Note that there may be multiple valid solutions for a given starting position. Your function only needs to produce (any) one of these. All given starting positions produce valid solutions.

If you wish to write more tests, the validity of a solution may be checked using preloaded function (see sample tests).

Hint: check the wiki article for the various algorithms that are applicable to this problem.

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

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Ad-hoc

Starter code: def queens(position, size):
	

Solutions:
def queens(fixQ, S):

	def areClashing(i, x):
		(j, y) = (qs[i], qs[x])
		return j == y or abs(i - x) == abs(j - y)

	def dfs(i=0):
		if i == iQ:
			return dfs(i + 1)
		if i == len(qs):
			return 1
		for y in range(S):
			qs[i] = y
			if not any((areClashing(i, ii) for ii in range(i))) and (iQ < i or not areClashing(i, iQ)) and dfs(i + 1):
				return 1
	(iQ, yQ) = (ord(fixQ[0]) - 97, (int(fixQ[1]) or 10) - 1)
	qs = [yQ if i == iQ else 0 for i in range(S)]
	dfs()
	return ','.join((f'{chr(x + 97)}{str(y + 1)[-1]}' for (x, y) in enumerate(qs)))


def queens(p, s):
	cols = 'abcdefghij'

	def rf(elem):
		if elem == 0:
			return s - 1
		else:
			return elem - 1
	_c = cols.index(p[0])
	_r = rf(int(p[1:]))

	def mf(elem):
		if elem == 10:
			return 0
		else:
			return elem

	def solver(c, dc, r, td, bd, rs):
		if c == s and len(rs) == s:
			return rs
		for i in range(0, s):
			if c == dc:
				return solver(c + 1, dc, r, td, bd, rs)
			ntd = c - i + s - 1
			nbd = -(c + i) + s * 2 - 2
			if r[i] or td[ntd] or bd[nbd]:
				continue
			r[i] = True
			td[ntd] = True
			bd[nbd] = True
			next_r = solver(c + 1, dc, r, td, bd, rs + [i * s + c])
			if next_r:
				return next_r
			r[i] = False
			td[ntd] = False
			bd[nbd] = False
		return False
	fr = [False for i in range(0, s)]
	ftd = [False for i in range(0, s * 2 - 1)]
	fbd = [False for i in range(0, s * 2 - 1)]
	fr[_r] = 1
	ftd[_c - _r + s - 1] = 1
	fbd[-(_c + _r) + s * 2 - 2] = 1
	result = solver(0, _c, fr, ftd, fbd, [_c + _r * s])
	result = ','.join([cols[i % s] + str(mf(i // s + 1)) for i in result])
	return result


from random import choice, shuffle
from typing import List, Optional, Tuple

def decode(cr: str, size: int) -> Tuple[int, int]:
	c = ord(cr[0]) - ord('a')
	r = (int(cr[1]) - 1) % size
	return (r, c)

def encode(r: int, c: int) -> str:
	return f"{chr(ord('a') + c)}{(r + 1) % 10}"

def build_coverage(queens: List[Tuple[int, int]], size: int) -> List[List[int]]:
	result = [[0 for _ in range(size)] for _ in range(size)]
	for (q, (qr, qc)) in enumerate(queens):
		result[qr][qc] -= 2
		for i in range(size):
			result[i][qc] += 1
			result[qr][i] += 1
			if i == 0:
				continue
			for (dr, dc) in [(-1, -1), (-1, 1), (1, 1), (1, -1)]:
				rr = qr + i * dr
				if 0 <= rr < size:
					cc = qc + i * dc
					if 0 <= cc < size:
						result[rr][cc] += 1
	return result

def solve(queens: List[Tuple[int, int]], size: int) -> Optional[str]:
	cycle = 0
	while True:
		cycle += 1
		coverage = build_coverage(queens, size)
		queen_coverage = [(coverage[qr][qc], qr, qc) for (qr, qc) in queens]
		if all((qc[0] == 0 for qc in queen_coverage)):
			break
		most = max((qc[0] for qc in queen_coverage[1:]))
		candidates = [(qr, qc, i) for (i, (c, qr, qc)) in enumerate(queen_coverage[1:], 1) if c == most]
		(tr, tc, ti) = choice(candidates)
		(best, best_pos) = (None, [])
		for r in range(size):
			if r == tr:
				continue
			cov = coverage[r][tc]
			if best is None or cov < best:
				(best, best_pos) = (cov, [r])
			elif cov == best:
				best_pos.append(r)
		queens[ti] = (choice(best_pos), tc)
		if cycle > 20:
			return None
	return ','.join([encode(qr, qc) for (qr, qc) in queens])

def queens(position, size):
	if size == 1:
		return 'a1'
	if size in [2, 3]:
		raise ValueError(f'No solution possible with size = {size}')
	(fixed_r, fixed_c) = decode(position, size)
	while True:
		rr = [i for i in range(size) if i != fixed_r]
		cc = [i for i in range(size) if i != fixed_c]
		shuffle(rr)
		shuffle(cc)
		queens = [(r, c) for (r, c) in zip([fixed_r] + rr, [fixed_c] + cc)]
		result = solve(queens, size)
		if result:
			return result


from itertools import permutations, combinations

def queens(queen, size):
	(X, Y, rng) = (ord(queen[0]) - 97, (int(queen[1]) or 10) - 1, range(size))
	q = next((p for p in permutations(rng) if p[X] == Y and all((abs(x - y) - abs(p[x] - p[y]) for (x, y) in combinations(rng, 2)))))
	return ','.join((f'{chr(x + 97)}{(1 + q[x]) % 10}' for (x, y) in enumerate(q)))


import string
import numpy as np

def remove_dups(list_in):
	no_dups_t = list(set([tuple(d) for d in list_in]))
	no_dups = [list(d) for d in no_dups_t]
	return no_dups

def init_board(size):
	cols = [s for s in string.ascii_lowercase]
	board = []
	for i in range(1, size + 1):
		row = str(size + 1 - i)
		board.append([col + row for col in cols[0:size]])
	return np.array(board)

def position_to_xy(board, position):
	position = position.replace('0', '10')
	return [np.where(board == position)[0][0], np.where(board == position)[1][0]]

def xy_to_position(xy_list, size):
	out = []
	board = init_board(size)
	for xy in xy_list:
		out.append(board[xy[0]][xy[1]])
	return out

def xy_to_string(input_list):
	out = str()
	for f in input_list:
		out = out + (str(f) + ',')
	out = out[0:-1]
	out = out.replace('10', '0')
	return out

def init_free_fields(size):
	rows = [i for i in range(0, size)]
	cols = [i for i in range(0, size)]
	free_fields = [[i, j] for i in rows for j in cols]
	return free_fields

def find_blocked_fields(queen, size):
	attack = []
	x_arr = []
	y_arr = []
	y_arr.append([i for i in range(queen[0] + 1, size)])
	y_arr.append([i for i in range(queen[0] + 1, size)])
	y_arr.append([i for i in reversed(list(range(queen[0])))])
	y_arr.append([i for i in reversed(list(range(queen[0])))])
	x_arr = []
	x_arr.append([i for i in range(queen[1] + 1, size)])
	x_arr.append([i for i in reversed(list(range(queen[1])))])
	x_arr.append([i for i in range(queen[1] + 1, size)])
	x_arr.append([i for i in reversed(list(range(queen[1])))])
	for i in range(0, 4):
		min_len = min(len(y_arr[i]), len(x_arr[i]))
		for (j, k) in zip(y_arr[i][0:min_len], x_arr[i][0:min_len]):
			if [j, k] not in attack:
				attack.append([j, k])
			else:
				pass
	for i in range(0, size):
		if [queen[0], i] not in attack:
			attack.append([queen[0], i])
		if [i, queen[1]] not in attack:
			attack.append([i, queen[1]])
	if queen in attack:
		attack.remove(queen)
	return attack

def remove_from_list(remove_list, from_list):
	for r in remove_list:
		if r in from_list:
			from_list.remove(r)

def update_board(size, solution):
	free_fields = init_free_fields(size)
	blocked_fields = []
	for s in solution:
		blocked_fields.extend(find_blocked_fields(s, size))
	blocked_fields = remove_dups(blocked_fields)
	remove_from_list(remove_list=solution, from_list=free_fields)
	remove_from_list(remove_list=blocked_fields, from_list=free_fields)
	return [free_fields, blocked_fields]

def place_queen(size, queen, solution):
	check_row = False
	for s in solution:
		if s[0] == queen[0]:
			check_row = True
			break
	if check_row == True:
		for (i, s) in enumerate(solution):
			if s[0] == queen[0]:
				solution = solution[0:i]
				solution.append(queen)
			else:
				pass
	else:
		solution.append(queen)
	board = update_board(size, solution)
	free_fields = board[0]
	blocked_fields = board[1]
	rows = [r for r in range(0, size) if r not in [s[0] for s in solution]]
	next_row = [[min(rows), f[1]] for f in free_fields if f[0] == min(rows)]
	if len(next_row) > 0:
		for p in next_row:
			if len(solution) == size:
				break
			else:
				solution = place_queen(size, p, solution)
	else:
		return solution
	return solution

def queens(position, size):
	board = init_board(size)
	queen = position_to_xy(board, position)
	solution = []
	solution = place_queen(size, queen, solution)
	xy = xy_to_position(solution, size)
	out = xy_to_string(xy)
	return out


MOVES = ((1, 1), (-1, 1), (1, -1), (-1, -1), (0, 1), (1, 0), (-1, 0), (0, -1))

def find_empty(row, X):
	for (y, spot) in enumerate(row):
		if spot == 0:
			yield (X, y)

def populating_board(x, y, board):
	board[x][y] += 1
	pos = [(x, y)]
	for (dx, dy) in MOVES:
		c = 0
		while True:
			c += 1
			xx = x + c * dx
			yy = y + c * dy
			if not (0 <= xx < len(board) and 0 <= yy < len(board)):
				break
			if (xx, yy) != (x, y):
				board[xx][yy] += 1
				pos.append((xx, yy))
	return pos

def queens(position, size):
	board = [[0] * size for i in range(size)]
	(y, x) = (ord(position[0]) - 97, size - (size == 10 and (not int(position[1])) and 10 or int(position[1])))
	initial_X = x
	populating_board(x, y, board)
	queens = [position]

	def dfs(counter, next_X):
		nonlocal board
		if counter == size:
			return True
		while next_X > 0 and 0 not in board[next_X]:
			next_X -= 1
		while next_X < size - 1 and 0 not in board[next_X]:
			next_X += 1
		for (x, y) in find_empty(board[next_X], next_X):
			queens.append(chr(y + 97) + str(size - (size == 10 and (not x) and 10 or x)))
			to_restore = populating_board(x, y, board)
			if dfs(counter + 1, x):
				return True
			queens.pop()
			for (pos_x, pos_y) in to_restore:
				board[pos_x][pos_y] -= 1
	if dfs(1, x):
		return ','.join(queens)


import math
import numpy as np
alph = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

def queens(position, size):
	if size == 1:
		return 'a1'
	x = num[:size]
	pos_step = []
	board = np.empty([size, size], dtype=object)
	for i in range(size):
		for j in range(size):
			board[i, j] = str(str(alph[j]) + str(x[-i - 1]))
	board_states = list(np.empty([size, size], dtype=object))
	pos = list(np.where(board == position))
	if len(pos[0]) == 0:
		return None
	new_queen(position, size, board, board_states, pos_step, x)
	board_states.append(np.copy(board))
	w_col = list(range(size))
	w_col.remove(pos[1])
	col_steps = [w_col.copy()]
	find_spot(size, board, board_states, pos_step, w_col, col_steps, x)
	output = str(','.join(sorted(pos_step)))
	return output

def new_queen(new_position, size, board, board_states, pos_step, x):
	pos_step.append(new_position)
	pos = list(np.where(board == new_position))
	for i in range(size):
		board[i, pos[1]] = '  '
	for i in range(size):
		board[pos[0], i] = '  '
	if pos[1] - pos[0] >= 0:
		np.fill_diagonal(board[:, int(pos[1] - pos[0]):], '  ')
	else:
		np.fill_diagonal(board[int(pos[0] - pos[1]):], '  ')
	if pos[0] + pos[1] >= size:
		np.fill_diagonal(board[int(pos[1] - (size - pos[0]) + 1):, ::-1], '  ')
	else:
		np.fill_diagonal(np.fliplr(board[:, :int(pos[1] + pos[0] + 1)]), '  ')
	board[tuple(pos)] = new_position
	board_states.append(np.copy(board))

def find_spot(size, board, board_states, pos_step, w_col, col_steps, x):
	fill = 0
	i = w_col[0]
	for j in range(size):
		if board[j, i] == '  ' or board[j, i] == '# ':
			continue
		pos_found = str(str(alph[i]) + str(x[-j - 1]))
		new_queen(pos_found, size, board, board_states, pos_step, x)
		fill = 1
		break
	if fill == 1:
		if len(pos_step) != size:
			w_col.remove(i)
			col_steps.append(w_col.copy())
			find_spot(size, board, board_states, pos_step, w_col, col_steps, x)
			return
	else:
		del board_states[-1]
		del col_steps[-1]
		board = np.copy(board_states[-1])
		w_col = col_steps[-1].copy()
		d_spot = list(np.where(board == pos_step[-1]))
		board[d_spot[0], d_spot[1]] = '# '
		del board_states[-1]
		board_states.append(np.copy(board))
		del pos_step[-1]
		find_spot(size, board, board_states, pos_step, w_col, col_steps, x)
		return