Alaptáblák

 

         Ha olyan programot akarunk készíteni, amely alkalmas Sudoku feladványok készítésére, akkor annak tudnia kell alaptáblát előállítani, feladványt megoldani, és ha minősíteni is szeretnénk a feladványainkat, akkor természetesen azt is. Az elkészült alaptáblákat és feladványokat célszerű valamilyen lemezes állományban tárolni a későbbi felhasználhatóság érdekében. Én a könnyebb kezelhetőséget szem előtt tartva, tipizált állományban tárolom a feladványokat.

 

         Nézzük a szükséges deklarációkat:

 

Const

  GAl=3;                       {generalasi alapszam (3)}
  Max=GAl*Gal;                 {a kis negyzet vagy tartomany (9)}
  MX=Max*Max;                  {a teljes tabla (81)}



Type

  St81=String[81];             {a tabla es a megoldas stringje}
  KTomb=Array[1..Max] Of Word; {kis tomb (9)}
  TTomb=Array[1..MX] Of Word;  {nagy tomb (81)}

  TGT=Record
    TTabla: St81;              {az alaptabla rekordja}
  End;

  TGS=Record                   {feladvany rekord}
    Ind: LongInt;              {tombindex}
    Tabla, Megold: ST81;       {a feladvany es a megoldas tombje}
    Elem, NFok: Word;          {a feladvany elemszama es nehezsegi foka}
  End;

Var

  DNevString;                {operacios rendszerbeli file nev}
  GTFileFile Of TGT;         {az alaptabla allomany logikai neve}
  GSFileFile Of TGS;         {a feladvany allomany logikai neve}
  ATbl: TGT;                   {egy teljes tabla}
  ARek: TGS;                   {aktualis rekord a file olvasasanal}
  ST: TTomb;                   {az alaptabla kiindulasi tombje}
  SA: TTomb;                   {alaptabla tombje egy feladvanynal}
  SM: TTomb;                   {feladvany tombje}

  TIndexArray[1..Max,1..Max] Of Word; {rogzitett tablaindexek}
  InXInYInTTTomb;        {rogzitett oszlop-, sor- es tartomanyindexek}
  TKIndTTomb;                {rogzitett tartomanyi kezdoindexek}
  UtTblArray[1..MX,1..MX] Or Word; {ahol ket cella szobatars, ott erteke 1}
  SzTArray[1..MX,1..20] Of Word; {a szobatarsak indexenek tombje}

 

Következzék egy kis magyarázat. A generálási alapszám megadásával egyszerűen meg lehet változtatni az alaptábla méretét. Ha például 2-t választunk, akkor 4 x 4-es feladványokat, ha 4-et, akkor pedig 16 x 16-os feladványokat készíthetünk a programmal.

 

A lemezes állományban a táblákat 81-es méretű stringben tárolom, míg a feldolgozás, generálás 81-es méretű számtömbökben történik. A lemezműveleteknél, amely aránylag ritkán fordul elő (főleg ha alacsony elemszámú feladványt készítünk) átváltást kell végrehajtani a két típus között.

        

         Az alaptáblákban az elemek tartomány-sorfolytonosan vannak elrendezve, azaz először a bal felső tartomány kilenc eleme sorfolytonosan, majd középső felső tartományé, aztán a jobb felső tartományé, stb. Végül a jobb alsó tartomány elemeit helyezzük be. Ez a sorrend jelenti a 81-es egydimenziós tömbbeli helyüket. Az alaptábla generálásánál csak egy tartományon belül cserélgetjük az elemeket, így csak sor- és oszlopütközéseket kell figyelni. Az alaptábla generálás előtti feltöltését (ST tömb) a következő ScreeShot-on láthatjuk:

 

 

         Ez pedig egy kész alaptábla (SA tömb):

 

 

 

A programban gyakran kellene meghatározni az alaptábla eleminek helyét a lineáris tömbben ezért ezeket a program futtatásának elején kiszámoljuk, és  egy TIndex táblázatban rögzítjük. Ennek értékei láthatók a következő ScreenShot-on:

 

 

 

Hasonlóan gyakran kell meghatározni, hogy egy elem milyen indexű sorban, oszlopban vagy tartományban van, ezért ezekre az értékekre hasonlóan járunk el mint a TIndex esetén. Példaként az InT és TKInd tömböket láthatjuk itt:

 

Az InT tömb.

 

A TKInd tömb.

 

Kicsit összetettebb az UtTbl és az SzT táblák előállítása. Ezek feltöltésére a következő programsorok alkalmasak:

 

//utkozesi tabla toltese
For I:= 1 To MX Do For J:= 1 To MX Do UtTbl[I,J]:= 0;
//soronkent
For L:= 0 To GAl-1 Do For KK:= 0 To GAl-1 Do For J:= 1 To Max Do For I:= 1 To Max Do
UtTbl[TIndex[I,L*GAl+(J-1) Div GAl+1],J+K*Max+L*GAl*Max]:= 1;
//oszloponkent
For L:= 0 To GAl-1 Do For K:= 0 To GAl-1 Do For J:= 1 To Max Do For I:= 1 To Max Do
UtTbl[TIndex[(J-1) Mod GAl+1+K*GAl,I],J+K*Max+L*GAl*Max]:= 1;
//tartomanyonkent
For I:= 1 To MX Do
For J:= Max*((I-1) Div Max)+1 To Max*((I-1) Div Max)+Max Do UtTbl[I,J]:= 1;
//atlo torlese
For I:= 1 To MX Do UtTbl[I,I]:= 0;

//szobatarsak
For I:= 1 To MX Do For J:= 1 To 20 Do SzT[I,J]:= 0;
For I:= 1 To MX Do
Begin
  K:= 0; For J:= 1 To MX Do If UtTbl[I,J]=1 Then
  Begin Inc(K); SzT[I,K]:= J End;
End;

 

Az ütközési tábla (UtTbl) egy része (az első 41 sora) így néz ki:

 

 

Végül lássuk az alaptábla (SA tömb) generálási kódját:

 

Procedure Csere(A, B: Word);
Var P: Word;
Begin
  P:= SA[A]; SA[A]:= SA[B]; SA[B]:= P;
End;

Function Utkozes: Word;
Var I, J, K, U: Word;
Begin
  U:= 0; For I:= 1 To Max Do For J:= 1 To Max Do For K:= 1 To 20 Do
  If SA[TIndex[I,J]]=SA[SzT[TIndex[I,J],K]] Then Inc(U); Utkozes:= U;
End;

Procedure Alap;
Var A, B, I, P, U: Word;
Begin
  //start allapot
  SA:= ST;
  //kever
  For I:= 1 To MX Do
  Begin
    A:= Random(MX)+1;
    Repeat B:= Max*((A-1) Div Max)+Random(Max)+1 Until A<>B;
    Csere(A,B);
  End;
  //rendez
  U:= MX*MX;
  While U>0 Do
  Begin
    A:= Random(MX)+1; B:= Max*((A-1) Div Max)+Random(Max)+1;
    P:= U; Csere(A,B); U:= Utkozes;
    If U>P Then Begin Csere(A,B); U:= P End;
  End;
End;