b*******d
发帖数: 750 | 1 今天刚遇到的。
写一个函数（getMatrix），给一个数N，生成一个随机的valid的NxN矩阵。valid是指
，矩阵上的每个cell也是一个数，但必须是从1到N的一个数。行列皆不能有重复的数。
每次call这个函数，返回的matrix都是独立随机。
完成这个函数后，follow up：反过来，如果得到这样一个matrix后，中间挖掉几个
cell，让其成空，剩下的是个sudoko puzzle，让人来猜。你能否定义一个difficulty
，来衡量你生成的puzzle有多难。难度需要与人们平均做出来的时间正相关。 | f*****e
发帖数: 2992 | 2 (N-1) regular bipartite matching，node i连接另一半里除i之外的nodes，随机
产生一个matching(i,j);然后去掉(j,i)形成(N-2)regular bipartite matching，再随
机产生一个matching，以此类推，这样可以产生随机矩阵。
然后挖掉方块后，剩余行和列元素的重合程度，(行-方块)交(列-方块)和方块大小决定
difficulty。
difficulty
【在 b*******d 的大作中提到】
: 今天刚遇到的。
: 写一个函数（getMatrix），给一个数N，生成一个随机的valid的NxN矩阵。valid是指
: ，矩阵上的每个cell也是一个数，但必须是从1到N的一个数。行列皆不能有重复的数。
: 每次call这个函数，返回的matrix都是独立随机。
: 完成这个函数后，follow up：反过来，如果得到这样一个matrix后，中间挖掉几个
: cell，让其成空，剩下的是个sudoko puzzle，让人来猜。你能否定义一个difficulty
: ，来衡量你生成的puzzle有多难。难度需要与人们平均做出来的时间正相关。
| b*******d
发帖数: 750 | 3
what if when you get (N-k) matching done, for the rest of the problem there
is actually no solution given your previous (N-k) matching? it is very
possible, how do you continue trying?
【在 f*****e 的大作中提到】
: (N-1) regular bipartite matching，node i连接另一半里除i之外的nodes，随机
: 产生一个matching(i,j);然后去掉(j,i)形成(N-2)regular bipartite matching，再随
: 机产生一个matching，以此类推，这样可以产生随机矩阵。
: 然后挖掉方块后，剩余行和列元素的重合程度，(行-方块)交(列-方块)和方块大小决定
: difficulty。
:
: difficulty
| p*****2
发帖数: 21240 | | a*******y
发帖数: 1040 | 5 你这个一共才1-N的数，矩阵有N^2个数， 为什么不重复？ | p*****2
发帖数: 21240 | 6
行列不重复。
【在 a*******y 的大作中提到】
: 你这个一共才1-N的数，矩阵有N^2个数， 为什么不重复？
| f*****e
发帖数: 2992 | 7 表述有点bug，sorry。
只要是k-regular的就会有perfect matching，一开始是(n-1)regular的，记为图1，后
来是(n-2),(n-3),...,1 regular的。只要保持图是k-regular的就有perfect matching
。
以4个点为例：
1 (2,3,4)
2 (1,3,4)
3 (1,2,4)
4 (1,2,3)
找到一个matching (i,j)=(1,2) (2,1) (3,4) (4,3)，然后在图1中删掉(j,i)得到
（j不能再和前面path里的点相连，也不能和自身相连，所以要删掉前面path里的点）
1 (3,4)
2 (3,4)
3 (1,2)
4 (1,2)
再找到一个matching (i,j)=(1,3) (2,4) (3,1) (4,2)，然后在图1中删掉前面path中
出现的点得到
matching:
1 2
2 1
3 4
4 3
然后把三个matching串在一起得到：
1-2-4-3
2-1-3-4
3-4-2-1
4-3-1-2
每行都是一个path。每一列到下一列的matching都是随机产生的。
也可以不用随机生成matching，直接在源头生成1-N的random shuffle就行了。
当然可能有的configuration的概率就为0。 | f*****e
发帖数: 2992 | 8 可能我想的太复杂了，还有一个简单办法，先生成一个矩阵
1 2 ...N-1 N
2 3 ... N 1
3 4 ... 1 2
. .
. .
N 1 ... N-2 N-1
然后对行和列做random permutation。
matching
【在 f*****e 的大作中提到】
: 表述有点bug，sorry。
: 只要是k-regular的就会有perfect matching，一开始是(n-1)regular的，记为图1，后
: 来是(n-2),(n-3),...,1 regular的。只要保持图是k-regular的就有perfect matching
: 。
: 以4个点为例：
: 1 (2,3,4)
: 2 (1,3,4)
: 3 (1,2,4)
: 4 (1,2,3)
: 找到一个matching (i,j)=(1,2) (2,1) (3,4) (4,3)，然后在图1中删掉(j,i)得到
| m*****k
发帖数: 731 | 9 NB!
【在 f*****e 的大作中提到】
: 可能我想的太复杂了，还有一个简单办法，先生成一个矩阵
: 1 2 ...N-1 N
: 2 3 ... N 1
: 3 4 ... 1 2
: . .
: . .
: N 1 ... N-2 N-1
: 然后对行和列做random permutation。
:
: matching
| b*******d
发帖数: 750 | 10
~~~~~~
虽然不知道能否cover所有的解，还是觉得很不错。赞一个。
【在 f*****e 的大作中提到】
: 可能我想的太复杂了，还有一个简单办法，先生成一个矩阵
: 1 2 ...N-1 N
: 2 3 ... N 1
: 3 4 ... 1 2
: . .
: . .
: N 1 ... N-2 N-1
: 然后对行和列做random permutation。
:
: matching
|
|
