8 (N) királynő probléma

Algoritmusok

Sziasztok!

Belebotlottam a 8 királynő problémába. Írtam is valamit, az eredmény korrekt, ugyanakkor
nem tudom, hogy futásidőben mennyire jó vagy nem. Van valakinek tapasztalata arról,
hogy milyen hardveren milyen futásidőt illik elérni? Én egyetlen szálon tesztelem most.

A válaszokat előre is köszönöm, üdv mindenkinek.

( sz332 v | 2017. 09. 06., sze – 15:53 )

Érdekes lenne egy eredményt felrakni. Milyen gépen, milyen futásidő. Esetleg
a githubra dobj fel egy példakódot.

( meditor | 2017. 09. 06., sze – 16:09 )

Futásidők:

N=8 :: 0.003 sec
N=9 :: 0.024 sec
N=10:: 0.212 sec
N=11:: 2.401 sec
N=12:: 30.307 sec
N=13:: 394.511 sec

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 37
model name : Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz
stepping : 5
cpu MHz : 3192.845
cache size : 4096 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 2
bogomips : 6385.69
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:

> Sol omnibus lucet.

A profik kicsit odébb tartanak: "Meglepő módon az n-királynő probléma esetén a min-konfliktusok algoritmus futási ideje a kezdeti elhelyezéseket nem számítva nagyjából független a probléma méretétől. Akár a millió-királynő problémát is megoldja átlagosan ötven lépésben (a kezdeti értékadást követően)."
A részleteket lásd az MI bibliában, a http://www.tankonyvtar.hu/hu/tartalom/tamop425/0026_mi_4_4/ch05s03.html oldalon. A DE-n ezt az módszert az MI alapjai tárgy keretében, BSc szinten oktatjuk.

Persze ez csak akkor használható, ha megelégszünk egy megoldással. Ha az összes megoldás kellene, akkor gondot okozhat azok elképesztően nagy száma. Viszont a http://www.tankonyvtar.hu/hu/tartalom/tamop425/0026_mi_4_4/ch05s02.html oldal tartalmazza mindazokat a heurisztikákat, mellyel a visszalépéses keresés felgyorsítható, amint azt az ott lévő táblázat is mutatja.

A konzisztencia hiánya még a legkisebb gond.
A rengeteg kikommentezett minusz felesleges, az egy szóközös indent alig látható, a kapcsos zárójelet közvetlenül követő utasítás wtf, végül pedig az olyan soroknak, mint 

