8 Queens on Chess Board
This story goes through the 8 Queens problem and implement a few Python programming skills and the use of Chess Library.
Chess is very popular actually for those who saw “The Queen’s Gambit” on Netflix (or other channels). https://en.wikipedia.org/wiki/The_Queen%27s_Gambit_(miniseries)
I used to play Chess since I am 6 years old and programming since 14 y.o. I am 55 y.o now, so you can imagine how long I dealt both topics. Each time, I started with a new language (and it has been a lot: Cobol, Modula-2, Turbo Pascal, VBA, Java, IOS, PHP, Javascript LotusScript and more recently Python) I tried to implement the 8 Queens problem.
Data Structures
This problem is a good topic to deal with programming structure such as lists, trees, folders and other data storage in memory. Most of the languages implements functions and methods to access items (array, tuple, dictionary, list, ..).
The Problem
Even for those who are not familiar with Chess, the 8 Queens problem is not complicated.
The chess is a strategic game where 2 players are faced. Each player has a set of piece on the board. Each piece has a specific behaviour (to move). The board is a surface of 8x8 cells codified from A..H on (x-axis) and (1..8) on (y-axis). The left-bottom cell is A1 and the top-right cell is H8.
A Queen can attack a piece on these directions:
- on the same line
- on the same column
- on each diagonal
Let’s have an example.
For the illustration I play with “wonderful” Chess Library available on python.
The Chess board is empty and a Queen is placed on the f5 cell (number 37). We can have a look on the possible attacks (and “eat” other pieces she can make).
The Queen in “f5” put in danger all pieces (other Queens) in row (5), columns (f) and 2 the diagonale.
The challenge !
How to place 8 Queens on the Chess Board for them to be safe from each other.
Preliminary Study
In a pure mathematic, there is a lot of combinaison to put 8 Queens on a Chess Board. As the the board is 8X8 this means we have [64*63*62*61*60*59*58*57] which means a lot combinaisons.
We can reduce the number of combinaison by setting one Queen per row and one per columns ! the number of combinaison will be less [8*7*6*5*4*3*2*1] = 40320 (options).
On the 1st row we have 8 positions, on the 2nd row with still have 7 position (minus the 1st row) and on the 3rd row we still have 6 position (minus the 1st and the 2nd row position). In total we have 40'320 combinaison which respect the rule of “not on the same row and not on the same column”.
The problem is simplified to check what happened with the diagonales.
Algorithm
The algorithm is quite simple, the process goes through all the (reduced) combinaisons and check if diagonal rules are respected. For this we have very useful function in numpy called “diag()” and “fliplr()”. For each combinaison the idea is to lock all cells for a specific queen. If I can place the 8 queen on the board, this means the combinaison is valid.
Let’s start programming :-)
Import a few libraries.
import numpy as np
import pandas as pd
import randomimport chess
Chess Library is used for illustration only. Here I show a few useful functions but nor relate to the algorithm.
board= chess.Board()
board.clear()board.set_piece_at(37,piece)board
These line create a chess board and set a queen on 37th cell (count the cell from left to right and bottom to top).
The core place of the program is to place a Queen on the board and store all “locked” cell in a numpy.array. Then doing again with a second queen and continue until the 8 queens are on the Chess Board or no more place for a new Queen.
This method will be called for all 40'320 combinaisons. So let’s start by creating the array with all combinaison.
combinaison=[]
for a1 in range(1,9):
i1=np.where((b_indices==a1))
a2_list=np.delete(b_indices,i1[1],1)[1]
for a2 in a2_list:
i2=np.where(b_indices==a2)
a3_list=np.delete(b_indices,[i1[1],i2[1]],1)[2]
for a3 in a3_list:
i3=np.where(b_indices==a3)
a4_list=np.delete(b_indices,[i1[1],i2[1],i3[1]],1)[3]
for a4 in a4_list:
i4=np.where(b_indices==a4)
a5_list=np.delete(b_indices,[i1[1],i2[1],i3[1],i4[1]],1)[4]
for a5 in a5_list:
i5=np.where(b_indices==a5)
a6_list=np.delete(b_indices,[i1[1],i2[1],i3[1],i4[1], i5[1]],1)[5]
for a6 in a6_list:
i6=np.where(b_indices==a6)
a7_list=np.delete(b_indices,[i1[1],i2[1],i3[1],i4[1], i5[1], i6[1]],1)[6]
for a7 in a7_list:
i7=np.where(b_indices==a7)
a8_list=np.delete(b_indices,[i1[1],i2[1],i3[1],i4[1], i5[1], i6[1], i7[1]],1)[7]
for a8 in a8_list:
temp=(a1,a2, a3, a4, a5, a6, a7, a8)
combinaison.append(temp)
print(len(combinaison))This code create a “combinaison” array with all possible combination of 8 Queens on a board respecting the rule “not on the same row and not on the same column”.
Programming a method to evaluate the place of a Queen
This function places a Queen on the board and “lock” all cells she might attack. I used a codification np.nan if the cell is in “danger” and “99” for the place of a Queen on the Chess Board.
def play_queen(b,h,v):
b[h,v]=1
dia_normal=None
dia_flipped=None
for i in range(-7,8):
#print(i)
if 1 in np.diag(b,i):
dia_normal=i
if 1 in np.diag(np.fliplr(b),i):
dia_flipped=i#print(h,v, dia_normal, dia_flipped)
locked=np.concatenate( (np.array(b_indices[h,:])
, np.array(b_indices[:,v])
, np.diag(b_indices,dia_normal)
, np.diag(np.fliplr(b_indices)
, dia_flipped) )
, axis=0)
#print(locked)
#in my original board, lock all places from locked
for lo in locked:
data_indices = np.where((b_indices==lo))
h_to_lock=data_indices[0][0]
v_to_lock=data_indices[1][0]
if b[h_to_lock,v_to_lock] != 1:
b[h_to_lock,v_to_lock]=np.nan
b[h,v]=99
#print(b)
free_places = np.where((b==0))
return b, free_places
The core issues in the functions is the use of np.diag() and np.fliplr(). These 2 methods of numpy gives the indices (or value) for a multidimensional array related to a position. In fact. these to methods return the indices (x,y) of the diagonal attacked by a queen on a board.
Calling the play_queen function
Time to loop over the 40320 combinaisons and call the play_queen function to evaluate cells in danger. For each item of the combinaison, the program try to set the queen if it is not possible (the place is locked by another queen) so the loop “break”, store the max queen for this combinaison and goes to the next one.
If all queens are on the board, the loop st the result to True.
for dx, r in test_df.iterrows():
#print(r.tolist())
ind=r.tolist()
b = np.zeros((8,8))
for j in range(8):
pos=np.where(b_indices==ind[j])
#print('pos', pos, pos[0][0], pos[1][0])
h = pos[0][0]
v = pos[1][0]
b, fp = play_queen(b,h,v)
x = fp[0]
y = fp[1]
if len(x) == 0:
if j == 7:
v8=np.where(b==99)
if (len(v8[0])==8) & (len(v8[1])==8):
print('Count of Queen = {}'.format(v8))
test_df.loc[dx,'result']=True
test_df.loc[dx,'failed']=8
break
else:
print(dx,ind,'* exit at {} *'.format(j))
test_df.loc[dx,'failed']=j
breakLooking the result
All the combination and result are stored in DataFrame which can be used to analyse results.
v=test_df['failed'].value_counts()
v=pd.DataFrame(v)
v['queens']=v.indexv
sns.set(rc={'figure.figsize':(11.7,8.27)})
ax=sns.barplot(data=v, y='failed', x='queens')
Finally we have 92 combinaisons which can accept the 8 Queens on the board without being in danger from the other one. This means 0.22% of the combinaison which respects the the rules (not the same row and not the same column) and “5.15513055215345e-11 %” of the total of possibilities to place 8 Queens on the Board.
Conclusion
- numpy offers 2 wonderful functions “diag()” and “fliplr()”
- chess game is a very good field to explore language programming such as Python
- data structure (list, tuple, dictionary, ..) is a must to learn in each language
- Python Chess library is powerful (more post on this topic to come)
And finally, all that story has been inspired by this image :-)
