I'm solving the Eight Queens problem with Python 3.5.1. The answer is 92, but it's 29. I don't think there's a problem with the algorithm, so what's the problem? It is a method of repeatedly finding a case that can be placed in the lower row after placing it from the top row.
global count
count = 0
def locate(b, co):
br = b[:]
y, x = (co[0], co[1])
if br[y][x] == 1:
return br
else:
for i in range(8):
br[i][x] = 1
br[y][i] = 1
for i in range(min(x,7-y)):br[y+i+1][x-i-1] = 1
for i in range(min(x,y)):br[y-i-1][x-i-1] = 1
for i in range(min(7-x,7-y)):br[y+i+1][x+i+1] = 1
for i in range(min(7-x,y)):br[y-i-1][x+i+1] = 1
return br
def newbr(li = []):
br = li[:]
if br == []:
for i in range(8):
br.append([])
for j in range(8):
br[i].append(0)
return br
def n0(br, y):
tmp = []
if len(br[y]) == 0:return tmp
for x in range(len(br[y])):
if br[y][x] == 0:
tmp.append(x)
return tmp
def cal(br, depth = 0):
l0 = n0(br, depth)
if depth == 7:
counter()
return
for x in l0:
print(depth, end='')
tmp = br[:]
tmp = locate(tmp, (depth, x))
if len(n0(tmp, depth+1)) != 0:
cal(tmp, depth+1)
def counter():
global count
count += 1
if __name__ == '__main__':
board = newbr()
cal(board)
print('\n'+str(count))
I thought you wanted to solve it with a recursive function, so I solved it with a recursive function.
Two queens cannot come in one row and one column. So the result is an eight-length list. The index of the list is row number, and the value of the index is column number. For example, if the result is [0, 4, 7, 5, 2, 6, 1, 3], then one queen for (0,0), one queen for (1,4), and one queen for (2,7)... This is how you place it.
The logic of writing the code is
Turn the blank list over to the function search_8queens that works like this.
def search_8queens(pos):
current_row = len(pos)
if current_row == 8:
print(pos)
for current_column in range(8):
if current_column in pos:
continue
break_rule = False;
for previous_row, previous_column in enumerate(pos):
if abs(current_column - previous_column) == abs(current_row - previous_row):
break_rule = True
break
if not break_rule:
search_8queens(pos+[current_column])
search_8queens([])
If you run it, it's faster than the short code I uploaded before.
The problem with 8 queens is to place 8 queens on the chessboard so that 8 queens don't attack each other. It doesn't seem easy because the Queen can move up, down, left, right, and right.
I searched and found an answer first.
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 vec
If you press [Run] and run it on the code executor, you'll see 92 lines, each row telling you how many columns the queen is in.
Study after pre-sharing. I need to study why this is happening. The answer comes out short like Python.
© 2024 OneMinuteCode. All rights reserved.