Ratsun kierto Pythonilla

Laudan luominen

Aivan ensimmäiseksi tarvitaan jokin järkevä tietorakenne kuvastamaan shakkilautaa. Käytetään tässä yksinkertaisuuden vuoksi sisäkkäisiä listoja, joiden suorituskyky riittää naiiviin ratkaisuumme mainiosti. Pythonin listat ovat sisäisesti taulukkoja, joissa indeksointi on vakioaikaista. Lautamme tulee siis olemaan lista listoja, joiden elementit ovat laudan ruutuja.

Aloitetaan kirjoittamalla pohja funktiolle, joka luo laudan. Olkoon lauta aluksi vaikkapa tyhjä lista, joka palautetaan kutsujalle. Haluamme toki, että samalla funktiolla voi luoda monen kokoisia lautoja, joten otetaan laudan koko vastaan parametrina. Kielen dynaamisen tyypityksen ansiosta parametrin tai laudan tyyppejä ei tarvitse erikseen määrittää.

def luolauta(koko):
    lauta = []
    return lauta

Voit testata pääohjelmassa, millaisen laudan funktiomme missäkin vaiheessa luo. Pythonissa listojakin voi tulostaa antamalla ne suoraan print-funktiolle.

def main():
    lauta = luolauta(5)
    print(lauta)

Seuraavaksi lautaan tulisi saada oikea määrä rivejä. Intuitiivisin tapa lienee kirjoittaa silmukka, joka lisää laudalle parametrina saadun leveyden verran tyhjiä listoja.

def luolauta(koko):
    lauta = []
    for i in range(koko):
        lauta.append([])
    return lauta

 
Lopuksi lisätään vielä jokaiselle riville oikea määrä ruutuja vastaavalla silmukalla. Eli sen sijaan, että rivin paikalle lisättäisiin tyhjä lista, lisätäänkin lista, joka sisältää parametrina saadun luvun verran elementtejä. Kuvataan ruutuja kokonaisluvuilla, jotta voimme säilyttää niissä ratsun siirtojen numeroita. Koska yhtäkään siirtoa ei ole vielä tehty, alustetaan lauta täyteen nollia.

def luolauta(koko):
    lauta = []
    for i in range(koko):
        rivi = []
        for j in range(koko):
            rivi.append(0)
        lauta.append(rivi)
    return lauta

 
luolauta-funktio toimii nyt oikein ja sillä voi luoda halutun kokoisen laudan, mutta toteutus ei ole Pythonin standardeilla kovinkaan elegantti. Funktio voidaan tiivistää kielen tarjoaman näppärän listakomprehension avulla jopa yhteen riviin.

def luolauta(koko):
    return [[0 for ruutu in range(koko)] for rivi in range(koko)]

Laudan tulostaminen

Tuloste ei muistuta vielä ihan shakkilautaa, koska print-funktio ei osaa itsekseen muotoilla tulostetta oikeanlaiseksi. Kirjoitetaan siis tyhjä pohja omalle tulostalauta-funktiolle, joka tulostaa laudan nätisti.

def tulostalauta(lauta):
    pass

 
Voimme jälleen silmukoida laudan läpi rivi kerrallaan ja tulostaa jokaisen rivin ruutu kerrallaan.

def tulostalauta(lauta):
    for rivi in lauta:
        for ruutu in rivi:
            print(ruutu)

Korvataan pääohjelman print-kutsu tulostalauta-kutsulla.

def main():
    lauta = luolauta(5)
    tulostalauta(lauta)

Nyt funktio tulostaa ruudut yksitellen, mutta lisää jokaisen perään rivinvaihdon. Tämä voidaan korjata vaihtamalla print-kutsun end-parametrin sisältö oletusarvoisesta rivinvaihdosta tyhjään merkkijonoon. Tulostetaan vielä yksi rivinvaihto tyhjällä print-kutsulla jokaisen rivin perään. Nyt ruudut tulostuvat omille riveilleen, mutta kiinni toisiinsa. Lisätään siis jokaisen ruudun perään vielä välilyönti. Emme kuitenkaan voi summata kokonaislukutyyppistä ruutua ja merkkijonotyyppistä välilyöntiä suoraan keskenään, joten muutetaan ruutu ensin merkkijonoksi str-funktiolla.

