Column-complete latin square problem: everyone rotates through all seats, never sitting at the same seat as another more than once

Question

The problem that this applies to is difficult to explain (for me), which may account for a lot of why I cannot solve it. The example below should highlight the process for which I want to come up with a function or conditional expression:

1. X people sit at a table with N seats (X = N). This is iteration 0 or position 1.
2. Everyone gets up and changes seats. This is iteration 1 and creates position 2.
3. A period of time goes by and then, again, everyone changes seats,BUT they cannot replace seats with the same person as last time (e.g., if I went and sat where Tim was sitting for the first iteration, I CANNOT go sit where Tim was just sitting again; I can only follow Tim 1x) AND they cannot return to a seat in which they have already sat. This is iteration 2 and creates position 3.
4. This continues until all X people have sat in all N seats without ever sitting in the same seat twice or replacing the same person twice.

I have been able to solve for particular N/X's, but then fail to have a formula that generalizes to others. Here is an example of a 4-person solution: Here is the formula from Google Sheets:

1. Identified each person w/ number that corresponds to original position.
2. Added subsequent iteration number to that person's number (which corresponds to their original position)
3. If the sum of the person's ID and the subsequent iteration > # of people (4), subtract the sum by 4.

This formula solved the problem for 4 people:

• no one is in a position more than once
• no one replaced the same person more than once
• everyone sat in every position.

The formula (shown in the second image), however, failed to work for X = 5 and X = 6.

THE GOAL: Create a formula that generalizes across all/most/positive values of X, people.

Answer 1

Note: I do hope I have not wasted my time with a misunderstanding of "they cannot replace seats with the same person as last time" - I interpreted that as "If Susan took Tim's seat last time, she cannot do so this time (but could next time)". See the end of the post for some results in the strict case.

---

I am not sure of an efficient algorithm to validate $N$ and yield a solution if one exists, but we can implement a naive algorithm that tries to find them, and also inspect the cases for small $N$.

A valid seating plan is a list of seating arrangements that adheres to your rules (much like the list of rows in your example).

Since everyone must sit in each seat exactly once a valid seating plan contains $N$ seating arrangements that, when arranged vertically, form a Latin square.

The rules then stipulate that a subset of such seating plans are valid (due to the no-following the same person rule described in your (3.)).

I count the number of valid plans produced by permuting Latin squares (my code does not enumerate fully reduced forms, so I then take a factor of $(N-1)!$ out from the sums in the equations below to put them back in line with reduced form).

$N=2$ has $1$ reduced form and yields $1!(1\times 2)=2$ seating plans.
This may be obvious but here they are:

((1,2), (2,1))

((2,1), (1,2))

$N=3$ has $1$ reduced form and yields $2!(1\times 0)=0$ seating plans
(we would need to make two seating changes, our options are limited to a cycle by $1$ seat or by $2$ seats since no one may remain in the same seat, however we must use both cycles so rule(3.) is not broken, but that would mean the second change would move everyone back to their original seats, breaking rule (4.))

$N=4$ has $4$ reduced forms and yields $3!(1\times 24+3\times 16)=432$ seating plans
(note that $1$ of the reduced forms yields $3!\times 24$ and the other $3$ yield $3!\times 16$)

$N=5$ has $56$ reduced forms and yields $4!(50\times 0+6\times 40)=5760$ seating plans, one is:

((1,2,3,4,5), (2,3,4,5,1), (4,5,1,2,3), (3,4,5,1,2), (5,1,2,3,4))

which follows the same scheme as your example, but swaps two of the arrangements (the third and fourth ones).

For $N=6$ the code will probably take too long to count them all (since it would naively check $\binom{6!}{6}=189492294437160$ combinations to find the Latin squares to permute).
However, if we just permute the Latin square your method would try we find this one first:

((1,2,3,4,5,6), (2,3,4,5,6,1), (4,5,6,1,2,3), (3,4,5,6,1,2), (5,6,1,2,3,4), (6,1,2,3,4,5))

If we do the same for larger $N$ we quickly find results $N<13$ and in a short time for $N=13$:

((1,2,3,4,5,6,7), (2,3,4,5,6,7,1),(4,5,6,7,1,2,3), (3,4,5,6,7,1,2), (6,7,1,2,3,4,5), (5,6,7,1,2,3,4), (7,1,2,3,4,5,6))

