8 királynő átlósan való ellenörzése, mit rontok el?

8 királynő átlósan való ellenörzése, mit rontok el?
2017-12-11T21:42:10+01:00
2017-12-14T20:45:48+01:00
2022-12-04T23:40:34+01:00
Kálmán Richárd
Sziasztok!

Szorgalmi feladatként kaptam hogy kérjek be egy sakk táblát fileból 0,1ekkel ahol 1esek vannak ott van a királynő és ugye az a cél, hogy ne üssék egymást. Azt letudom ellenőrizni, hogy jobbra balra, fel le ellenőrizze, de amikor átlósan akarom ellenőrizni, sosem jön ki jó érték. 

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; //lefele(x + 1, y) //felfele(x - 1, y) //jobbra(x,y + 1) //balra(x,y - 1) //lejobbra(x + 1, y + 1) //feljobbra namespace n_kiralynoproblem { class Program { const int N = 8; static bool[,] tabla = new bool[N, N]; //false értéket adunk meg, ha üti királynőt, true, ha minden rendben van static bool lefele(int x, int y) { for (; x < N; x++)//lefelé lépegetünk mert lefelé mindig nő egyel az x érték { if (tabla[x, y]) { return false; } } return true; } static bool felfele(int x, int y) { for (; x >= 0; x--)// felfelé lépegetünk csak az x csökken { if (tabla[x, y]) { return false; } } return true; } static bool jobbra(int x, int y) { for(; y < N; y++) { if (tabla[x, y]) { return false; } } return true; } static bool balra(int x, int y) { for (; y >= 0; y--) { if (tabla[x, y]) { return false; } } return true; } static bool lejobbra(int x, int y) { for(; x < N; x++) { //if (y == 8) y = 7; //if (x == 8) x = 7; if (x != N-1 && y != N - 1) { if (tabla[x, y]) { return false; } if(y!=7) y++; } } return true; } static void ellenoriz() { for(int x = 0; x < N; x++) { for (int y = 0; y < N; y++) { if (tabla[x, y])//ellenorizuk hogy van-e királynő { if (lejobbra(x + 1,y+1)) { } else { Console.WriteLine("szar van a palacsintában"); } } } } } static void beolvas() { int i = 0; StreamReader sr = new StreamReader("sakk.txt"); while (!sr.EndOfStream) { string sor = sr.ReadLine(); for (int j = 0; j < N; j++) { if (sor[j] == '0') tabla[i, j] = false; else tabla[i, j] = true; } i++; } } static void kiir() { for (int k = 0; k < N; k++) { for (int j = 0; j < N; j++) { if (!tabla[k, j]) Console.Write("0"); else Console.Write("1"); } Console.WriteLine(); } } static void Main(string[] args) { beolvas(); kiir(); ellenoriz(); Console.ReadKey(true); } } }
Akármit próbálok nem megy, mit rontok el? Egy kis útbaigazítást szeretnék
Mutasd a teljes hozzászólást!
Nagyon macerás és teljesen felesleges cellánként ellenőrizni mind a nyolc szomszédos cella irányában minden cellát. Fel-le-jobbra-balra irányba egyszerű trükk, ha a sor- és oszlopösszegeket ellenőrzöd, egyik sem lehet egynél több, mert akkor az adott sor vagy oszlop két királynőt is tartalmazott.
Ilyesmi:

int sorosszeg[N]; int oszloposszeg[N]; for (x = 0; x < N; x++) { for (y = 0; y < N; y++) { if (!tabla[x, y]) continue; sorosszeg[x]++; oszloposszeg[y]++; } }
Aztán megnézheted, hogy a sorösszeg és oszlopösszeg tömbök értéke nagyobb-e bárhol, mint egy és visszatérhetsz hamissal, ha igen.
Ha nem, akkor jön az átlós ütés kérdése, ami itt elég problémás, de ezzel a megoldással sem lehetetlen. NxN-es sakktáblán összesen irányonként 2*N-3 értelmes átló húzható be, a fenti kód ügyes módosításával ezen átlók összegeit is számon tudod tartani a sor- és oszlopösszeghez hasonlóan.

