8 Queens on a chessboard | PYTHON | Memory Error

Question

I came across this question where 8 queens should be placed on a chessboard such that none can kill each other.This is how I tried to solve it:

import itertools
def allAlive(position):
    qPosition=[]
    for i in range(8):
        qPosition.append(position[2*i:(2*i)+2])
    hDel=list(qPosition)     #Horizontal
    for i in range(8): 
        a=hDel[0]
        del hDel[0]
        l=len(hDel)
        for j in range(l):
            if a[:1]==hDel[j][:1]:
                return False
    vDel=list(qPosition)     #Vertical
    for i in range(8):
        a=vDel[0]
        l=len(vDel)
        for j in range(l):
            if a[1:2]==vDel[j][1:2]:
                return False
    cDel=list(qPosition)     #Cross
    for i in range(8):
        a=cDel[0]
        l=len(cDel)
        for j in range(l):
            if abs(ord(a[:1])-ord(cDel[j][:1]))==1 and abs(int(a[1:2])-int(cDel[j][1:2]))==1:
                return False
    return True
chessPositions=['A1','A2','A3','A4','A5','A6','A7','A8','B1','B2','B3','B4','B5','B6','B7','B8','C1','C2','C3','C4','C5','C6','C7','C8','D1','D2','D3','D4','D5','D6','D7','D8','E1','E2','E3','E4','E5','E6','E7','E8','F1','F2','F3','F4','F5','F6','F7','F8','G1','G2','G3','G4','G5','G6','G7','G8','H1','H2','H3','H4','H5','H6','H7','H8']
qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]
for i in qPositions:
    if allAlive(i)==True:
        print(i)

Traceback (most recent call last):

qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]

MemoryError

I'm still a newbie.How can I overcome this error?Or is there any better way to solve this problem?

Answer 1

What you are trying to do is impossible ;)!

qPositions=[''.join(p) for p in itertools.combinations(chessPositions,8)]

means that you will get a list with length 64 choose 8 = 4426165368, since len(chessPositions) = 64, which you cannot store in memory. Why not? Combining what I stated in the comments and @augray in his answer, the result of above operation would be a list which would take

(64 choose 8) * 2 * 8 bytes ~ 66GB

of RAM, since it will have 64 choose 8 elements, each element will have 8 substrings like 'A1' and each substring like this consists of 2 character. One character takes 1 byte.

You have to find another way. I am not answering to that because that is your job. The n-queens problem falls into dynamic programming. I suggest you to google 'n queens problem python' and search for an answer. Then try to understand the code and dynamic programming.

---

I did searching for you, take a look at this video. As suggested by @Jean François-Fabre, backtracking. Your job is now to watch the video once, twice,... as long as you don't understand the solution to problem. Then open up your favourite editor (mine is Vi :D) and code it down!

Answer 2

This is one case where it's important to understand the "science" (or more accurately, math) part of computer science as much as it is important to understand the nuts and bolts of programming.

From the documentation for itertools.combinations, we see that the number of items returned is n! / r! / (n-r)! where n is the length of the input collection (in your case the number of chess positions, 64) and r is the length of the subsequences you want returned (in your case 8). As @campovski has pointed out, this results in 4,426,165,368. Each returned subsequence will consist of 8*2 characters, each of which is a byte (not to mention the overhead of the other data structures to hold these and calculate the answer). Each character is 1 byte, so in total, just counting the memory consumption of the resulting subsequences gives 4,426,165,368*2*8=70818645888. dividing this by 1024^3 gives the number of Gigs of memory held by these subsequences, about 66GB.

I'm assuming you don't have that much memory :-) . Calculating the answer to this question will require a well thought out algorithm, not just "brute force". I recommend doing some research on the problem- Wikipedia looks like a good place to start.