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)

Difficulty: interview

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]:
    """
    Decode chess notation into a row, col tuple
    E.g.: 'd2' -> (1, 3)
    """
    c = ord(cr[0]) - ord('a')
    r = (int(cr[1]) - 1) % size
    return r, c

def encode(r: int, c: int) -> str:
    """
    Encode a row, col tuple into chess notation (works up to a board size of 10)
    E.g.: (1, 3) -> 'd2'
    """
    return f'{chr(ord("a") + c)}{(r + 1) % 10}'

def build_coverage(queens: List[Tuple[int, int]], size: int) -> List[List[int]]:
    """
    Given the queens on a board of given size, returns a matrix of the coverage of
    each position on the board
    :param queens: List of queens with (row, column) coordinates
    :param size: Edge size of the board
    """
    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]:
    """
    Given a list of (row, col) queen positions and a size of board, apply a iterative repair algorithm
    until we find a position where no queen can take another.
    :param queens: List of positions, the first queen will not be moved by the algorithm
    :param size: Size of the board
    :return: String containing chess encoded positions if a solution is found, None if too many cycles pass without a solution 
    """
    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):
            # Found solution
            break
        
        # Find most coverage on queens, and chose a random queen with that coverage
        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
        ]
        # Target queen
        tr, tc, ti = choice(candidates)            

        # Find the positions with the lowest coverage on the same row
        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)
        
        # Move to a random row on the column (from options with the lowest coverage)
        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):
    """
    Given a chess encoded queen position and a size of board, find and return a chess encoded series of positions where 
    no queen can take another.
    :param queen: Fixed position of one queen, e.g.: 'd5'
    :param size: Size of the board
    :return: String containing chess encoded positions of size queens that cannot take each other 
    """
    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:
        # Build an initialrandomised state where no two queens share the same row or column
        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)]
        # Attempt to reduce conflicts until we find a solution
        result = solve(queens, size)
        if result:
            return result
        # Looks like we found a local optimum, so re-randomise and start again



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):

    # init
    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])))])

    # diagonal fields
    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

    # horizontal and vertical fields
    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 if queen´s row is already part of solution
    check_row = False
    for s in solution:
        if s[0] == queen[0]:
            check_row = True
            break

    # replace solution from row on with new queen and update solution
    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)

    # update board
    board = update_board(size, solution)
    free_fields = board[0]
    blocked_fields = board[1]

    # move to next row
    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):

    # init
    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)]

    #HANDLING VERTICAL AND HORIZONTAL AND DIAGONALS
    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 with not possible Q positions
    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 = []
    
    #making the board
    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))
    
    #position coordinates
    pos = list(np.where(board == position))
    if len(pos[0]) == 0:
        return None
    
    # first queen
    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))

    #row
    for i in range(size):
        board[i,pos[1]]="  "
    
    #column
    for i in range(size):
        board[pos[0],i]="  "
     
    #diagonal1
    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]):], "  ")
    #diagonal2
    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


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 = []
    
    #making the board
    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))
    
    #position coordinates
    pos = list(np.where(board == position))
    if len(pos[0]) == 0:
        return None
    
    # first queen
    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))

    #row
    for i in range(size):
        board[i,pos[1]]="  "
    
    #column
    for i in range(size):
        board[pos[0],i]="  "
     
    #diagonal1
    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]):], "  ")
    #diagonal2
    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())
            print(col_steps)
            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


import math
import numpy as np

alph = ["a","b","c","d","e","f","g","h","i","j"]

def queens(position, size):
    if size == 1:
        return "a1"
    if size != 10:
        x = list(range(1,size+1))
    if size == 10:
        x = list(range(1,size))
        x.append(0)
        
    print(x)
    pos_step = []
    #making the board
    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]))
    print(board)
    board_states = list(np.empty([size,size],dtype=object))
    
    #position coordinates
    pos = list(np.where(board == position))
    print(pos)
    if len(pos[0]) == 0:
        return None
    
    # first queen
    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))

    #row
    for i in range(size):
        board[i,pos[1]]="  "
    
    #column
    for i in range(size):
        board[pos[0],i]="  "
     
    #diagonal1
    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]):], "  ")
    #diagonal2
    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())
            print(col_steps)
            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


MOVES = ( (1,1), (-1,1), (1,-1), (-1,-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 i in range(len(board)):
        if (x,y) != (i,y):
            board[i][y] += 1
            pos.append((i,y))
        
        if (x,y) != (x,i):
            board[x][i] +=1
            pos.append((x,i))

    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 with not possible Q positions
    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)