Binární Tango

Znáte logickou hru Tango? Pojďme se na ni podívat podrobněji. Řekneme si, jak se hraje, a taky jak se generují úlohy. (Ano, dnes to bude trošku programátorštější...)

Před časem jsem, nevím co mě to napadlo, vlezl na LinkedIn a objevil jsem tam hru Tango. Neznáte?

Je docela jednoduchá. Máte mřížku 6x6 a do ní doplňujete jeden ze dvou symbolů: slunce, nebo měsíc. Pravidla jsou prostá:

• v každém řádku musí být tři slunce a tři měsíce

• mohou být vedle sebe maximálně dva stejné symboly

• hra má jednoznačné logické řešení a každý další krok by měl být odvoditelný dedukcí, tedy neměli byste hádat.

Vaším úkolem je zaplnit celou mřížku. Na začátku jsou některé symboly dané, ty nemůžete změnit.

A aby to nebylo takhle triviální, tak jsou někdy nezi dvěma sousedními políčky symboly “=” nebo “x” - pokud je mezi dvěma políčky “=”, musí. být symboly v obou políčcích stejné, pokud je tam “x”, musí být odlišné.

Tango / LinkedIn

Hra mě začala velmi bavit, ale štvalo mě, že mám jen jednu denně. Tak jsem začal hledat, jestli to je nějaká LinkedIn unikátnost, nebo jestli udělali už známou hru.

Není to unikátní. Tango vychází ze hry Takuzu (též Binairo a spousta dalších názvů). Najdete je online (třeba tady). Nejčastější je varianta 6x6, ale jsou možné i větší (8x8, 10x10…), s patřičně upravenými pravidly.

U varianty 8x8 jsem našel dvě verze pravidel. Podle jedněch můžete mít maximálně 2 stejné symboly vedle sebe (jako u 6x6), podle druhé můžete mít 3 stejné symboly vedle sebe.

Brzo jsem dohrál i ty, a tak nastal čas na vlastní generátor.

To přeci nemůže být těžké to naprogramovat…

… jsem si říkal. A jen tak zlehka jsem si tu myšlenku oťukával.

Protože jsem vyrostl v době osmibitů a binární čísla jsou mi druhým domovem, tak jsem na první pohled viděl: řádek má 6 symbolů. To je šesticiferné binární číslo. Těch je 64. Kolik z nich splňuje podmínky? Vygeneroval jsem si je všechny, pak jsem z nich vyhazoval ty, co neprošly (obsahovaly “000” nebo “111”, popřípadě měly nestejný počet jedniček a nul), a zůstalo jich přesně 14.

Pokud vás to zajímá, jsou to tyto kombinace: "001011","001101","010011","010101","010110","011001","011010","100101","100110","101001","101010","101100","110010","110100"

(Skript zde)

U verze 8x8 záleží na “pravidle společných znaků”. Pokud povolíme max. 2 vedle sebe, máme 34 možných kombinací. Pokud povolíme 3 vedle sebe, je jich 62.
Verze 10x10 má 84 kombinací (opakování 2), 194 kombinací (opakování 3), nebo 242 kombinací (opakování 4).
Ověřit si to můžete zde.

Pokud chci hru a la Binairo generovat, tak musím začít od konce, tj. s platným řešením. To je krok 1. V kroku 2 odeberu náhodný symbol a zkusím, jestli má hra řešení. Pokud ano, odebírám další symbol. Pokud řešení nemá, tak ten stávající vrátím a zkusím odebrat jiný. Když už není co odebrat, mám hotové zadání.

Nejprve jsem si zkusil udělat základní variantu, bez těch znaků “=” a “x”, tedy klasické Binairo, jaké najdete třeba zde.

Generování platného řešení

V každém řádku může být jedna ze 14 hodnot. (V tuto chvíli jsem zapomněl na slunce a měsíce a držel jsem se jedniček a nul.) Ale ne naprosto libovolně. První řádek je OK, tam můžu dát cokoli. Druhý řádek taky. U třetího řádku musím přemýšlet, aby mi někde ve sloupci nevznikla posloupnost tří stejných znaků…

Šlo by to řešit algoritmicky, ale já na to šel prostě: připravil jsem si pro každý nový řádek masku - vlastně regulární výraz. Ten vznikl tak, že jsem si prošel všechny předchozí řádky a z nich jsem určil, jestli na dané pozici musí být 1, 0, nebo cokoli (“.”), a pak jsem seznam povolených kombinací vyfiltroval touto maskou.