def tulostalauta(lauta):
    for rivi in lauta:
        for ruutu in rivi:
            print(str(ruutu) + ' ', end='')
        print()

Nyt jokainen ruutu tulostuu nätisti omalle paikalleen. Tuloste menee kuitenkin sekaisin, kun alamme täyttää lautaa ja osa ruuduista sisältää yli kymmenen olevia askelnumeroita. Pakotetaan siis vielä jokainen ruutu tulostumaan kahden merkin mittaisena käyttämällä format-funktiota.

def tulostalauta(lauta):
    for rivi in lauta:
        for ruutu in rivi:
            print(format(ruutu, '02d') + ' ', end='')
        print()

Valmiin tulostalauta-funktion tulisi nyt siis tuottaa alla oleva tuloste tyhjästä laudasta.

00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00

Ratkaisualgoritmi: ensimmäinen askel

Kun lauta on saatu luotua ja tulostettua, voimme alkaa rakentamaan ratkaisua itse ongelmaan. Perusideana on kirjoittaa rekursiivinen funktio, joka siirtää ratsun vapaana olevaan ruutuun ja toistaa itseään niin kauan, kunnes koko lauta on täytetty. Ratsu voi kullakin askeleella liikkua kaksi ruutua eteenpäin ja yhden sivulle, tai yhden ruudun eteenpäin ja kaksi sivulle. Jokaisesta ruudusta voi siis jatkaa yhteensä kahdeksaan uuteen ruutuun, olettaen että nämä ruudut eivät ole laudan rajojen ulkopuolella tai jo askellettuna. Voit varmistaa tämän itse hahmottelemalla siirtoja ruutupaperilla.

Tallennetaan ensin kaikki eri siirtomahdollisuudet yhteen globaaliin muuttujaan, joka sisältää tässä tapauksessa kahdeksanalkioisen listan. Siirron tietotyypiksi sopii hyvin kokonaislukuja sisältävä tuple, joka luodaan kirjoittamalla luvut kaarisulkeiden sisään pilkulla erotettuna. Globaalit muuttujat on hyvä määrittää heti ohjelman alussa. Yleinen käytäntö on myös kirjoittaa tällaiset vakiot isoilla kirjaimilla.

SIIRROT = [ (1,2),(1,-2),(-1,2),(-1,-2),
            (2,1),(2,-1),(-2,1),(-2,-1) ]

Määritetään myös aloitusruudun paikka globaalissa muuttujassa, jotta sitä on helppo vaihtaa myöhemmin. Paikkaa kuvataan kahdella luvulla, joista ensimmäinen on x-koordinaatti ja toinen on y-koordinaatti.

ALKUPAIKKA = (0,0)

Samalla voimme siirtää laudan koon globaaliin muuttujaan ja käyttää tämän muuttujan arvoa luolauta-kutsussa.

KOKO = 5
ALKUPAIKKA = (0,0)
SIIRROT = [ (1,2),(1,-2),(-1,2),(-1,-2),
            (2,1),(2,-1),(-2,1),(-2,-1) ]
    
def main():        
    lauta = luolauta(KOKO)
    tulostalauta(lauta)

Aloitetaan itse ratkaisualgoritmin kirjoittaminen luomalla tynkätoteutus funktiolle, joka saa parametrinaan laudan, aloitusruudun paikan sekä askeleen numeron. Kutsutaan samalla tätä funktiota pääohjelmasta antamalla sille aiemmin luotu lauta, globaalista muuttujasta löytyvä aloituspaikka ja ensimmäisen askeleen numero.

def ratsasta(lauta, paikka, askel):
    pass
    
def main():
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)
    tulostalauta(lauta)

paikka-parametri on kaksi lukua sisältävä tuple, joten sen sisällön voi Pythonissa purkaa kätevästi kahteen muuttujaan. Kielen aiemmissa versioissa saman on voinut tehdä jopa suoraan parametrilistassa, mutta tämä ominaisuus poistettiin versiossa 3.0.

