unit1.~pas

九宫重排

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Mask, Buttons, Menus,math, Spin, ExtCtrls,unit3;

type
tori=array[1..9] of shortint;
t3x3=array[1..3,1..3] of shortint;


type
  P1=^Tchild;
  Tchild=record
    sn:integer;
  Pbrother:P1;
end;

type
  Tnode=record
   parent:integer;
   status:T3x3;
   children:array[1..4] of integer;
   s:integer;
   layer:integer;
   //pchild:P1;
end;
 type
 Topen_ex=array[1..10000] of Tnode;
 Tclose_ex=array[1..30000] of Tnode;
type
  TForm1 = class(TForm)
    MaskEdit1: TMaskEdit;
    MaskEdit2: TMaskEdit;
    MaskEdit3: TMaskEdit;
    MaskEdit4: TMaskEdit;
    MaskEdit5: TMaskEdit;
    MaskEdit6: TMaskEdit;
    MaskEdit7: TMaskEdit;
    MaskEdit8: TMaskEdit;
    MaskEdit9: TMaskEdit;
    Label3: TLabel;
    GroupBox1: TGroupBox;
    BitBtn2: TBitBtn;
    Button1: TButton;
    Edit2: TEdit;
    Label2: TLabel;
    Button2: TButton;
    Button3: TButton;
    RadioGroup1: TRadioGroup;
    Button4: TButton;
    MainMenu1: TMainMenu;
    N1: TMenuItem;
    N2: TMenuItem;
    N3: TMenuItem;
    procedure FormCreate(Sender: TObject);
    procedure BitBtn2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure RadioGroup1Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure N2Click(Sender: TObject);



  private
  ori:Tori;
  root,target,rand3x3,wujie:T3x3;
  open_ex:Topen_ex;
  close_ex:Tclose_ex;
  over:boolean;
   path:array[1..1000] of integer;
   wf_over,nodisplay:boolean;
   steps:integer;
  procedure op_cl;
  function  expand(n:integer;model:string):byte;
  function isequal(a1:T3x3;a2:T3x3):boolean;
  function h(sa:Tnode;md:string):integer;
  procedure draw(a: T3x3);
   procedure append_open(nn:Tnode);
   procedure sort;
   procedure delay_c(ms:longint);
   procedure pai; //
     procedure reset;
   function init:boolean;
     procedure rand;
    procedure search(model:string);
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
var
temp:shortint;
i,n:integer;
flag:byte;
label l1;
begin
target[1,1]:=1;
target[1,2]:=2;
target[1,3]:=3;
target[2,1]:=8;
target[2,2]:=0;
target[2,3]:=4;
target[3,1]:=7;
target[3,2]:=6;
target[3,3]:=5;
wujie[1,1]:=1;
wujie[1,2]:=2;
wujie[1,3]:=3;
wujie[2,1]:=7;
wujie[2,2]:=0;
wujie[2,3]:=4;
wujie[3,1]:=8;
wujie[3,2]:=6;
wujie[3,3]:=5;
n:=1;
for i:=1 to 10000 do
  begin
   open_ex[i].parent:=-2;
   //open_ex[i].status:=(((0,0,0),(0,0,0),(0,0,0)));
  //new(open_ex[i].pchild);
    open_ex[i].s:=999999;
     open_ex[i].children[1]:=0; open_ex[i].children[2]:=0;  open_ex[i].children[3]:=0; open_ex[i].children[4]:=0;

   close_ex[i].parent:=-2;
   //close_ex[i].status:=((0,0,0),(0,0,0),(0,0,0));
     close_ex[i].children[1]:=0;close_ex[i].children[2]:=0; close_ex[i].children[3]:=0; close_ex[i].children[4]:=0;
     close_ex[i].s:=999999;
  end;

{for i:=1 to 9 do
  begin
  ori[i]:=-1
  end;
Randomize;
ori[1]:=Random(9);
repeat
 l1:
 Randomize;
 temp:=Random(9);
 flag:=0;
 for i:=1 to 9 do
  begin
   if temp=ori[i] then flag:=1;
  end;
 if flag=1 then
  begin
  goto l1;
  end  else
  begin
    ori[n]:=temp;n:=n+1;
   end;
until ori[9]<>-1;}
ori[1]:=1;
ori[2]:=2;
ori[3]:=3;
ori[4]:=8;
ori[5]:=0;
ori[6]:=4;
ori[7]:=7;
ori[8]:=6;
ori[9]:=5;
maskedit1.Text:=inttostr(ori[1]);
maskedit2.Text:=inttostr(ori[2]);
maskedit3.Text:=inttostr(ori[3]);
maskedit4.Text:=inttostr(ori[4]);
maskedit5.Text:=inttostr(ori[5]);
maskedit6.Text:=inttostr(ori[6]);
maskedit7.Text:=inttostr(ori[7]);
maskedit8.Text:=inttostr(ori[8]);
maskedit9.Text:=inttostr(ori[9]);
rand;
end;