{j=i+1;while(j<NUMBER_OF_QUEENS)

vagy főleg 

i=0;while(i<NUMBER_OF_QUEENS){printf("%3d",PermuArray[i]);i++;}printf("\n");

egyszerűen nem szabadna létezniük. A for ciklus smafu!?

Előző életemben, ha gyakorlaton egy hallgató ilyet merészelt volna beadni, azt reflexből visszadobtuk volna.

Marha jól át tudod tekinteni a kódot, amikor egy képernyőoldalra max 6-8 nagyon szépen és konzisztensen írt sor fér el. Amit te konzisztenciának hívsz az egyfajta konszenzus és bizonyos mértékig szubjektív.

Vegyük pl ezt a sor:

i=0;while(i < NUMBER_OF_QUEENS){printf("%3d",PermuArray[i]);i++;}printf("\n");

Ha úgy akarok tesztelni, hogy a kiíratást átugrom, csak EGY sort kell kikommentezni. Ez az EGY sor ezenkívül EGY konkrét műveletet hajt végre, indokolt hogy minél kompaktabb képet mutasson. (...és igen, a sok mínusznak is van jelentése, nem kell megfejteni).

Továbbá, ha már itt tartunk: persics fórumtárs kifogásolta, hogy a típus és a név között változó mennyiségű space van. Nem tudom feltűnt-e neki, hogy a változónevek szépen oszlopba vannak rendezve, mert így sokkal könnyebb áttekinteni az egészet. Ez csak 2-3 példa, arra hogy miért így néz ki a kód. Én ÍGY tudok hatékonyan dolgozni, nekem ÍGY áttekinthető a program.

Szerencsére számos kódformázó létezik, mindenki úgy formázza MÁS kódját, ahogy akarja.

> Sol omnibus lucet.

ps.: A for és a while ciklusra ugyanaz a gépi kód fordul. Van egy goto is a 40. sorban azon is lehetne rágódni.

"Marha jól át tudod tekinteni a kódot, amikor egy képernyőoldalra max 6-8 nagyon szépen és konzisztensen írt sor fér el."

Hm?

"Ha úgy akarok tesztelni, hogy a kiíratást átugrom, csak EGY sort kell kikommentezni. Ez az EGY sor ezenkívül EGY konkrét műveletet hajt végre, indokolt hogy minél kompaktabb képet mutasson."

Ez esetben inkább az lenne indokolt, hogy a kiíratás egy saját függvénybe kerüljön, rendesen tagoltan.

"és igen, a sok mínusznak is van jelentése, nem kell megfejteni"

El nem tudom képzelni, hogy mi lehet az, plána a file végi "End of file"-nak, de azt hiszem, hogy nem is akarom megtudni.

"Szerencsére számos kódformázó létezik, mindenki úgy formázza MÁS kódját, ahogy akarja."

Vagy nem akarja, mert az ilyen sorokat meglátva úgy megijedt, hogy egyből bezárta? :)

"A for és a while ciklusra ugyanaz a gépi kód fordul"

Tehát még ez sem indok arra, hogy miért nem for ciklust írsz, ha már úgyis ugyanabba a sorba akarod írni a ciklusváltozó inicializálását és tesztelését...

Kiváncsian várom, hogy mi a for ciklus előnye a while-la szemben, ha még a gépi fordítás SEM. És annak az indoklását is, hogy miért jobb kitenni egy fv-be egy 4 utasításos kiírást, mint egy sorba leírni, ha már megadatott az a lehetőség, hogy egy utasítás lezárhat egy ';'-vel.

> Sol omnibus lucet.

A for ciklusnak például az az előnye, hogy a létrehozott változó csak a for ciklus scope-ján belül él, nem szennyezed vele a külső scope-ot. A clean code elvek (!= kőbe vésett szabályok) szerint egy sorba legfeljebb egy utasítást szabad írni (ha egymás után írod az utasításokat, akkor vízszintesen is végig kell olvasnod a sort, amikor átnézed; nehezebb átolvasni a kódot), és egy sor hossza legfeljebb 120 karakter lehet.

C-nél a fordító ahol tudja, úgyis inline-olja a függvényt, ezért nem lesz különösebb hatása a teljesítményre.

Valóban zavarja az olvashatóságot a konzisztencia hiánya a kódolási stílusban.

Van, hogy az utasításblokk kezdete és az első utasítás egy sorban van, van, hogy külön sorban.
Van, hogy egy utasításblokk 4 szóköznyi behúzással kezdődik, van, hogy egy szóköznyi behúzással.
Van, hogy az utasításblokk egy sorban van.
Van, hogy egy sorba több utasítás kerül, míg más sorokban csak egy utasítás van.
Van, hogy a változódeklaráció és az inicializálás együtt történik, van, hogy külön.
Van, hogy 3 szóköz választja el a változódeklarációban a típust és a nevet, van, hogy 8. Van, hogy 2.
Van, hogy van szóköz az egyenlőségjel két oldalán, van, hogy nincs.
Van, hogy szóköz választja el a függvény argumentumait a függvény nevétől, van, hogy nem választja el.

n=13 gcc 5.4.0 -O3-al forditva
real 1m6.664s
user 1m6.660s
sys 0m0.000s

