Eight Queens is one of the popular algorithms in backtracking. The solution given below uses simple math to reduce the processing. The logic is keep placing the coins on the board with below rules:

- Don't place the coin if there is another coin present in the same row
- Don't place the coin if there is another coin present in the same col
- Don't place the coin if there is another coin present in any of the diagonal lines.

Keep repeating the above 3 rules recursively until we keep all the coins. Problem Definition: http://en.wikipedia.org/wiki/Eight_queens_puzzle

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | ```
board = {}
def render():
s = dict([(i, ['-'] * 8) for i in range(8)])
for (x, y) in board.keys():
s[x][y] = 'Q'
for line in s.keys():
print ''.join(s[line])
def gen(row):
if row == 8:
render()
print "\n"
return
else:
for col in range(8):
if row not in [x for (x,y) in board.keys()] and \
col not in [y for (x,y) in board.keys()] and \
len([(x,y) for (x,y) in board.keys() if abs(row-x) == abs(col-y)]) == 0:
board[(row, col)] = 1
gen(row+1)
board.__delitem__((row, col))
for i in range(8):
board[(0, i)] = 1
gen(1)
board.__delitem__((0, i))
``` |