数独の配置問題

[一只玉米人 (玉米🌽)]

Problem Statement:
An n‑order Sudoku means that for the numbers 1‑n, each appears exactly once in every row and column. For any two adjacent numbers that are in the same row of the Sudoku, we construct the corresponding ordered pair (i, j). For example, if a row contains … i j …, then the ordered pair (i, j) can be formed. Our goal is to find a valid n‑order Sudoku such that for every ordered pair (i, j) with

1\leq i , j \leq n,\; i \neq j

it holds that across the entire n‑order Sudoku, (i, j) appears exactly once.

Input: n

Output: If no such Sudoku arrangement exists, output "NaN"; if a valid arrangement exists, output any one such Sudoku in matrix form.

Example 1:
Input: 1
Output: 1

Example 2:
Input: 2
Output:

[一只玉米人 (玉米🌽)]

Note:
Actually the original problem’s requirement is:
For ordered pairs in the array, they must not appear multiple times.

For example:
1 2 3
2 3 1
3 1 2
This is not allowed, because:
(1 2), (2 3), (3 1) each appear twice.

Whereas
1 2 3 4
3 1 4 2
2 4 1 3
4 3 2 1
In this case
(1 2), (2 3), (3 4), (3 1), (1 4), (4 2), … each appear only once.

Since this is an n × n matrix, there are n × (n‑1) ordered pairs. And

(i,j), \quad 1\leq i , j \leq n, i \neq j

also has exactly n × (n‑1) distinct combinations, so I transformed the original problem into each ordered pair appears exactly once.

[Komeiji_Koishi]

I think I understand the case where n is even, but I’m still not quite sure about the case where n is odd.

For the case where n is even, first consider a permutation of 0 to n‑1.

First row: 0, n‑1, 1, n‑2, 2, n‑3 … n/2‑1, n/2

The first n/2 rows: each row is obtained from the previous row by adding 1 modulo n to each position.

The last n/2 rows: take the first n/2 rows, reverse their order, and place them sequentially as the last n/2 rows.

Example: n = 6:
051423
102534
213045
540312
435201
324150

The proof is not difficult and is left as an exercise… It feels that the main idea is to construct a permutation whose difference array modulo n has no repetitions… then a cyclic shift works… The odd case feels a bit mysterious; for n = 3 I tried and it seems to have no solution.

[一只玉米人 (玉米🌽)]

At first I constructed the “rotational central‑symmetric” case with n = 4, and then I guessed whether all 2^k are possible . But when I tried to follow the “rotational” construction method, I couldn’t get the case for n = 8.

It turned out that last night, shortly after I posted the question, a classmate who asked me the question also constructed n = 6, although his construction was rather messy and had no obvious pattern. At that time we were wondering whether odd numbers don’t work and even numbers do , but after some trial we still couldn’t find a general solution for the n = 2k case…

Anyway, many thanks to K‑brother for the answer . I’ve passed it on to that classmate .

[一只玉米人 (玉米🌽)]

Pictionary Problem

Assume there are n people playing Pictionary, with n‑1 rounds of passing the drawings. We want to find a passing schedule that satisfies:

1. Each drawing is handled by each person only once
2. After each pass, everyone holds exactly one drawing, i.e., no one is idle and no one is overburdened
3. Each person’s n‑1 passes are to n‑1 different recipients

Question: For which values of n does such a schedule exist?

(Actually this is the original problem; a classmate encountered it while arranging the Pictionary passing order )

[Komeiji_Koishi]

I checked, and it seems that for odd n only 3 and 5 don’t work; all other odd numbers are fine… See this paper: https://www.sciencedirect.com/science/article/pii/0095895680900441

Although I still haven’t fully understood it.

[一只玉米人 (玉米🌽)]

I tried to search but couldn’t find it thank you