One solution would be:
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
Actually, that's two solutions, since you could read
the rows as days and columns as rooms, or vice versa.
Each permutation of the numbers assigned to people, and each permutation of the rooms (columns), and each permutation of the days (rows) leads to another solution as well.
Here is Python code, based on Egor Skriptunoff's solution. The main idea is the same: Generate a list of all the pairs of people, and start placing them one at a time on the board. If there is no valid placement, then backtrack and try something else. In the code below a list of tasks records board states, so when a dead end is reached, the next candidate board state is popped off the tasks list. The trick is to enumerate all the possibilites in an organized, efficient way.
There are some minor differences:
- This code is iterative rather than recursive.
- The
solve function tries to generate all solutions instead of stopping after finding one.
- For simplicity, the initialization condition has been removed.
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)
By the way, this problem is very similar to the Zebra problem and other constraint puzzles. You might look there for more ideas on how to solve your problem.
