Miinaharava ja matematiikka

Kirjoittanut Veikko Halmetoja · julkaistu 18.10.2026

Vuonna 2000 Windowsin vaatimaton ajanviete päätyi matematiikan lehteen. Birminghamin yliopiston matemaatikko Richard Kaye osoitti, että miinaharavaan liittyvä ongelma on NP-täydellinen. Sama vuosi oli se, jolloin Clay-instituutti lupasi miljoonan dollarin palkinnon P vastaan NP -ongelman ratkaisijalle. Miinaharava liittyi siis suoraan yhteen matematiikan suurimmista avoimista kysymyksistä.

Mikä ongelma tarkalleen?

Kaye tutki kysymystä, jota hän kutsui miinaharavan johdonmukaisuusongelmaksi. Annetaan kenttä, jossa osa ruuduista on avattu ja niissä näkyy numeroita. Onko olemassa jokin miinojen sijoittelu, joka sopii kaikkiin numeroihin?

Pienessä kentässä vastaus löytyy kokeilemalla. Mutta kun kenttä kasvaa, vaihtoehtojen määrä kasvaa räjähdysmäisesti. Rintaman jokainen avaamaton ruutu on joko miina tai ei, joten 100 ruudun rintamassa vaihtoehtoja on 2¹⁰⁰ – enemmän kuin maailmankaikkeudessa on tähtiä.

NP-täydellinen lyhyesti

Ongelmaluokka NP sisältää kysymykset, joiden ratkaisun voi tarkistaa nopeasti. Miinaharavan johdonmukaisuus kuuluu siihen: jos joku antaa sinulle miinojen sijoittelun, voit tarkistaa jokaisen numeron hetkessä. Vaikeaa on löytää sijoittelu.

NP-täydelliset ongelmat ovat NP:n vaikeimpia. Jos yhdellekin niistä löytyisi nopea ratkaisutapa, kaikki NP:n ongelmat ratkeaisivat nopeasti. Tähän joukkoon kuuluvat esimerkiksi kauppamatkustajan ongelma ja sudokun ratkaiseminen yleisessä muodossa. Kaye osoitti, että miinaharava kuuluu samaan joukkoon.

Logiikkapiirejä miinoista

Todistuksen idea on havainnollinen. Kaye rakensi miinaharavan numeroista ja avaamattomista ruuduista osia, jotka toimivat kuin sähköpiirin komponentit:

• Johto: pitkä kapea kuvio, jossa ruutujen tila välittyy päästä toiseen. Jos alkupäässä on miina, loppupäässä on miina, ja päinvastoin.
• Haara: kohta, jossa johto jakautuu kahdeksi.
• Portit: AND-, OR- ja NOT-portit, joissa ulostulon ruudun tila määräytyy sisääntulojen tiloista.

Kun näistä osista kootaan kenttä, kysymys ”onko olemassa sopiva miinasijoittelu” muuttuu kysymykseksi ”voiko tämän logiikkapiirin sisääntulot valita niin, että ulostulo on tosi”. Tämä on tunnettu NP-täydellinen ongelma (SAT), joten miinaharava on vähintään yhtä vaikea.

Myöhemmät tulokset

Lisäksi on osoitettu, että kun miinatiheys ylittää noin 25 %, kentän ratkaiseminen vaatii lähes aina arvauksia, joiden onnistuminen on epätodennäköistä. Vertailun vuoksi Windowsin vaikean tason tiheys on 20,6 %.

Tarkoittaako tämä, että peli on mahdoton?

Ei. NP-täydellisyys kertoo pahimmasta tapauksesta mielivaltaisen suurilla kentillä. Tavallinen 30 × 16 -kenttä on niin pieni, että ihminen ja tietokone ratkaisevat sen helposti. Suurin osa tilanteista ratkeaa muutamalla paikallisella säännöllä, jotka esittelemme sivuilla strategia ja kuviot.

Tulos on silti hyvä muistutus: kun kenttä näyttää vaikealta, se voi oikeasti olla sitä. Hyvä pelaaja ei yritä käydä läpi kaikkia vaihtoehtoja vaan etsii ensin paikallisia, varmoja päätelmiä.

Miljoonan dollarin miinaharava

Clay Mathematics Institute julkisti vuonna 2000 seitsemän Millennium-ongelmaa, joista kunkin ratkaisusta luvataan miljoona dollaria. Yksi niistä on P vastaan NP. Koska miinaharava on NP-täydellinen, nopea ja aina toimiva algoritmi miinaharavan johdonmukaisuuden ratkaisemiseen ratkaisisi samalla P vastaan NP -ongelman.

Palkintoa ei ole vielä jaettu.