Hlavne menu We are sorry, but magazine AMMO is suspended. Here is just read-only access to the articles archive. Some features are removed because they were outdated, pointless in read-only (voting and pools), or it was missused by spammers (comments) etc. Now the webpages aren't maintained so when something will get broken most probably it won't be fixed at all. If you liked our magazine then please make donation with paypal so we can pay for traffic on this server.

TOP Výuka
01 OpenGL, lákadlo 38 bodov
02 MySQL (+ použitie Visual C++ a PHP) 28 bodov
03 OpenGL, časť 1 21 bodov
04 Huffmanove kódovanie 19 bodov
05 Pascal, časť 1 18 bodov
06 Ako tlačiť s HP 16 bodov
07 Základy HTML časť 2 16 bodov
08 Základy HTML časť 3 13 bodov
09 Hry pre nenáročných + zdrojáky 10 bodov
10 OpenGL, úvod 8 bodov
11 Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0 7 bodov
12 OpenGL – Intermezzo 1 7 bodov
13 OpenGL povinná literatúra 6 bodov
14 Základy HTML časť 1 6 bodov
15 WinSocket Communication via VC++ 6 bodov
Najnovsie clanky
Kvalitné služby podľa skúseností iných - TopSlužby.sk
LOTR - Dve veže - Parodia - Scénka 2. časť
Neverwinter nights
Children Of Bodom-Hatebreeder
Kult Duny - 6. časť (Bonus)
Kult Duny - 5. časť (Filmy, Hry)
Dobré ráno. (morc certa, hora incerta...)
Kult Duny - 4. časť (Knihy 2/2)
Stretnutie Spoločenstva Tolkiena
GRAVE DIGGER – Knights Of The Cross
Kult Duny - 3. časť (Knihy 1/2)
Kult Duny - 2. časť (Pojmy)
Kult Duny - 1. časť (Úvod)
LOTR - Dve veže - Parodia - Scénka
Jackass
Vsetky clanky
Airsoft - Specnaz [4 clanky]
Básne [6 clankov]
Fantázia [4 clanky]
Filmy a DVD [51 clankov]
Hardware [10 clankov]
Hry [170 clankov]
Hry, návody [6 clankov]
Hudba [8 clankov]
Internet [7 clankov]
Knihy [6 clankov]
O AMME [4 clanky]
Pandemonium [10 clankov]
Poviedky [14 clankov]
Programy [18 clankov]
Rôzne [8 clankov]
Technické [3 clanky]
Úvahy [8 clankov]
Výuka [50 clankov]
Ako tlačiť s HP
Algoritmy v grafoch
Fake2
Faktúrka
Faktúrka v4.0 + zdrojáky v MS Visual C++ 6.0
Fract
HLSaver
Hry pre nenáročných + zdrojáky
Huffmanove kódovanie
IPicture2 & aggresiveoptimize.h
MySQL (+ použitie Visual C++ a PHP)
OpenGL - GLWnd
OpenGL AMMO Saver
OpenGL povinná literatúra
OpenGL – Intermezzo 1
OpenGL, časť 10
OpenGL, časť 11
OpenGL, časť 12
OpenGL, časť 13
OpenGL, časť 14
OpenGL, časť 15
OpenGL, časť 16
OpenGL, časť 17
OpenGL, časť 18
OpenGL, časť 7
OpenGL, časť 8
OpenGL, časť 9
Opengl – Cloth Simulation
RenameR
SkinMagic
WinSocket Communication via VC++
Údajové štruktúry
viac...
Zábava [5 clankov]
Zdravie [15 clankov]
Celkovy pocet clankov: 407
Maľované krížovky 
Výuka | Dna 16.1.2004 | Johny | 109 znamok, priemer 2.38 | 3889 videni | 186 WAP videni

Čo sú to maľované krížovky ? Ako ich riešiť ? Dokázal by to aj počítač ? Na všetky tieto otázky odpovedá tento článok o maľovaných krížovkách, ktoré môžete nájsť v špeciálnych časopisoch, ale objavujú sa už aj inde. Naučíte sa ako ich riešiť ručne a aj niektoré metódy riešenia na PC a ich efektívnosť a náročnosť...

