趣味题——同距运动员

题目

  • 有27个参加跑步的人，每3人一组，分成9组，同一组用同一个号。就是1号3个，2号3个，3号3个……现在假设第一组的赢得了比赛，每次只有一个人到达。所有人到达的时候满足规律，1号参赛者之间都间隔一个人，2号参赛者之间都间隔2个人，3号参赛者之间都间隔3个人…9号参赛者之间都间隔9人。问27个人的到达顺序是否有解？如果有，解是什么？

解决方案

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
def check_row(row, gap):
    a = abs(row[0] - row[1]) == gap
    b = abs(row[1] - row[2]) == gap
    c = abs(row[2] - row[0]) == gap
    abc = [a, b, c]
    if sum([1 if e else 0 for e in abc]) != 2:
        return False
    return True


def generate_conds(ri, rest_number):
    size = len(rest_number)
    gap = ri + 2
    conds = list()
    for i in range(size):
        for j in range(i+1, size):
            for k in range(j+1, size):
                row = rest_number[i], rest_number[j], rest_number[k]
                if check_row(row, gap):
                    conds.append(row)
    return conds


def backtrace(maze, ri, rest_number, all_maze):
    if not rest_number:
        data_ = [[e for e in row] for row in maze]
        all_maze.append(data_)
        return True
    conds = generate_conds(ri, rest_number)
    if not conds:
        return False
    for row in conds:
        local_rest = [e for e in rest_number]
        for e in row:
            # print("local rest: %s and e: %s" % (local_rest, e))
            local_rest.remove(e)
        maze[ri] = [e for e in row]
        backtrace(maze, ri + 1, local_rest, all_maze)


def solution():
    maze = list()
    for i in range(9):
        row = [0 for _ in range(3)]
        maze.append(row)
    rest_number = list(range(1, 28))
    maze[0][0] = 1
    maze[0][1] = 3
    maze[0][2] = 5
    rest_number.remove(1)
    rest_number.remove(3)
    rest_number.remove(5)
    all_maze = list()
    # print(rest_number)
    # print(maze)
    backtrace(maze, 1, rest_number, all_maze)
    for maze in all_maze:
        print(maze)


if __name__ == "__main__":
    solution()