Welcome, guest | Sign In | My Account | Store | Cart

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:

1. Don't place the coin if there is another coin present in the same row
2. Don't place the coin if there is another coin present in the same col
3. 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

Python, 27 lines
 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)) Created by Narayana Chikkam on Wed, 21 Jul 2010 (MIT)