Kakuro

A Kakuro  egy számrejtvény . _ A Kakuro név a japán kasan kurosu (加算ク ロス keresztösszeadás ) rövidítésből származik ; az Egyesült Államokban a rejtvényt Cross Sums néven is ismerik ).

Játékszabályok

A mező fekete és fehér cellákból áll. Több fehér cellát, amelyek vízszintesen vagy függőlegesen futnak egymás után, blokknak nevezzük . Minden egyes blokknál ismert azon számjegyek összege, amelyeknek ebben a blokkban szerepelniük kell. Vízszintes blokkoknál ezt az összeget általában közvetlenül a blokk bal oldalára írják, függőleges blokkoknál pedig közvetlenül fölé.

Minden fehér cellában meg kell adnia egy számjegyet 1-től 9-ig, hogy először is az egyes blokkokban lévő számjegyek összege megegyezzen a megadott számmal, másodszor pedig azért, hogy az egyes blokkok minden számjegye eltérő legyen.

Számítási összetettség

A kakuro probléma NP-teljes . A legfeljebb 3 csúcsfokozatú síkbeli vegyes gráf Hamilton részgráfjainak problémája redukálódik rá ( lásd a kakuro - feladat NP-teljességének bizonyítása ).

Linkek

• Hogyan válasszuk ki a kakurót (Utasítás a Nikoli kiadótól) (hu)
• A kakuro megoldásához szükséges számkombinációk listája (en)
• Orosz nyelvű oldal a kakuróról
• kakuro on-line

Szótárak és enciklopédiák	Nagy dán
Bibliográfiai katalógusokban	NKC : ph341314