Feladványok megoldása (1)

A Sudoku játék alapfeladata a feladványok megoldása. Két alapvetően különböző lehetőség van a megoldásra: kézi és gépi. Kézi megoldásnál nem használunk számítógépet a jelöltek meghatározására. Ekkor mi magunk fejtjük meg a rejtvényt, keresünk a feladványban olyan helyeket, ahova csak egyetlen szám írható. Ennek eredményessége természetesen személytől függő, de mindenképp időigényes mutatvány. Gépi megoldásnál a számítógép dolgozik helyettünk, különböző gépi algoritmusokat használva.

Jelölteknek nevezzük azokat az elemeket (számokat), amelyek egy bizonyos elemzés után a cellába beírhatóknak tűnnek. Cél az, hogy minél okosabb algoritmusokat használva a jelöltek számát a minimális 1-re csökkentsük. A jelöltek számának csökkentésére különböző metódusok állnak rendelkezésünkre, melynek alkalmazása révén elérhetjük a feladvány megfejtését. A metódusok közül néhány könnyen alkalmazható kézi megoldásnál is, és ráadásul olyanok is vannak közöttük, amelyek igen hatékonyak. Az is előfordulhat (a kézi és a gépi megoldásnál egyaránt), hogy nem létezik minden állapotban egyértelmű továbblépés (azaz nincs egyetlen olyan mező sem, ahol a jelöltek száma 1 lenne). Ekkor a jelöltek közül (ha van olyan cella, amelyben a jelöltek száma 2, akkor célszerű ebből) találomra kiválasztunk egyet, és ezzel addig próbálkozunk, ameddig teljesen kitöltjük a táblát, vagy valamely cellában a jelöltek száma 0 nem lesz (nem sikerül a kitöltés). Ha nem sikerül a kitöltés végére érni, akkor ki kell törölni a véletlenül kiválasztott elemet, (és minden olyat is törölni kell, amit ez után írtunk be!), és másik jelölttel kell próbálkoznunk. Ennek a gépi megfelelője a BackTrack algoritmus. Ha a metódusok közé ezt is felvesszük, akkor – legalább is géppel – minden megoldható feladványt meg is tudunk oldani.

Következzenek a metódusok. A szakirodalomban szokásos nevükkel fogom használni őket. Rögtön az első olyan – Basic – amelyet én neveztem el így, de szerintem elég logikusra sikeredett. A metódusok hatását egy (géppel segített) kézi megoldó program segítségével mutatom be, melynek az alapképernyője így néz ki:

A feladványokat beírhatjuk kézzel (a bal oldali rácsba), vagy adatbázisból választhatjuk ki egy lenyíló ListBox segítségével. Válasszuk ki például a D-24.gsf adattábla 111-es feladványát:

A baloldali StringGrid-ben megjelent a feladvány, a jobboldaliban a jelöltek. Az adattáblákon a rekordléptető gombokkal mozoghatunk (Első, Előző, Következő, Utolsó és Ugrás – a beírt index alapján). Látható, hogy a feladvány 24 elemszámú, az alap metódus (Basic) szerint 3 rögtön beírható jelöltet tartalmaz (zöld háttérszín). A képernyő további részeinek leírása: A Timer vagyis időzítő, ami be van kapcsolva, azaz bármilyen változtatás a feladványban, vagy változtatás a metódusok ki-be kapcsolt állapotán, azonnal kiértékelődnek, azaz a jelöltek táblája aktualizálódik. Megnézhetjük a feladvány Alap tábláját (megoldását), Feladványt írhatunk be, Rögzíthetjük a gépi Megoldás számára, Újra kezdhetjük a beírást, és Fájlba menthetjük a kézzel beírt feladványt. Meg lehet vizsgálni, hogy a feladvány Megoldható-e? Látjuk a megoldhatósági vizsgálat kezdő időpontját és a végét, valamint az Igen (vagy Nem) választ. Külön láthatjuk az aktuális feladvány adatbázisbeli Indexét (rekordszámát) és a Nehézségi Fokát (minél nagyobb az érték, annál nehezebben oldható meg a feladvány). Az angol szín feliratú gombok (Red, Yellow, Olive) segítségével a jelölteket tartalmazó cellák háttérszínét állíthatjuk be (a jelen bemutatás könnyebb megértése végett), a Töröl gomb az alapértelmezett szint adja vissza. A Be és Ki gomb a metódusok csoportos ki-be kapcsolását végzik.