Najprv, teda, čo sú to maľované krížovky ? Toto:

Obr�zok


Maľovaná krížovka je akýsi štvorec alebo obdĺžnik. Je to sieť políčok, ktorá má „r“ riadkov a „s“ stĺpcov. Na konci Vám vznikne nejaký obrázok. Ako ste si všimli, tak pri každom riadku a stĺpci sú nejaké čísla. Pokúsite sa uhádnuť, čo znamenaju ? Ak hej, tak prestaňte čítať a do toho! ;o).

Tak ako? Podarilo sa? Myslím, že ste určite prišli na to, ze ak je v riadku alebo stĺpci 0, tak v tom stĺpci nie je žiadne políčko. Napr. riadok, kde je len číslo 4 nám hovorí, že v tomto riadku budú 4 vyfarbené políčka a že tieto políčka budú vedľa seba. Zatiaľ nevieme, kde budú. Ďalej napr. riadok „3 3 2 2“ nám hovorí, že v tom riadku bude spolu 3+3+2+2 vyfarbených políčok, spolu je to 10. Ak by sme išli po tom riadku zľava doprava, tak by sme museli prísť najprv k vyfarbenej trojici políčok, potom musíme nájsť minimálne jednu medzeru, znova musíme nájsť trojicu, medzeru, dvojicu, medzeru a nakoniec dvojicu. Takže číslo vždy označuje n-ticu vyfarbených políčok, ktoré sú vedľa seba. Toto platí pre každú skupinu políčok. Medzi skupinami políčok musí byť najmenej 1 medzera. Pre stĺpce platia tie isté pravidlá ako pre riadky.

Takže čísla nám prezradia len veľkosti skupín vymaľovaných políčok a že medzi nimi je aspoň 1 medzera. Pozície skupín alebo medzier nevieme.


Ako riešiť MK ?
Musíme postupovať tak, aby sme postupným vymaľovaním políčok o ktorých sme si istý, že tam niečo bude vymaľovali celý obrázok. V priebehu riešenia je dôležité označovať si políčka o ktorých vieme, že tam nič nebude. To nám neskôr pomôže. Napríklad na obrázku vyšie je v niektorom riadku číslo 0. Teda v tomto riadku nie sú žiadne políčka, ktoré by sme mohli vymaľovať, tak tam zakreslíme paličku alebo čokoľvek chcete a tým označíme toto políčko a vieme, že tam už vymaľované políčko byť nemôže, lebo inak by bola informácia zapísaná v riadku nepravdivá. My veríme tomu, že informácie v riadkoch aj v stĺpcoch sa riadia vyššie napísanými pravidlami. Teda riadku a stĺpce s 0 môžeme kľudne celé vypaličkovať. O prázdnych miestach zatiaľ neviem povedať, že tam niečo bude. O všetko, čo kreslíme si musíme byť na 100% istý, inak riskujeme, že to pokazí výsledný obrázok, ak vôbec nejaký vznikne. Tým, ako postupne maľujeme plné políčka alebo prázdne políčka, tak zmenšujeme počet tých o ktorých nič nevieme. Až nakoniec vieme o všetkých a krížovka je vyriešená.

Teraz nám ešte ostáva určiť spôsob ako začať a ako pokračovať. Na začiatku sú všetky políčka prázdne a pri prvom pohľade človeka, ktorý to nikdy neriešil veľa neuvidí. Pri každom vašom pohľade na krížovku musíte nájsť políčka o ktorých viete niečo povedať. Príklad:

Obr�zok



