# set {0,1,...,7}
CSET = { i for i in range(0,8) }
def find_one_solution(b,r):
"""
Find one solution for b, if any, and store it in r.
"""
assert type(b) == type(r) == type(list())
pass
def find_all_solutions(b,r):
"""
Find all solutions for b, if any, and store them in r.
"""
assert type(b) == type(r) == type(list())
pass
def solved(b):
"""
Check if the given board is solved.
"""
global CSET
assert type(b) == type(list())
return set(b) == CSET
def get_candidate(b):
"""
Return an index in b representing a candidate for backtracing;
if there is no candidate, then return None.
"""
r,i,found = None,0,False
while i < 8 and not(found):
i,found = i+1,b[i]==-1
if found:
r = i-1
return r
def get_options(b,i):
"""
Return a list of possible column values for row i in the board b.
"""
assert type(b) == type(list())
assert len(b) == 8
assert 0 <= i < 8
r = list()
if b[i] == -1:
for c in range(0,8):
if is_safe(b,i,c):
r.append(c)
else:
r.append(b[i])
return r
def is_valid(b):
"""
Return True if there are no conflicts in the board b; False otherwise.
"""
assert type(b) == type(list())
assert len(b) == 8
r,i = True,0
while r and i < 8:
if b[i] != -1:
t,b[i] = b[i],-1
r = is_safe(b,i,t)
b[i] = t
i += 1
return r
def is_safe(b,i,c):
"""
Return True if placing a queen in (i,c) is safe; otherwise
return False.
"""
assert type(b) == type(list())
assert len(b) == 8
assert 0 <= i < 8
assert 0 <= c < 8
r = True
# check if row i is empty
if b[i] == -1:
# if row i is empty, then check if placing a queen in
# row i and column c is safe
# first check if there is a queen already in column c; if so,
# then placing a queen at (i,c) is not safe
r = not(c in b)
if r:
# check if there is a conflict with any of the diagonals
d = 1
while r and i+d < 8 and c+d < 8:
r,d = (b[i+d]!=c+d),d+1
d = 1
while r and i-d >= 0 and c-d >= 0:
r,d = (b[i-d]!=c-d),d+1
d = 1
while r and i+d < 8 and c-d >= 0:
r,d = (b[i+d]!=c-d),d+1
d = 1
while r and i-d >= 0 and c+d < 8:
r,d = (b[i-d]!=c+d),d+1
else:
# row (i+1) is not empty, hence placing a queen in row (i+1)
# and column c is safe if and only if there is a queen already
# in row (i+1) and column c
r = (b[i] == c)
return r