def ratsasta(lauta, paikka, askel):
    x, y = paikka

Nyt vain asetetaan askellettavaan paikkaan parametrina saatu askelnumero ja ratsumme ottaa ensimmäisen askeleensa. Oikeaan ruutuun askeltamisen kanssa tulee kuitenkin olla erittäin tarkkana. Lautamme koostuu listoista, jotka kuvastavat laudan vaakasuuntaisia rivejä. Näin ollen meidän tulee ensin valita laudalta oikea rivi y-koordinaatin perusteella. Tästä rivistä valitsemme oikean paikan x-koordinaatin perusteella. paikka-muuttujan x- ja y-koordinaatteja käytetään siis ikään kuin väärässä järjestyksessä verrattuna normaaliin koordinaatistoon. Hahmottele laudan ja koordinaattien rakennetta paperilla, jos asia tuntuu epäselvältä.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel

Kun nyt ajamme ohjelman, pitäisi tulostua lauta, jossa ensimmäinen siirto on tehty paikkaan (0,0). Testaa vielä, vaihtuuko ensimmäisen siirron paikka, jos muutat globaalin ALKUPAIKKA-muuttujan arvoa esimerkiksi pisteeseen (1,2).

00 00 00 00 00 
00 00 00 00 00 
00 01 00 00 00 
00 00 00 00 00 
00 00 00 00 00

Ratkaisualgoritmi: seuraava askel

Ratsumme osaa nyt asettua annettuun aloituspisteeseen. Yritetään seuraavaksi ottaa tästä pisteestä askel johonkin suuntaan. Kaikki jatkomahdollisuudet aloituspisteestä voidaan laskea helposti auki globaalin SIIRROT-listan arvoista. Liikutetaan ratsua listan ensimmäisen siirron mukaan. Otetaan siis SIIRROT-listan ensimmäinen alkio ja puretaan se deltax- ja deltay-muuttujiin. Seuraavaksi lasketaan ratsun uusi paikka summaamalla siirron arvot ratsun nykyiseen sijaintiin. Lopuksi sijoitetaan seuraava askelnumero tähän uuteen paikkaan.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    deltax, deltay = SIIRROT[0]
    uusix, uusiy = (x+deltax, y+deltay)
    lauta[uusiy][uusix] = askel+1

Nyt pitäisi tulostua lauta, missä seuraava askel on otettu paikkaan (3,4).

00 00 00 00 00 
00 00 00 00 00 
00 01 00 00 00 
00 00 00 00 00 
00 00 02 00 00

Jos kuitekin yrittämme tehdä vastaavan siirron aloittamalla esimerkiksi oikean alakulman pisteestä (4,4), uusi paikka on laudan ulkopuolella ja ohjelma kaatuu.

IndexError: list index out of range

Tarvitsemme siis funktion, joka tarkistaa, voiko uuteen paikkaan siirtyä. Annetaan tälle funktiolle parametrina lauta ja potentiaalinen uusi paikka. Funktio tarkistaa muutamalla ehtolauseekkeella, onko uusi paikka laudan sisällä ja palauttaa tämän perusteella totuusarvon True tai False.

def saakosiirtya(lauta, paikka):
    x, y = paikka
    return x >= 0 and y >= 0 and x < len(lauta) and y < len(lauta)

Toteutusta voi myös lyhentää hieman standardikirjaston min- ja max-funktioiden avulla, jotka palauttavat paikka-tuplen minimi- ja maksimiarvon. Mieti itse, miksi ja miten tämä toimii.

def saakosiirtya(lauta, paikka):
    x, y = paikka
    return min(x,y) >= 0 and max(x,y) < len(lauta)

Emme myöskään halua siirtyä ruutuun, jossa on jo käyty. Siispä tarkistetaan funktiossa vielä, että uusi paikka ei ole jo varattu. Koska tiedämme, että tyhjät paikat on täytetty nollilla, voimme vain tarkistaa, onko uudessa paikassa luku 0. Pidetään samalla mielessä, että lautamme käyttää x- ja y-koordinaatteja yhä päinvastaisessa järjestyksessä.