procedure Tform1.op_cl;
var
i,n,p:integer;
begin
  i:=1;
 while true do
  begin
   if close_ex[i].parent=-2 then //check close_ex[i] if be used
     begin
       //sort;
      close_ex[i]:=open_ex[1];   // open_ex[1] to close_ex[i]
        if open_ex[1].parent=-1  then //if is root
           begin
            break;
           end else    //if isn't root
            begin
                 for n:=1 to 4 do
                begin
                    if close_ex[close_ex[i].parent].children[n]=0 then
                      begin
                       close_ex[close_ex[i].parent].children[n]:=i;
                       break;//set close_ex[i]'s parent's children
                       end;
                  end;
                  break;
            end;
      end;
      i:=i+1;
   end;

  n:=2;
 repeat  //modify queue
  open_ex[n-1]:=open_ex[n];
  open_ex[n].parent:=-2;
  n:=n+1;
 until open_ex[n].parent=-2;
end;
 function Tform1.expand(n:integer;model:string):byte;
 var
 j,k,m,p,tem,jj,kk,no:integer;//
 tems : t3x3;
 temss:array[1..4] of t3x3;
 node:Tnode;
 nnnn:Topen_ex;
 r:boolean;
 begin
     over:=false;
    r:=false;

   for m:=1  to 4  do
   begin
    temss[m][1,1]:=-2;
   end;

   for jj:=1 to 3 do
     begin
       for kk:=1 to 3 do
        begin
        if close_ex[n].status[jj,kk]=0 then begin j:=jj;k:=kk; break;end; // search"0"
        end;
     end;
  if j>=2 then
    begin
       tems:=close_ex[n].status;
      tem:=tems[j-1,k];
      tems[j-1,k]:=tems[j,k];
      tems[j,k]:=tem;
      temss[1]:=tems;
    end;
  if j<=2 then
    begin
      tems:=close_ex[n].status;
      tem:=tems[j+1,k];
      tems[j+1,k]:=tems[j,k];
      tems[j,k]:=tem;
      temss[2]:=tems;
    end;
  if k>=2 then
    begin
      tems:=close_ex[n].status;
      tem:=tems[j,k-1];
      tems[j,k-1]:=tems[j,k];
      tems[j,k]:=tem;
      temss[3]:=tems;
    end;
  if k<=2 then
    begin
      tems:=close_ex[n].status;
      tem:=tems[j,k+1];
      tems[j,k+1]:=tems[j,k];
      tems[j,k]:=tem;
      temss[4]:=tems;
    end;

    //if exist target
if model='wf' then //sousuo
begin
  for m:=1  to 4  do
   begin
     if isequal(temss[m],wujie)=true  then begin expand:=3;exit;end;
     if isequal(temss[m],target)=true then
      begin
      close_ex[n].children[1]:=-9;
        no:=1;
        repeat
        path[no]:=n;
        if n=1 then break;
        p:=close_ex[n].parent;
        no:=no+1;
        path[no]:=p;
        no:=no+1;
        n:=close_ex[p].parent;
        until n=-1;
        expand:=1;
        exit;
      end;//-9 equivalence target
   end;
 end;
  //if exited in close table


  m:=1;
  for m:=1 to 4 do
  begin
   if temss[m][1,1]<>-2 then
    begin
     for  p:=1  to 10000 do
      begin
       if close_ex[p].parent=-2 then break;
       if isequal(temss[m],close_ex[p].status)=true then
        begin
          temss[m][1,1]:=-2;
          break;
        end;

      end;
    end;
    end;

    //if exited in open table
  for m:=1 to 4 do
  begin
   if temss[m][1,1]<>-2 then
    begin
     for  p:=1  to 10000 do
      begin
       if open_ex[p].parent=-2 then break;
       if isequal(temss[m],open_ex[p].status)=true then
         begin
        temss[m][1,1]:=-2;
        break;
        end;

      end;
    end;
  end;
  //input open table
   //nnnn:=open_ex;
  for m:=1 to 4 do
  begin
    if temss[m][1,1]<>-2 then
    begin
     node.parent:=n;
     node.status:=temss[m];

     node.children[1]:=0; node.children[2]:=0; node.children[3]:=0; node.children[4]:=0;
     node.layer:=close_ex[n].layer+1;
     node.s:=h(node,model);
     append_open(node);
     //end;

     end;
  end;
  //sort open  erwe
   sort;
  // nnnn:=open_ex;

   expand:=2;
 end;

 function Tform1.isequal(a1:T3x3;a2:T3x3):boolean;
 var
   j,k:integer;