de beleneztem hat ezen meg lenne mit optimalizalni :)
anno 20 eve az egyetemen pascalban ennel jobbat irtam, csak mar nem emlexem a reszletekre, de akkor eleg sokat optimalizaltam az eredeti peldan.
meg ugye ez 1 szalon fut, lehetne parhuzamositani, akar cuda-ra atirni stb
mondjuk ertelme kb semmi :)

A'rpi

ps: itt van sok verzio: https://rosettacode.org/wiki/N-queens_problem#C
az utolso n=13-al 0.01s, n=17-el 20s alatt fut le nalam

Bizonyára van jobb algoritmus, nem kétlem.

Ugyanakkor nem látom át, hogy EZT a kódot hogyan lehetne
LÉNYEGESEN gyorsítani. A futásidő döntő többségét a két ciklus
viszi el: RS_permutation() és az IsItDancingQueen(), kb fele-fele
arányban osztozva az időn. Mindkettő számtani haladvány
szerint hosszabbodik, illetve az egész faktoriálisan függ
a NUMBER_OF_QUEENS-től (ez a faktoriális növekedés nagyon szépen
látszik is az általam közölt futásidőkön).

Az RS_permutation()-ban vizsgálni lehetne, hogy nem rekurzíve szervezve
a stack műveletek elhagyásával, ugyanakkor más műveleti költségek
megjelenésével lehet-e időt fogni, gyanítom, hogy nem. Az időt
általában az összehasonlító műveletek viszik viszik el, a stack műveletek
gyorsak. Az eljárás a ciklusszervező utasításokon és a rekurzív híváson
kívül csak egy swap-ot tartalmaz, assemblyben lehetne ezt is
stackon keresztül csinálni így:

push a
push b
pop a
pop b

Ez biztos, hogy gyorsabb az egyszerű értékadásnál, főleg, ha a-t és b-t
regiszterben tartod.

Az IsItDancingQueen() szerintem semmit olyat nem tartalmaz, ami felesleges,
talán a két értékadás lenne elhagyható, ha magát a műveletet az abs() fv-nek
adjuk át.

Kiváncsian várom ugyanakkor a véleményed, Te mit látsz másként.

> Sol omnibus lucet.

Nem.

Ma már kb. minden fordító kioptimalizálja neked a temp változós cserét, még a xort nem. Ráadásul a xor csere speciális esetekben szar, meg általában olvashatatlan.

Majd ha lesz az elsősöknek erről írás (október vége, kb), ide linkelem.

Szerk.: a Wikipedia is hasonlót ír.
--
blogom

Összedobtam én is valamit, ennek a futásideje:
:~/python/nqueen$ time python queens.py -n 8
92

real 0m0.069s
user 0m0.060s
sys 0m0.008s
:~/python/nqueen$ time python queens.py -n 9
352

real 0m0.188s
user 0m0.172s
sys 0m0.016s
:~/python/nqueen$ time python queens.py -n 10
724

real 0m0.451s
user 0m0.420s
sys 0m0.028s
:~/python/nqueen$ time python queens.py -n 11
2680

real 0m1.517s
user 0m1.504s
sys 0m0.012s
:~/python/nqueen$ time python queens.py -n 12
14200

real 0m7.746s
user 0m7.724s
sys 0m0.020s
:~/python/nqueen$ time python queens.py -n 13
73712

real 0m44.659s
user 0m44.648s
sys 0m0.004s

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 60
model name : Intel(R) Core(TM) i7-4600M CPU @ 2.90GHz
stepping : 3
microcode : 0x1e
cpu MHz : 1082.175
cache size : 4096 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts
bugs :
bogomips : 5787.06
clflush size : 64
cache_alignment : 64
address sizes : 39 bits physical, 48 bits virtual
power management:

( persicsb | 2017. 09. 06., sze – 16:39 )

Csak nem?
http://index.hu/tech/2017/09/01/programozas_sakk_jutalom_problema/

Megsúgom, NEM lehet vele egymilliót keresni.
Egymilliót a Clay Mathematics Institute ad, a P ? NP probléma megoldásáért, azonban a felvetett és hivatkozott cikk a n-Queen Completion Problemről szól, ami tök más.
Lásd: http://www.claymath.org/events/news/8-queens-puzzle
A "Unfortunately, some reports of our work have given the impression that solving the 8-queens puzzle, or the n-queens puzzle for all n, might result in the award of the Millennium Prize. This is not the case, for two reasons." kezdetű bekezdést olvasd el.

Ha meg akarnád oldani, akkor a futásidőt ne másodpercben mérd, mert az értelmetlen, egy matematikus nem is tud vele mit kezdeni, hanem aszimptotikus jelöléssel add meg. Senkit nem érdekel a konkrét implementáció futásideje, az algoritmus komplexitása a lényeg.

Miért is?
Lehet , hogy P = NP, de a bizonyítás nem konstruktív, csak egzisztenciabizonyítás.
Azaz bebizonyítja, hogy P = NP, de nem mutatja meg, hogy ha egy probléma NP-beli, akkor hogyan lehet rá P-beli megoldó algoritmust alkotni.

Miért alacsony összeg ez? Nem gondolnám annak. Több, mint egy Nobel-díj.

A kérdést vizsgáljuk más szemszögből:
- Ha csak egzisztenciabizonyítás, akkor már érdemes az algoritmus keresésébe jelentős összegeket fektetni. Hiszen bizonyosan létezik. Az aki megtalálja nagyot kaszálhat vele.
- Ha algoritmust is ad, akkor azzal újabb jelentős befektetés nélkül lehet sokat keresni. Amennyiben nem hozza nyilvánosságra az algoritmust.
- Ha azt sikerülne bizonyítani, hogy nem áll fenn az egyenlőség, akkor azt tudnánk meg, hogy felesleges további pénzeket és időt beleölni a kutatásba. Ebben az esetben az 1 millió már nem olyan kevés.

( Raynes | 2017. 09. 06., sze – 18:14 )

Ezért kell nézni hová lépsz, mert könnyen belebotlassz ilyen váratlan problémákba. Érthető, akárkivel megeshet :D

„Pár marék nerd-et leszámítva kutyát se érdekel már 2016-ban a Linux. Persze, a Schönherz koliban biztos lehet villogni vele, de el kéne fogadni, ez már egy teljesen halott platform. Hagyjuk meg szervergépnek stb…” Aron1988@Proharder Fórum

( Szenti v | 2017. 09. 06., sze – 18:22 )

1200 MHz-es Athlon procin egy általános (tetszőleges alakú, 9 elemű cellákat megoldó) Pascalban írt megoldó rutinom 160 megoldás/másodperc sebességgel dolgozott szabályos, négyzet alakú mátrixokat tartalmazó, 9x9-es sudokura. Az összehasonlításnak csak akkor van értelme, ha azonos gépen és azonos fordítóval fordítod/futtatod.

akkor lehet meg is van az sokezer$ tulaja, aszondja:

Systematic & greedy search multithreaded version For N = 1000: 4 sec

-- vagy valahol valamit nagyon benezek.

update: letoltottem a futtathato exet, 1 megoldast ir ki, nem az osszeset.

--
HUP te Zsiga !

( KGer | 2017. 09. 08., p – 13:57 )

írtam egy fgv hívás nélkülit saját kútfőből
elsőnek java-ban majd átraktam C-be
összehasonlítottam az említett wiki-set azt enyémmel egy nemtom milyen hardveres virtuális gépen

1.
https://rosettacode.org/wiki/N-queens_problem#C
ebből az első
kikommenteztem a printf-es részt


$ time ./wiki1 12

real 0m0.346s
user 0m0.345s
sys 0m0.000s

$ time ./wiki1 13

real 0m2.181s
user 0m2.170s
sys 0m0.001s

$ time ./wiki1 14

real 0m14.624s
user 0m14.547s
sys 0m0.008s

$ time ./wiki1 15

real 1m44.196s
user 1m42.165s
sys 0m1.590s

--------------------------------------
2.
enyém


$ time ./kger2 12
N=12, id=0, found=14200

real 0m0.111s
user 0m0.110s
sys 0m0.000s

$ time ./kger2 13
N=13, id=0, found=73712

real 0m0.625s
user 0m0.622s
sys 0m0.000s

$ time ./kger2 14
N=14, id=0, found=365596

real 0m3.770s
user 0m3.753s
sys 0m0.000s

$ time ./kger2 15
N=15, id=0, found=2279184

real 0m24.144s
user 0m24.012s
sys 0m0.028s

--------------------------------------
3.
https://rosettacode.org/wiki/N-queens_problem#C
ebből a negyedik


$ time ./wiki2 12
Number of solution for 12 is 14200

real 0m0.011s
user 0m0.010s
sys 0m0.000s

$ time ./wiki2 13
Number of solution for 13 is 73712

real 0m0.056s
user 0m0.056s
sys 0m0.000s

$ time ./wiki2 14
^[[ANumber of solution for 14 is 365596

real 0m0.323s
user 0m0.321s
sys 0m0.000s

$ time ./wiki2 15
Number of solution for 15 is 2279184

real 0m2.012s
user 0m1.994s
sys 0m0.010s

( hokuszpk | 2017. 09. 12., k – 14:05 )

na megfejtettem en is, n=15
i7-5820K 3.3Ghz linux :

~]$ time ./sokvezir
vezerszam = 15
start: 13:28:22:53
megoldasok szama = 2279184
stop: 13:29:25:42

real 1m2.896s
user 1m2.737s
sys 0m0.053s

Phenom II X4 2.8Ghz windows
~1m10s :

Running "c:\fpc\nyocvezir.exe "
vezerszam = 15
start: 12:57:48:46
megoldasok szama = 2279184
stop: 12:58:58:95

update : ha kiveszem az eredmenyek fileba irasat, akkor gyorsabb :)

Running "c:\fpc\sokvezir.exe "
vezerszam = 15
start: 14 2 17 56
megoldasok szama = 2279184
stop: 14 3 12 28

--
HUP te Zsiga !

( meditor | 2017. 09. 13., sze – 17:51 )

A függetlennek (lényeges különbözőnek) mondott konstellációk egy része nagyon egyszerűen egymásba transzformálható. Még vizsgálom hogy ezzel a transzformációval az összes lényegesen különböző előállítható-e.

> Sol omnibus lucet.

A összes lehetséges kimenetet elő lehet állítani brute-force-szal:
- az összes kimenet előállítása: n királynő elhelyezése nxn elemen. N db egymásba ágyazott ciklussal megoldható.
- ha ütik egymást a királynők, akkor eldobás. Egyszerű feltétel-ellenőrzés.
- ha egyezik valamelyik már meglévő megoldássa, akkor eldobás. Erről lásd lentebb.
- egyébként hozzáadás a megoldások listájához.

Egyszerű 4 lépéses algoritmus, csak éppen marha lassú.

Az, hogy a harmadik pontban két megoldást mikor tekintünk egyezőnek és mikor nem, az meg definíció kérdése, egy egyszerű bináris függvény, ami két megoldásról megmondja, hogy egyezőek-e, vagy nem.
Például más a megoldások száma, ha az elforgatásokat egyezőnek tekinted. Itt még bejön az is, hogy a 90 fokos elforgatás is számít, vagy csak a 180 fokos. Stb. Megint más, ha a tükrözéseket egyezőnek tekinted. Megint más, hogy ha ezeket különbözőnek tekinted.

Azaz szépen szólva kell egy ekvivalencia-relációt értelmezni a megoldások halmazán, és elég sokféle ekvivalencia-reláció értelmezhető.