V tomto obrázku si všímnite stredný riadok. Riadky nad a pod ním sú už celé vyriešené, takže nás teraz nezaujímajú. A stĺpce si teraz nevšímajme.
Vidíme informáciu „6 4 4 5“. Keď sa pozrieme úplne na koniec riadku, tak vidíme 3 medzery a potom 3 políčka vyfarbené, 1 neznáme a 1 opäť vyfarbené. Posledná skupina políčok v tomto riadku má mať 5 políčok. Keby sme políčko vyfarbili na mieste prázdneho políčka, tak by sme presne získali skupinu o 5 políčkach a bola by to aj posledná skupina v tomto riadku. Takže táto možnosť je správna a to vyfarbené políčko tam bude. Predposledná skupina má mať 4 riadky a pri použití tej istej úvahy ako pred chvíľou dospojeme k tomu, že treba vymaľovať prázdne políčko. Presunieme sa do stredu, kde vidíme 4 prázdne políčka. Poslednú aj predposlednú skupinu už máme nakreslenú a mala by nasledovať skupina o 4 políčkach. Tá sa nám sem vojde perfektne, ale nie je tu žiadne vyfarbené políčko, ktoré by nás v tom utvrdilo. Veď aj kúsok vľavo sú už 4 políčka vyfarbené, čo ak sú to naše 4 políčka ? A tie 4 prázdne miesta majú byť medzery, teda paličky. Keby už nakreslené 4 políčka boli tie naše 4 políčka, potom by nám ostalo vymaľovať ešte 6 políčok naľavo od nich. Ale jediné prázdne miesto má už len 5 políčok. Stačíte ma ešte sledovať ? ;o) Skúsme teda radšej ísť spredu, teda zľava. Narazíme na 5 prázdnych políčok, sem sa 6 políčková skupina určite nevojde, kto neverí nech preráta, ak ani potom, tak treba vrátiť vysvedčenie z 1 triedy ZŠ. ;o). Ale my vieme, že prvá skupina má mať 6 prvkov. A my máme 5 voľných miesti. Z toho sa dá usúdiť, že tých 5 políčok môžme označiť ako prázdne, teda ic opaličkujeme.
Náš riadok teraz vyzerá takto:

Obr�zok



Pozerajme sa postupne zľava doprava. Vidíme nejaké opaličkované políčka a potom skupinu 4 políčok. Tieto 4 políčka budú určite patriť tej 6 skupinovej skupine políčok. Nevieme však kde budú tie zvyšné políčka. Za touto 6-kou sú 2 prázdne políčka. Teraz máme zase dilemu, či sa sem vojde tá 4-ka. ;o). Určite sa nevojde. A keby sa aj náhodou vošla, tak ešte nie je isté, že tam bude, pretože aj vpravo sú 4 miesta. V našom prípade sa nevojde a jediné miesto je vpravo na mieste 4 prázdnych miest. Tie teda môžme spokojne vymaľovať. No a teraz ešte musíme porozmýsľať nad tou 6-kou. V tomto riadku nám teda ostali 3 prázdne miesta. 1 medzera, 4 vyfarbené a za ním 2 medzery. Položme si teraz otázku, kde by tie políčka mohli byť ? Ak by sa tá 6-ka začínala na medzera vľavo, tak by sa končila na prvej medzera vpravo. Ak by sa aj nezačínala na medzere vľavo, tak by určite išla cez medzeru vpravo. Tá prvá medzera vpravo bude plne vymaľovaná, nech tú 6-ku tam umiestnite ako-koľvek. V našom prípade znamená ako-koľvek len 2 možnosti a v oboch je to políčko prekryté. Keby náhodou existovalo také umiestnenie tej 6-ky, že to políčko prekryté nebude, tak nemôžme povedať, že je na isto prekryté, lebo tá 1 možnosť môže nastať a naša istota sa rozplynie v plači nad pokazenou krížovkou...
Zatiaľ teda máme:

Obr�zok