A lapon található Pascal rutinok a következő deklarációkat használják:

Type
KTomb=Array[1..Max] Of Word; //kis (9) tomb
TTomb=Array[1..MX] Of Word;  //teljes (81 - nagy) tomb

Var SM: TTomb;                 //feladvany tombje
    SA: TTomb:                 //alaptabla tombje
    SC: TTomb;                 //ideiglenes feladvanytomb
    SH: Array[1..MX] Of KTomb; //elemei 0 vagy 1 - a jelolteket tartalmazza
SzT: Array[1..MX,1..20] Of Word; //szobatarsak indexenek tombje

A továbbiakban nézzük az egyes metódusok bemutatását.

Basic (BS)

A szakirodalom nem nevesíti azt a metódust, amely a kitöltési szabályból közvetlenül származik. Én Basic-nek neveztem el. Ez az első lépés akkor, ha sikerül egy újabb elemet beírni a feladványba (egy cellában csak egy jelölt volt). Ilyenkor minden szobatársából a beírt számot törölni kell, amennyiben abban szerepelt. Most a kézi megoldóban egyetlen metódus sincs aktiválva csak a BS, amely ki sem kapcsolható. A lentebbi feladványban a C8-as cellába csak egyetlen jelölt található, ez a 2-es. Ha ezt beírjuk, akkor a C oszlopból, a 8-as sorból és az A7C9-es tartományból minden 2-es törlődik. (Az érintett cellákat piros háttérszín jelzi. A zöld háttérszín mindig a beírhatót – az egyetlen jelöltet jelöli.)

A C8-as cellába (sárga háttérszín a feladvány rácsban) történő beírás után a jelöltek így változnak meg:

A Basic rutinja:

Procedure TSzal.Basic;
Var I, J: Word;
Begin
For I:= 1 To MX Do If SM[I]>0 Then
Begin
//a mezo teljes torlese
For J:= 1 To Max Do SH[I,J]:= 0;
//torles a szobatarsakban
For J:= 1 To 20 Do SH[SzT[I,J],SM[I]]:= 0;
End;
End;

Singles Out (SO)

Ez egy sajátos módszert, melyet az SO jelölőnégyzettel kapcsolhatunk ki-be. Ezt én Singles Out–nak neveztem el. Lényege, hogy minden egyértelmű jelöltet beírtnak tekint, majd a BS-el a szoba többi cellájából törli a jelöltet. Majd újra kezdi, és mindaddig folytatja, amíg újabb beírhatót – azaz szinglit – talál. Nagyon jól látható hatása egy olyan feladvány megoldásánál, ahol a teljes feladvány csak Basic segítségével megoldható. Ilyen a D-20.gsf adattábla 2318-as feladványa.. Ebben a feladványban az elemek száma 20 és 1-es nehézségi fokú – ahogy látható. A feladványnak csak a B4-es cellájában van egyetlen jelölt.

Most kapcsoljuk be az SO funkciót, meglepő dolog fog történni. Minden be nem töltött cellában egyetlen jelölt lesz, gyakorlatilag az SO teljesen megoldotta a feladványt (Elemszám: 20, Beírható: 61). Íme:

A Singles Out rutinja:

Function Osszeg(A: KTomb): Word; //A[] tomb elemeinek osszege
Var I, S: Word;
Begin
  S:= 0; For I:= 1 To Max Do S:= S+A[I]; Osszeg:= S;
End;

Procedure SingleOut;
Var I, J, N: Word;
    Volt: Boolean;
Begin
  Volt:= True;
While Volt Do
Begin
    Volt:= False;
For I:= 1 To MX Do If (SM[I]=0) And (Osszeg(SH[I])=1) Then
Begin
      N:= 0; For J:= 1 To Max Do If SH[I,J]=1 Then Begin N:= J; Break End;
For J:= 1 To 20 Do If SH[SzT[I,J],N]<>0 Then
Begin SH[SzT[I,J],N]:= 0; Volt:= True End;
End;
End;
End;

Hidden Singles (HS)

A metódus: Ha egy sorban, egy oszlopban vagy egy tartományban csak egyetlen cellában van egy adott jelölt, akkor a cellába ez a jelölt beírható, és a szoba további celláiból a jelölt törölhető. (Ezzel a metódussal egy jelölt beírhatóvá válik az érintett cellába.) A kézi megoldóban a BS mellett a HS is be van kapcsolva. A HS bemutatására nézzük a következő feladványt. Látható, hogy az 5-ös sorban csak a B oszlopban található 3-as. (További ilyen esetek a feladványban: a 3-as sorban csak az I oszlopban van 1-es, és az 1-es sorban csak a G oszlopban található 6-os.)

