在一维数组中查找对角线边界
Finding a diagonal boundary in a one dimensional array
我有一个棋盘数组，如下所示：
00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
现在我试图找到 position 的函数，这是黑板上的一个数字，它给出了 up/right 对角线上的倒数第二个数字，例如对于 60，我试图找到 38，对于 30，我试图找到 22。我可以对这该死的东西进行硬编码，但找到一个执行此操作的函数真的更好。到目前为止，它难倒了我。
我没有遇到 down/right 和对角线和 [=23=] 对角线的问题，但是这个让我很困惑。任何帮助表示赞赏。
下面是我正在处理的代码：
# EightQueens.py
# Joshua Marshall Moore
# thwee.abacadabra.alchemist@gmail.com
# June 24th, 2017
# The eight queens problem consists of setting up eight queens on a chess board
# so that no two queens threaten each other.
# This is an attempt to find all possible solutions to the problem.
# The board is represented as a set of 64 numbers each representing a position
# on the board. Array indexing begins with zero.
# 00 01 02 03 04 05 06 07
# 08 09 10 11 12 13 14 15
# 16 17 18 19 20 21 22 23
# 24 25 26 27 28 29 30 31
# 32 33 34 35 36 37 38 39
# 40 41 42 43 44 45 46 47
# 48 49 50 51 52 53 54 55
# 56 57 58 59 60 61 62 63
# Test:
# The following combination should yield a True from the check function.
# 6, 9, 21, 26, 32, 43, 55, 60
from itertools import combinations
import pdb
# works
def down_right_boundary(pos):
boundary = (8-pos%8)*8
applies = (pos%8)+1 > int(pos/8)
if applies:
return boundary
else:
return 64
# works
def up_left_boundary(pos):
boundary = ((int(pos/8)-(pos%8))*8)-1
applies = (pos%8) <= int(pos/8)
if applies:
return boundary
else:
return -1
def up_right_boundary(pos):
boundary = [7, 15, 23, 31, 39, 47, 55, 62][pos%8]-1
# 7: nil
# 14: 7-1
# 15: 15-1
# 21: 7-1
# 22: 15-1
# 23: 23-1
# 28: 7-1
# 29: 15-1
# 30: 23-1
# 31: 31-1
# 35: 7-1
# 36: 15-1
# 37: 23-1
# 38: 31-1
# 39: 39-1
# 42: 7-1
# 43: 15-1
# 44: 23-1
# 45: 31-1
# 46: 39-1
applies = pos%8>=pos%7
if applies:
return boundary
else:
return -1
def down_left_boundary(pos):
boundary = 64
applies = True
if applies:
return boundary
else:
return 64
def check(positions):
fields = set(range(64))
threatened = set()
# two queens per quadrant
quadrants = [
set([p for p in range(0, 28) if (p%8)<4]),
set([p for p in range(4, 32) if (p%8)>3]),
set([p for p in range(32, 59) if (p%8)<4]),
set([p for p in range(36, 64) if (p%8)>3])
]
#for q in quadrants:
# if len(positions.intersection(q)) != 2:
# return False
# check the queen's ranges
for pos in positions:
pdb.set_trace()
# threatened |= set(range(pos, -1, -8)[1:]) # up
# threatened |= set(range(pos, 64, 8)[1:]) # down
# threatened |= set(range(pos, int(pos/8)*8-1, -1)[1:]) # left
# threatened |= set(range(pos, (int(pos/8)+1)*8, 1)[1:]) # right
# down right diagonal:
# There are two conditions here, one, the position is above the
# diagonal, two, the position is below the diagonal.
# Above the diagonal can be expressed as pos%8>int(pos/8).
# In the event of a position above the diagonal, I need to limit the
# range to 64-(pos%8) to prevent warping the board into a field that
# connects diagonals like Risk.
# Otherwise, 64 suffices as the ending condition.
threatened |= set(range(pos, down_right_boundary(pos), 9)[1:]) # down right
print(pos, threatened)
pdb.set_trace()
#
# up left diagonal:
# Similarly, if the position is above the diagonal, -1 will suffice as
# the range's ending condition. Things are more complicated if the
# position is below the diagonal, as I must prevent warping, again.
threatened |= set(range(pos, up_left_boundary(pos), -9)[1:]) # up left
print(pos, threatened)
pdb.set_trace()
#
# up right diagonal:
# Above the diagonal takes on a different meaning here, seeing how I'm
# dealing with the other diagonal. It is defined by pos58>pos%7. Now I
# restrict the range to a (pos%8)*8, creating a boundary along the right
# side of the board.
threatened |= set(range(pos, up_right_boundary(pos), -7)[1:]) # up right
print(pos, threatened)
pdb.set_trace()
#
# down left diagonal:
# I reuse a similar definition to that of the diagonal as above. The
# bound for left hand side of the board looks as follows:
# ((pos%8)*7)+(pos%8)
threatened |= set(range(pos, down_left_boundary(pos), 7)[1:]) # down left
print(pos, threatened)
pdb.set_trace()
#
if len(positions.intersection(threatened)) > 0:
return False
return True
if __name__ == '__main__':
# print(check(set([55]))) # pass
# print(check(set([62]))) # pass
# print(check(set([63]))) # pass
# print(check(set([48]))) # pass
# print(check(set([57]))) # pass
# print(check(set([56]))) # pass
# print(check(set([8]))) # pass
# print(check(set([1]))) # fail
# print(check(set([0])))
# print(check(set([6])))
# print(check(set([15])))
# print(check(set([7])))
# print(check(set([6])))
# print(check(set([9])))
print(check(set([21])))
print(check(set([26])))
print(check(set([32])))
print(check(set([43])))
print(check(set([55])))
print(check(set([60])))
print(
check(set([6, 9, 21, 26, 32, 43, 55, 60]))
)
# for potential_solution in combinations(range(64), 8):
# is_solution = check(set(potential_solution))
# if is_solution:
# print(is_solution, potential_solution)
使用以下棋盘位置：
chessboard = [0,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,28,29,30,31,
32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,
56,57,58,59,60,61,62,63]
我写了一个你想要的对应的函数（注释描述代码）：
def return_diagonal(position): # with position being chessboard position
while ((position+1)%8) != 0: # while (chess position)+1 is not divisible by eight:
position -= 7 # move diagonally upwards (7 chess spaces back)
position -= 1 # when reached the right end of the chessboard, move back one position
if position < 6: # if position happens to be in the negative:
position = 6 # set position by default to 6 (smallest possible value)
return position # return the position
函数首先询问位置是否在最后一列。
如果不是，则返回 7spaces，即向右斜上方
然后再次检查，直到到达最后一列。
那里，它往后退一space，所以它是从棋盘右端的左边一space。
但是，如果这个数字是负数（就像左上角的许多数字一样），这意味着对角线完全延伸到 8x8 棋盘之外。
所以，默认情况下，答案应该是 6。
我做了几个测试
print(60,return_diagonal(60))
print(30,return_diagonal(30))
print(14,return_diagonal(14))
print(1,return_diagonal(1))
输出如下：
原始位置，up/right对角线上的倒数第二个数字
60 38
30 22
14 6
1 6
我有一个棋盘数组，如下所示：
00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
现在我试图找到 position 的函数，这是黑板上的一个数字，它给出了 up/right 对角线上的倒数第二个数字，例如对于 60，我试图找到 38，对于 30，我试图找到 22。我可以对这该死的东西进行硬编码，但找到一个执行此操作的函数真的更好。到目前为止，它难倒了我。
我没有遇到 down/right 和对角线和 [=23=] 对角线的问题，但是这个让我很困惑。任何帮助表示赞赏。
下面是我正在处理的代码：
# EightQueens.py
# Joshua Marshall Moore
# thwee.abacadabra.alchemist@gmail.com
# June 24th, 2017
# The eight queens problem consists of setting up eight queens on a chess board
# so that no two queens threaten each other.
# This is an attempt to find all possible solutions to the problem.
# The board is represented as a set of 64 numbers each representing a position
# on the board. Array indexing begins with zero.
# 00 01 02 03 04 05 06 07
# 08 09 10 11 12 13 14 15
# 16 17 18 19 20 21 22 23
# 24 25 26 27 28 29 30 31
# 32 33 34 35 36 37 38 39
# 40 41 42 43 44 45 46 47
# 48 49 50 51 52 53 54 55
# 56 57 58 59 60 61 62 63
# Test:
# The following combination should yield a True from the check function.
# 6, 9, 21, 26, 32, 43, 55, 60
from itertools import combinations
import pdb
# works
def down_right_boundary(pos):
boundary = (8-pos%8)*8
applies = (pos%8)+1 > int(pos/8)
if applies:
return boundary
else:
return 64
# works
def up_left_boundary(pos):
boundary = ((int(pos/8)-(pos%8))*8)-1
applies = (pos%8) <= int(pos/8)
if applies:
return boundary
else:
return -1
def up_right_boundary(pos):
boundary = [7, 15, 23, 31, 39, 47, 55, 62][pos%8]-1
# 7: nil
# 14: 7-1
# 15: 15-1
# 21: 7-1
# 22: 15-1
# 23: 23-1
# 28: 7-1
# 29: 15-1
# 30: 23-1
# 31: 31-1
# 35: 7-1
# 36: 15-1
# 37: 23-1
# 38: 31-1
# 39: 39-1
# 42: 7-1
# 43: 15-1
# 44: 23-1
# 45: 31-1
# 46: 39-1
applies = pos%8>=pos%7
if applies:
return boundary
else:
return -1
def down_left_boundary(pos):
boundary = 64
applies = True
if applies:
return boundary
else:
return 64
def check(positions):
fields = set(range(64))
threatened = set()
# two queens per quadrant
quadrants = [
set([p for p in range(0, 28) if (p%8)<4]),
set([p for p in range(4, 32) if (p%8)>3]),
set([p for p in range(32, 59) if (p%8)<4]),
set([p for p in range(36, 64) if (p%8)>3])
]
#for q in quadrants:
# if len(positions.intersection(q)) != 2:
# return False
# check the queen's ranges
for pos in positions:
pdb.set_trace()
# threatened |= set(range(pos, -1, -8)[1:]) # up
# threatened |= set(range(pos, 64, 8)[1:]) # down
# threatened |= set(range(pos, int(pos/8)*8-1, -1)[1:]) # left
# threatened |= set(range(pos, (int(pos/8)+1)*8, 1)[1:]) # right
# down right diagonal:
# There are two conditions here, one, the position is above the
# diagonal, two, the position is below the diagonal.
# Above the diagonal can be expressed as pos%8>int(pos/8).
# In the event of a position above the diagonal, I need to limit the
# range to 64-(pos%8) to prevent warping the board into a field that
# connects diagonals like Risk.
# Otherwise, 64 suffices as the ending condition.
threatened |= set(range(pos, down_right_boundary(pos), 9)[1:]) # down right
print(pos, threatened)
pdb.set_trace()
#
# up left diagonal:
# Similarly, if the position is above the diagonal, -1 will suffice as
# the range's ending condition. Things are more complicated if the
# position is below the diagonal, as I must prevent warping, again.
threatened |= set(range(pos, up_left_boundary(pos), -9)[1:]) # up left
print(pos, threatened)
pdb.set_trace()
#
# up right diagonal:
# Above the diagonal takes on a different meaning here, seeing how I'm
# dealing with the other diagonal. It is defined by pos58>pos%7. Now I
# restrict the range to a (pos%8)*8, creating a boundary along the right
# side of the board.
threatened |= set(range(pos, up_right_boundary(pos), -7)[1:]) # up right
print(pos, threatened)
pdb.set_trace()
#
# down left diagonal:
# I reuse a similar definition to that of the diagonal as above. The
# bound for left hand side of the board looks as follows:
# ((pos%8)*7)+(pos%8)
threatened |= set(range(pos, down_left_boundary(pos), 7)[1:]) # down left
print(pos, threatened)
pdb.set_trace()
#
if len(positions.intersection(threatened)) > 0:
return False
return True
if __name__ == '__main__':
# print(check(set([55]))) # pass
# print(check(set([62]))) # pass
# print(check(set([63]))) # pass
# print(check(set([48]))) # pass
# print(check(set([57]))) # pass
# print(check(set([56]))) # pass
# print(check(set([8]))) # pass
# print(check(set([1]))) # fail
# print(check(set([0])))
# print(check(set([6])))
# print(check(set([15])))
# print(check(set([7])))
# print(check(set([6])))
# print(check(set([9])))
print(check(set([21])))
print(check(set([26])))
print(check(set([32])))
print(check(set([43])))
print(check(set([55])))
print(check(set([60])))
print(
check(set([6, 9, 21, 26, 32, 43, 55, 60]))
)
# for potential_solution in combinations(range(64), 8):
# is_solution = check(set(potential_solution))
# if is_solution:
# print(is_solution, potential_solution)
使用以下棋盘位置：
chessboard = [0,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,28,29,30,31,
32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,
56,57,58,59,60,61,62,63]
我写了一个你想要的对应的函数（注释描述代码）：
def return_diagonal(position): # with position being chessboard position
while ((position+1)%8) != 0: # while (chess position)+1 is not divisible by eight:
position -= 7 # move diagonally upwards (7 chess spaces back)
position -= 1 # when reached the right end of the chessboard, move back one position
if position < 6: # if position happens to be in the negative:
position = 6 # set position by default to 6 (smallest possible value)
return position # return the position
函数首先询问位置是否在最后一列。
如果不是，则返回 7spaces，即向右斜上方
然后再次检查，直到到达最后一列。
那里，它往后退一space，所以它是从棋盘右端的左边一space。
但是，如果这个数字是负数（就像左上角的许多数字一样），这意味着对角线完全延伸到 8x8 棋盘之外。
所以，默认情况下，答案应该是 6。
我做了几个测试
print(60,return_diagonal(60))
print(30,return_diagonal(30))
print(14,return_diagonal(14))
print(1,return_diagonal(1))
输出如下：
原始位置，up/right对角线上的倒数第二个数字
60 38
30 22
14 6
1 6