Telefon Googlu porazí nejlepší lidské luštitele sudoku

Telefon Google Nexus S a aplikace Googles dokáží vyřešit hádanku sudoku rychleji než nejlepší lidští hráči. Úloha je přitom zadána na papíře.

Sdílet

Člověk pomocí smart phonu zadání nejprve vyfotografuje. Následuje OCR, při němž se rozpoznají vstupní hodnoty. Samotné luštění pak neprobíhá v telefonu, ten jen odešle zadání do výpočetního prostředí Google Apps/Google Googles. Na displeji se pak prakticky vzápětí zobrazí vyplněná mřížka.

Postup ukazuje video, inženýr Google zde předběhne mistryni USA v luštění Sudoku za rok 2009 Tammy McLeod. Soupeřce ukáže vyluštěnou úlohu na mobilu, nepřepisuje výsledek zpátky do papírového zadání (vyhrál by i pak?). Každopádně není divu, že Nexus S je na soutěžích v luštění sudoku zakázán.

Samotný algoritmus, pomocí něhož prostředí cloudu vyřeší úlohu, zde není přesněji specifikován.

Není to jediná ukázka rozpoznávání obrazu. Google Googles umí rozpoznávat např. také reklamy v tištěným médiích a automaticky vyhledat na internetu informace o příslušném produktu nebo značce. Telefon se snaží rozpoznávat i čárové kódy. Každopádně se jedná o hezkou ukázku toho, jak budou brzy vypadat aplikace rozšířené/obohacené (augmented) reality. Google nedávno prezentoval i technologii speciálních brýlí, při které aplikace automaticky překládá rozpoznané nápisy z jednoho jazyka do druhého a zobrazuje je uživateli rovnou v cílovém jazyce.

Video z YouTube

autor Pavel Houser

Další články z rubriky

Související články

Tagy

sudoku · ocr · augmented reality

pridat Linkuj | Jagg | Delicious | Facebook | vybrali.sme.sk

Komentáře

07.02.11, 14:54 SashaCZ

Postup řešení

Moc pěkně jsou některé metody vysvětleny a předvedeny na http://www.sudokuwiki.org/sudoku.htm
Vložíte zadaní a klikáte na tlačítko "TAKE STEP"

Zkuste si tam zadat (Import a sudoku) jedno 17-číselné sudoku, třeba toto:
000000010400000000020000000000050604008000300001090000300400200050100000000807000
Zvláštní, že na řešení nemusel program použít žádnou pokročilou techniku.

06.02.11, 15:41 lmecir

Netreba lustit hrubou silou

To je presne naopak - netreba lustit jako clovek, jsem-li pocitac.

06.02.11, 11:42 oldsoft

Netřeba luštit hrubou silou

Hrubá síla není třeba, zde algoritmus luštění "jako člověk":
http://www.algoritmy.net/article/1351/Sudoku

01.02.11, 22:27 lmecir

hrubá síla s ořezáváním

Asi by se ten popsaný algoritmus měl nazvat "hrubá síla s ořezáváním", protože se ořezávají (nedovyplňují) všechny varianty, kdy už "nelze pokračovat" ve vyplňování. Toto bohatě stačí, aby to počítač zvládnul děsně rychle.

01.02.11, 22:05 lmecir

hruba sila

A algoritmus vyplňující prázdná políčka počínaje tím, že do prvního "vrazí" 1 a zkontroluje, jestli to lze, pokud ne, zkusí 2, atd., Pokračuje dalším políčkem, kde to zkouší opět, a pokud někde "narazí" s tím, že se mu nepovede vrazit tam ani devítku, tak se vrátí na předchozí pole a zvýší v něm číslo byste za hrubou sílu už nepovažoval?

01.02.11, 20:15 Roky

To už tu nějakou dobu je.

Toto řeší bezplatná aplikace pro android Sudoku capture. Zvládá to i bez internetu rychle a zřejmě na jakémkoliv přístroji s androidem.

01.02.11, 14:23 pavelhouser

hruba sila

mozna si nerozumime, ale hrubou silou jsem myslel proste pokus projit vsechny moznosti, otrocky na kazde volne policko doplnovat 9 cislic a po vyplneni cele mrizky testovat, zda je to dobre. to bude nejaky astronomicky pocet moznosti...

01.02.11, 12:03 lmecir

hrubou silou

"urcite se to neda resit uplne jen hrubou silou" - naopak, pro počítač je triviální řešit to hrubou silou

25.01.11, 23:15 pavelhouser

sudoku

popravde receno nevim, jak je ted na tom sudoku a pocitacovy rozbor hry. urcite se to neda resit uplne jen hrubou silou.
mam pocit, ze pred cca 2 lety se napr. jeste nevedelo, jaky je minimalni pocet predvyplnenych cislic, aby to mohlo mit jednoznacne reseni.
btw, jako jsou "antipocitacove" sachove ulohy, existuji i nejake ulohy v sudoku snazsi pro lidske hrace nez pro programy? (asi ne)

25.01.11, 15:19 SashaCZ

Normální

Taky na tom nevidím nic zvláštního.

Jedna věc je načtení zadání z papíru (kamery už mají dost mpix, čísel je jen 10....)
Druhá věc luštění sudoku.
Opět velká výhoda PC, člověk prostě nemůže být lepší.

25.01.11, 10:00 Czenek

to scena

Naprogramování takové aplikace sice není velký problém, ale tady je ukázána hlavně schopnost telefonu řešit komplexní úlohy. Jenom vyextrahovat z fotografie zadání není úplně snadná věc (při různých perspektivách, úrovní osvětlení apod.) a že je vše řešeno na cloudu je ještě zajímavější.

Hlavně se mi líbí ta lehkost a nadsázka, se kterou Google často prezentuje svoje produkty.

25.01.11, 08:37 scena

Nedivím se

Není to až zase takový problém naprogramovat si "luštič" sudoku. Drobná komplikace je samozřejmě u větší obtížnosti, kde musíte simulovat "tahy dopředu".

Napsat vlastní komentář

Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.

Science World