‘Eight Queens Puzzle’ is a classic chess puzzle, where you are challenged to place 8 queens, of the same colour, onto a chess board, such that no queen attacks any other queen. So, none of them may share a row, column, or diagonal with any other.
In a previous post, I introduced Raymond Hettinger’s ‘Easy AI with Python‘. Here is the first of his ‘AI’ programs; it solves the 8 queens chess puzzle.
Raymond’s solution relies on the permutations() function from itertools, and is:
… represented as a vector with one queen in each row, we don’t have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don’t have to check to see if two queens are on the same column. Since rook moves don’t need to be checked, we only need to check bishop moves.
The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).
Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.
See Rosettacode for other solutions.
# 8 Queens
# from http://code.activestate.com/recipes/576647/
from itertools import permutations
n = 8
cols = range(n)
for vec in permutations(cols):
if (n == len(set(vec[i]+i for i in cols))
== len(set(vec[i]-i for i in cols))):
print ("\n".join('#' * i + 'Q' + '#' * (n-i-1) for i in vec) + '\n')