def saakosiirtya(lauta, paikka):
    x, y = paikka
    return min(x,y) >= 0 and max(x,y) < len(lauta) and lauta[y][x] == 0

Kun tarkistusfunktiomme on valmis, tarkistetaan sen avulla, onko seuraavan siirron kohde laudan rajojen sisällä ja tehdään siirto ainoastaan, jos näin on.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    deltax, deltay = SIIRROT[0]
    uusix, uusiy = (x+deltax, y+deltay)
    if saakosiirtya(lauta, (uusix, uusiy)):
        lauta[uusiy][uusix] = askel+1

Nyt voimme asettaa aloitusruuduksi minkä tahansa ruudun kentän rajojen sisältä, eikä ohjelma kaadu. Ratsumme jää tosin jumiin, jos yritämme askeltaa ulos kentältä.

Ratkaisualgoritmi: rekursio

Jotta ratsumme askeltaisi useammin kuin kerran, on ratsasta-funktio saatava toistamaan itseään. Funktion sisältöä tarkasteltaessa huomataan, että toisella rivillä se osaa jo asettaa ratsun parametrina saatuun paikkaan. Siispä sen sijaan, että asettaisimme seuraavan paikan funktion viimeisellä rivillä, korvataankin viimeinen rivi kutsulla aliohjelmaan itseensä.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    deltax, deltay = SIIRROT[0]
    uusix, uusiy = (x+deltax, y+deltay)
    if saakosiirtya(lauta, (uusix, uusiy)):
        ratsasta(lauta, (uusix, uusiy), askel+1)

Jos asetamme aloituspaikaksi taas ruudun (0,0), huomaamme, että ratsu osaa nyt hyppiä loputtomasti samaan suuntaan, kunnes törmää kentän reunaan.

01 00 00 00 00 
00 00 00 00 00 
00 02 00 00 00 
00 00 00 00 00 
00 00 03 00 00

Koska askelnumeron asettaminen tapahtuu nyt vain kerran funktion toisella rivillä, voimme myös poistaa turhaa purkamista ja pakkaamista rekursiivisen kutsun yhteydessä.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    deltax, deltay = SIIRROT[0]
    uusipaikka = (x+deltax, y+deltay)
    if saakosiirtya(lauta, uusipaikka):
        ratsasta(lauta, uusipaikka, askel+1)

Ratsumme liikkuu nyt muuten oikein, mutta osaa siirtyä vain yhteen suuntaan. Sen sijaan, että yrittäisimme siirtää ratsua vain SIIRROT[0]-paikan arvojen mukaan, silmukoidaan koko SIIRROT-lista läpi ja yritetään siirtyä listan jokaisen arvon mukaan.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    for deltax, deltay in SIIRROT:
        uusipaikka = (x+deltax, y+deltay)
        if saakosiirtya(lauta, uusipaikka):
            ratsasta(lauta, uusipaikka, askel+1)

Kun ajamme ohjelman, ratsumme on yllättäen täyttänyt koko laudan.

01 16 15 12 13 
16 13 12 07 14 
15 02 09 04 11 
14 17 06 13 08 
07 14 03 10 05 

Tulos ei kuitenkaan ole kunnollinen kierros, sillä siinä esiintyy esimerkiksi askel 14 useammin kuin kerran. Tämä johtuu siitä, että algoritmimme osaa myös peruuttaa, lähestulkoon vahingossa. Jokaisen ratsasta-kutsun yhteydessä ratsumme yrittää askeltaa kaikkiin potentiaalisiin uusiin ruutuihin. Jos ratsu päätyy ruutuun, josta ei ole yhtäkään validia jatkomahdollisuutta, rekursio päättyy tältä osin ja ratsu palaa takaisin edelliseen ruutuun yrittämään uudelleen. Askel 14 on siis yritetty ottaa useammin kuin kerran ja vanhat yritykset on jätetty laudalle.

