Tartalom
Bevezető információk: Egy A mátrix soraira nézve sztochasztikus, ha elemei nemnegatívak, és minden sorösszege 1, és oszlopaira nézve sztochasztikus, ha elemei nemnegatívak, és minden oszlopösszege 1. Ha soraira és oszlopaira nézve is sztochasztikus, akkor kétszeresen (duplán) sztochasztikusnak nevezzük.
13.1. feladat (Sztochasztikus mátrix – szint: 2). Egy text fájlban szereplő (tört számokat tároló)
mátrix elemeit olvassuk be, majd dönstük el, hogy a mátrix duplán sztochasztikus-e!
Magyarázat: Ezt egy egyszerű függvény képes eldönteni (13.41. forráskód). A „minden szám nemnegatív” vizsgálatot érdemes belefoglalni valamelyik sor- vagy oszlopösszeg- ellenőrző lépésbe, mivel azok szkennelik a mátrix minden elemét, illetve kis ügyességgel egyetlen mátrixbejárással elvégezhető a teljes ellenőrzés (13.42. forráskód).
13.1. forráskód. Duplán sztochasztikusság ellenőrzése klasszikus megoldással
static bool duplan_sztochasztikus(int[,] m) { int N = m.GetLength(0); int M = m.GetLength(1); // minden eleme nemnegatív ? for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (m[i, j] < 0) return false; // sorosszeg mindenütt 1.0 ? for (int i = 0; i < N; i++) { double sum = 0.0; for (int j = 0; j < M; j++) sum = sum + m[i, j]; if (sum != 1.0) return false; } // oszlop osszegek mindenütt 1.0 ? for (int j = 0; j < M; j++) { double sum = 0.0; for (int i = 0; i < N; i++) sum = sum + m[i, j]; if (sum != 1.0) return false; } // minden rendben return true; }
13.2. forráskód. Duplán sztochasztikusság ellenőrzése optimalizált módon
static bool duplan_sztochasztikus_opt(int[,] m) { int N = m.GetLength(0); int M = m.GetLength(1); double[] sorok = new double[N]; double[] oszlopok = new double[M]; // matrix bejarasa for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (m[i, j] < 0) return false; sorok[i] = sorok[i] + m[i, j]; oszlopok[j] = oszlopok[j] + m[i, j]; } // ellenorzes for (int i = 0; i < N; i++) if (sorok[i]!=1.0) return false; for (int j = 0; j < M; j++) if (oszlopok[j] != 1.0) return false; // minden rendben return true; }
Bevezető információk: A duplán sztochasztikus mátrixokhoz hasonlóak a mágikus négyzetek. Ezek olyan mátrixok, melyek egész számokat tartalmaznak, minden szám egyedi (nem ismétlődik a mátrixban), és soraikban, oszlopaikban, valamint az átlókban szereplő számok összege egyenlő egymással. Ezt az értéket nevezzük mágikus értéknek, vagy kulcsértéknek[1].
A mágikus négyzetek több ezer éve ismertek, a középkorban talizmánként is használták őket.
Egyik híres felbukkanási helye Albrecht Dürer (1471–1528) német festő és grafikus Melankólia c.
metszetének (lásd a 13.1. ábra) jobb felső sarka, ahol egy 
méretű mágikus négyzet[2] látható. A négyzet alsó sorában
középen szereplő két érték összeolvasva 1514, mely a kép keletkezésének éve is
egyben.
A mágikus négyzeteket már a kínaiak is ismerték, egyik legrégebbi felbukkanása a változások könyve jóskönyv, mely i. e. 3000 körül készülhetett.
13.2. feladat (Mágikus négyzet-e – szint: 2). Egy fájlban szereplő
méretű mátrixról döntsük el, hogy mágikus négyzet-e! Ha igen, adjuk meg a mágikus mátrix kulcsértékét!
Magyarázat: A 13.2. ábrán látható egy Benjamin Franklin által készített
méretű mágikus négyzet[3], ahol a sorok és oszlopok
összege 260. A 13.1 feladatban elkészített ellenőrző függvény módosításokkal alkalmas a
mágikus négyzet tulajdonság ellenőrzésére is. A különbség nemcsak az, hogy nem 1.0-nak kell
lenni az összegeknek, de egymással is egyezőknek. Ha minden sorösszeg egyezik az első sor
összegével, valamint minden oszlopösszeg egyezik az első oszlop összegével, akkor ez a
tulajdonság már majdnem rendben is van. De meg kell még vizsgálni, hogy a sorok és
oszlopok összege egymással is egyenlő-e! Ezenfelül ugyanezen összegnek kell szerepelni a két
főátlóbeli számok összegeiként is. Nem szabad elfelejtkezni a számok egyediségének
ellenőrzéséről sem! Mindezek a 13.43. ... 13.47. forráskódokban
találhatók.
méretű mágikus négyzete
13.3. forráskód. Bűvös négyzet – „buvos_negyzet_e”
static bool magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] sorok = new int[N]; int[] oszlopok = new int[N]; osszegekGen(m, sorok, oszlopok); // sorok, oszlopok osszegei if (mindEgyenlo(sorok) == false || mindEgyenlo(oszlopok) == false || sorok[0] != oszlopok[0]) return false; // atlok osszegei int atlo1, atlo2; atlokGen(m, out atlo1, out atlo2); if (atlo1 != atlo2 || atlo1 != sorok[0]) return false; // egyediseg for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (megszamol(m, m[i, j]) != 1) return false; // minden rendben return true; }
13.4. forráskód. Bűvös négyzet – „osszegekGen”
static void osszegekGen(int[,] m, int[] sorok, int[] oszlopok) { for (int i = 0; i < sorok.Length; i++) for (int j = 0; j < oszlopok.Length; j++) { sorok[i] = sorok[i] + m[i, j]; oszlopok[j] = oszlopok[j] + m[i, j]; } }
13.5. forráskód. Bűvös négyzet – „mindEgyenlo”
static bool mindEgyenlo(int[] l) { int x = l[0]; foreach (int a in l) if (x != a) return false; return true; }
13.6. forráskód. Bűvös négyzet – „atlokGen”
static void atlokGen(int[,] m, out int a, out int b) { a = 0; b = 0; int N = m.GetLength(0); for (int i = 0; i < N; i++) { a = a + m[i, i]; b = b + m[i, N - i - 1]; } }
13.7. forráskód. Bűvös négyzet – „megszamol”
static int megszamol(int[,] m, int x) { int N = m.GetLength(0); int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i, j] == x) db++; return db; }
Bevezető információk: Az olyan mágikus négyzeteket, melyekben minden érték prímszám, prím mágikus négyzeteknek nevezzük (lásd pl. a 13.3. ábra).
méretű mágikus négyzet
13.3. feladat (Prím mágikus négyzet-e – szint: 3). Feladat: egy fájlból beolvasott
méretű mátrixról döntsük el, hogy bűvös négyzet-e, és ha igen, akkor prímekből felépített mágikus négyzet-e! Soroljuk fel tételesen, melyik cellában szereplő mely értékek nem prímek, amelyek elrontják ezt a tulajdonságot! A megoldás során az 1 értéket kivételesen kell kezelni. Ha szerepel valamelyik cellában, de mindegyik másik cellaérték prím, akkor az még elfogadható prím mágikus négyzet kategóriának.
Magyarázat: A prímszám eldöntésére több módszer is létezik, jelen probléma esetén majdnem mindegy, melyik módszert választjuk. Egy „prímszám-e” bevizsgáló függvény megírása után a probléma kezelhető szintre redukálódik: a 13.2 feladatban leírt ellenőrzést esetünkben csak azzal kell kiegészíteni, hogy a mátrix minden egyes számáról el kell dönteni, hogy prímszám-e vagy sem.
13.8. forráskód. A mátrix értékeinek ellenőrzése
bool mindegyikPrim = true; for(int i=0;i<N && mindegyikPrim;i++) { for(int j=0;j<M && mindegyikPrim;j++) { if (prim-e(m[i,j]==false) mindegyikPrim = false; } }
Bevezető információk: A pánmágikus négyzetek nem egyszerű mágikus négyzetek, hanem
egyéb jellemzőkkel is bírnak. Nemcsak a sorokban és oszlopokban szereplő értékek összege
egyenlő, hanem a főátlókban lévő számok összege is, valamint az ún. törtátlókban is. A
13.4. ábrán látható, mit értünk törtátlón. Egy 
méretű
mátrixnál berajzoltuk ezeket is. A 13.5. ábrán újabb pánmágikus mátrixokat
mutatunk be.
13.4. feladat (Pánmágikus négyzet – szint: 4). A feladat: írjunk olyan programot, amely beolvas fájlból egy
méretű mátrixot, és eldönti, hogy pánmágikus-e! A program jelenítse meg az egyes törtátlókat eltérő színnel, és adja meg az adott törtátlóban lévő értékek összegét (egy időben csak egy törtátlóra koncentrálva, vagyis az adott törtátló számai legyenek zöldek, minden más szám legyen szürke)!
A mátrix törtátlós színezésével foglalkozik a 13.49. forráskód (jobbra-le törtátlók), a másik (balra-le) törtátlós színes kiírásával a 13.50. forráskódban található egyfajta megoldás. A színeket egy vektorba helyezzük. Konzolos felületen limitált mennyiségű színt használhatunk fel, és érdemes úgy válogatni a színeket egymás mellé, hogy lényegesen elüssenek egymástól. Ezért a színek vektorát manuálisan töltöttük fel színekkel. A két kiírás között egyébként a lényeges különbség mindössze a külső i ciklusban lévő szin kiválasztás módja.
13.9. forráskód. Jobbra-le törtátlók
static void panmagikus_kiir_A(int[,] m) { int N = m.GetLength(0); ConsoleColor[] color = new ConsoleColor[] { ConsoleColor.Red, ConsoleColor.Green, ConsoleColor.Yellow, ConsoleColor.Cyan, ConsoleColor.White, ConsoleColor.Magenta }; // int szin = 0; for (int i = 0; i < N; i++) { szin = i; for (int j = 0; j < N; j++) { Console.ForegroundColor = color[szin]; Console.Write("{0,4}", m[i, j]); szin++; if (szin >= N) szin = 0; } Console.WriteLine(); } }
13.10. forráskód. Balra-le törtátlók
static void panmagikus_kiir_A(int[,] m) { int N = m.GetLength(0); ConsoleColor[] color = new ConsoleColor[] { ConsoleColor.Red, ConsoleColor.Green, ConsoleColor.Yellow, ConsoleColor.Cyan, ConsoleColor.White, ConsoleColor.Magenta }; // int szin = 0; for (int i = 0; i < N; i++) { szin = i; for (int j = 0; j < N; j++) { Console.ForegroundColor = color[szin]; Console.Write("{0,4}", m[i, j]); szin++; if (szin >= N) szin = 0; } Console.WriteLine(); } }
A színek váltogatása során ismertetett módszer egyúttal a törtátlók szummájának képzéséhez is szükséges. A 13.51. forráskódban a két törtátlós összegek képzése és összehasonlítása történik meg. Ne feledjük azonban, hogy ezenfelül szükséges még a sorok és az oszlopok összegeinek ellenőrzése is (valamint a sorok és oszlopok összegeinek is egyezniük kell a törtátlók összegeivel)!
13.11. forráskód. Törtátlókban található összegek képzése és összehasonlítása
static bool panmagikus_ell(int[,] m) { int N = m.GetLength(0); int[] sum1 = new int[N]; int[] sum2 = new int[N]; // int i1, i2; for (int i = 0; i < N; i++) { i1 = i; i2 = N - i - 1; for (int j = 0; j < N; j++) { sum1[i1] = sum1[i1] + m[i, j]; sum2[i2] = sum2[i2] + m[i, j]; i1++; if (i1>= N) i1= 0; i2++; if (i2 >= N) i2 = 0; } } // for (int i = 1; i < N; i++) if (sum1[i] != sum1[0]) return false; for (int i = 1; i < N; i++) if (sum2[i] != sum2[0]) return false; if (sum1[0] != sum2[0]) return false; // minden ok return true; }
Bevezető információk: Az ördögkeretek[4] olyan (nagyobb méretű) mágikus négyzetek, melyek külső keretét eltávolítva szintén mágikus négyzetet kapunk – tehát mágikus négyzetek vannak egymásba ágyazva. Értelemszerűen ezen kisebb méretű mágikus négyzet kulcsértéke is kisebb, mivel a keretet alkotó értékek már nem szerepelnek a sorok és oszlopok összegszámításában. Érdekesebb esetben ez az egymásba ágyazás több szinten is előfordulhat, mígnem egy olyan belső mátrixhoz jutunk el, amire már nem teljesül, hogy ő is egy önálló mágikus négyzet. A 13.6. ábrán egy 12-ed rendű ördögkeret látható.
13.5. feladat (Ördögkeretek – szint: 4). Írjunk olyan programot, amely beolvas egy fájlból egy
méretű mátrixot, és meghatározza, hogy milyen mélységben tartalmaz mágikus négyzeteket egymásba ágyazva! Ha ez a szám 0, akkor már a kiinduló mátrix sem volt mágikus négyzet.
Magyarázat: Ehhez 13.2 feladatban leírt mágikus négyzet ellenőrzése módszert kell kiterjeszteni, hogy ne a teljes mátrixra, csak annak egy részére terjedjen ki az ellenőrzés. Ez a módosítás nemcsak a fő ellenőrző függvényt (buvos_negyzet_e) érinti, hanem a belőle hívott segédfüggvényeket is.
13.12. forráskód. Bűvös négyzet – „buvos_negyzet_e_2”
static bool magikus_negyzet_e_2(int[,] m,int eltolas) { int N = m.GetLength(0) - 2 * eltolas; int[] sorok = new int[N]; int[] oszlopok = new int[N]; osszegekGen2(m, sorok, oszlopok, eltolas); // sorok, oszlopok osszegei if (mindEgyenlo(sorok) == false || mindEgyenlo(oszlopok) == false || sorok[0] != oszlopok[0]) return false; // atlok osszegei int atlo1, atlo2; atlokGen2(m, out atlo1, out atlo2,eltolas); if (atlo1 != atlo2 || atlo1 != sorok[0]) return false; // egyediseg for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (megszamol2(m, m[i, j],eltolas) != 1) return false; // minden rendben return true; }
13.13. forráskód. Bűvös négyzet – „osszegekGen2”
static void osszegekGen2(int[,] m,int[] sorok,int[] oszlopok,int eltolas) { for (int i = 0; i < sorok.Length; i++) for (int j = 0; j < oszlopok.Length; j++) { sorok[i] = sorok[i] + m[i + eltolas, j + eltolas]; oszlopok[j] = oszlopok[j] + m[i + eltolas, j + eltolas]; } }
13.14. forráskód. Bűvös négyzet – „mindEgyenlo”
static bool mindEgyenlo(int[] l) { int x = l[0]; foreach (int a in l) if (x != a) return false; return true; }
13.15. forráskód. Bűvös négyzet – „atlokGen2”
static void atlokGen2(int[,] m, out int a, out int b, int eltolas) { a = 0; b = 0; int N = m.GetLength(0); for (int i = 0; i < N; i++) { a = a + m[i + eltolas, i + eltolas]; b = b + m[i + eltolas, N - i - 1 - +eltolas]; } }
13.16. forráskód. Bűvös négyzet – „megszamol2”
static int megszamol2(int[,] m, int x, int eltolas) { int N = m.GetLength(0)-eltolas; int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i+eltolas, j+eltolas] == x) db++; return db; }
Bevezető információk: Az olyan 
méretű mátrixok, amelyekben minden
szám szerepel 
intervallumból, s melyeknél a sorok, az oszlopok és az átlókban
szereplő összegek különbözőek: antimágikus négyzetnek nevezzük. Bizonyítható, hogy nem
létezik 
, 
, 
méretű anti mágikus
négyzet.
13.6. feladat (Antimágikus négyzet ellenőrzése – szint: 2). Egy
méretű kitöltött mátrixot ellenőrizzünk le, hogy antimágikus négyzet-e! Az ellenőrzés után jelenítsük meg a mátrixot a képernyőn, minden sorhoz és oszlophoz jelenítsük meg az összegeket, a főátló és a mellékátló összegét is! Az ellenőrzés eredményét írjuk vörös színnel, ha nem felelt meg, és zölddel, ha megfelelt!
Magyarázat: A főprogramban (a 13.57. forráskód) a mátrixot az alapadatokal történő
feltöltés után megjelenítjük a képernyőn. A 13.59. forráskódban egy
intelligens megjelenítő függvényt készítettünk, amely maga számolja ki a sor- és
oszlopösszegeket, valamint az átlók összegét (semmit sem bízván a véletlenre). A
sorok összegét kiírás közben számolja a sum változóba, és minden sor kiírásának
végén azt meg is jeleníti. Az oszlopösszegeket a oszlopok vektorban számolja, mert az
csak a legalsó sor kiírása után lesz látható. A főátlóbeli összeget a jobb sarokban
jeleníti meg, a foatlo változó alapján. A mellékátló összegét az alsó sorban, az
oszlopátlók előtt írja ki. A vizsgálatot a 13.58. forráskódban szereplő
anti_buvos_negyzet_e függvény végzi. A sorok összege N, az oszlopok összege is N, a főátlóbeli és
a mellékátlóbeli elemek összege 2 darab szám, így összesen 2 * N + 2 összeget kell kiszámítani,
ezért készül az osszegek vektor ezzel a mérettel el. Az első N elemében szerepelnek
majd a sorok összegei, a további N elemében az oszlopok, az utolsó előtti a főátló,
az utolsó a mellékátló összege. A vektor feltöltése után ellenőrizzük, hogy van-e az
összegek között két egyforma. Ha idáig minden rendben, akkor még azt is ellenőrizni kell,
hogy minden szám szerepel-e az 
intervallumból, mindegyik pontosan
egyszer.
13.17. forráskód. Anti bűvös négyzet-e – teszt főprogram
static void Main() { const int N = 5; int[,] m = new int[N, N]; // kezdo feltoltes int a = 1; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { m[i, j] = a; a++; } // Magikus_Kiiras_2(m); // Console.SetCursorPosition(0, N + 2); if (anti_magikus_negyzet_e(m) == false) { Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine("NEM ANTI-MAGIKUS NEGYZET"); } else { Console.ForegroundColor = ConsoleColor.Green; Console.WriteLine("IGENIS ANTI-MAGIKUS NEGYZET"); } Console.ReadLine(); }
13.18. forráskód. Anti bűvös négyzet-e – az ellenőrző függvény
static bool anti_magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2*N+2]; // az osszegek kepzese for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { // i. sor osszege osszegek[i] = osszegek[i] + m[i, j]; // j. oszlop osszege osszegek[N+j] = osszegek[i] + m[i, j]; // foatlo osszege if (i==j) osszegek[2 * N] = osszegek[2*N] + m[i, j]; // mellekatlo osszege if (i == N-j-1) osszegek[2 * N+1] = osszegek[2 * N+1] + m[i, j]; } // van-e ket egyforma osszeg ? for (int i = 0; i < osszegek.Length; i++) for (int j = i + 1; j < osszegek.Length; j++) if (osszegek[i] == osszegek[j]) return false; // minden szam szerepel? for (int k = 1; k <= N * N; k++) { int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i, j] == k) db++; if (db != 1) return false; } // minden ok return true; }
13.19. forráskód. Anti bűvös négyzet-e – mátrix megjelenítés
static void Magikus_Kiiras(int[,] m) { int N = m.GetLength(0); int[] oszlopok = new int[N]; int foatlo = 0; int mellekatlo = 0; // // for (int i = 0; i < N; i++) { Console.ForegroundColor = ConsoleColor.Yellow; int sum = 0; Console.Write(" "); for (int j = 0; j < N; j++) { Console.Write("{0,3} ", m[i, j]); // sum = sum + m[i, j]; oszlopok[j] = oszlopok[j] +m[i, j]; if (i==j) foatlo=foatlo+m[i,j]; if (i == N - j - 1) mellekatlo = mellekatlo + m[i, j]; } // Console.ForegroundColor = ConsoleColor.Cyan; Console.Write("{0,4} ", sum); Console.WriteLine(); } // Console.ForegroundColor = ConsoleColor.Green; Console.Write("{0,3} ", mellekatlo); Console.ForegroundColor = ConsoleColor.Cyan; for (int j = 0; j < N; j++) Console.Write("{0,3} ", oszlopok[j]); Console.ForegroundColor = ConsoleColor.Green; Console.Write("{0,3} ", foatlo); Console.ForegroundColor = ConsoleColor.Gray; }
13.7. feladat (Antimágikus négyzet generálása – szint: 2). Generáljunk egy
méretű mátrixot oly módon, hogy a végeredménye antimágikus négyzet legyen!
Magyarázat: A generálás során először feltöltjük a mátrixot módszeresen 
közötti értékekkel. Majd kiszámítjuk a sorok, oszlopok, átlók összegeit az előző
feladatban ismertetett módon egy 2 * N + 2 méretű vektorba. Megkeressük, melyik két
összeg egyenlő egymással. Ha nincs egyenlőség, akkor készen vagyunk. Ha találunk
egyenlőséget, akkor választunk egy cellát a problémás sorból/oszlopból/átlóból, valamint
egy véletlen cellát a mátrix tetszőleges helyéről. A két cellában lévő értéket
felcseréljük.
Ezt addig ismételjük, amíg már nem lesz egyenlőség sehol. A mátrix megjelenítésén is finomítottunk: amelyik két összeg egyenlő egymással, azokat piros színnel jelenítjük meg. Valamint kiírásra kerül az is, hogy hány cserét kellett elvégezni, hogy a kívánt eredményt elérjük. Ez általában kevés csere, mivel a mátrix kezdeti feltöltése majdnem megfelelő. Ezért azzal bonyolítottuk a megoldást, hogy a kezdeti feltöltés után sok cserét hajtottunk végre a mátrix cellái között, hogy egy összekevert kezdő állapotot elérjünk. A mátrix ezen állapota is elég kedvező az antimágikus négyzet kiindulási állapotához, mert ezek után sincs szükség sok cserére. Úgy tűnik, ilyen négyzetek előállítása könnyű. A 13.60. ... 13.65. közötti forráskódok fedik le a megoldást.
13.20. forráskód. Anti bűvös négyzet generálás – főprogram
static void Main() { const int N = 8; int[,] m = new int[N, N]; int[] osszegek = new int[2 * N + 2]; kezdoFeltoltes(m); osszekeveres(m, N * N * 40); // ulong fdb = 0; while (true) { int i, j; osszegekSzamol(m, osszegek); if (egyformaIndexek(osszegek, out i, out j)) { int a, b, c, d; valasztElem(i, out a, out b, N); c = rnd.Next(0, N); d = rnd.Next(0, N); // csere int x = m[a, b]; m[a, b] = m[c, d]; m[c, d] = x; } else break; // folyamat kozbeni kijelzes if (fdb % 100000 == 0) { Console.Clear(); Magikus_Kiiras_2(m); Console.SetCursorPosition(0, N + 1); Console.Write(fdb); } fdb++; } // Console.Clear(); Magikus_Kiiras_2(m); Console.SetCursorPosition(0, N + 2); Console.WriteLine("{0} | K É S Z ! ", fdb); Console.ReadLine(); }
13.21. forráskód. Anti bűvös négyzet generálás – az összegek számítása
static void osszegekSzamol(int[,] m, int[] osszegek) { int N = m.GetLength(0); for (int i = 0; i < osszegek.Length; i++) osszegek[i] = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { // i. sor osszege osszegek[i] = osszegek[i] + m[i, j]; // j. oszlop osszege osszegek[N + j] = osszegek[i] + m[i, j]; // foatlo osszege if (i == j) osszegek[2 * N] = osszegek[2 * N] + m[i, j]; // mellekatlo osszege if (i == N - j - 1) osszegek[2 * N + 1] = osszegek[2 * N + 1] + m[i, j]; } }
13.22. forráskód. Anti bűvös négyzet generálás – mátrix megjelenítése v2
static void Magikus_Kiiras_2(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); int x,y; egyformaIndexek(osszegek, out x, out y); // Console.ForegroundColor = ConsoleColor.Yellow; for (int i = 0; i < N; i++) { Console.Write(" "); for (int j = 0; j < N; j++) { Console.ForegroundColor = ConsoleColor.Yellow; Console.Write("{0,3} ", m[i, j]); } Console.WriteLine(); } // sorok osszegei for(int i=0;i<N;i++) { if (i==x || i==y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(N*4+4,i); Console.Write("{0,3} ", osszegek[i]); } // oszlopok osszegei for (int i = 0; i < N; i++) { if (i+N == x || i+N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(4+i*4, N); Console.Write("{0,3} ", osszegek[i+N]); } // foatlo if (2*N == x || 2*N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(4 + N * 4, N); Console.Write("{0,3} ", osszegek[2*N]); // mellektalo if (2 * N+1 == x || 2 * N+1 == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(0, N); Console.Write("{0,3} ", osszegek[2 * N+1]); }
13.23. forráskód. Anti bűvös négyzet generálás – elem választása
static void valasztElem(int i, out int a, out int b, int N) { // i egy sor indexe if (i < N) { a = i; b = rnd.Next(0, N); return; } // i egy oszlop indexe if (i < 2*N) { a = rnd.Next(0, N); b = i-N; return; } // i a foatlo if (i == 2 * N) { a = rnd.Next(0, N); b = a; return; } // i a mellekatlo a = rnd.Next(0, N); b = N - a - 1; }
13.24. forráskód. Anti bűvös négyzet generálás – mátrix kezdőfeltöltése
static void kezdoFeltoltes(int[,] m) { int N = m.GetLength(0); int k = 1; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { m[i, j] = k; k++; } }
13.25. forráskód. Anti bűvös négyzet generálás – elem összekeverése
static void osszekeveres(int[,] m, int db) { int N = m.GetLength(0); while (db > 0) { int x = rnd.Next(0, N); int y = rnd.Next(0, N); int v = rnd.Next(0, N); int w = rnd.Next(0, N); // int c = m[x, y]; m[x, y] = m[v, w]; m[v, w] = c; // db--; } }
13.8. feladat (Antimágikus négyzet befejezése – szint: 3). Egy text fájlból olvassunk be egy
mátrixot, melynek bizonyos celláiban a 0 érték fog szerepelni! Ezen 0 értékeket tekintsük úgy, mintha a mátrix ezen a ponton még kitöltetlen lenne! Fejezzük be az antimágikus négyzetet oly módon, hogy a kitöltetlen cellákba
közötti számokat helyezünk! Ügyeljünk arra, hogy a feladat esetleg megoldhatatlan! Ha ha a kitöltött cellákban ismétlődés szerepel, vagy van teljesen kitöltött sor, oszlop, átló, melyek valamelyikében a benne szereplő értékek összege megegyezik, akkor nem lehetséges a definíciónak megfelelni.
Magyarázat: A mátrix kitöltetlen celláiba eleve olyan értékeket kell elhelyezni az 
értékekből, amelyek még nem szerepeltek benne. A továbbiakban az előző feladatban ismertetett
módon hajthatunk végre cseréket a mátrixon belül, csak arra kell ügyelnünk, hogy a kitöltött
cellákat kihagyjuk. Ez azonban nem is olyan egyszerű. A valasztElem függvényt alaposan
módosítani kell, ha például egy teljes kitöltött sorból kellene neki véletlen cellát
választani, akkor az nem sikerülhet. Emiatt Main függvényben is alaposan át kell gyúrni ezt a
részt.
Külön problémát okoz, hogyan különítjük el a fixen kitöltött cellákat a kitöltetlenektől. Ennek támogatásához bevezettünk egy fix nevű logikai mátrixot, melyben a benne lévő érték true, ha a cella fixen kitöltött, false ha szabadon módosítható. A mágikus négyzetet megjelenítő eljárást is módosítottuk, hogy a fix cellákat más színnel jelenítse meg, mint a szabad cellákat.
A program a fájl beolvasása után megjeleníti a kitöltött és kitöltetlen cellákat (a fix cellákat zöld alapon feketével). Majd kitölti a maradék cellákat a soron következő sorszámokkal, és ezt az állapotot is megjeleníti, végül megpróbálja megoldani a feladatot. A 13.74. és a 13.73. forráskódok olyan szinten fedik le a feladatot, hogy a megoldhatatlansági kérdéssel nem foglalkozunk.
A Main függvény először beolvassa a fájl tartalmát, majd befejezi a kitöltést. A továbbiakban hasonlóan működik, mint az előző feladatban leírtak.
A beolvasas függvény a leírtak szerint beolvassa a mátrix tartalmát a text fájlból, és közben párhuzamosan beállítja a fix logikai mátrix celláinak értékeit is.
A matrixBefejez függvény a nem kitöltött cellákba rak értékeket az
intervallumból.
A kovNemSzereplo függvény megkeresi k-tól kiindulva a következő, a mátrixban még nem szereplő számértéket.
A Buvos_Kiiras_3 függvény hasonlóan a korábbiakhoz színesen kiírja a mátrix elemeit, valamint a sorok, oszlopok, átlók összegeit. A fix cellákat színes háttérrel, a közönséges cellákat fekete háttérrel jeleníti meg.
A valasztElem2 függvény az egymással ütköző i vagy j sorból választ cellát, ügyelve arra, hogy ne válasszunk fix cellát.
13.26. forráskód. Anti bűvös négyzet generálás – elem összekeverése
static void Main() { int[,] m; bool[,] fix; beolvasas(out m,out fix,@"hianyos-anti-magikus-negyzet.txt"); int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; Console.Clear(); Magikus_Kiiras_3(m, fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot beolvasva (nyomj le egy billt)"); Console.ReadLine(); // matrixBefejez(m); Console.Clear(); Magikus_Kiiras_3(m, fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot befejezve (nyomj le egy billt)"); Console.ReadLine(); // ulong fdb = 0; while (true) { int i, j; osszegekSzamol(m, osszegek); if (egyformaIndexek(osszegek, out i, out j)) { int a, b, c, d; valasztElem2(i, j,out a, out b, N, fix); while (true) { c = rnd.Next(0, N); d = rnd.Next(0, N); if (fix[c, d] == false) break; } int x = m[a, b]; m[a, b] = m[c, d]; m[c, d] = x; } else break; if (fdb % 100000 == 0) { Console.Clear(); Magikus_Kiiras_3(m,fix); Console.SetCursorPosition(0, N + 1); Console.Write(fdb); } fdb++; } // Console.Clear(); Magikus_Kiiras_3(m,fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("{0} | K É S Z ! ", fdb); Console.ReadLine(); }
13.27. forráskód. Anti bűvös négyzet generálás – beolvasás
static void beolvasas(out int[,] m, out bool[,] fix, string fnev) { m = null; fix = null; int N = 0; int i = 0; System.IO.StreamReader r = new System.IO.StreamReader(fnev, System.Text.Encoding.Default); while (!r.EndOfStream) { string s = r.ReadLine().Trim(); string[] ss = s.Split(’ ’); if (m == null) { N = ss.Length; m = new int[N, N]; fix = new bool[N, N]; } if (ss.Length != N) throw new Exception("File feldolgozasi hiba"); if (i>=N) throw new Exception("Tul sok sor a file-ban"); for (int j = 0; j < N; j++) { m[i, j] = int.Parse(ss[j]); fix[i, j] = (m[i, j] != 0); } i++; } r.Close(); if (m==null) throw new Exception("File ures volt"); }
13.28. forráskód. Anti bűvös négyzet generálás – a maradék cellák kitöltése
static void matrixBefejez(int[,] m) { int N = m.GetLength(0); int k = 1; for(int i=0;i<N;i++) { for (int j = 0; j < N; j++) { if (m[i, j] == 0) { k = kovNemSzereplo(m, k); m[i, j] = k; } } } }
13.29. forráskód. Anti bűvös négyzet generálás – következő még nem szereplő érték keresése
static int kovNemSzereplo(int[,] m, int k) { int N = m.GetLength(0); while (true) { int db = 0; for (int i = 0; i < N && db==0; i++) for (int j = 0; j < N && db == 0; j++) if (k == m[i, j]) db++; if (db == 0) return k; k++; } }
13.30. forráskód. Anti bűvös négyzet generálás – megjelenítés
static void Magikus_Kiiras_3(int[,] m, bool[,] fix) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); int x,y; egyformaIndexek(osszegek, out x, out y); // Console.ForegroundColor = ConsoleColor.Yellow; for (int i = 0; i < N; i++) { Console.Write(" "); for (int j = 0; j < N; j++) { if (fix[i, j]) { Console.BackgroundColor = ConsoleColor.Green; Console.ForegroundColor = ConsoleColor.Black; } else { Console.BackgroundColor = ConsoleColor.Black; Console.ForegroundColor = ConsoleColor.Yellow; } Console.Write("{0,3} ", m[i, j]); Console.BackgroundColor = ConsoleColor.Black; } Console.WriteLine(); } // sorok osszegei for(int i=0;i<N;i++) { if (i==x || i==y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(N*4+4,i); Console.Write("{0,3} ", osszegek[i]); } // oszlopok osszegei for (int i = 0; i < N; i++) { if (i+N == x || i+N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(4+i*4, N); Console.Write("{0,3} ", osszegek[i+N]); } // foatlo if (2*N == x || 2*N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(4 + N * 4, N); Console.Write("{0,3} ", osszegek[2*N]); // mellektalo if (2 * N+1 == x || 2 * N+1 == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(0, N); Console.Write("{0,3} ", osszegek[2 * N+1]); Console.ForegroundColor = ConsoleColor.Gray; }
13.31. forráskód. Anti bűvös négyzet generálás – cserélendő cellák választása
static void valasztElem2(int i, int j,out int a, out int b, int N, bool[,] fix) { while (true) { valasztElem(i, out a, out b, N); if (fix[a, b] == false) return; valasztElem(j, out a, out b, N); if (fix[a, b] == false) return; } }
Bevezető információk: A szép antimágikus négyzetek alatt értsük azt az eset, amikor az egyes sorokban szereplő értékek egymást követő természetes számok, valamint (hasonlóan) az oszlopokban szereplő értékek összegei is egymást követő természetes számok!
13.9. feladat (Szép antimágikus négyzet ellenőrzése – szint: 2). Készítsünk olyan függvényt, amely beolvas fájlból egy
méretű mátrixot, majd ellenőrzi, hogy az szép antimágikus négyzet-e!
Magyarázat: A 13.68. függvény képes beolvasni mátrixot fájlból. A 13.58. függvény képes eldönteni, hogy antimágikus négyzet-e. A 13.61. forráskódban bemutatott osszegekSzamol függvény képes előállítani a sorok és oszlopok összegeit. Az összegek ellenőrzése ettől kezdve már nem nehéz (lásd a 13.74. forráskód).
13.32. forráskód. Szép anti bűvös négyzet ellenőrzés
static bool szep_magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); // sorok osszegei for (int i = 1; i < N; i++) if (osszegek[i - 1] != osszegek[i] + 1) return false; // oszlopok osszegei for (int i = N; i < 2*N; i++) if (osszegek[i - 1] != osszegek[i] + 1) return false; // minden rendben return true; }
Bevezető információk: A magyar kártyában négy szín (piros, zöld, makk, tök) fordul elő, mindegyik színből van számozott (7...10) és figurás (alsó, felső, király, ász) lap, így összesen 32 lapos. Figurás lapokból 4 különböző van, ha mind a 4 szín figurás lapjait összeszedjük, akkor pontosan 16 lapot kapunk.
13.10. feladat (Kártyaalapú mágikus négyzet – szint: 3). Helyezzük el a magyar kártya figurás lapjait egy 4 x 4-es mágikus négyzetben úgy, hogy minden sorban, minden oszlopban, valamint a két átlóban is különböző színű és különböző figurás lapok legyenek!
Magyarázat: Természetesen konzolos felületen nem lehet ilyen szép outputot generálni, mint amit a 13.11. ábrán láthatunk. Alkalmazzunk kódolást a kártyákra. Jelöljük 11, 12, 13, 14-gyel a piros színű alsó, felső, király, ász lapokat! Hasonlóan 21, 22, 23, 24 értékekkel a zöld alsó, felső, király, ász, 31, 32, 33, 34-gyel a makk, 41, 42, 43, 44 értékkel a tök színű lapokat. A szabályt ekkor úgy fogalmazhatjuk meg: egyetlen sorban, oszlopban, átlóban sem fordulhat elő két olyan számérték, melyeknek 10-zel való egész vagy maradékos osztásának eredménye egyenlő. Ha a 10-zel való egész osztás eredménye egyenlő lenne, akkor az egyforma színt jelentene. Ha a modulo 10 értéke egyenlő, akkor az egyforma figurát jelentene.
Készítsük el a mátrix egy alapkitöltését, helyezzük el benne az összes számértéket módszeresen sorfolytonosan! Az így feltöltött mátrix nyilván nem felel meg a feltételeknek. Válasszunk ki két cellát véletlenszerűen, és cseréljük fel a bennük lévő értékeket, mindaddig, míg meg nem kapjuk a kért tulajdonságú végeredményt! Ez lényegében egyezik az antimágikus négyzet generálásánál bemutatott módszerrel.
Sajnos gyakorlatilag reménytelen, hogy a véletlen cserék révén helyes mátrixot kapjunk. Ezért hasonlóan, most is meg kell keresnünk, melyik sorok vagy mely oszlopok hiúsítják meg a kívánt végeredmény elérését, azon belül melyik két cella okozza a konfliktust. Elegendőek az egyik problémás cella koordinátái. Válasszunk hozzá véletlenszerűen egy másik cellát a mátrixból, és cseréljük fel e két cella tartalmát! A módszer elvileg működőképes, de gyakorlatilag nem lehet megmondani, mennyi időbe kerül. A futási idő egy dupla magos gépen futtatva körülbelül 3 perc és 5 perc között változott. A program outputja a 13.76. ábrán látható, a 13.75. ... 13.82. forráskódok tartalmazzák a megoldást.
13.33. forráskód. Kártyás – főprogram
static void Main() { const int N = 4; int[,] m = new int[N,N]; kezdoFeltoltes(m); ulong fdb = 0; int v,w; DateTime start = DateTime.Now; while (matrixRendben(m, out v, out w ) == false) { int x = rnd.Next(0, N); int y = rnd.Next(0, N); // int c = m[x, y]; m[x, y] = m[v, w]; m[v, w] = c; // // fdb++; // if (fdb % 1000000 == 0) Megjelenit(m); } DateTime stop = DateTime.Now; TimeSpan kul = stop - start; Megjelenit(m); Console.WriteLine(); Console.WriteLine(); Console.ForegroundColor = ConsoleColor.Gray; Console.WriteLine("Futasi ido={0}", kul); Console.ReadLine(); }
13.34. forráskód. Kártyás – megjelenítés
static void Megjelenit(int[,] m) { Console.Clear(); int N = m.GetLength(0); ConsoleColor[] szinek = new ConsoleColor[] { ConsoleColor.Green, ConsoleColor.Red, ConsoleColor.Cyan, ConsoleColor.Yellow}; string[] lapok = new string[] { "also", "felso", "kiraly", "asz" }; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Console.SetCursorPosition(j * 8, i * 2); int x = m[i, j]; int v = x / 10 - 1; int w = x % 10 - 1; Console.ForegroundColor = szinek[v]; Console.Write(lapok[w]); } } }
13.35. forráskód. Kártyás – a mátrix megfelelőségének ellenőrzése
static bool matrixRendben(int[,] m, out int k, out int l) { k = -1; l = -1; int N = m.GetLength(0); for (int i = 0; i < N; i++) { if (sorRendben(m, i, N, out l) == false) { k = i; return false; } if (oszlopRendben(m, i, N, out k) == false) { l = i; return false; } } if (atlokRendben(m, N,out k, out l) == false) return false; return true; }
13.36. forráskód. Kártyás – átlók megfelelőségének ellenőrzése
static bool atlokRendben(int[,] m, int N, out int v, out int w) { v = -1; w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) { if (hasonlo(m[i, i], m[j, j])) { v = i; w = i; return false; } if (hasonlo(m[i, N - i - 1], m[j, N - j - 1])) { v = i; w = N - i - 1; return false; } } // return true; }
13.37. forráskód. Kártyás – a mátrix k. oszlopának ellenőrzése
static bool oszlopRendben(int[,] m, int k, int N, out int w) { w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) if (hasonlo(m[i, k], m[j, k])) { w = i; return false; } // return true; }
13.38. forráskód. Kártyás – a mátrix k. sorának ellenőrzése
static bool sorRendben(int[,] m, int k, int N, out int w) { w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) if (hasonlo(m[k, i], m[k, j])) { w = i; return false; } // return true; }
13.39. forráskód. Kártyás – két cella színének és lapjának vizsgálata
static bool hasonlo(int a, int b) { if (a / 10 == b / 10 || a % 10 == b % 10) return true; return false; }
13.40. forráskód. Kártyás – a mátrix kezdő feltöltése
static void kezdoFeltoltes(int[,] m) { int N = m.GetLength(0); for (int i = 0; i < N; i++) { int k = (i+1)*10+1; for (int j = 0; j < N; j++) { m[i, j] = k; k++; } } }
Bevezető információk: Egy 
mátrixot latin négyzetnek nevezünk, ha minden
sorában és minden oszlopában – tetszőleges sorrendben – ugyanaz az N darab szám áll, de
mindegyik csak egyszer.
Tehát nem kell a mágikus négyzetekhez hasonlóan minden mezőbe különböző számot írni, és – általában – az átlókra sincs kikötés.
13.11. feladat (Latin négyzet – szint: 2). Generáljunk egy
méretű latin négyzetet, ahol N értékét a program indulásakor a felhasználó adja meg! A generált négyzetet táblázatos alakban írjuk ki a latin-negyzet.txt fájlba!
Magyarázat: Ez utóbbi könnyítések miatt a latin négyzetek kitöltése rendkívül egyszerű: az első sorba írjuk tetszőleges sorrendben az 1, 2, ..., n számokat, majd lefelé haladva a következő sorba – a sorrendet megtartva – eggyel jobbra (vagy balra) tolva írjuk le, azaz ciklikusan permutáljuk. A megoldás a 13.83. forráskódban olvasható.
Bevezető információk: A matematikában egy mágikus négyzetet másodfokúnak[5] nevezhetünk, ha mágikus négyzet marad akkor is, ha a benne szereplő minden n számot négyzetre emeljük. Harmadfokúnak[6] nevezhetjük, ha minden számot harmadik hatványára emelve az szintén mágikus négyzet marad. A harmadfokúak nem feltétlenül másodfokúak. Általában véve, k-ad fokúnak nevezünk egy mágikus négyzetet, ha minden számot k. hatványra emelve szintén egy mágikus négyzetet kapunk.
13.12. feladat (K-ad fokú mágikus négyzetek – szint: 2). Készítsünk olyan függvényt, amely egy adott
méretű mágikus négyzetről eldönti, hogy még milyen k-ad fokú mágikus négyzet is egyben! A függvény kimenete egy lista, melyben a k értékei szerepelnek. Ez a lista legyen üres, ha a mágikus négyzetünk semmilyen k értékre nem k-ad fokú! A k értékeit [1 ... 10] között vizsgálja a program!
Magyarázat: A feladat nagyon egyszerű. A 13.43. kódban megadott ellenőrző függvény képes ellenőrizni, hogy egy m mátrix mágikus négyzet-e. Mindössze elő kell állítani a mátrixelemek különböző hatványát, és alkalmazni kell az ellenőrző függvényt (lásd a 13.84. forráskódot).
Bevezető információk: Egy négyzetet bűvös négyzetnek nevezünk, ha mágikus négyzet, és az
N
N méretű mátrix celláiban az összes 
szám szerepel
(13.87. ábra).
13.13. feladat (Bűvös négyzet-e – szint: 2). Készítsünk programot, amely egy
méretű mátrixot beolvas fájlból, majd eldönti, hogy a mátrix bűvös négyzet-e!
Magyarázat: A 13.43. forráskódban leírt mágikusnégyzet-ellenőrző függvényt kell
annyiban bővíteni, hogy 
közötti minden szám szerepel-e a mátrixban (pontosan
egyszer szerepel-e). Mivel a mátrix mérete is 
, így ha minden szám szerepel a szóban
forgó intervallumból, akkor egyúttal pontosan egyszer szerepel. A plusz ellenőrzés kódja (melyet be
lehet szúrni a 13.43. kódban megadott függvény belsejébe) a 13.85.
forráskódban olvasható.
Bevezető információk: A misztikus négyzetek előállításának több módszere is van. Általában külön szokták venni a páros és a páratlan N méretű mátrixok előállítási módszereit. Ha N páratlan, akkor a huszármódszerrel próbálkozhatunk. Ennek során írjuk be a mátrix tetszőleges pontjára az 1 értéket, majd a sakkban ismert huszár L lépési technikájával lépjünk 2-t fel 1-et jobbra, és ide írjuk a következő számot! Ha eközben kilépnénk a mátrixból, akkor úgy kell kezelni a cellát, hogy ott is egy ugyanilyen mátrix áll, és az abba eső pozíciót kell az itteni mátrixban felölteni. Ha az a cella már foglalt, akkor a lóugrás kiindulási pontja alatti cellába kell írni (lásd a 13.14. és a 13.15. ábrák).
13.14. feladat (Huszármódszer – szint: 4). Kérjük be N értékét billentyűzetről,
, és páratlan. Készítsük el az
méretű misztikus mátrixot a huszármódszerrel, jelenítsük meg táblázatos alakban a képernyőn, és ellenőrízzük le, hogy valóban teljesíti-e a misztikus mátrixok tulajdonságait!
Az algoritmus alapján készült 13.86. forráskód tartalmazza a huszármódszer C# nyelvi kódját. Az utólagos ellenőrzést a 13.85. forráskódban található függvénnyel végezhetjük el. A program futását a 13.1. videón követketjük nyomon.
13.1. videó. A huszármódszer futási képernyője
Bevezető információk: Az ún. lépcsős módszer[7] nagyon sokban hasonlít a huszármódszerre, de ennek során felfele nem kettőt, csak 1-et kell lépni, és kezdőpontja kötelezően adott. Segítségével ugyanúgy páratlan N méretű bűvös négyzeteket lehet generálni. A módszer az alábbi lépésekből áll:
Írjuk be az 1 értéket a felső sor középső eleméhez!
Lépjünk fel és jobbra egy lépéssel, az ottani cellába! Ha közben kilépnénk a mátrixból, akkor ciklikusan balról
jobbra, fentről 
lefele kötve
a cellákat visszaléphetünk a mátrixba.
Ha üres a cella, akkor oda írjuk be a soron következő számot!
Ha a cella nem üres, akkor lépjünk az eredeti cellából lefele (ciklikusan ha alul kilépnénk, akkor fenn lépjünk be újra)!
Ismételjük a lépéseket, amíg az összes cella be nem telik!
Ha mindent jól csináltunk, a legmagasabb szám a mátrix legalsó sorának közepére fog esni (itt kell befejeznünk a generálást).
13.15. feladat (Lépcsős generáló módszer – szint: 2). Készítsünk olyan programot, amely bekéri N értékét, ahol
és N páratlan! Generáljunk bűvös négyzetet a lépcsős módszer segítségével, és jelenítsük meg a képernyőn táblázatos formában!
Magyarázat: Az algoritmus alapján a kód elkészítése nem különösebben nehéz (13.87. forráskód).
Bevezető információk: A mindennapi életben a keresztrejtvények szintjén a bűvös négyzetet sokkal szabadabban értelmezik. Ott gyakran csak egy olyan négyzetre gondolnak, melynek celláiban számok szerepelnek, mindegyik csak egyszer, és a sorok és oszlopok összegei egyeznek egy (az adott sorhoz és oszlophoz külön-külön megadott) értékkel. Tehát korántsem kikötés, hogy ezen oszlop- és sorösszegek egymással egyezzenek, illetve jellemzően nincs szó az átlókban szereplő összegekről. Ezen rejtvényfeladványok esetén a mátrixok kitöltését valahány elemig meg is adják, a feladvány csak ezen kezdemény jó befejezése. Ez persze papíron ceruzával ettől még igazi feladvány, melynek megoldása a fejben számolást mindenképpen fejleszti, de egyéb logikai képességeket is, és igazi sikerélményhez juttat.
13.16. feladat (Keresztrejtvény bűvös mátrixa – szint: 3). Egy
méretű mátrix kezdő feltöltését egy szöveges fájlban adjuk meg. A fájlban soronként N + 1 cella értéke szerepel, mely kétféle lehet: vagy egy szám szerepel (a cella értéke), vagy a nem kitöltött cellákat egy . (pont) karakter jelöli. Az utolsó szám a sorokban nem valamely cella értéke, hanem az adott sor elvárt sorösszege (és emiatt sosem pont, hanem konkrét szám szerepel ott). A mátrix méretét az első sorában szereplő számok és pont karakterek számából állapíthatjuk meg. A fájlban az N + 1 sorban a mátrix N oszlopának elvárt oszlopösszegei szerepelnek (emiatt itt csak N számérték szerepel, nem N + 1). A fájl további sorában újabb számok vannak szóközzel határolva, melyek mennyisége pontosan egyezik a korábban a mátrix nem kitöltött (pont karakterrel jelölt) celláinak számával. Ezen felhasználható számok listája alapján próbáljunk meg a kitöltetlen cellákba számokat írni oly módon, hogy a korábban megadott sor- és oszlopösszegek előálljanak! Minden felhasználható számot pontosan egyszer használhatunk fel valamely cella feltöltésére. A már kitöltött cellákban lévő számokat nem cserélhetjük ki. Ha a mátrix nem megoldható (nincs olyan feltöltés, mellyel a sor- és oszlopösszegek előállnak), akkor jelezzük (a feladat értelmezéséhez segítség a 13.84. ábra)!
Magyarázat: A feladat nagyban hasonlít a 13.8. feladatban leírt antimágikus négyzet
befejezéséhez. Ott is 
közötti kell számokkal kell kiegészíteni a mátrixot, el kell
különíteni a fixen rögzített cellákat a szabad celláktól. A különbség mindössze az, mikor kapunk
megfelelő kitöltést. A megoldással kapcsolatos C# függvények az 13.88...
13.94. forráskódokban olvashatóak. A program futását a 13.2. képernyőn
követhetjük nyomon.
13.2. videó. A keresztrejtvény-feladat megoldása
13.41. forráskód. Duplán sztochasztikusság ellenőrzése klasszikus megoldással
static bool duplan_sztochasztikus(int[,] m) { int N = m.GetLength(0); int M = m.GetLength(1); // minden eleme nemnegatív ? for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (m[i, j] < 0) return false; // sorosszeg mindenütt 1.0 ? for (int i = 0; i < N; i++) { double sum = 0.0; for (int j = 0; j < M; j++) sum = sum + m[i, j]; if (sum != 1.0) return false; } // oszlop osszegek mindenütt 1.0 ? for (int j = 0; j < M; j++) { double sum = 0.0; for (int i = 0; i < N; i++) sum = sum + m[i, j]; if (sum != 1.0) return false; } // minden rendben return true; }
13.42. forráskód. Duplán sztochasztikusság ellenőrzése optimalizált módon
static bool duplan_sztochasztikus_opt(int[,] m) { int N = m.GetLength(0); int M = m.GetLength(1); double[] sorok = new double[N]; double[] oszlopok = new double[M]; // matrix bejarasa for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (m[i, j] < 0) return false; sorok[i] = sorok[i] + m[i, j]; oszlopok[j] = oszlopok[j] + m[i, j]; } // ellenorzes for (int i = 0; i < N; i++) if (sorok[i]!=1.0) return false; for (int j = 0; j < M; j++) if (oszlopok[j] != 1.0) return false; // minden rendben return true; }
13.43. forráskód. Bűvös négyzet – „buvos_negyzet_e”
static bool magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] sorok = new int[N]; int[] oszlopok = new int[N]; osszegekGen(m, sorok, oszlopok); // sorok, oszlopok osszegei if (mindEgyenlo(sorok) == false || mindEgyenlo(oszlopok) == false || sorok[0] != oszlopok[0]) return false; // atlok osszegei int atlo1, atlo2; atlokGen(m, out atlo1, out atlo2); if (atlo1 != atlo2 || atlo1 != sorok[0]) return false; // egyediseg for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (megszamol(m, m[i, j]) != 1) return false; // minden rendben return true; }
13.44. forráskód. Bűvös négyzet – „osszegekGen”
static void osszegekGen(int[,] m, int[] sorok, int[] oszlopok) { for (int i = 0; i < sorok.Length; i++) for (int j = 0; j < oszlopok.Length; j++) { sorok[i] = sorok[i] + m[i, j]; oszlopok[j] = oszlopok[j] + m[i, j]; } }
13.45. forráskód. Bűvös négyzet – „mindEgyenlo”
static bool mindEgyenlo(int[] l) { int x = l[0]; foreach (int a in l) if (x != a) return false; return true; }
13.46. forráskód. Bűvös négyzet – „atlokGen”
static void atlokGen(int[,] m, out int a, out int b) { a = 0; b = 0; int N = m.GetLength(0); for (int i = 0; i < N; i++) { a = a + m[i, i]; b = b + m[i, N - i - 1]; } }
13.47. forráskód. Bűvös négyzet – „megszamol”
static int megszamol(int[,] m, int x) { int N = m.GetLength(0); int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i, j] == x) db++; return db; }
13.48. forráskód. A mátrix értékeinek ellenőrzése
bool mindegyikPrim = true; for(int i=0;i<N && mindegyikPrim;i++) { for(int j=0;j<M && mindegyikPrim;j++) { if (prim-e(m[i,j]==false) mindegyikPrim = false; } }
13.49. forráskód. Jobbra-le törtátlók
static void panmagikus_kiir_A(int[,] m) { int N = m.GetLength(0); ConsoleColor[] color = new ConsoleColor[] { ConsoleColor.Red, ConsoleColor.Green, ConsoleColor.Yellow, ConsoleColor.Cyan, ConsoleColor.White, ConsoleColor.Magenta }; // int szin = 0; for (int i = 0; i < N; i++) { szin = i; for (int j = 0; j < N; j++) { Console.ForegroundColor = color[szin]; Console.Write("{0,4}", m[i, j]); szin++; if (szin >= N) szin = 0; } Console.WriteLine(); } }
13.50. forráskód. Balra-le törtátlók
static void panmagikus_kiir_A(int[,] m) { int N = m.GetLength(0); ConsoleColor[] color = new ConsoleColor[] { ConsoleColor.Red, ConsoleColor.Green, ConsoleColor.Yellow, ConsoleColor.Cyan, ConsoleColor.White, ConsoleColor.Magenta }; // int szin = 0; for (int i = 0; i < N; i++) { szin = i; for (int j = 0; j < N; j++) { Console.ForegroundColor = color[szin]; Console.Write("{0,4}", m[i, j]); szin++; if (szin >= N) szin = 0; } Console.WriteLine(); } }
13.51. forráskód. Törtátlókban található összegek képzése és összehasonlítása
static bool panmagikus_ell(int[,] m) { int N = m.GetLength(0); int[] sum1 = new int[N]; int[] sum2 = new int[N]; // int i1, i2; for (int i = 0; i < N; i++) { i1 = i; i2 = N - i - 1; for (int j = 0; j < N; j++) { sum1[i1] = sum1[i1] + m[i, j]; sum2[i2] = sum2[i2] + m[i, j]; i1++; if (i1>= N) i1= 0; i2++; if (i2 >= N) i2 = 0; } } // for (int i = 1; i < N; i++) if (sum1[i] != sum1[0]) return false; for (int i = 1; i < N; i++) if (sum2[i] != sum2[0]) return false; if (sum1[0] != sum2[0]) return false; // minden ok return true; }
13.52. forráskód. Bűvös négyzet – „buvos_negyzet_e_2”
static bool magikus_negyzet_e_2(int[,] m,int eltolas) { int N = m.GetLength(0) - 2 * eltolas; int[] sorok = new int[N]; int[] oszlopok = new int[N]; osszegekGen2(m, sorok, oszlopok, eltolas); // sorok, oszlopok osszegei if (mindEgyenlo(sorok) == false || mindEgyenlo(oszlopok) == false || sorok[0] != oszlopok[0]) return false; // atlok osszegei int atlo1, atlo2; atlokGen2(m, out atlo1, out atlo2,eltolas); if (atlo1 != atlo2 || atlo1 != sorok[0]) return false; // egyediseg for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (megszamol2(m, m[i, j],eltolas) != 1) return false; // minden rendben return true; }
13.53. forráskód. Bűvös négyzet – „osszegekGen2”
static void osszegekGen2(int[,] m,int[] sorok,int[] oszlopok,int eltolas) { for (int i = 0; i < sorok.Length; i++) for (int j = 0; j < oszlopok.Length; j++) { sorok[i] = sorok[i] + m[i + eltolas, j + eltolas]; oszlopok[j] = oszlopok[j] + m[i + eltolas, j + eltolas]; } }
13.54. forráskód. Bűvös négyzet – „mindEgyenlo”
static bool mindEgyenlo(int[] l) { int x = l[0]; foreach (int a in l) if (x != a) return false; return true; }
13.55. forráskód. Bűvös négyzet – „atlokGen2”
static void atlokGen2(int[,] m, out int a, out int b, int eltolas) { a = 0; b = 0; int N = m.GetLength(0); for (int i = 0; i < N; i++) { a = a + m[i + eltolas, i + eltolas]; b = b + m[i + eltolas, N - i - 1 - +eltolas]; } }
13.56. forráskód. Bűvös négyzet – „megszamol2”
static int megszamol2(int[,] m, int x, int eltolas) { int N = m.GetLength(0)-eltolas; int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i+eltolas, j+eltolas] == x) db++; return db; }
13.57. forráskód. Antimágikus négyzet-e – teszt főprogram
static void Main() { const int N = 5; int[,] m = new int[N, N]; // kezdo feltoltes int a = 1; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { m[i, j] = a; a++; } // Magikus_Kiiras_2(m); // Console.SetCursorPosition(0, N + 2); if (anti_magikus_negyzet_e(m) == false) { Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine("NEM ANTI-MAGIKUS NEGYZET"); } else { Console.ForegroundColor = ConsoleColor.Green; Console.WriteLine("IGENIS ANTI-MAGIKUS NEGYZET"); } Console.ReadLine(); }
13.58. forráskód. Antimágikus négyzet-e – az ellenőrző függvény
static bool anti_magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2*N+2]; // az osszegek kepzese for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { // i. sor osszege osszegek[i] = osszegek[i] + m[i, j]; // j. oszlop osszege osszegek[N+j] = osszegek[i] + m[i, j]; // foatlo osszege if (i==j) osszegek[2 * N] = osszegek[2*N] + m[i, j]; // mellekatlo osszege if (i == N-j-1) osszegek[2 * N+1] = osszegek[2 * N+1] + m[i, j]; } // van-e ket egyforma osszeg ? for (int i = 0; i < osszegek.Length; i++) for (int j = i + 1; j < osszegek.Length; j++) if (osszegek[i] == osszegek[j]) return false; // minden szam szerepel? for (int k = 1; k <= N * N; k++) { int db = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (m[i, j] == k) db++; if (db != 1) return false; } // minden ok return true; }
13.59. forráskód. Antimágikus négyzet-e – mátrixmegjelenítés
static void Magikus_Kiiras(int[,] m) { int N = m.GetLength(0); int[] oszlopok = new int[N]; int foatlo = 0; int mellekatlo = 0; // // for (int i = 0; i < N; i++) { Console.ForegroundColor = ConsoleColor.Yellow; int sum = 0; Console.Write(" "); for (int j = 0; j < N; j++) { Console.Write("{0,3} ", m[i, j]); // sum = sum + m[i, j]; oszlopok[j] = oszlopok[j] +m[i, j]; if (i==j) foatlo=foatlo+m[i,j]; if (i == N - j - 1) mellekatlo = mellekatlo + m[i, j]; } // Console.ForegroundColor = ConsoleColor.Cyan; Console.Write("{0,4} ", sum); Console.WriteLine(); } // Console.ForegroundColor = ConsoleColor.Green; Console.Write("{0,3} ", mellekatlo); Console.ForegroundColor = ConsoleColor.Cyan; for (int j = 0; j < N; j++) Console.Write("{0,3} ", oszlopok[j]); Console.ForegroundColor = ConsoleColor.Green; Console.Write("{0,3} ", foatlo); Console.ForegroundColor = ConsoleColor.Gray; }
13.60. forráskód. Antimágikus négyzet generálása – főprogram
static void Main() { const int N = 8; int[,] m = new int[N, N]; int[] osszegek = new int[2 * N + 2]; kezdoFeltoltes(m); osszekeveres(m, N * N * 40); // ulong fdb = 0; while (true) { int i, j; osszegekSzamol(m, osszegek); if (egyformaIndexek(osszegek, out i, out j)) { int a, b, c, d; valasztElem(i, out a, out b, N); c = rnd.Next(0, N); d = rnd.Next(0, N); // csere int x = m[a, b]; m[a, b] = m[c, d]; m[c, d] = x; } else break; // folyamat kozbeni kijelzes if (fdb % 100000 == 0) { Console.Clear(); Magikus_Kiiras_2(m); Console.SetCursorPosition(0, N + 1); Console.Write(fdb); } fdb++; } // Console.Clear(); Magikus_Kiiras_2(m); Console.SetCursorPosition(0, N + 2); Console.WriteLine("{0} | K É S Z ! ", fdb); Console.ReadLine(); }
13.61. forráskód. Antimágikus négyzet generálása – az összegek számítása
static void osszegekSzamol(int[,] m, int[] osszegek) { int N = m.GetLength(0); for (int i = 0; i < osszegek.Length; i++) osszegek[i] = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { // i. sor osszege osszegek[i] = osszegek[i] + m[i, j]; // j. oszlop osszege osszegek[N + j] = osszegek[i] + m[i, j]; // foatlo osszege if (i == j) osszegek[2 * N] = osszegek[2 * N] + m[i, j]; // mellekatlo osszege if (i == N - j - 1) osszegek[2 * N + 1] = osszegek[2 * N + 1] + m[i, j]; } }
13.62. forráskód. Antimágikus négyzet generálása – mátrix megjelenítése v2
static void Magikus_Kiiras_2(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); int x,y; egyformaIndexek(osszegek, out x, out y); // Console.ForegroundColor = ConsoleColor.Yellow; for (int i = 0; i < N; i++) { Console.Write(" "); for (int j = 0; j < N; j++) { Console.ForegroundColor = ConsoleColor.Yellow; Console.Write("{0,3} ", m[i, j]); } Console.WriteLine(); } // sorok osszegei for(int i=0;i<N;i++) { if (i==x || i==y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(N*4+4,i); Console.Write("{0,3} ", osszegek[i]); } // oszlopok osszegei for (int i = 0; i < N; i++) { if (i+N == x || i+N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(4+i*4, N); Console.Write("{0,3} ", osszegek[i+N]); } // foatlo if (2*N == x || 2*N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(4 + N * 4, N); Console.Write("{0,3} ", osszegek[2*N]); // mellektalo if (2 * N+1 == x || 2 * N+1 == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(0, N); Console.Write("{0,3} ", osszegek[2 * N+1]); }
13.63. forráskód. Antimágikus négyzet generálása – elem választása
static void valasztElem(int i, out int a, out int b, int N) { // i egy sor indexe if (i < N) { a = i; b = rnd.Next(0, N); return; } // i egy oszlop indexe if (i < 2*N) { a = rnd.Next(0, N); b = i-N; return; } // i a foatlo if (i == 2 * N) { a = rnd.Next(0, N); b = a; return; } // i a mellekatlo a = rnd.Next(0, N); b = N - a - 1; }
13.64. forráskód. Antimágikus négyzet generálása – mátrix kezdőfeltöltése
static void kezdoFeltoltes(int[,] m) { int N = m.GetLength(0); int k = 1; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { m[i, j] = k; k++; } }
13.65. forráskód. Antimágikus négyzet generálása – elem összekeverése
static void osszekeveres(int[,] m, int db) { int N = m.GetLength(0); while (db > 0) { int x = rnd.Next(0, N); int y = rnd.Next(0, N); int v = rnd.Next(0, N); int w = rnd.Next(0, N); // int c = m[x, y]; m[x, y] = m[v, w]; m[v, w] = c; // db--; } }
13.66. forráskód. Antimágikus négyzet generálása – egyforma index-e
static bool egyformaIndexek(int[] v, out int a, out int b) { a = -1; b = -1; for (int i = 0; i < v.Length; i++) for (int j = i + 1; j < v.Length; j++) if (v[i] == v[j]) { a = i; b = j; return true; } // return false; }
13.67. forráskód. Antimágikus négyzet generálása – elem összekeverése
static void Main() { int[,] m; bool[,] fix; beolvasas(out m,out fix,@"hianyos-anti-magikus-negyzet.txt"); int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; Console.Clear(); Magikus_Kiiras_3(m, fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot beolvasva (nyomj le egy billt)"); Console.ReadLine(); // matrixBefejez(m); Console.Clear(); Magikus_Kiiras_3(m, fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot befejezve (nyomj le egy billt)"); Console.ReadLine(); // ulong fdb = 0; while (true) { int i, j; osszegekSzamol(m, osszegek); if (egyformaIndexek(osszegek, out i, out j)) { int a, b, c, d; valasztElem2(i, j,out a, out b, N, fix); while (true) { c = rnd.Next(0, N); d = rnd.Next(0, N); if (fix[c, d] == false) break; } int x = m[a, b]; m[a, b] = m[c, d]; m[c, d] = x; } else break; if (fdb % 100000 == 0) { Console.Clear(); Magikus_Kiiras_3(m,fix); Console.SetCursorPosition(0, N + 1); Console.Write(fdb); } fdb++; } // Console.Clear(); Magikus_Kiiras_3(m,fix); Console.SetCursorPosition(0, N + 2); Console.WriteLine("{0} | K É S Z ! ", fdb); Console.ReadLine(); }
13.68. forráskód. Antimágikus négyzet generálása – beolvasás
static void beolvasas(out int[,] m, out bool[,] fix, string fnev) { m = null; fix = null; int N = 0; int i = 0; System.IO.StreamReader r = new System.IO.StreamReader(fnev, System.Text.Encoding.Default); while (!r.EndOfStream) { string s = r.ReadLine().Trim(); string[] ss = s.Split(’ ’); if (m == null) { N = ss.Length; m = new int[N, N]; fix = new bool[N, N]; } if (ss.Length != N) throw new Exception("File feldolgozasi hiba"); if (i>=N) throw new Exception("Tul sok sor a file-ban"); for (int j = 0; j < N; j++) { m[i, j] = int.Parse(ss[j]); fix[i, j] = (m[i, j] != 0); } i++; } r.Close(); if (m==null) throw new Exception("File ures volt"); }
13.69. forráskód. Antimágikus négyzet generálása – a maradék cellák kitöltése
static void matrixBefejez(int[,] m) { int N = m.GetLength(0); int k = 1; for(int i=0;i<N;i++) { for (int j = 0; j < N; j++) { if (m[i, j] == 0) { k = kovNemSzereplo(m, k); m[i, j] = k; } } } }
13.70. forráskód. Antimágikus négyzet generálása – következő még nem szereplő érték keresése
static int kovNemSzereplo(int[,] m, int k) { int N = m.GetLength(0); while (true) { int db = 0; for (int i = 0; i < N && db==0; i++) for (int j = 0; j < N && db == 0; j++) if (k == m[i, j]) db++; if (db == 0) return k; k++; } }
13.71. forráskód. Antimágikus négyzet generálása – megjelenítés (1. rész)
static void Magikus_Kiiras_3(int[,] m, bool[,] fix) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); int x,y; egyformaIndexek(osszegek, out x, out y); // Console.ForegroundColor = ConsoleColor.Yellow; for (int i = 0; i < N; i++) { Console.Write(" "); for (int j = 0; j < N; j++) { if (fix[i, j]) { Console.BackgroundColor = ConsoleColor.Green; Console.ForegroundColor = ConsoleColor.Black; } else { Console.BackgroundColor = ConsoleColor.Black; Console.ForegroundColor = ConsoleColor.Yellow; } Console.Write("{0,3} ", m[i, j]); Console.BackgroundColor = ConsoleColor.Black; } Console.WriteLine(); } // sorok osszegei for(int i=0;i<N;i++) { if (i==x || i==y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(N*4+4,i); Console.Write("{0,3} ", osszegek[i]); } /* --- folytatása a következő forráskódban --- */
13.72. forráskód. Antimágikus négyzet generálása – megjelenítés (befejezés)
/* ---- folytatása a "Magikus_Kiiras_3" függvény kódjának static void Magikus_Kiiras_3(int[,] m, bool[,] fix) -------------------------------------------------------- */ // oszlopok osszegei for (int i = 0; i < N; i++) { if (i+N == x || i+N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(4+i*4, N); Console.Write("{0,3} ", osszegek[i+N]); } // foatlo if (2*N == x || 2*N == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(4 + N * 4, N); Console.Write("{0,3} ", osszegek[2*N]); // mellektalo if (2 * N+1 == x || 2 * N+1 == y) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Green; Console.SetCursorPosition(0, N); Console.Write("{0,3} ", osszegek[2 * N+1]); Console.ForegroundColor = ConsoleColor.Gray; }
13.73. forráskód. Antimágikus négyzet generálása – cserélendő cellák választása
static void valasztElem2(int i, int j,out int a, out int b, int N, bool[,] fix) { while (true) { valasztElem(i, out a, out b, N); if (fix[a, b] == false) return; valasztElem(j, out a, out b, N); if (fix[a, b] == false) return; } }
13.74. forráskód. Szép anti bűvös négyzet ellenőrzés
static bool szep_magikus_negyzet_e(int[,] m) { int N = m.GetLength(0); int[] osszegek = new int[2 * N + 2]; osszegekSzamol(m, osszegek); // sorok osszegei for (int i = 1; i < N; i++) if (osszegek[i - 1] != osszegek[i] + 1) return false; // oszlopok osszegei for (int i = N; i < 2*N; i++) if (osszegek[i - 1] != osszegek[i] + 1) return false; // minden rendben return true; }
13.75. forráskód. Kártyás – főprogram
static void Main() { const int N = 4; int[,] m = new int[N,N]; kezdoFeltoltes(m); ulong fdb = 0; int v,w; DateTime start = DateTime.Now; while (matrixRendben(m, out v, out w ) == false) { int x = rnd.Next(0, N); int y = rnd.Next(0, N); // int c = m[x, y]; m[x, y] = m[v, w]; m[v, w] = c; // // fdb++; // if (fdb % 1000000 == 0) Megjelenit(m); } DateTime stop = DateTime.Now; TimeSpan kul = stop - start; Megjelenit(m); Console.WriteLine(); Console.WriteLine(); Console.ForegroundColor = ConsoleColor.Gray; Console.WriteLine("Futasi ido={0}", kul); Console.ReadLine(); }
13.76. forráskód. Kártyás – megjelenítés
static void Megjelenit(int[,] m) { Console.Clear(); int N = m.GetLength(0); ConsoleColor[] szinek = new ConsoleColor[] { ConsoleColor.Green, ConsoleColor.Red, ConsoleColor.Cyan, ConsoleColor.Yellow}; string[] lapok = new string[] { "also", "felso", "kiraly", "asz" }; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Console.SetCursorPosition(j * 8, i * 2); int x = m[i, j]; int v = x / 10 - 1; int w = x % 10 - 1; Console.ForegroundColor = szinek[v]; Console.Write(lapok[w]); } } }
13.77. forráskód. Kártyás – a mátrix megfelelőségének ellenőrzése
static bool matrixRendben(int[,] m, out int k, out int l) { k = -1; l = -1; int N = m.GetLength(0); for (int i = 0; i < N; i++) { if (sorRendben(m, i, N, out l) == false) { k = i; return false; } if (oszlopRendben(m, i, N, out k) == false) { l = i; return false; } } if (atlokRendben(m, N,out k, out l) == false) return false; return true; }
13.78. forráskód. Kártyás – átlók megfelelőségének ellenőrzése
static bool atlokRendben(int[,] m, int N, out int v, out int w) { v = -1; w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) { if (hasonlo(m[i, i], m[j, j])) { v = i; w = i; return false; } if (hasonlo(m[i, N - i - 1], m[j, N - j - 1])) { v = i; w = N - i - 1; return false; } } // return true; }
13.79. forráskód. Kártyás – a mátrix k. oszlopának ellenőrzése
static bool oszlopRendben(int[,] m, int k, int N, out int w) { w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) if (hasonlo(m[i, k], m[j, k])) { w = i; return false; } // return true; }
13.80. forráskód. Kártyás – a mátrix k. sorának ellenőrzése
static bool sorRendben(int[,] m, int k, int N, out int w) { w = -1; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) if (hasonlo(m[k, i], m[k, j])) { w = i; return false; } // return true; }
13.81. forráskód. Kártyás – két cella színének és lapjának vizsgálata
static bool hasonlo(int a, int b) { if (a / 10 == b / 10 || a % 10 == b % 10) return true; return false; }
13.82. forráskód. Kártyás – a mátrix kezdő feltöltése
static void kezdoFeltoltes(int[,] m) { int N = m.GetLength(0); for (int i = 0; i < N; i++) { int k = (i+1)*10+1; for (int j = 0; j < N; j++) { m[i, j] = k; k++; } } }
13.83. forráskód. Latin négyzet feltöltése
static void latinFeltoltes(int[,] m) { int N = m.GetLength(0); for (int i = 0; i < N; i++) { int k = 1+ i; for (int j = 0; j < N; j++) { m[i, j] = k; k++; if (k > N) k = 1; } } }
13.84. forráskód. K-ad fokú bűvös négyzetek
static List<int> K_ad_foku(int[,] m) { List<int> ret = new List<int>(); int N = m.GetLength(0); int[,] mm = (int[,])(m.Clone()); for (int k = 2; k <= 10; k++) { // hatvanyozas for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) mm[i, j] = mm[i, j] * m[i, j]; // ellenorzes if (magikus_negyzet_e(mm)) ret.Add(k); } return ret; }
13.85. forráskód. Kiegészítő ellenőrzés a bűvös négyzethez
for(int k=0;k<N*N;k++) if (megszamol(m, k) != 1) return false;
13.86. forráskód. Huszármódszer algoritmusa
static void huszarModszer(int[,] m) { int N = m.GetLength(0); // paratlan! int y = rnd.Next(0,N); int x = rnd.Next(0, N); // kezdo pozicio m[x, y] = 1; // int db=1; int k = 2; while (db < N * N) { // fel fel jobbra int yy = y-2; int xx = x+1; // kilepunk fenn? if (yy < 0) yy = N + yy; // kilepunk jobbra if (xx>=N) xx=0; // ez a cella mar foglalt? if (m[xx, yy] != 0) { xx = x; yy = y + 1; if (yy >= N) yy = 0; } if (m[xx, yy] != 0) throw new Exception("valami nem stimmel"); // szam elhelyezese m[xx, yy] = k; // ez az uj aktualis cella x = xx; y = yy; // szamlalok k++; db++; } }
13.87. forráskód. Lépcsős módszer forráskódja
static void lepcsosModszer(int[,] m) { int N = m.GetLength(0); // paratlan! int y = 0; int x = N / 2; // elso sor kozepe m[x, y] = 1; // int db=1; int k = 2; while (db < N * N) { // fel jobbra int yy = y-1; int xx = x+1; // kilepunk fenn? if (yy < 0) yy = N - 1; // kilepunk jobbra if (xx>=N) xx=0; // ez a cella mar foglalt? if (m[xx, yy] != 0) { xx = x; yy = y + 1; if (yy >= N) yy = 0; } if (m[xx, yy] != 0) throw new Exception("valami nem stimmel"); // szam elhelyezese m[xx, yy] = k; // ez az uj aktualis cella x = xx; y = yy; // szamlalok k++; db++; } }
13.88. forráskód. Keresztrejtvény – főprogram
static void Main() { int[,] m; bool[,] fix; int[] osszegek; List<int> l = new List<int>(); beolvasas_rejtv(out m, out fix, out osszegek, l, "negyzet.txt"); int N = m.GetLength(0); Magikus_Kiiras_4(m, fix,osszegek); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot beolvasva"); Console.ReadLine(); // matrixBefejez_4(m,l); Console.Clear(); Magikus_Kiiras_4(m, fix, osszegek); Console.SetCursorPosition(0, N + 2); Console.WriteLine("Kezdeti allapot befejezve"); Console.ReadLine(); // ulong fdb = 0; int[] sumst = new int[N * 2]; while (true) { int i; osszegekSzamol_4(m, sumst); if (elteroOsszeg(osszegek, sumst, out i)) { int a, b, c, d; valasztElem_4(i, out a, out b, N, fix); while (true) { c = rnd.Next(0, N); d = rnd.Next(0, N); if (fix[c, d] == false) break; } // csere int x = m[a, b]; m[a, b] = m[c, d]; m[c, d] = x; } else break; if (fdb % 100000 == 0) { Console.Clear(); Magikus_Kiiras_4(m, fix, osszegek); Console.SetCursorPosition(50, N + 2); Console.Write(fdb); } fdb++; } // Console.Clear(); Magikus_Kiiras_4(m, fix, osszegek); Console.ReadLine(); }
13.89. forráskód. Keresztrejtvény – rejtvény beolvasása
static void beolvasas_rejtv(out int[,] m, out bool[,] fix, out int[] osszegek, List<int> szamok, string fnev) { m = null; fix = null; osszegek = null; int N = 0; int i = 0; System.IO.StreamReader r = new System.IO.StreamReader(fnev, System.Text.Encoding.Default); while (!r.EndOfStream) { string s = r.ReadLine().Trim(); string[] ss = s.Split(’ ’); if (m == null) { N = ss.Length-1; m = new int[N, N]; fix = new bool[N, N]; osszegek = new int[2 * N]; } if (i == N) // utolso sor { for (int j = 0; j < N; j++) osszegek[N + j] = int.Parse(ss[j]); } else if (i == N+1) // felhasznalhato szamok { for (int j = 0; j < ss.Length; j++) szamok.Add(int.Parse(ss[j])); } else { if (i > N+1) throw new Exception("Tul sok sor a file-ban"); for (int j = 0; j < N + 1; j++) { if (j == N) osszegek[i] = int.Parse(ss[j]); else { if (ss[j] == ".") m[i, j] = 0; else m[i, j] = int.Parse(ss[j]); fix[i, j] = (m[i, j] != 0); } } } i++; } r.Close(); if (m == null) throw new Exception("File ures volt"); }
13.90. forráskód. Keresztrejtvény – eltérő összegek keresése
static bool elteroOsszeg(int[] osszegek, int[] sumst, out int i) { i = -1; for (int k = 0; k < osszegek.Length; k++) { if (osszegek[k] != sumst[k]) { i = k; return true; } } return false; }
13.91. forráskód. Keresztrejtvény – sor- és oszlopösszegek számítása
static void osszegekSzamol_4(int[,] m, int[] osszegek) { int N = m.GetLength(0); for (int i = 0; i < osszegek.Length; i++) osszegek[i] = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { // i. sor osszege osszegek[i] = osszegek[i] + m[i, j]; // j. oszlop osszege osszegek[N + j] = osszegek[N+j] + m[i, j]; } }
13.92. forráskód. Keresztrejtvény – megjelenítés
static void Magikus_Kiiras_4(int[,] m, bool[,] fix, int[] sums) { int N = m.GetLength(0); int[] sum2 = new int[2 * N + 2]; osszegekSzamol_4(m, sum2); // Console.ForegroundColor = ConsoleColor.Yellow; for (int i = 0; i < N; i++) { Console.Write(" "); for (int j = 0; j < N; j++) { if (fix[i, j]) { Console.BackgroundColor = ConsoleColor.Green; Console.ForegroundColor = ConsoleColor.Black; } else { Console.BackgroundColor = ConsoleColor.Black; Console.ForegroundColor = ConsoleColor.Yellow; } Console.Write("{0,3} ", m[i, j]); Console.BackgroundColor = ConsoleColor.Black; } Console.WriteLine(); } // sorok osszegei for (int i = 0; i < N; i++) { if (sum2[i]!=sums[i]) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(N * 4 + 4, i); Console.Write("{0,3} ", sum2[i]); Console.ForegroundColor = ConsoleColor.Gray; Console.Write("{0,3} ", sums[i]); } // oszlopok osszegei for (int i = 0; i < N; i++) { if (sum2[N+i] != sums[N+i]) Console.ForegroundColor = ConsoleColor.Red; else Console.ForegroundColor = ConsoleColor.Cyan; Console.SetCursorPosition(4 + i * 4, N); Console.Write("{0,3} ", sum2[i + N]); Console.SetCursorPosition(4 + i * 4, N+1); Console.ForegroundColor = ConsoleColor.Gray; Console.Write("{0,3} ", sums[N+i]); } Console.ForegroundColor = ConsoleColor.Gray; }
13.93. forráskód. Keresztrejtvény – kezdő kitöltés befejezése
static void matrixBefejez_4(int[,] m, List<int> szamok) { int N = m.GetLength(0); int k = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (m[i, j] == 0) { m[i, j] = szamok[k]; k++; } } } }
13.94. forráskód. Keresztrejtvény – cserélendő elem választása
static void valasztElem_4(int i, out int a, out int b, int N, bool[,] fix) { while (true) { valasztElem(i, out a, out b, N); if (fix[a, b] == false) return; } }
[1] Nincs igazán
konszenzus az angol és magyar elnevezésekben. Angolul létező fogalmak a „magic square” és „mystic
square”, ami két hasonló, bár egy ponton különböző dolog. A „mystic square”-ben az is követelmény,
hogy az 
négyzetben csak 
közötti számok fordulhatnak elő.
Ennek megfelelője jegyzetünkben a „bűvös négyzet”, a „magic square”-t ellenben „mágikus
négyzetnek” fordítjuk.
[2] egyben bűvös négyzet
[3] egyben bűvös négyzet
[4] angolul néha Border Square-nek nevezik
[5] Bimagic square
[6] Trimagic square
[7] Staircase method