Az egész feladatra szerintem a legegyszerűbb megoldás egy teljesen új megközelítés: ha a fenti két egymásba ágyazott ciklust lefuttatod és minden talált 1 értéknél eltárolod egy struktúrában az adott talált királynő x, y koordinátáját, a koordináták páronkénti elemzésével könnyedén meg tudod nézni, hogy üti-e egymást két vezér. Ha az x koordináták egyeznek, sorban ütik egymást, ha az y koordináták egyeznek, oszlopban. Ha az x és y koordináták páronkénti különbségének abszolút értéke azonos, akkor átlóban. (Ez itt a trükk, gondold át.) Ezeket halál egyszerű számítani, és a kódod működni fog N=100000 esetén is, nem fog szaggatni hatékonysági okokból. (Értelemszerűen az elemzést új koordináta felvétele előtt célszerű futtatni, az újonnan talált vezér pozícióját összehasonlítani az eddig ismertekkel és csak akkor felvenni a listára, ha nincs konfliktus, egyébként meg return false.)
Mutasd a teljes hozzászólást!

  • Hali!

    Tökéletesen erre gondoltam én is!  Mivel jelenleg nincs fent C# fejlesztőeszköz (meg amúgy is kevésbé ugatom, mint pl. a Javascriptet), de érdekelt a dolog, elkészítettem egy JS-megvalósítást (főleg a magam szórakoztatására): Eight Queens Puzzle. Kattintgatva lehet elhelyezni/levenni a királynőket addig, amíg elérjük a 8-at vagy ütéshelyzet nem áll elő. 

    Mutasd a teljes hozzászólást!
  • Én meg prolog-ban raktam össze szórakozásból

    safe(_, []). safe(X1/Y1, [X2/Y2 | tail]) :- Y1 =\= Y2, Y2 - Y1 =\= X2 - X1, Y2 - Y1 =\= X1 - X2, safe(X/Y, tail).

    Amúgy fel se tűnt, hogy az eredeti kérdés C#-ban van, csak úgy látszik, a pszeudokódom fordul C#-ban is. Tetszik amúgy a megvalósításod, bár fura, hogy a megjegyzések magyarok.
    Mutasd a teljes hozzászólást!
  • Még sok-sok évi programozás után is előfordul, hogy az ember az első működő algoritmust megvalósítja... 'oszt jónapot.

    Mert 8x8 táblán tényleg érdektelen milyen algoritmussal keressük az ütközéseket.
    De az általad mondott algoritmus tényleg nagyon frappáns. 

    Egy programozónak azt is meg kell tanulnia, hogy megérezze, kell még lennie valami jobb-hatékonyabb-egyszerűbb algoritmusnak. 
    Mutasd a teljes hozzászólást!
  • 8 sor, 8 oszlop, és 15-15 átló van.
    mindegyikre felveszel egy-egy int vagy bool tömböt
    végigmész az adatokon, ha van királynő, akkor megjelölöd mind a 4 tömbben a megfelelő pozíciót. ha ott már true van, vagy int tömb esetén >0, akkor ütés lesz.

    x: 0-7, y: 0-7 esetén
    sor index: y
    oszlop index: x
    / átló index: x+y
    \ átló index x-y+7
    Mutasd a teljes hozzászólást!
  • Ez így túl bonyolult és hosszú. Valóságban elég az oszlop és a 15 átló, ahol a metszéspontokra leraksz 1-8 ig egy számot.  Ebből már a tábla előállítható, cserébe a tesztelése egyszerű lesz, amikor keresni kell benne egy szabad helyet : megnézed az oszlopot, majd választasz hozzá egy hozzá tartozó átlót (mert pl az A oszlophoz nem tartozhat a 9. átló...) .


    Így ez elvileg két egymásba ágyazott ciklus, vagy méginkább a backtrack pont szuper hozzá ;)
    Mutasd a teljes hozzászólást!
  • Köszönöm a segítséget, minden érthető lett így.

    ui.: bocsi a késő reagálásért
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd