题目
- 有27个参加跑步的人，每3人一组，分成9组，同一组用同一个号。就是1号3个，2号3个，3号3个……现在假设第一组的赢得了比赛，每次只有一个人到达。所有人到达的时候满足规律，1号参赛者之间都间隔一个人，2号参赛者之间都间隔2个人，3号参赛者之间都间隔3个人…9号参赛者之间都间隔9人。问27个人的到达顺序是否有解？如果有，解是什么？
解决方案
- 解决方案（Python 代码）
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
62def 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()