Skip to main content
 首页 » 编程设计

python之在一维数组中查找对角线边界

2025年02月15日8Free-Thinker

我有一个棋盘数组,如下所示:

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 的函数,这是板上的一个数字,它给我上/右对角线中的倒数第二个数字,例如对于 60,我试图找到 38,对于 30,我试图找到 22。我可以对这该死的东西进行硬编码,但找到一个执行此操作的函数真的更好。到目前为止,它难倒了我。

我在下/右和对角线以及上/左对角线方面没有遇到问题,但是这个让我很困惑。任何帮助表示赞赏。

下面是我正在处理的代码:

# 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 

函数首先询问位置是否在最后一列。

如果不是,则向后退7格,即向右斜上走。

然后它会再次检查,直到到达最后一列。

在那里,它向后退一格,即距离棋盘右端左边一格。

但是,如果这个数字是负数(就像左上角的许多数字一样),这意味着对角线完全延伸到 8x8 棋盘之外。

因此,默认情况下,答案应为 6。

我做了几个测试

print(60,return_diagonal(60)) 
print(30,return_diagonal(30)) 
print(14,return_diagonal(14)) 
print(1,return_diagonal(1)) 

输出如下:

原始位置,上/右对角线的倒数第二个数字

60 38 
30 22 
14 6 
1 6