# 8 Queen Problem

###### tags: `week7` `dfs` `recursion` `brute force`

In a chess game, a queen can go vertically,
horizontally, and diagonolly.
Chess player Max Bezzel promoted a problem that
if we put 8 queens simultaneously on the board,
how many solutions s.t. for each queen on the board,
one cannot attack another in 1 move.

For example:
    # # # # # Q # #
    # # # Q # # # #
    # # # # # # Q #
    Q # # # # # # #
    # # # # # # # Q
    # Q # # # # # #
    # # # # Q # # #
    # # Q # # # # #
    
In the case shown above, none queen can attack another
in one move.

Solution 1: Brute Force
(It can be shorter, but I am lazy to condenze it.)
> [name=Jason Lin]

n = 8 #default
n = eval(input())
def isexist(x,y): return 0<=x<n and 0<=y<n
def check(l):
    board = [[0]*n for i in range(len(l))]
    for i in range(len(l)):
        ll = l[i]
        board[i][ll] = 'Q'
        for ii in range(len(board)):
            if isexist(ii,i+ll-ii):
                if board[ii][i+ll-ii] == 'Q' and i!=ii: return False
            if isexist(ii,ll-i+ii):
                if board[ii][ll-i+ii] == 'Q' and i!=ii: return False
    return True
def permute(n):
    if n == 0: return [[0]]
    subset = permute(n-1)
    retSet = []
    for s in subset:
        for j in range(len(s)+1):
            l = s.copy()
            l.insert(j,n)
            retSet.append(l)
    return retSet
def ochoqueen():
    permutes = permute(n-1)
    solutions = []
    for i in range(len(permutes)):
        if check(permutes[i]): solutions.append(permutes[i])
    print(len(solutions))
if __name__ == '__main__':
    print(ochoqueen())

Solution 2: DFS - not good enough cuz it'll do many meaningless tries

Solution 3: Back-Tracking - a better solution based on DFS

#check if (x,y) is a legal index
def islegal(x,y): return 0<=x<n and 0<=y<n
#main recursive function based on dfs
def ochoqueen(b,x):
    #if we go through the whole board(we get a solution!)
    #,and add the solution to the list of solutions
    if x == len(b):
        sols.append(b)
        return
    #go through all possible column ys in row x
    for y in range(n):
        b[x][y] = 1
        safe = 1
        #check if (x,y) is a point that won't be  
        #attacked by the previous placed queens
        for i in range(x):
            if (islegal(i,y) and b[i][y]==1) \
            or (islegal(i,x+y-i) and b[i][x+y-i]==1) \
            or (islegal(i,y-x+i) and b[i][y-x+i]==1):
                b[x][y] = 0
                safe = 0
                break
        if safe: ochoqueen(b,x+1)
        b[x][y] = 0
    return

n = eval(input())
board = [[0]*n for i in range(n)]
sols = []
ochoqueen(board,0)
print(len(sols))

Solution by 學一

n = eval
b = []
for _ in range(n): b.append([0]*n)
    s = [0]*n
    z = 0
# input

def printsolution():
    global z
    print((z := z + 1))
    print('-'*n)
    for r in range(n):
        for c in range(n):
            print('Q'if c == s[r] else '', end = '')
        print('')
    print('-'*n)

def explore(r):
    def mark(d, j=0):
        for i in range(r+1, n):
            b[i][c] += d
            if c+j < n: b[i][c+j] += d
            if c-j >= 0: b[i][c-j] += d
            j+=1
			
        for c in range(n):
            if b[r][c]>0: continue
            s[r] = c
            if r == n - 1: printsolution(); continue
            mark(1)
            explore(r+1)
            mark(-1)
explore(0)