Siispä jos silmukkamme on kiertänyt läpi kaikki nykyisen ruudun jatkomahdollisuudet, eikä yksikään niistä ole ollut validi, tiedämme, että ratsumme lähtee peruuttamaan. Tässä tapauksessa nykyiseen ruutuun tulee asettaa luku 0, jotta siihen voidaan jatkossa hypätä uudelleen.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    for deltax, deltay in SIIRROT:
        uusipaikka = (x+deltax, y+deltay)
        if saakosiirtya(lauta, uusipaikka):
            ratsasta(lauta, uusipaikka, askel+1)
    lauta[y][x] = 0

Kun ajamme ohjelman, saamme muutaman sekunnin kuluttua toisen seuraavista tulosteista:

00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00 
00 00 00 00 00

Runtime exceeded, maybe loop forever

Miksi ratsumme, joka äsken täytti laudan lähes täydellisesti, ei ole nyt tehnyt mitään järkevää? Ongelmana on, että emme ole missään vaiheessa määrittäneet, milloin suoritus on valmis. Nyt ratsu kiertää joka ikisen mahdollisen reitin laudalla ja lähtee peruuttamaan viimeistään siinä vaiheessa, kun koko lauta on täytetty. Ohjelman suoritus päättyy vasta, kun kaikki reitit on kierretty läpi ja alkuruudusta ei ole enää uusia jatkomahdollisuuksia. TIM pysättää suorituksen automaattisesti kymmenen sekunnin kuluttua, joten koko lautaa ei välttämättä ehditä kiertämään. Alempi tuloste johtuu tästä.

Määritellään siis, että jos nykyinen askelnumero on saavuttanut laudan ruutujen määrän, ongelma on ratkaistu ja ohjelman suoritus voidaan lopettaa. Lopetetaan suoritus myös siinä tapauksessa, jos kaikki jatkomahdollisuudet on käyty läpi ja ratsu on ensimmäisessä ruudussa. Tässä tapauksessa lautaa ei voi ratkaista kyseisestä aloitusruudusta.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    if askel == KOKO * KOKO:
        exit()
    for deltax, deltay in SIIRROT:
        uusipaikka = (x+deltax, y+deltay)
        if saakosiirtya(lauta, uusipaikka):
            ratsasta(lauta, uusipaikka, askel+1)
    lauta[y][x] = 0
    if askel == 1:
        exit()

Siirretään vielä tulostuskutsu pääohjelmasta ratsasta-funktion sisään, jotta ehdimme näkemään ratkaistun laudan ennen suorituksen lopetusta. Jos ratkaisua ei ole olemassa, tulostetaan tieto siitä.

def ratsasta(lauta, paikka, askel):
    x, y = paikka
    lauta[y][x] = askel
    if askel == KOKO * KOKO:
        tulostalauta(lauta)
        exit()
    for deltax, deltay in SIIRROT:
        uusipaikka = (x+deltax, y+deltay)
        if saakosiirtya(lauta, uusipaikka):
            ratsasta(lauta, uusipaikka, askel+1)
    lauta[y][x] = 0
    if askel == 1:
        print('Ratkaisua ei ole olemassa.')
        exit()
        
def main():
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)

Aikavaativuudesta

Ohjelman toimintaa voi nyt testailla helposti eri kokoisilla laudoilla ja eri aloitusruuduilla muokkaamalla globaaleja muuttujia. Ratkaisu tosin perustuu raakaan voimaan ja lienee aikavaativuudeltaan nopeasti järkeiltynä luokkaa \(O(8^n)\), missä n on laudan ruutujen määrä. Standardikokoisella 8x8 shakkilaudalla askelluksia siis suoritetaan pahimmassa tapauksessa \(8^{64}\). TIM lopettaa ohjelman suorituksen kymmenen sekunnin jälkeen säästääkseen resursseja, joten isompien lautojen kanssa suoritus kannattaa ajaa omalla koneella.

Käynnistysparametrit

