请教9*9阵列排序的算法 ( 积分: 100 )

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #1

是这样的，导师给我一道题：在一个正方格阵列里9*9格，将9个
1、2、3、4、5、6、7、8、9共81个数填充到里面，必须确保任
何一个节点所在的行或列不能出现出现重复的数字；举例：
例子1：
1 2 3 4 5 6 7 8 9
2
3
4
5
6
7
8
9
上面这个就是正确的！注意，这81个数的填充位置是随机的，而
不是上面那样“好看”
我已经昨夜做了一部分，但是总在最后9个数无法插入，也就是
这9个数插入阵列就出现重复，调试了很久还是无法修正；因此
到这里请教大家，广益思路，谢谢了！
需要我的代码请说一声！

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #2

是这样的，导师给我一道题：在一个正方格阵列里9*9格，将9个
1、2、3、4、5、6、7、8、9共81个数填充到里面，必须确保任
何一个节点所在的行或列不能出现出现重复的数字；举例：
例子1：
1 2 3 4 5 6 7 8 9
2
3
4
5
6
7
8
9
上面这个就是正确的！注意，这81个数的填充位置是随机的，而
不是上面那样“好看”
我已经昨夜做了一部分，但是总在最后9个数无法插入，也就是
这9个数插入阵列就出现重复，调试了很久还是无法修正；因此
到这里请教大家，广益思路，谢谢了！
需要我的代码请说一声！

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #3

啊，没有人会吗？？？

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #4

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
晕，这样排不就可以了，代码自己写！

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #5

忘了说句，你再调换每行的顺序结果就出来了！[]

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #6

谢谢ak_2005！
但是存在一个问题是数有时不是这么顺序排的，例如
阵列中已经存在N（N<=9）个位置已经存在数字(数字属于81个数中选择)，这些数字的位置绝对符合题意，就是行和列都不会重复
如：
6 2 7
5
4
1
4
3
1
9
8
如果阵列中已经存在这些数，要求填充剩下的位置，且符合题意要求，那算法应该怎么改进呢？

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #7

问题的难点就是这里，需要考虑无规则的位置现象

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #8

说个思路，正确的算法应该是先把那九个数字打乱，以后排的时候它们的顺序的就不能变了，然后按上面的方法进行排列，就可以得出全部结果。
----------------------------------------------------------------------------
哈哈，其实上面的图就可以得出那N个数字的的位置了，结果也唯一了。
不太对，如果以某行为准就是了。

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #9

ak_2005，非常感谢，我明白你的意思了！
马上试试！！！
无论成功与否，分都是送你，谢谢！

 

C

chaos518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #10

其实有个笨办法的，就是你先把第一排先随即排列出来，
然后第二排开始的时候， 每次随即出来的那个数，都于同列的已经排列的数做比较，出现了的就不保存，再随即， 这样的话就能保证同列的没有重复的数字出现了，

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #11

To chaos518：能保证同列，但不一定能保证同行是唯一的啊

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-28

• #12

To ak_2005:你好，我照你的思路来写，发现还是无法保证完全正常，下面我个例子你看看
如已经存在的阵列(0表示待填位置)：
0 0 0 0 0 0 1 0 0
6 0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 7 0
0 0 7 0 0 0 0 0 8
0 0 0 0 0 0 0 9 0
0 0 0 0 0 2 0 0 0
0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 9
0 8 0 0 0 0 0 0 0
这样的阵列应该怎么填充呢？(注意，这样的阵列中，已经填充的数字是随机的，可能存在下一个阵列的数字是另外的位置)请指点！
在线等待...

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #13

就是先得出字串顺序啊：6 0 0 3 4 2 1 7 8(5、9随便定了)（我是从上到下排）
然后把九行生成出来，按现在图上的数字确定每行的位置

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #14

容我再想想，反正那行数字越多就优先考虑。

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #15

我就是先考虑各行的数字来排列新的一行，当新的一行建立后，再依次来排列这九行，发现存在两行或一行无法排了

 

T

tranke

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #16

To ak_2005：我就是能得出 6 8 7 3 4 2 1 9 5
但是，在开始插入各行时，出现两行无法符合题意，因为原阵列已经存在了随机数，且这些随机数不能改变位置

 

A

ak_2005

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #17

不能象你那么得，要以某行数字最多的考虑（0 0 0 0 4 0 0 7 0）
然后以行来得出数字串中数字的位置，不是以列，即6 0 0 3 4 2 1 7 8
两个0的位置5、9随机试一下，成功就不试了。

 

J

jeffrey_s

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-27

• #18

首先，不考虑固定的情况，很明显，第一行可以是任意的。
组合很明显 是 9！种情况。
然后考虑第 二、三行等的情况，实际上的 相对与第一行的偏移量，但值不相同。
同样 组合有 8！种情况。
结果很明显有 8！*9！种了。
写成程序是
procedure Run;
var
i, j: integer;
a, b: array [1..9] of byte;
c: array [1..9, 1..9] of byte;
begin
While GetN9(a)do
//取 9！种情况放在 a中 范围 1-9
While GetN8(b)do
//取 8！种情况放在 b中，b[1]固定=0，范围0-8
begin
for i := 1 to 9
for j := 1 to 9;
c[i, j] := Mod9Add(a + b[j]) //函数返回 1-9
if Not Check(IniData, c) then
Contiune;
//判断条件是否相同；
do
YourSelf(c);
end;
end;

 

J

jeffrey_s

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-28

• #19

其实答案并不只有 8！*9！种方法。
上面的算法只是其中的一部分而已。
比如说 n=4时第一行和第一列确定时，答案并不是1种，而是有4种。很显然，N=9时答案有更多。
如果想要算法的可能要使用递归了，不过想简单的可以使用 9个循环 回溯求出来。

 

L

liugaohui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-28

• #20

帮顶一下