拼图/谜语把1到8个数字的唯一组合在7 × 7矩阵

Question

我被下面的难题困住了。需要你的帮助来解决这个问题:有8个人在一家酒店预定了7个房间，并决定只使用这7个房间中的4个，方法是让两个人的组合在7天内不会重复，也不会让一个人在一个房间里呆两次。例如，如果1& 2,3& 4,5& 6和7& 8留在房间1，房间2，房间3和房间4，那么这些组合永远不会呆在一起。他们必须做出不同的组合，并改变房间。另一个例子，我不能再和任何人呆在1号房间，这也适用于其他人。

有谁能帮我解决这个7x7矩阵吗?感谢您的努力!

Answer 1

1&2       6&7       3&8       4&5  
5&6  1&3       4&8            2&7  
     5&7  1&4            2&8  3&6  
7&8       2&3  1&5       4&6       
     2&4  5&8  3&7  1&6            
3&4  6&8            2&5  1&7       
               2&6  4&7  3&5  1&8 

程序:)

Answer 2

一个解决方案是:

18          36 27 45
35 17    46 28      
47 25 16          38
26    37 15    48   
      58 23 14    67
   68 24    57 13   
   34    78    56 12

实际上，这是两个解，因为你可以阅读行代表天，列代表房间，反之亦然。分配给人们的每一个数字的排列，每一个房间(列)的排列，每一个日期(行)的排列，也会导致另一个解决方案。

---

以下是Python代码，基于Egor Skriptunoff的解决方案。主要思想是相同的:生成所有成对的人的列表，并开始将他们一次一个地放在黑板上。如果没有有效的位置，那么就回溯并尝试其他内容。在下面的代码中，tasks的列表记录了董事会状态，因此当到达死胡同时，下一个候选董事会状态将从tasks列表中弹出。关键在于以一种有组织、有效的方式列举所有的可能性。

有一些小的区别:

这段代码是迭代的，而不是递归的。
• solve函数尝试生成所有解，而不是在找到一个解后停止。
• 为简单起见，删除了初始化条件。

---

import itertools as IT
import collections
import copy
import random
people = range(1, 9)
days = range(7)
rooms = range(7)
pairs = list(IT.combinations(people, 2))

def solve():
    board = [[None for room in rooms] for day in days]
    pairidx = 0
    tasks = [(pairidx, board)]
    while tasks:
        pairidx, board = tasks.pop()
        if pairidx == len(pairs):
            yield board
            continue
        for day, room in IT.product(days, rooms):
            if not (used_day(board, pairidx, day)
                    or used_room(board, pairidx, room)
                    or used_day_room(board, day, room)):
                tasks.append(
                    (pairidx + 1, move(board, pairidx, day, room)))

def used_day(board, pairidx, day):
    """
    Return True if any person in persons has already been assigned a room
    """
    return any([person in pairs[idx] for idx in board[day] if idx is not None
                for person in pairs[pairidx]])

def used_room(board, pairidx, room):
    """
    Return True if any person in persons already been in the room
    """
    return any([person in pairs[row[room]] for row in board if row[room] is not None
                for person in pairs[pairidx]])

def used_day_room(board, day, room):
    """
    Return True if the room has already been assigned a pair for the day
    """
    return board[day][room] is not None

def move(board, pairidx, day, room):
    """
    Assign a pair to a room on a given day. Return the new (copy) of the board.
    """
    board = copy.deepcopy(board)
    board[day][room] = pairidx
    return board

def report(board):
    print('n'.join(
        [' '.join([''.join(map(str, pairs[col])) if col is not None else
                   '  ' for col in row])
         for row in board]))
    print('-' * 20)
for solution in solve():
    report(solution)

---

顺便说一下，这个问题与斑马问题和其他约束难题非常相似。