{"topic":{"id":13605,"title":"数独排列问题","slug":"topic","categoryId":54,"createdAt":"2024-09-30 12:15:36.036716","bumpedAt":"2024-10-02 00:46:19.800949","views":179,"postsCount":7,"highestPostNumber":7,"likeCount":6,"closed":false,"pinned":false,"excerpt":"题干：一个 n 阶数独是指，对于数字 1-n，它们在每行每列都恰出现一次。对于数独中的任意两个同在一行的相邻数字，我们构造相应的有序数对 (i,j)。例如，若存在某一行：xxx i j xxx，此时可构成有序数对 (i,j)。我们的目标是寻找出一张合法的 n 阶数独，使得对于任意的有序数对 (i,j)，其中 1≤i,j≤n,i≠j 1\\leq i , j \\leq n, i \\not = j 1≤i,j≤n,i=j 满足：在整张…","deletedAt":null,"isAnonymous":false,"category":{"id":54,"name":"学术专区","slug":"academic","color":"9EB83B"},"author":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg"},"tags":[]},"posts":[{"id":40999,"postNumber":1,"raw":"**题干：**\n一个 n 阶数独是指，对于数字 1-n，它们在每行每列都恰出现一次。对于数独中的任意两个同在一行的相邻数字，我们构造相应的有序数对 (i,j)。例如，若存在某一行：xxx i j xxx，此时可构成有序数对 (i,j)。我们的目标是寻找出一张合法的 n 阶数独，使得对于任意的有序数对 (i,j)，其中 \n$$\n1\\leq i , j \\leq n, i \\not = j\n$$ \n满足：在整张 n 阶数独中，(i,j) 均恰好出现一次。\n\n**输入：** n\n**输出：** 若不存在这样的数独排列，则输出\"NaN\"；若存在符合要求的排列方式，则以矩阵形式输出任意一种符合要求的数独内容。\n\n示例 1：\n输入：1\n输出：1\n\n示例 2：\n输入：2\n输出：\n1 2\n2 1\n\n示例 3：\n输入：3\n输出：NaN\n\n示例 4：\n输入：4\n输出：\n1 2 3 4\n3 1 4 2\n2 4 1 3\n4 3 2 1\n\n\n有无组合/编程大手子来做做？ :thinking_face_clown_face:\n这道题目是一位同学问我的，原题是：有哪些 n 是可以构造出如上数独的？\n我只找到了 2 和 4，后面的没有毅力写了，求助一下万能的門友。","cooked":"

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

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

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

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

示例 1：
\n输入：1
\n输出：1

示例 2：
\n输入：2
\n输出：
\n1 2
\n2 1

示例 3：
\n输入：3
\n输出：NaN

示例 4：
\n输入：4
\n输出：
\n1 2 3 4
\n3 1 4 2
\n2 4 1 3
\n4 3 2 1

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

\n","createdAt":"2024-09-30 12:15:36.263223","updatedAt":"2024-09-30 12:19:43.739334","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":344,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

年月擦身过，暂且问，会更好吗？

\n"}},{"id":41001,"postNumber":2,"raw":"注：\n其实原题的要求是：\n对于数组中的有序数对，它不能存在出现多次。\n\n就比如：\n1 2 3\n2 3 1\n3 1 2\n他就不行，理由是：\n(1 2)、(2 3)、(3 1) 均出现了两次。\n\n而\n1 2 3 4\n3 1 4 2\n2 4 1 3\n4 3 2 1\n其中 \n(1 2)、 (2 3)、(3 4)、(3 1)、(1 4)、(4 2)、....都只出现了一次。\n\n由于这是 n * n 的方阵，所以有 n * (n-1) 个有序数对。而\n$$\n(i,j), \\quad 1\\leq i , j \\leq n, i \\not = j\n$$ \n也恰有 n * (n-1) 个不同组合，所以我把原问题转化为了 **每种二元组恰出现一次**。","cooked":"

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

就比如：
\n1 2 3
\n2 3 1
\n3 1 2
\n他就不行，理由是：
\n(1 2)、(2 3)、(3 1) 均出现了两次。

而
\n1 2 3 4
\n3 1 4 2
\n2 4 1 3
\n4 3 2 1
\n其中
\n(1 2)、 (2 3)、(3 4)、(3 1)、(1 4)、(4 2)、....都只出现了一次。

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

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

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

\n","createdAt":"2024-09-30 12:52:08.571883","updatedAt":"2024-09-30 12:56:05.683258","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":173,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

年月擦身过，暂且问，会更好吗？

\n"}},{"id":41025,"postNumber":3,"raw":"我感觉我会 n 是偶数的情况了，n 是奇数的还不太会\n\nn 是偶数的情况，首先看作 0 到 n-1 的排列\n\n第一行：0,n-1,1,n-2,2,n-3……n/2-1,n/2\n\n前 n/2 行：每一行是在上一行的基础上对应位置 +1 mod n\n\n后 n/2 行：把前 n/2 行全部 reverse 倒序反转过来依次放在后 n/2 行\n\n例：n=6:\n051423\n102534\n213045\n540312\n435201\n324150\n\n\n证明不难，留作练习。。。感觉主要是想到这个题差不多相当于构造一个排列使得其 mod n 意义下的差分数组不能重复。。。然后就循环位移就可以。。。奇数感觉有点神秘，n=3 跑了一下应该是无解的","cooked":"

我感觉我会 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:
\n051423
\n102534
\n213045
\n540312
\n435201
\n324150

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

\n","createdAt":"2024-09-30 19:10:06.414756","updatedAt":"2024-09-30 19:10:06.414756","replyToPostNumber":null,"replyCount":1,"likeCount":3,"wordCount":179,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"hugging_face_exploding_head","count":1,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"}],"hasReacted":false},{"reaction":"❤️","count":3,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"},{"id":4668,"username":"IO","name":null},{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":426,"username":"Komeiji_Koishi","name":"Komeiji_Koishi","avatarUrl":"/uploads/image/5c/54/5c54227268cd2f275501ca5efdf88f7b1083908db846496c2c46eeb38cf65caa.avif","admin":true,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":41030,"postNumber":4,"raw":"刚开始我构出来了上面那种“旋转型中心对称”的 n=4，然后我就猜测是不是 2^k 都可以 🤔 但是我接下来按照“旋转型”的构造方式，我搞不出 n=8 的情况。\n\n结果昨晚在我发布问题不久，问我问题的同学也构造出了 n=6，不过他的构造比较乱，没有什么明显的规律。当时我们就在猜，是不是奇数不行偶数行 😗 可是我们摸索了一会儿也没能搞出来 n=2k 情形的通解。。。\n\n总之非常感谢 K 哥的解答 😘 我已转告给那位同学 🥳","cooked":"

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

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

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

\n","createdAt":"2024-10-01 02:47:56.450576","updatedAt":"2024-10-01 03:11:27.89994","replyToPostNumber":3,"replyCount":1,"likeCount":0,"wordCount":175,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":3,"publicVersion":3,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

年月擦身过，暂且问，会更好吗？

\n"}},{"id":41032,"postNumber":5,"raw":"# 你画我猜问题\n假设现在有 n 个人进行你画我猜，共进行 n-1 次传稿，现在希望找到一个传稿规划，满足：\n\n1. 每份稿子每个人只接手一次\n2. 每次传稿后人手一稿，也就是没有人闲着也没有人累死\n3. 每个人的 n-1 次传稿都传给了 n-1 个不同的下\n\n问：该规划对哪些 n 存在？\n\n（实际上这是原问题，是一位同学在编排你画我猜的传稿顺序的时候遇见的🤣）","cooked":"

你画我猜问题

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

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

问：该规划对哪些 n 存在？

（实际上这是原问题，是一位同学在编排你画我猜的传稿顺序的时候遇见的🤣）

\n","createdAt":"2024-10-01 03:02:43.323053","updatedAt":"2024-10-01 03:13:56.661157","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":149,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

年月擦身过，暂且问，会更好吗？

\n"}},{"id":41081,"postNumber":6,"raw":"我查了下，好像 n 为奇数的情况只有 3 和 5 不行，其他奇数都可以。。。见这篇论文：https://www.sciencedirect.com/science/article/pii/0095895680900441\n\n虽然我还没有非常看懂","cooked":"

我查了下，好像 n 为奇数的情况只有 3 和 5 不行，其他奇数都可以。。。见这篇论文：https://www.sciencedirect.com/science/article/pii/0095895680900441

虽然我还没有非常看懂

\n","createdAt":"2024-10-01 18:35:31.84768","updatedAt":"2024-10-01 18:35:31.84768","replyToPostNumber":4,"replyCount":1,"likeCount":3,"wordCount":46,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"hugging_face_exploding_head","count":1,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"}],"hasReacted":false},{"reaction":"❤️","count":3,"users":[{"id":30,"username":"一只玉米人","name":"玉米🌽"},{"id":5905,"username":"PipaQinse233","name":"PipaQinse233"},{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":426,"username":"Komeiji_Koishi","name":"Komeiji_Koishi","avatarUrl":"/uploads/image/5c/54/5c54227268cd2f275501ca5efdf88f7b1083908db846496c2c46eeb38cf65caa.avif","admin":true,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":41083,"postNumber":7,"raw":"😯我尝试去搜但是没搜出来😭阿里嘎多🥰","cooked":"

😯我尝试去搜但是没搜出来😭阿里嘎多🥰

\n","createdAt":"2024-10-02 00:46:19.800949","updatedAt":"2024-10-02 00:46:19.800949","replyToPostNumber":6,"replyCount":0,"likeCount":0,"wordCount":18,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":30,"username":"一只玉米人","name":"玉米🌽","avatarUrl":"/uploads/blob/14/96/14961aeaa46ccbb75a61eec0c27b26e74fb5d1c00ccdcbbe898ca9ea37087dd6.svg","admin":false,"moderator":true,"signatureRaw":"*年月擦身过，暂且问，会更好吗？*","signatureCooked":"

年月擦身过，暂且问，会更好吗？

\n"}}],"hasMore":false,"lastReadPostNumber":6,"hasUrlPostNumber":true}