Teraz môžu nastať 2 prípady. Buď tá 6-ka bude vľavo alebo vpravo. Šanca je 50:50. Tipovať však neodporúčam. Z tohto riadku sa toho už nedá vyskúmať, vudedukovať alebo vyčarovať viac. Čo teraz ? Mám si myslieť, že som blbý ? To rozhodne nie, viac si spraviť nemohol. Pokračovať len podľa informácii z riadkov sa nedá. Ale my máme aj stĺpce, a v nich sú ťiež informácie. Spojením týchto 2 zdrojov informácii o tej istej krížovke sa dá zisťiť, kde tá 6-ka bude. Pre stĺpce platia rovnaké úvahy ako pre riadky. Vždy keď na niečo prídete v riadku, zároveň si tým pomôžete aj v niektorom stĺpci.

Teraz už viete ako pokračovať. Ako však začať ?

Obr�zok


Tu je riadok, kde má byť 16 políčková skupina. Nech ju tam umiestnite akokoľvek, určite tam budú tieto políčka.

Obr�zok


Ak neveríte, tak skúste nájsť takú možnosť, kde tých 16 políčok nebude prechádzať cez tie, ktoré som vyznačil. Stačí Vám skúsiť dať tú 16-ku úplne vľavo, úplne vrapvo a kde sa Vám to pretne, tam máte tie políčka isté. Robte to však opatrne, dá sa to použiť na mnohých miestach, ale ľahko sa aj pomýlite, ak je tam viacej skupín a vám sa pretnú nejaké 2 rozličné skupiny.

Po niekoľkých vylúštených krížovkách začnete robiť niektoré veci automaticky a nebude Vám toľko trvať kým si zdôvodníte, že políčko je naozaj plné alebo prázdne. Stačí len trochu používať rozum a naostriť ceruzku a pripraviť pre istotu aj gumu.

Toľko ku maľovaným krížovkám a ich ručnému riešeniu. Teraz trochu ku počítačovému riešeniu.

Dokáže počítač riešiť maľované krížovky ?

Počítač dokáže všetko, čo ho naučíte, alebo naprogramujete, lebo samoučiace sa počítače ešte nie sú také dokonalé a rozšírené. Takže to čo nenaprogramujete sami Váš počítač nikdy robiť nebude.

Na úvod chcem povedať, že zatiaľ som sa nestretol so žiadnym programom alebo algoritmom, ktorý by maľované krížovky riešil. Skúšal som hľadať aj na internete, ale zatiaľ som nič nenašiel...

Obr�zok



Počítač má jednu výhodu od človeka. Je strašne rýchly. To, čo by človeku trvalo prejsť 10 rokov, on spraví za pár sekúnd. Ale aj naopak. Človek má výhodu „Pozriem a vidím...“. Pri riešení viete kam sa pozerať a už pri pohľade viete či sa oplatí uvažovať alebo je to na nič.

Najprv skúsme spočítať koľko je 10^20. Keby náš počítač vedel urobiť 1 miliardu operácii za sekundu, tak vykonanie 10^20 operácií by mu trvalo 3170 rokov. 10^12 by mu trvalo 16 minút. Viac ako 10^12 je už veľa. A to predpokladáme miliardu operácii za sekundu, čo je viac ako dosť, lebo operácia zvyčajne nebýva 1 inštrukcia, ale aj celé funkcie.

Metóda 1: Brute Force. Nie je čo výmýšlať. Zoberme napríklad 20x20 políčok. To máme 400 políčok. Každé môže byť plné alebo prázdne. Takže to máme 2^400 možností. To je asi 10^120 operácii, bez kontroly či je to správna trefa. Na výsledok by ste si počkali a neverím, že by skôr nevypli prúd, nepresťahovali by ste sa Mars, že by skôr nezhaslo slnko a možno sa zrútil aj celý vesmír... Aj keby na tom robili všetky počítače planéty, tak by ste sa toho nedožili. Jedine, že by nejakou náhodou padol správny výsledok.

Metóda 2: Vylepšený brute force. Prečo triafať 400 políčok, keď iba niektoré budú plné. Stačí triafať buď plné alebo prázdne. Ďaľšie vylepšenie je triafať v riadku a stĺpci len toľko, koľko ich tam má byť.

Ďaľšie metódy sú niečo medzi brute force a rozmýšľaním...
Netreba triafať možnosti, keď vieme, že niektoré políčka pôjdu za sebou. Čo tak pri tom ešte testovať či je taká možnosť prípustná. No a pridajte ešte pár fínt ako skúšať len riadky a stĺpce, kde bola zmena, alebo, ktorý nie je prázdny a dostanete sa k celkom dobrému algoritmu. Ešte ho treba obmedziť len na skúšanie môžností, ktoré majú perspektívu a máte super algoritmus, ktorý rozmýšla ako človek, len mu to ide omnoho rýchlejšie. Toto aj bola podstata môjho algoritmu. Obmedziť, čo najviac bezduché skúšanie. Stačí ak viete riešiť krížovky ručne a odtiaľ pri riešení najlepšie zbadáte, ako uvažujete. Nepúštajte sa do veľkých a viacnásobných úvah typu „čo ak... potom...“, ale skôr sa sústredujte na to, čo sa dá urobiť po 1 úvahe. Môj algoritmus sa snaží tak ako ľudia spoliehať na tie políčka, ktoré považuje za isté. Jeho nedostatok je skúšanie možností, ktoré sa dajú generovať z jedného riadku alebo stĺpca. A zatiaľ neviem ako to trochu zlepšiť, lebo človek pozrie a vidí, ale program to nevie. Človek tak trochu vycíti alebo jednoducho si povie, že aha tamto budem rozmýšlať menej. Program to nevie.

Skúšal som aj či sa to nedá nejako vypočítať alebo nejako odvodiť z niečoho, ale okrem ľudskej metódy alebo skúšania som na nič neprišiel. Skúšal som použiť každú oblasť matematiky, algebru, pravdepodobnosť, operačnú analyzú, ale veľmi mi to nepomohlo. Operačnou analýzou sa mi podaril urobiť model, ktorý však nebol spojitý, za to však lineárny. Metódy riešenia ako napr. Land-Doigova metóda sú však asi ešte náročnejšie pri takom množstve bivalentných premenných. A ťiež som nevedel nájsť správnu účelovú funkciu.
Určite zaujímavých pár riadkov pre nezasvetených ľudí ;o).

Na záver prikladám zdroják prvej verzie MK. MK ako Maľované krížovky. Program si generuje možnosti a priebežne ich aj kontroluje. Nie je veľmi rýchly, slúži ako inšpirácia. Zdrojáky druhej verzie nedávam, lebo sa je v nich ťažko vyznať a nechcem vás nútiť pokračovať v mojom bordeli, navyše slovný opis som uviedol vyššie. Pravdaže, ak ich veľmi chcete, tak ich môžem poslať emailom. Prvá verzia obsahuje zdroják s týmito základmi. Druhá verzia len používa nejaké finty navrch, ako priebežná kontrola riadkov a stĺpcov, snaží sa generovať len prípustné kombinácie, riadky bez zmien preskakuje, a snaží sa tak trochu odhaliť riadky, kde to nemá žiadny zmysel. Funkcia permute je základom oboch verzíí. Generovanie všetkých možností však nie je najrýchlejšie. Avšak nevedel som sa tomu nijako vyhnúť... Ďalej som uvažoval nad nejakou lepšou verziou funkcie permute, ktorá by generovala možnosti viacej rovnomerne, lebo táto to robí zaradom. Ale ako obmedziť generovanie všetkých možnosti ?

Všetko som testoval na svojom PC Amd Duron 750 Mhz. Pamäť nehrá rolu, pretože program používa len pár kb. Niektoré časy môžu byť prehnané, lebo som mal zapnutú telku cez komp. Pri vašich programoch stopujte vždy čas release verzie, lebo debug je niekedy aj 100 krát pomalší. Ako základ by som bral krížovku Freda Flinstona, je to 30x30 a je to taká priemerne náročná krížovka. Výsledky môžete potom napísať do diskusie.

MK v1.0
Jeho výsledky sú od niekoľkých sekúnd po niekoľko minút. Krížovku 30x30 – Fred Flinstone riešil 30 minút. Väčšie krížovky som neskúšal, lebo by som asi pri tom umrel. Žiadne okienka, len jedno okno s konzolou.

MK v2.0
Priamy potomok MK v1.0. Je niekoľko sto násobne rýchlejší. A to všetko urobilo len pár fínt, ktoré som popísal hore. Ako generovať, len keď je treba, alebo preskočiť riadky, ktoré boli bez zmeny. Aj kontroly som obmedzil čo najviac. Program síce nefunguje, tak ako jeho predchodca, ale sú si dosť blízke. MK v2.0 rieši krížovky vcelku rýchlo. Krížovky do 30x30 rieši do pár sekúnd. Väčšie krízovky môže, ale nemusí riešiť dlhšie. Krížovky 50x70 a väčšie ani neskúšajte. Iba ak máte procesor 2Ghz a viac a máte aj dosť času ;o). Program nevie odhadnúť ako dlho mu to bude trvať, takže ak po pár minútach nevidno nijakú zmenu, tak to stopnite, pretože ak jedna zmena trvala 15 minút, tak ak sa krížovka vyrieši po 50 zmenách, tak to bude trvať dosť dlho.
K verzii 2.0 som dorobil win okienko, kde sa to kreslí a ponuku uložiť vyriešenú krížovku.
MK2 funguje tak, že vygeneruje každú prípustnú možnosť pre daný riadok a z tých, ktoré vyhovujú danému riadku urobí prienik. Tak sa ukáže, ktoré políčka tam budú naisto a ktoré nie. Napadli ma ešte zlepšenia, ako negenerovať všetky možnosti, ale trochu ich obmedziť. A potom ako sa vyhnúť generovaniu možností, ktoré určite budú zlé. Týmto sa to zrýchli na rýchlosť svetla.

MK v3.0
Táto verzia zatiaľ nie je dokončená, ešte do nej zrejme zapracujem spomínané finty na obmedzenie toľkých možností a bude to chodiť na každom PC do 500 až 1000ms.

Obe verzie používajú ten istý typ súborov typu *.mk. Prvý riadok obsahuje 2 čísla, „r s“, kde r je počet riadkov a s počet stĺpcov. Potom nasleduje r riadkov na každom sú čísla oddelené medzerou, ktoré určujú počet políčok v skupinách. Zápis zľava doprava, tak ako na obrázku maľovanej krížovky. Potom nasleduje riadok so znakom „#”, ktorý oddeluje riadky od stĺpcov. Potom nasleduje s stĺpcov na každom z nich sú čísla určujúce počet políčok v skupine. Písané zľava doprava, tak ako idú v krížovke v danom stĺpci smerom zhora dole.
Ako príklad si môžete pozrieť súbor cplusplus.mk.

Všetky použité maľované krížovky boli z Knihy Maľovaných krížoviek č. 4/03, prevažne s výsledkov minulého čísla.

Neskôr som zistil anglický ekvivalent, je ich niekoľko, napr. griddler alebo nonogram. Ostatné sa dajú nájsť na stránkach, kde je spomínaný griddler alebo nonogram. Takisto nájdete aj pár programov na ich riešenie.

http://www.softsklad.host.sk/c/mk1.zip

http://www.softsklad.host.sk/c/mk2.zip

http://www.softsklad.host.sk/c/mk3.zip

http://www.softsklad.host.sk/c/mk42.zip

http://www.softsklad.host.sk/c/MalovaneKrizovky42.zip

http://www.softsklad.host.sk/c/mk5.zip

http://frix.fri.utc.sk/~johny

http://www.softsklad.host.sk/c/mk_robic.zip
http://www.softsklad.host.sk/c/mk5.zip

A na záver niekoľko screenshotov mk2.
Buduce verzie mk solveru, ich popis a linky na stiahnutie sa budu objavovat v diskusii..




Obr�zok - Klikni a zv�?�� sa Obr�zok - Klikni a zv�?�� sa Obr�zok - Klikni a zv�?�� sa
Najnovsie clanky od tohto redaktora