Začínám s maskou “……” (šest teček, šestkrát cokoli). Touto maskou projdou všechny kombinace, takže z nich jednu náhodně vyberu. Dejme tomu 100101.

Teď si udělám masku pro druhý řádek. Beru sloupec po sloupci, i když jsou nehotové, a kontroluju, jestli tam náhodou už nejsou tři stejné symboly, nebo jestli na konci sekvence nejsou dva stejné symboly. Pokud jsou v sekvenci dva stejné, v masce musí následovat ten opačný. Pokud jsou v sekvenci už tři jednoho typu, v masce musí být opačný. A takhle si po sloupcích vygeneruju celou masku.

Pro druhý řádek je zase maska “……”. Tedy jakákoli kombinace vyhoví, a mně náhoda určila “001011”.

Opět si generuju masku, po sloupcích. První sloupec je 10, následovat může cokoli, takže maska pro první sloupec je “.”, druhý sloupec ale tvoří 00, takže v masce pro druhý sloupec musí být “1” (aby nevznikla trojice). A tak dál. Výsledná maska pro třetí řádek bude “.1...0”

Vyberu ze sady kombinací takové, které odpovídají této masce (skript zde). Jsou to tyto: ["010110","011010","110010","110100"]

Z nich zvolím jednu. Mně vyšlo “011010”… Opět pokračuju, tvořím masku, další řádek, dokud jich nemám šest. Pokud se mi nepodaří obsadit další řádek, vrátím se o krok zpět a zkusím jinou dostupnou kombinaci.

Už z popisu algoritmu je jasné, že jde o rekurzivní funkci, říkejme jí třeba addRow. Na vstupu má aktuální hrací pole (na začátku prázdné). Pokud má pole šest řádků, funkce končí. Pokud ne, tak se vytvoří maska a vybere se hodnota. Není-li žádná dostupná, vracím chybu. Vybranou hodnotu přidám k herní ploše a volám opět addRow. Buď vrátí kompletní herní pole a já se vracím, nebo vrátí chybu, a pak vybírám jinou hodnotu, která vyhoví masce…

Poznámka z praxe k “výběru náhodné hodnoty” - lepší než “vybírat náhodné” je vzít si všechny možné, zamíchat je, vybrat první a odstranit ji ze seznamu. Když nevyhovuje, vezmu další…

A tak mám nakonec hotové řešení. Teď z něj potřebuju připravit zadání.

Věřte nebo ne - má to logické řešení!

Mezikrok: Řešitel

Předložit hráči vyřešenou hádanku nelze. Sice by ho to možná překvapilo, ale nezahrál by si. Proto je potřeba redukovat nápovědy. Princip jsem už nastiňoval: odeberu z herní plochy jeden symbol a kontroluju, jestli je úloha ještě řešitelná a má právě jedno řešení.

Potřebuju proto další část algoritmu, anglicky zvanou “solver”, česky asi “řešitel”. Je to algoritmus, který dostane předvyplněnou mřížku a pokouší se logicky dojít k řešení. Jakmile se dostane do bodu, kdy není schopen určit, jak pokračovat, tak vrátí chybu. Jsou dva možné scénáře, kdy se dostane do problémů: buď nemůže přidat symbol, protože by porušil pravidla, anebo nemá k dispozici žádné volné pole, které by mohl na základě pravidel obsadit, a musel by tipovat: “Vyšlo by to, kdybych sem dal 1?”

Nejjednodušší je toto “spekulativní řešení” zakázat a naprogramovat “konzervativní solver”. Důsledkem je ta věta v pravidlech o tom, že “zadání má jednoznačné logické řešení”. To není proto, aby vám to tvůrci ulehčili, to je proto, že solver nespekuluje a řeší úlohu konzervativně.

V podstatě ho řeší stejně jako vy. Ta pravidla, jak řešit Binairo, jsou poměrně jednoduchá:

• jakmile jsou někde dva stejné symboly, musí okolo nich být opačné: “00” vede k “1001” a vice versa. Samozřejmě, na začátku nebo na konci řádku nedoplňujete symbol mimo mřížku. :)

• Jakmile jsou někde dva stejné symboly s jednou mezerou (“1.1” nebo “0.0”), musí být uprostřed opačný. Jinak by vznikla trojice.

Primitivní solver si s tímto vystačí, ale pokud budete řešit jen těmito pravidly, tak výsledky budou příliš jednoduché. Musíte si objevit i další pravidla. Například toto: