数独排列问题

题干:
一个 n 阶数独是指,对于数字 1-n,它们在每行每列都恰出现一次。对于数独中的任意两个同在一行的相邻数字,我们构造相应的有序数对 (i,j)。例如,若存在某一行:xxx i j xxx,此时可构成有序数对 (i,j)。我们的目标是寻找出一张合法的 n 阶数独,使得对于任意的有序数对 (i,j),其中

1\leq i , j \leq n, i \not = j

满足:在整张 n 阶数独中,(i,j) 均恰好出现一次。

输入: n
输出: 若不存在这样的数独排列,则输出"NaN";若存在符合要求的排列方式,则以矩阵形式输出任意一种符合要求的数独内容。

示例 1:
输入:1
输出:1

示例 2:
输入:2
输出:
1 2
2 1

示例 3:
输入:3
输出:NaN

示例 4:
输入:4
输出:
1 2 3 4
3 1 4 2
2 4 1 3
4 3 2 1

有无组合/编程大手子来做做? :thinking_face_clown_face:
这道题目是一位同学问我的,原题是:有哪些 n 是可以构造出如上数独的?
我只找到了 2 和 4,后面的没有毅力写了,求助一下万能的門友。

注:
其实原题的要求是:
对于数组中的有序数对,它不能存在出现多次。

就比如:
1 2 3
2 3 1
3 1 2
他就不行,理由是:
(1 2)、(2 3)、(3 1) 均出现了两次。


1 2 3 4
3 1 4 2
2 4 1 3
4 3 2 1
其中
(1 2)、 (2 3)、(3 4)、(3 1)、(1 4)、(4 2)、…都只出现了一次。

由于这是 n * n 的方阵,所以有 n * (n-1) 个有序数对。而

(i,j), \quad 1\leq i , j \leq n, i \not = j

也恰有 n * (n-1) 个不同组合,所以我把原问题转化为了 每种二元组恰出现一次

我感觉我会 n 是偶数的情况了,n 是奇数的还不太会

n 是偶数的情况,首先看作 0 到 n-1 的排列

第一行:0,n-1,1,n-2,2,n-3……n/2-1,n/2

前 n/2 行:每一行是在上一行的基础上对应位置 +1 mod n

后 n/2 行:把前 n/2 行全部 reverse 倒序反转过来依次放在后 n/2 行

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

证明不难,留作练习。。。感觉主要是想到这个题差不多相当于构造一个排列使得其 mod n 意义下的差分数组不能重复。。。然后就循环位移就可以。。。奇数感觉有点神秘,n=3 跑了一下应该是无解的

3 Likes

刚开始我构出来了上面那种“旋转型中心对称”的 n=4,然后我就猜测是不是 2^k 都可以 :thinking: 但是我接下来按照“旋转型”的构造方式,我搞不出 n=8 的情况。

结果昨晚在我发布问题不久,问我问题的同学也构造出了 n=6,不过他的构造比较乱,没有什么明显的规律。当时我们就在猜,是不是奇数不行偶数行 :kissing: 可是我们摸索了一会儿也没能搞出来 n=2k 情形的通解。。。

总之非常感谢 K 哥的解答 :kissing_heart: 我已转告给那位同学 :partying_face:

你画我猜问题

假设现在有 n 个人进行你画我猜,共进行 n-1 次传稿,现在希望找到一个传稿规划,满足:

  1. 每份稿子每个人只接手一次
  2. 每次传稿后人手一稿,也就是没有人闲着也没有人累死
  3. 每个人的 n-1 次传稿都传给了 n-1 个不同的下

问:该规划对哪些 n 存在?

(实际上这是原问题,是一位同学在编排你画我猜的传稿顺序的时候遇见的:rofl:

我查了下,好像 n 为奇数的情况只有 3 和 5 不行,其他奇数都可以。。。见这篇论文:A Hamiltonian decomposition of K2m∗, 2m ≥ 8 - ScienceDirect

虽然我还没有非常看懂

2 Likes

:hushed:我尝试去搜但是没搜出来:sob:阿里嘎多:smiling_face_with_three_hearts: