We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
def is_valid(row, col, placement):
for r2 in range(row):
c2 = placement[r2]
if col == c2 or abs(row - r2) == abs(col - c2):
return False
for r1 in range(r2):
c1 = placement[r1]
if is_colinear(r1, c1, r2, c2, row, col):
return False
return True
def solve(n, placement=[], used_cols=set()):
row = len(placement)
if row == n:
return placement
for col in range(n):
if col in used_cols:
continue
if is_valid(row, col, placement):
res = solve(n, placement + [col], used_cols | {col})
if res:
return res
return None
if name == "main":
max_n = 13
for n in range(max_n, 0, -2):
result = solve(n)
if result:
print(n)
print(" ".join(str(c + 1) for c in result))
break
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Spies, Revised
You are viewing a single comment's thread. Return to all comments →
def is_colinear(r1, c1, r2, c2, r3, c3): return (r2 - r1) * (c3 - c1) == (r3 - r1) * (c2 - c1)def is_valid(row, col, placement): for r2 in range(row): c2 = placement[r2] if col == c2 or abs(row - r2) == abs(col - c2): return False for r1 in range(r2): c1 = placement[r1] if is_colinear(r1, c1, r2, c2, row, col): return False return True
def solve(n, placement=[], used_cols=set()): row = len(placement) if row == n: return placement for col in range(n): if col in used_cols: continue if is_valid(row, col, placement): res = solve(n, placement + [col], used_cols | {col}) if res: return res return None
if name == "main": max_n = 13 for n in range(max_n, 0, -2): result = solve(n)if result: print(n) print(" ".join(str(c + 1) for c in result)) break