请教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个数插入阵列就出现重复，调试了很久还是无法修正；因此
到这里请教大家，广益思路，谢谢了！
需要我的代码请说一声！
2楼: 啊，没有人会吗？？？ 如进销存破解
3楼: 123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678
晕，这样排不就可以了，代码自己写！
4楼: 忘了说句，你再调换每行的顺序结果就出来了！[:D]
5楼: 谢谢ak_2005！
但是存在一个问题是数有时不是这么顺序排的，例如
阵列中已经存在N（N<=9）个位置已经存在数字(数字属于81个数中选择)，这些数字的位置绝对符合题意，就是行和列都不会重复
如：
6 2 7
5
4
1
4
3
1
9
8
如果阵列中已经存在这些数，要求填充剩下的位置，且符合题意要求，那算法应该怎么改进呢？
6楼: 问题的难点就是这里，需要考虑无规则的位置现象
进销存管理软件版7楼: 说个思路，正确的算法应该是先把那九个数字打乱，以后排的时候它们的顺序的就不能变了，然后按上面的方法进行排列，就可以得出全部结果。
----------------------------------------------------------------------------
哈哈，其实上面的图就可以得出那N个数字的的位置了，结果也唯一了。
不太对，如果以某行为准就是了。
8楼: ak_2005，非常感谢，我明白你的意思了！
马上试试！！！
无论成功与否，分都是送你，谢谢！
9楼: 其实有个笨办法的，就是你先把第一排先随即排列出来，
然后第二排开始的时候， 每次随即出来的那个数，都于同列的已经排列的数做比较，出现了的就不保存，再随即， 这样的话就能保证同列的没有重复的数字出现了，
10楼: To chaos518：能保证同列，但不一定能保证同行是唯一的啊
11楼: 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
这样的阵列应该怎么填充呢？(注意，这样的阵列中，已经填充的数字是随机的，可能存在下一个阵列的数字是另外的位置)请指点！
在线等待...
12楼: 就是先得出字串顺序啊：6 0 0 3 4 2 1 7 8(5、9随便定了)（我是从上到下排）
然后把九行生成出来，按现在图上的数字确定每行的位置 如金蝶erp软件价格
13楼: 容我再想想，反正那行数字越多就优先考虑。
进销存管理软件版14楼: 我就是先考虑各行的数字来排列新的一行，当新的一行建立后，再依次来排列这九行，发现存在两行或一行无法排了
15楼: To ak_2005：我就是能得出 6 8 7 3 4 2 1 9 5
但是，在开始插入各行时，出现两行无法符合题意，因为原阵列已经存在了随机数，且这些随机数不能改变位置
16楼: 不能象你那么得，要以某行数字最多的考虑（0 0 0 0 4 0 0 7 0）
然后以行来得出数字串中数字的位置，不是以列，即6 0 0 3 4 2 1 7 8
两个0的位置5、9随机试一下，成功就不试了。
17楼: 首先，不考虑固定的情况，很明显，第一行可以是任意的。
组合很明显 是 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[i] + b[j]) //函数返回 1-9
if Not Check(IniData, c) then Contiune; //判断条件是否相同；
DoYourSelf(c);
end;
end;
18楼: 其实答案并不只有 8！*9！种方法。
上面的算法只是其中的一部分而已。
比如说 n=4时第一行和第一列确定时，答案并不是1种，而是有4种。很显然，N=9时答案有更多。
如果想要算法的可能要使用递归了，不过想简单的可以使用 9个循环 回溯求出来。
19楼: 帮顶一下
20楼: 你可以定义A1[j]....A9[j]来判断同一行中有没出现重复的数
定义B1[i].....B9[i]来判断同一列中有没出现重复的数
也就是说，当你给C[i][j]附值的时候，你就只要判断Ai[i]和Bj[j]
比如给C[3][4]附值的时候，只要判断A3[i]和B4[j]中有没出现重复的数就可以了
进销存管理软件版21楼: 感谢各位，由于家里不能上网！
我现在来看看各位建议的算法。
chaos518，你说的算法是不可行的，因为最终会存在至少9各数无法插入，不信你可以试试。
22楼: 那就只能这样了， 先随即出第一排A[1]，A[2]，。。。A[9]，
然后第二排的时候就是A[2]。。。A[9]，A[1]
第三排的时候就是A[3]A[4]。。。A[9]A[1]A[2]
到最后一排的时候就是A[9]。。。。。A[8]
不过这样虽然能得到你要的结果，但肯定不是全部，实在想不出什么好办法了。
不过这个也能蒙混过关的吧，嘿嘿 如免费手机进销存软件
23楼: 这个跟ak_2005最开始说的不是一样吗！
问题是没有这么顺序，要考虑到有时已经存在的各个位置的数字，再来填充，你再仔细看看前面的解说吧
24楼: 顶chaos518,在chaos518的基础上再把每列的顺序随机，就是所有的结果了,我是这么想的，赫赫[:D]
25楼: To divelove2003，你试过没有？麻烦你试试后再来发表高见好吗？
跟你说，一定会出现存在几个数无法填入的！因为填入了就变成重复了！！！
26楼: 我搞了一下午，总算找到此例
6 2 7
5
4
1
4
3
1
9
8
的算法解，但是就这一个例子不能保证算法正确性，你再给出你无法解决的几个例子吧
27楼: 谢谢cactus123456，本题的意思是阵列中可能存在某些位置存在一些数，然后我们再来填充其它的数并且要符合题意，我上面给出的是一个可能存在的例子，并不是具体的问题，知道我意思吗？我到现在也还没有找到具体的解决方法，郁闷啊
进销存管理软件版28楼: unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Memo2: TMemo;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
i,j,k:integer;
adj,adv:integer;
ss:string;
blline,blfind:boolean;
matrix: array [1..9,1..9] of integer;
mcopy:array [1..9] of integer;
//------------------------------------
//列检测
function checkrownum(row:integer):boolean;
var
i:integer;
count:array [1..9] of integer;
begin
for i:=1 to 9 do count[i]:=0;
for i:=1 to 9 do
begin
if (matrix[i,row]>0) and (matrix[i,row]<10) then
inc(count[matrix[i,row]]);
end;
result:=true;
for i:=1 to 9 do
begin
if count[i]>1 then
begin
result:=false;
break;
end;
end;
end;
//------------------------------------
//行检测
function checkcownum(cow:integer):boolean;
var
i:integer;
count:array [1..9] of integer;
begin
for i:=1 to 9 do count[i]:=0;
for i:=1 to 9 do
begin
if (matrix[cow,i]>0) and (matrix[cow,i]<10) then
inc(count[matrix[cow,i]]);
end;
result:=true;
for i:=1 to 9 do
begin
if count[i]>1 then
begin
result:=false;
break;
end;
end;
end;
//------------------------------------
begin
adv:=0;
adj:=0;
while true do
begin
//初始化
for i:=1 to 9 do
for j:=1 to 9 do
begin
matrix[i,j]:=0;
end;
//初始值
// 1 2 3 4 5 6 7 8 9
//1 6 2 7
//2 5
//3 4
//4 1
//5 4
//6 3
//7 1
//8 9
//9 8
//赋初值
matrix[1,1]:=6;
matrix[1,5]:=2;
matrix[1,9]:=7;
matrix[2,3]:=5;
matrix[3,2]:=4;
matrix[4,7]:=1;
matrix[5,1]:=4;
matrix[6,5]:=3;
matrix[7,1]:=1;
matrix[8,9]:=9;
matrix[9,1]:=8;
//检测初值的正确性
for i:=1 to 9 do
begin
if not checkrownum(i) then showmessage(＇＇初始化error＇＇);
if not checkcownum(i) then showmessage(＇＇初始化error＇＇);
end;
//显示初值
memo1.Lines.Clear;
for i:=1 to 9 do
begin
ss:=＇＇＇＇;
for j:=1 to 9 do
begin
ss:=ss+＇＇ ＇＇+inttostr(matrix[i,j]);
end;
memo1.Lines.Add(ss);
end;
//运算
//checkrownum(j) and checkcownum(i)
//快速填充
for i:=1 to 9 do
begin
//复制行副本
for j:=1 to 9 do mcopy[j]:=matrix[i,j];
adj:=adv;
while true do
begin
//保证此行正确
blline:=true;
for j:=1 to 9 do
if matrix[i,j]=0 then
begin
blfind:=false;
for k:=0 to 8 do
begin
matrix[i,j]:=((k+adj) mod 9)+1;
if checkrownum(j) and checkcownum(i) then
begin
blfind:=true;
break;
end;
end;
if not blfind then
begin
blline:=false;
break;
end;
end;
if blline then
break
else
begin
inc(adj);
for j:=1 to 9 do matrix[i,j]:=mcopy[j];
if adj>18 then break;
end;
end; //end while
end;
//验证结果
adj:=0;
for i:=1 to 9 do
for j:=1 to 9 do
begin
if matrix[i,j]=0 then
begin
inc(adj);
break;
end;
end;
//结果判断
if adj>0 then
begin
inc(adv);
if adv>9 then break;
end
else
break;
end;
//显示结果
memo2.Lines.Clear;
//显示adv
memo2.Lines.Add(＇＇========adv=＇＇+inttostr(adv)+＇＇===========＇＇);
if adj=0 then
begin
for i:=1 to 9 do
begin
ss:=＇＇＇＇;
for j:=1 to 9 do
begin
ss:=ss+＇＇ ＇＇+inttostr(matrix[i,j]);
end;
memo2.Lines.Add(ss);
end;
end
else
begin
memo2.Lines.Add(＇＇无解＇＇);
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
i,j,k:integer;
adj,adv:integer;
ss:string;
blline,blfind:boolean;
matrix: array [1..9,1..9] of integer;
mcopy:array [1..9] of integer;
//------------------------------------
//列检测
function checkrownum(row:integer):boolean;
var
i:integer;
count:array [1..9] of integer;
begin
for i:=1 to 9 do count[i]:=0;
for i:=1 to 9 do
begin
if (matrix[i,row]>0) and (matrix[i,row]<10) then
inc(count[matrix[i,row]]);
end;
result:=true;
for i:=1 to 9 do
begin
if count[i]>1 then
begin
result:=false;
break;
end;
end;
end;
//------------------------------------
//行检测
function checkcownum(cow:integer):boolean;
var
i:integer;
count:array [1..9] of integer;
begin
for i:=1 to 9 do count[i]:=0;
for i:=1 to 9 do
begin
if (matrix[cow,i]>0) and (matrix[cow,i]<10) then
inc(count[matrix[cow,i]]);
end;
result:=true;
for i:=1 to 9 do
begin
if count[i]>1 then
begin
result:=false;
break;
end;
end;
end;
//------------------------------------
begin
adv:=0;
adj:=0;
while true do
begin
//初始化
for i:=1 to 9 do
for j:=1 to 9 do
begin
matrix[i,j]:=0;
end;
//初始值
// 1 2 3 4 5 6 7 8 9
//1 6 2 7
//2 5
//3 4
//4 1
//5 4
//6 3
//7 1
//8 9
//9 8
//赋初值
matrix[1,1]:=6;
matrix[1,5]:=2;
matrix[1,9]:=7;
matrix[2,3]:=5;
matrix[3,2]:=4;
matrix[4,7]:=1;
matrix[5,1]:=4;
matrix[6,5]:=3;
matrix[7,1]:=1;
matrix[8,9]:=9;
matrix[9,1]:=8;
//检测初值的正确性
for i:=1 to 9 do
begin
if not checkrownum(i) then showmessage(＇＇初始化error＇＇);
if not checkcownum(i) then showmessage(＇＇初始化error＇＇);
end;
//显示初值
memo1.Lines.Clear;
for i:=1 to 9 do
begin
ss:=＇＇＇＇;
for j:=1 to 9 do
begin
ss:=ss+＇＇ ＇＇+inttostr(matrix[i,j]);
end;
memo1.Lines.Add(ss);
end;
//运算
//checkrownum(j) and checkcownum(i)
//快速填充
for i:=1 to 9 do
begin
//复制行副本
for j:=1 to 9 do mcopy[j]:=matrix[i,j];
adj:=adv;
while true do
begin
//保证此行正确
blline:=true;
for j:=1 to 9 do
if matrix[i,j]=0 then
begin
blfind:=false;
for k:=8 downto 0 do
begin
matrix[i,j]:=((k+adj) mod 9)+1;
if checkrownum(j) and checkcownum(i) then
begin
blfind:=true;
break;
end;
end;
if not blfind then
begin
blline:=false;
break;
end;
end;
if blline then
break
else
begin
inc(adj);
for j:=1 to 9 do matrix[i,j]:=mcopy[j];
if adj>18 then break;
end;
end; //end while
end;
//验证结果
adj:=0;
for i:=1 to 9 do
for j:=1 to 9 do
begin
if matrix[i,j]=0 then
begin
inc(adj);
break;
end;
end;
//结果判断
if adj>0 then
begin
inc(adv);
if adv>9 then break;
end
else
break;
end;
//显示结果
memo2.Lines.Clear;
//显示adv
memo2.Lines.Add(＇＇========adv=＇＇+inttostr(adv)+＇＇===========＇＇);
if adj=0 then
begin
for i:=1 to 9 do
begin
ss:=＇＇＇＇;
for j:=1 to 9 do
begin
ss:=ss+＇＇ ＇＇+inttostr(matrix[i,j]);
end;
memo2.Lines.Add(ss);
end;
end
else
begin
memo2.Lines.Add(＇＇无解＇＇);
end;
end;
end.
29楼: 好的，我试试！
不过没想到你是用memo，我用的是stringGrid这个倒比较直观
30楼: 当然也存在正解 for k:=0 to 8 do 和反解
for k:=8 downto 0 do 都无解的情况，但是你还可以通过中间求解比如5+-1，等方法求出解，此思路，供参考
31楼: 谢谢，测试中，有问题我会提出来
32楼: >>可以通过中间求解比如5+-1，等方法求出解，此思路，供参考？
请问cactus123456，“5+-1”是什么意思呢？
的确，存在一些阵列无法自动排列出来，看来是需要再改进算法！
33楼: 求解过程就是排列组合的过程，最简单的构造就是
1，2，3，4，5，6，7，8，9 正序
9，8，7，6，5，4，3，2，1 倒序
我的意思就是你可以在构造一个中间开始的顺序，规则就是+-1
5，6，4，7，3，8，2，9，1 因为这种训序有规律，可以算出来。
if (k mod 2)=0 then matrix[i,j]:=(4-(k div 2)+adj) mod 9+1
else matrix[i,j]:=(4+(k div 2)+1+adj) mod 9+1;
5，4，6，3，7，2，8，1，9 等等
阵列的全解应该是个天文数字，因为排列组合的方法太多了9！
34楼: 明白了，我试试吧，明天我再上来
进销存管理软件版35楼: 问题的算法还需要完善，不过，我打算结帖了，谢谢大家
同时，请cactus123456到这里另外领分，很感谢你的指点
http://www.delphibbs.com/delphibbs/dispq.asp？lid=3223981
联系我们