Ha HS-t bekapcsoljuk, akkor ezt láthatjuk (1 cella helyett 5 cellában lett egy jelölt, ezek a zöld háttérszínűek, a H8-ban eddig is egy jelölt volt – zöld háttérszínnel):

Ha e mellé az SO-t is bekapcsoljuk, akkor válik teljessé a kép (a piros hátterű mezők jelöltjeinek száma csökkent, ez összesen 19 mezőt érintett és ezek között létrejött egy beírható jelölt is a H9 cellában, melynek háttérszínét zöldről pirosra változtattam – a változást érzékeltetendő. Ebből is látszik, hogy a Hidden Singles egy igen hatékony metódus a jelöltek számának csökkentésére, ugyanakkor kézi megoldásban is aránylag könnyen használható):

A Hidden Singles rutinja:

Function OszlopN(S,X: Word): Word; //az SH X oszlopaban S szama
Var I, N: Word;
Begin
  N:= 0; For I:= 1 To Max Do N:= N+SH[TIndex[X,I],S]; OszlopN:= N;
End;

Function SorN(S,Y: Word): Word;    //az SH Y soraban S szama
Var I, N: Word;
Begin
  N:= 0; For I:= 1 To Max Do N:= N+SH[TIndex[I,Y],S]; SorN:= N;
End;

Function TartN(S,T: Word): Word;   //az SH T tartomanyaban S szama
Var I, N: Word;
Begin
  N:= 0; For I:= Max*(T-1)+1 To Max*T Do N:= N+SH[I,S]; TartN:= N;
End;

Procedure HiddenSingles;
Var I, J, L, M: Word;
    Volt: Boolean;
Begin

//Hidden Singles, J: a keresendo szam
Volt:= True;
While Volt Do
Begin
    Volt:= False;
//ha egy oszlopban csak egy helyen van egy szam, mellole a tobbit torli
For I:= 1 To Max Do For J:= 1 To Max Do If OszlopN(J,I)=1 Then
Begin
      L:= 1; While SH[TIndex[I,L],J]=0 Do Inc(L);
For M:= 1 To Max Do If (SH[TIndex[I,L],M]=1) And (M<>J) Then
Begin SH[TIndex[I,L],M]:= 0; Volt:= True End;
End;
//ha egy sorban csak egy helyen van egy szam, mellole a tobbit torli
For I:= 1 To Max Do For J:= 1 To Max Do If SorN(J,I)=1 Then
Begin
      L:= 1; While SH[TIndex[L,I],J]=0 Do Inc(L);
For M:= 1 To Max Do If (SH[TIndex[L,I],M]=1) And (M<>J) Then
Begin SH[TIndex[L,I],M]:= 0; Volt:= True End;
End;
//ha egy tartományban csak egy helyen van egy szam, mellole a tobbit torli
For I:= 1 To Max Do For J:= 1 To Max Do If TartN(J,I)=1 Then
Begin
      L:= Max*(I-1)+1; While SH[L,J]=0 Do Inc(L);
For M:= 1 To Max Do If (SH[L,M]=1) And (M<>J) Then
Begin SH[L,M]:= 0; Volt:= True End;
End;
End;

End;

Pointing Pairs (PP)

A metódus: Ha egy tartományban egy jelölt csak két helyen van, de egy sorban vagy egy oszlopban, akkor a jelölt – a kijelölt teljes sorban vagy oszlopban – a többi helyről törölhető. A következő feladványban három ilyen jelölt-pár is található: az A4 és a B4-ben a 8-as jelölt az A4C6 tartományban, a G6 és a H6-ban a 4-es jelölt a G4I6 tartományban és az F7 és F8-ban az 5-ös jelölt a D7F9 tartományban teljesíti a feltételeket. A PP metódus bekapcsolása előtti állapot így néz ki:

Ha bekapcsoljuk a PP-t, akkor a pirossal jelölt cellákból az érintett jelöltek törlődnek (D4-ből a 8-as, F4-ből az 5-ös, míg D6, E6 és F6-ból a 4-es):

A Pointing Pairs rutinja:

Procedure PointingPairs;
Var I, J, K, A, B, U, V: Word;
Begin
//Pointing Pairs
//ha egy tartomanyban egy szam csak ket helyen van, de egy sorban vagy egy
//oszlopban, akkor a kijelolt sorban vagy oszlopban a tobbi helyrol a szam
//torolheto
For I:= 1 To MX Do If SM[I]=0 Then For J:= 1 To Max Do //J: keresendo szam
If TartN(J,InT[I])=2 Then
Begin
    A:= 0; B:= 0; U:= 0; V:= 0; //a tartományon beluli helyek
For K:= TKInd[I] To TKInd[I]+Max-1 Do If SH[K,J]=1 Then If A=0 Then
Begin U:= K; A:= InX[K] End Else Begin V:= K; B:= InX[K] End;
If (A<>0) And (A=B) Then For K:= 1 To MX Do If SM[K]=0 Then //egy oszlop
If (InX[K]=A) And (K<>U) And (K<>V) Then SH[K][J]:= 0;

    A:= 0; B:= 0; U:= 0; V:= 0; //a tartományon beluli helyek
For K:= TKInd[I] To TKInd[I]+Max-1 Do If SH[K,J]=1 Then If A=0 Then
Begin U:= K; A:= InY[K] End Else Begin V:= K; B:= InY[K] End;
If (A<>0) And (A=B) Then For K:= 1 To MX Do If SM[K]=0 Then //egy sor
If (InY[K]=A) And (K<>U) And (K<>V) Then SH[K][J]:= 0;
End;
End;

Naked Pairs (NP)

A metódus: Ha egy szobának két cellájában csak ugyanaz a két jelölt van, akkor a szoba többi cellájából (a kijelölt sorból vagy oszlopból, és ha egy tartományban vannak, akkor tartományból is) ezek a jelöltek törölhetők. A következő feladványban két pár cella is teljesíti a feltételeket: B6 és B7, valamint D8 és F8.

Ha bekapcsoljuk az NP-t akkor a piros hátterű cellákból a megfelelő jelöltek (4-6 és 4-5) törlődnek (a B9-ben csak egy jelölt maradt, de a változás érzékeltetése miatt a hátterét pirosra állítottam). Mivel a 8-as sorban csak a D és F oszlopban található 4-es és 5-ös, ezért csak a D7F9 tartományban törlődnek jelöltek.

A következő feladványban a jelölt-pár egy tartományban van, de különböző sorokban és oszlopokban. Ekkor csak a tartományon belül történik jelölttörlés. Az A2 és C1 a megfelelő cellák és csak az A1C3 tartományban törlődik az 1-9 jelölt-pár.

Az NP bekapcsolása után ezt láthatjuk:

A Naked Pairs rutinja:

Function SHStr(K: KTomb): String;
Var I: Word;
    S: String;
Begin
  S:= ''; For I:= 1 To Max Do If K[I]=1 Then S:= S+IntToStr(I); SHStr:= S;
End;

Function Egyenlo(A, B: KTomb): Boolean; //A és B egyenlo-e
Var I: Word;
Begin
Egyenlo:= True; For I:= 1 To Max Do If A[I]<>B[I] Then
Begin Egyenlo:= False; Break End;
End;

Function Kivesz(A, B: KTomb): KTomb; //A-B: A-bol toroljuk B-t
Var I: Word;
    P: KTomb;
Begin
  P:= A; For I:= 1 To Max Do If B[I]=1 Then P[I]:= 0; Kivesz:= P;
End;

Procedure NakedPairs;
Var I, J, K: Word;
Begin
//Naked Pairs
//ha egy szobaban ket helyen van csak ugyanaz a ket szem,
//akkor a tobbi helyrol ezek a szamok torolhetok
For I:= 1 To MX-1 Do If SM[I]=0 Then If Length(SHStr(SH[I]))=2 Then
For J:= I+1 To MX Do If SM[J]=0 Then If Length(SHStr(SH[J]))=2 Then
Begin
If (InX[I]=InX[J]) And Egyenlo(SH[I],SH[J]) Then //ha egy oszlopban vannak
For K:= 1 To MX Do If SM[K]=0 Then
If (InX[K]=InX[J]) And (K<>I) And (K<>J) Then
Begin SH[K]:= Kivesz(SH[K],SH[J]) End;
If (InY[I]=InY[J]) And Egyenlo(SH[I],SH[J]) Then //ha egy sorban vannnak
For K:= 1 To MX Do If SM[K]=0 Then
If (InY[K]=InY[J]) And (K<>I) And (K<>J) Then
Begin SH[K]:= Kivesz(SH[K],SH[J]) End;
If (InT[I]=InT[J]) And Egyenlo(SH[I],SH[J]) Then //ha egy tart.ban vannak
For K:= 1 To MX Do If SM[K]=0 Then
If (InT[K]=InT[J]) And (K<>I) And (K<>J) Then
Begin SH[K]:= Kivesz(SH[K],SH[J]) End;
End;
End;