Lisätään vielä mahdollisuus syöttää laudan koko ja aloitusruutu samalla, kun ohjelma käynnistetään. Otetaan siis käynnistysparametrit vastaan käyttäjältä ja sijoitetaan ne globaaleihin muuttujiin. Pythonin tulkki ei kuitenkaan osaa implisiittisesti erottaa lokaaleja ja globaaleja muuttujia toisistaan. Jotta siis voisimme sijoittaa niihin arvoja pääohjelmassa, täytyy tulkille erikseen kertoa, että nyt viitataan globaaliin muuttujaan.

def main():
    global KOKO, ALKUPAIKKA
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)

Seuraavaksi otetaan käyttöön sys-moduuli, jotta parametreihin päästään käsiksi. Tuodaan samalla ast-moduulista literal_eval-funktio, jolla voidaan kätevästi parsia syötteestä aloituspiste, kun se syötetään muodossa (n,m). Annetaan tälle funktiolle samalla jokin käyttötarkoitusta paremmin kuvaava nimi; vaikkapa luopiste. Nämä rivit tulevat siis ohjelman alkuun, kommenttirivien perään.

import sys
from ast import literal_eval as luopiste

Sitten vain parsitaan käyttäjän syöttämät arvot sys.argv-listasta globaaleihin muuttujiin. Parametrit ovat tullessaan merkkijonoja, joten muutetaan laudan koko int-tyyppiseksi int-funktiolla ja aloituspiste tuple-tyyppiseksi luopiste-funktiolla.

def main():
    global KOKO, ALKUPAIKKA
    KOKO = int(sys.argv[1])
    ALKUPAIKKA = luopiste(sys.argv[2])
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)

Ohjelmalle voi antaa haluamansa arvot kirjoittamalla ne kutsussa ohjelman nimen perään tai tämän sivun pluginin Args-laatikoon alla olevalla tavalla.

5 (1,1)

Nyt ohjelma arvatenkin kaatuu, jos käyttäjä ei syötä kahta arvoa. Tarkistetaan siis kummankin parametrin kohdalla onko se annettu, ennen kuin lähdetään parsimaan sitä. Tarkistetaan samalla, että käyttäjän syöttämä laudan koko ei ole 0 ja annettu piste on laudan rajojen sisäpuolella.

def main():
    global KOKO, ALKUPAIKKA
    if len(sys.argv) > 1:
        koko = int(sys.argv[1])
        if koko > 0:
            KOKO = koko
    if len(sys.argv) > 2:
        paikka = luopiste(sys.argv[2])
        if max(paikka) < KOKO:
            ALKUPAIKKA = paikka
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)

Enää ohjelman saa rikki syöttämällä päättömiä arvoja, sillä esimerkiksi parametreja kissa ja koira ei voida muuttaa kokonaisluvuksi ja pisteeksi. Suljetaan vielä koko parametrien käsittely try-except-lohkoon, joka nappaa poikkeukset, mikäli parsiminen sellaisia aiheuttaa.

def main():
    global KOKO, ALKUPAIKKA
    
    try:
        if len(sys.argv) > 1:
            KOKO = int(sys.argv[1])
        if len(sys.argv) > 2:
            paikka = luopiste(sys.argv[2])
            if max(paikka) < KOKO:
                ALKUPAIKKA = paikka
    except:
        print('Virheellinen syöte.')
        exit()
        
    lauta = luolauta(KOKO)
    ratsasta(lauta, ALKUPAIKKA, 1)

Valmiissa muodossaan ohjelmalle voi siis syöttää mielivaltaisia arvoja ja jos syötteet ovat järkevää muotoa, niitä käytetään ohjelman suorituksessa. Muussa tapauksessa käytetään globaaleissa muuttujissa määritettyjä oletusarvoja.

Vaihtoehtoisesti myös laudan kokoa voi kuvata tuple-tyypillä, joka mahdollistaa muidenkin kuin neliskanttisten lautojen luomisen. Alla on toinen versio ohjelmasta toteutettuna tällä tavalla. Ohjelmalla voi luoda esimerkiksi 7x4-kokoisen laudan ja ratkaista sen aloittamalla viimeisestä ruudusta.