((1,2,3,4,5,6,7,8), (2,3,4,5,6,7,8,1), (4,5,6,7,8,1,2,3), (3,4,5,6,7,8,1,2), (5,6,7,8,1,2,3,4), (6,7,8,1,2,3,4,5), (8,1,2,3,4,5,6,7), (7,8,1,2,3,4,5,6))

((1,2,3,4,5,6,7,8,9), (2,3,4,5,6,7,8,9,1), (4,5,6,7,8,9,1,2,3), (3,4,5,6,7,8,9,1,2), (5,6,7,8,9,1,2,3,4), (6,7,8,9,1,2,3,4,5), (8,9,1,2,3,4,5,6,7), (7,8,9,1,2,3,4,5,6), (9,1,2,3,4,5,6,7,8))

((1,2,3,4,5,6,7,8,9,10), (2,3,4,5,6,7,8,9,10,1), (4,5,6,7,8,9,10,1,2,3), (3,4,5,6,7,8,9,10,1,2), (5,6,7,8,9,10,1,2,3,4), (6,7,8,9,10,1,2,3,4,5), (8,9,10,1,2,3,4,5,6,7), (7,8,9,10,1,2,3,4,5,6), (9,10,1,2,3,4,5,6,7,8), (10,1,2,3,4,5,6,7,8,9))

((1,2,3,4,5,6,7,8,9,10,11), (2,3,4,5,6,7,8,9,10,11,1), (4,5,6,7,8,9,10,11,1,2,3), (3,4,5,6,7,8,9,10,11,1,2), (5,6,7,8,9,10,11,1,2,3,4), (6,7,8,9,10,11,1,2,3,4,5), (8,9,10,11,1,2,3,4,5,6,7), (7,8,9,10,11,1,2,3,4,5,6), (10,11,1,2,3,4,5,6,7,8,9), (9,10,11,1,2,3,4,5,6,7,8), (11,1,2,3,4,5,6,7,8,9,10))

((1,2,3,4,5,6,7,8,9,10,11,12), (2,3,4,5,6,7,8,9,10,11,12,1), (4,5,6,7,8,9,10,11,12,1,2,3), (3,4,5,6,7,8,9,10,11,12,1,2), (5,6,7,8,9,10,11,12,1,2,3,4), (6,7,8,9,10,11,12,1,2,3,4,5), (8,9,10,11,12,1,2,3,4,5,6,7), (7,8,9,10,11,12,1,2,3,4,5,6), (9,10,11,12,1,2,3,4,5,6,7,8), (10,11,12,1,2,3,4,5,6,7,8,9), (12,1,2,3,4,5,6,7,8,9,10,11), (11,12,1,2,3,4,5,6,7,8,9,10))

((1,2,3,4,5,6,7,8,9,10,11,12,13), (2,3,4,5,6,7,8,9,10,11,12,13,1), (4,5,6,7,8,9,10,11,12,13,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,1,2), (5,6,7,8,9,10,11,12,13,1,2,3,4), (6,7,8,9,10,11,12,13,1,2,3,4,5), (8,9,10,11,12,13,1,2,3,4,5,6,7), (7,8,9,10,11,12,13,1,2,3,4,5,6), (9,10,11,12,13,1,2,3,4,5,6,7,8), (10,11,12,13,1,2,3,4,5,6,7,8,9), (12,13,1,2,3,4,5,6,7,8,9,10,11), (11,12,13,1,2,3,4,5,6,7,8,9,10), (13,1,2,3,4,5,6,7,8,9,10,11,12))

but at $N=14$ it will need to check $87178291200$ permutations to confirm that there are none, I thought this would be too many to bother with.

I noted however that the number of permutations checked before the first was found looks suspiciously like $(N-3)!$:

                        N : 4, 5, 6,  7,   8,   9,   10,    11,     12,      13
                   (N-3)! : 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 
tested before first yield : 1, 2, 6, 26, 121, 722, 5046, 40346, 363001, 3629522

So a back of the envelope calculation was that it would take about 14 times as long as it did for $N=13$,

Sure enough after $15$ minutes and going through $39921846\approx 11!$ invalid permutations it returned this result for $N=14$:

((1,2,3,4,5,6,7,8,9,10,11,12,13,14), (2,3,4,5,6,7,8,9,10,11,12,13,14,1), (4,5,6,7,8,9,10,11,12,13,14,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,14,1,2), (5,6,7,8,9,10,11,12,13,14,1,2,3,4), (6,7,8,9,10,11,12,13,14,1,2,3,4,5), (8,9,10,11,12,13,14,1,2,3,4,5,6,7), (7,8,9,10,11,12,13,14,1,2,3,4,5,6), (9,10,11,12,13,14,1,2,3,4,5,6,7,8), (10,11,12,13,14,1,2,3,4,5,6,7,8,9), (12,13,14,1,2,3,4,5,6,7,8,9,10,11), (11,12,13,14,1,2,3,4,5,6,7,8,9,10), (13,14,1,2,3,4,5,6,7,8,9,10,11,12), (14,1,2,3,4,5,6,7,8,9,10,11,12,13))

---

Python code:

from itertools import combinations, permutations

def examples(fromN=2, toN=13, strict=False):
    for n in range(fromN, toN + 1):
        leftShifLatinSquare = makeLeftShiftLatinSquare(range(1, n + 1))
        print('N = {0}:'.format(n))
        try:
            if strict:
                plan, countPrevious = next(iterPlansStrict(leftShifLatinSquare))
            else:
                plan, countPrevious = next(iterPlans(leftShifLatinSquare))
        except StopIteration:
            print('reached the end of the possibilities. No valid seating plan found.')
        else:
            print('iterated through {0} invalid seating plans, and then found:'.format(countPrevious))
            print(plan)
        print()

def iterSeatingPlans(people, strict=False):
    if strict:
        for latinSquare in iterLatinSquares(people):
            for plan in iterPlansStrict(latinSquare):
                yield plan
    else:
        for latinSquare in iterLatinSquares(people):
            for plan in iterPlans(latinSquare):
                yield plan

def seatingPlanCounts(nPeople, strict=False):
    people = tuple(p for p in range(nPeople))
    counts = dict()
    if strict:
        for latinSquare in iterLatinSquares(people):
            count = 0
            for plan, priorCount in iterPlansStrict(latinSquare):
                count += 1
            if count in counts:
                counts[count] += 1
            else:
                counts[count] = 1
    else:
        for latinSquare in iterLatinSquares(people):
            count = 0
            for plan, priorCount in iterPlans(latinSquare):
                count += 1
            if count in counts:
                counts[count] += 1
            else:
                counts[count] = 1

    return counts

def makeLeftShiftLatinSquare(elements):
    n = len(tuple(elements))
    return tuple(tuple(elements[(row+i) % n] for i in range(n)) for row in range(n))

def iterPlans(latinSquare):
    elements = latinSquare[0]
    for countPrevious, plan in enumerate(permutations(latinSquare)):
        prevMoves = [plan[0][plan[1].index(e)] for e in elements]
        for j in range(2, len(plan)):
                curMoves = [plan[j-1][plan[j].index(e)] for e in elements]
                if any(cur == prev for cur, prev in zip(curMoves, prevMoves)):
                        break
                prevMoves = curMoves
        else:
            yield plan, countPrevious

def iterPlansStrict(latinSquare):
    elements = latinSquare[0]
    for countPrevious, plan in enumerate(permutations(latinSquare)):
        replacements = [set((plan[0][plan[1].index(e)],)) for e in elements]
        for j in range(2, len(plan)):
                curMoves = [plan[j-1][plan[j].index(e)] for e in elements]
                if any(cur in replacements for cur, replacements in zip(curMoves, replacements)):
                        break
                for i, e in enumerate(elements):
                    replacements[i].add(curMoves[i])
        else:
            yield plan, countPrevious

def iterLatinSquares(elements):
    n = len(elements)
    for possible in combinations([e for e in permutations(elements)], n):
        if any(len(set(sp.index(e) for sp in possible)) != n for e in elements):
            continue
        yield possible

---

Solving the stricter version

I added 'strict' options to allow for the stricter version here are some results:

$N=2$ and $N=3$ remain the same

$N=4$ has $3!(1\times 0+3\times 8)=24$ solutions

$N=5$ has $4!(56\times 0)=0$ solutions

$N=6$ has solutions, one is:

((1,2,3,4,5,6), (2,3,4,5,6,1), (6,1,2,3,4,5), (3,4,5,6,1,2), (5,6,1,2,3,4), (4,5,6,1,2,3))

$N=7$ has no solutions that are permutations of your method

$N=8$ has solutions, one is:

((1,2,3,4,5,6,7,8), (2,3,4,5,6,7,8,1), (4,5,6,7,8,1,2,3), (7,8,1,2,3,4,5,6), (3,4,5,6,7,8,1,2), (8,1,2,3,4,5,6,7), (6,7,8,1,2,3,4,5), (5,6,7,8,1,2,3,4))

$N=9$ has no solutions that are permutations of your method

$N=10$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10), (2,3,4,5,6,7,8,9,10,1), (4,5,6,7,8,9,10,1,2,3), (3,4,5,6,7,8,9,10,1,2), (8,9,10,1,2,3,4,5,6,7), (5,6,7,8,9,10,1,2,3,4), (9,10,1,2,3,4,5,6,7,8), (7,8,9,10,1,2,3,4,5,6), (10,1,2,3,4,5,6,7,8,9), (6,7,8,9,10,1,2,3,4,5))

$N=11$ has no solutions that are permutations of your method

$N=12$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10,11,12), (2,3,4,5,6,7,8,9,10,11,12,1), (4,5,6,7,8,9,10,11,12,1,2,3), (3,4,5,6,7,8,9,10,11,12,1,2), (8,9,10,11,12,1,2,3,4,5,6,7), (11,12,1,2,3,4,5,6,7,8,9,10), (9,10,11,12,1,2,3,4,5,6,7,8), (5,6,7,8,9,10,11,12,1,2,3,4), (12,1,2,3,4,5,6,7,8,9,10,11), (6,7,8,9,10,11,12,1,2,3,4,5), (10,11,12,1,2,3,4,5,6,7,8,9), (7,8,9,10,11,12,1,2,3,4,5,6))

$N=14$ has solutions, one is:

((1,2,3,4,5,6,7,8,9,10,11,12,13,14), (2,3,4,5,6,7,8,9,10,11,12,13,14,1), (4,5,6,7,8,9,10,11,12,13,14,1,2,3), (3,4,5,6,7,8,9,10,11,12,13,14,1,2), (6,7,8,9,10,11,12,13,14,1,2,3,4,5), (11,12,13,14,1,2,3,4,5,6,7,8,9,10), (9,10,11,12,13,14,1,2,3,4,5,6,7,8), (5,6,7,8,9,10,11,12,13,14,1,2,3,4), (12,13,14,1,2,3,4,5,6,7,8,9,10,11), (7,8,9,10,11,12,13,14,1,2,3,4,5,6), (13,14,1,2,3,4,5,6,7,8,9,10,11,12), (10,11,12,13,14,1,2,3,4,5,6,7,8,9), (14,1,2,3,4,5,6,7,8,9,10,11,12,13), (8,9,10,11,12,13,14,1,2,3,4,5,6,7))

Answer 2

The table you're looking for is called in mathematical terms a "column-complete latin square".

For even N, they are easy to construct: assuming the tables are in a circular arrangement, have everyone move right 1 table, then move left 2, then right 3, and so on.

For odd values of N it can get complicated. If N is 3,5 or 7, then there is no possible table that fulfills all constraints.

Jeffrey Higham gave in 1998 a way to make a table for every composite N in "Construction methods for row-complete latin squares", but it's not very simple.

As for the remaining prime numbers, no one knows how to construct a table for them or prove that the table does not exist.

Here's how a sample solution looks for the first odd composite number, 9:

123456789
291784635
376948152
418295376
547861923
635129847
789513264
864372591
952637418

Answer 3

Label the seats $0, \dots, n-1$ and the iterations and people likewise. Let addition be modulo $n$. Suppose that in each iteration $i$, whichever person $P_i$ is in seat $0$, person $P_i+s$ is in seat $s$. Then we need a sequence $P_0,...,P_{n-1}$ which is a permutation of $0, \dots, n-1$, with all the $n-1$ successive differences $P_{i}-P_{i-1}$ distinct, modulo $n$.
If $n$ is even, this is possible with $P_{2k} = k$ and $P_{2k-1} = n-k$.