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

Eight Queens With out Permutations (Python recipe) by Narayana Chikkam
ActiveState Code (http://code.activestate.com/recipes/577325/)

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
Download
 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))
Tags: eight, queens