Hidden Pairs (HP)

A metódus: Ha egy szobában csak két cellában van ugyanaz a két jelölt (de más még lehet), akkor a szoba ezen két mezőjéből minden más jelölt törölhető. Nézzük a következő feladványt. A A oszlopban csak az 5-ös és a 9-es sorban van a 2-es és 3-as jelölt, a 7-es sorban csak az E és F oszlopban van 4-es és 7-es jelölt, valamint a G4I6 tartományban csak a G5-ös és I4-es cellákban van 4-es és 6-os jelölt. A HP bekapcsolása előtt a piros hátterű cellák jelzik a törlési helyeket:

Ha a HP-t bekapcsoljuk, akkor a törlések végrehajtódnak:

A Hidden Pairs rutinja:

Procedure HiddenPairs;
Var I, J, K, L, A, B, U, V: Word;
OFi, SFi, TFi: Array[1..Max] Of Boolean;
Begin
//Hidden Pairs     - hasznaljuk az InX,InY és InT-t az egybetartozashoz
For I:= 1 To Max Do Begin OFi[I]:= False; SFi[I]:= False; TFi[I]:= False End;
//ha egy szobaban csak ket helyen van ugyanaz a ket szam (de mas meg lehet),
//akkor a szoba ezen ket mezejebol minden mas szam torolheto
For I:= 1 To MX Do If SM[I]=0 Then
For J:= 1 To Max Do For K:= 1 To Max Do //J,K: a keresett szamok
If J<>K Then
Begin
//ha mindkettobol ketto van egy oszlopban
If Not OFi[InX[I]] Then
If (OszlopN(J,InX[I])=2) And (OszlopN(K,InX[I])=2) Then
Begin
      A:= 0; B:= 0; U:= 0; V:= 0;
For L:= 1 To MX Do If SM[L]=0 Then
If (InX[L]=InX[I]) And (SH[L,J]=1) Then
If A=0 Then A:= L Else B:= L;
For L:= 1 To MX Do If SM[L]=0 Then
If (InX[L]=InX[I]) And (SH[L,K]=1) Then
If U=0 Then U:= L Else V:= L;
If (A=U) And (B=V) Then
Begin
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[A,L]:= 0;
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[B,L]:= 0;
OFi[InX[I]]:= True;
End;
End;
//ha mindkettobol ketto van egy sorban
If Not SFi[InY[I]] Then
If (SorN(J,InY[I])=2) And (SorN(K,InY[I])=2) Then
Begin
      A:= 0; B:= 0; U:= 0; V:= 0;
For L:= 1 To MX Do If SM[L]=0 Then
If (InY[L]=InY[I]) And (SH[L,J]=1) Then
If A=0 Then A:= L Else B:= L;
For L:= 1 To MX Do If SM[L]=0 Then
If (InY[L]=InY[I]) And (SH[L,K]=1) Then
If U=0 Then U:= L Else V:= L;
If (A=U) And (B=V) Then
Begin
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[A,L]:= 0;
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[B,L]:= 0;
SFi[InY[I]]:= True;
End;
End;
//ha mindkettobol ketto van egy tartomanyban
If Not TFi[InT[I]] Then
If (TartN(J,InT[I])=2) And (TartN(K,InT[I])=2) Then
Begin
      A:= 0; B:= 0; U:= 0; V:= 0;
For L:= 1 To MX Do If SM[L]=0 Then
If (InT[L]=InT[I]) And (SH[L,J]=1) Then
If A=0 Then A:= L Else B:= L;
For L:= 1 To MX Do If SM[L]=0 Then
If (InT[L]=InT[I]) And (SH[L,K]=1) Then
If U=0 Then U:= L Else V:= L;
If (A=U) And (B=V) Then
Begin
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[A,L]:= 0;
For L:= 1 To Max Do If (L<>J) And (L<>K) Then SH[B,L]:= 0;
TFi[InT[I]]:= True;
End;
End;
End;
End;