Survo-ristikko

Survo-ristikko on suomalaisen professori Seppo Mustosen vuoden 2006 alkupuolella esittämä ja tutkima matemaattinen peli. Ristikon nimi tulee Mustosen kehittämästä Survo-nimisestä tietojenkäsittelyjärjestelmästä. Survo-ristikoissa tehtävänä on täyttää m × n -taulukko luvuilla 1, 2, ..., m*n siten, että jokainen luvuista esiintyy vain kerran, ja että rivi- ja sarakesummat täsmäävät reunoilla annettuihin lukuihin. Taulukkoon on saatettu sijoittaa joitakin lukuja jo valmiiksi, jottei ratkaiseminen olisi liian hankalaa eikä mahdollisia ratkaisuja olisi yhtä enempää.

Survo-ristikot muistuttavat jossain määrin Sudoku- ja Kakuro-ristikoita. Ratkaiseva ero kumpaankin on siinä, ettei rajoituta vain lukuihin 1,2,...,9 ja siinä, että ristikon koko on yleensä varsin pieni. Survo-ristikoiden ratkaiseminen on myös sukua taikaneliöiden laatimiselle.

Survo-ristikkojen vaikeusaste vaihtelee suuresti. Helpot, koululaisille tarkoitetut, tehtävät edellyttävät pelkkiä peruslaskutoimituksia, kun taas hankalammat vaativat myös hyvää loogista päättelykykyä. Kaikkein vaikeimpia tehtäviä ei voi selvittää ilman tietokoneelle tehtyä ratkaisuohjelmaa.

Survo-ohjelmiston tietyt ominaisuudet (esimerkiksi editoriaalinen laskenta ja muun muassa kokonaislukujen rajoitettuja osituksia laskeva COMB-ohjelma) tukevat Survo-ristikkojen ratkaisua.

Survo-ristikkoja on julkaistu vuoden 2006 huhtikuulta lähtien säännöllisesti paitsi Survo-ohjelmiston ristikkosivuilla, hieman myöhemmin myös muun muassa Ilta-Sanomissa ja Yliopisto-lehdessä.

Esimerkki

Ratkaistaan helppo (vaikeusaste 25) Survo-ristikko, jossa on 3 riviä ja 4 saraketta:

	A	B	C	D
1		6			30
2	8				18
3			3		30
	27	16	10	25

Valmiiksi on annettuina luvut 3, 6 ja 8. Tehtävänä on löytää oikeat paikat lopuille luvuista 1–12 (3×4=12) siten että summat täsmäävät.

Ristikko ratkeaa vaiheittain yksikäsitteisesti seuraavasti: Taulukosta puuttuvat 9 lukua ovat 1,2,4,5,7,9,10,11,12. Ratkaisu kannattaa yleensä aloittaa rivistä tai sarakkeesta, jossa on vähiten puuttuvia lukuja. Tässä ristikossa sarakkeet A,B ja C ovat sellaisia.

Sarake A ei kuitenkaan ole kiitollinen, sillä puuttuvien lukujen summa 19 voidaan esittää sääntöjen sallimalla tavalla useassa muodossa (esimerkiksi 19=7+12=12+7=9+10=10+9). Sarakkeella B puuttuvien lukujen summa on 10, jolla on vain yksi mahdollinen esitys 10=1+9 sillä muut vaihtoehdot 10=2+8=3+7=4+6 sulkeutuvat pois jo taulukossa esiintyvien lukujen johdosta. Lukua 9 ei voi sijoittaa riville 2, koska silloin tuon rivin summa ylittäisi arvon 18. Siis taulukko täydentyy aluksi muotoon

	A	B	C	D
1		6			30
2	8	1			18
3		9	3		30
	27	16	10	25

Nyt sarakkeelle A jää vain vaihtoehto 27-8=19=7+12=12+7. Luku 7 ei voi kuitenkaan olla rivillä 1, sillä sen puuttuvien lukujen summa olisi 30-7-6=17, jonka ositus kahden luvun summaksi sallitulla tavalla ei onnistu. Taulukko saadaan näin muotoon

	A	B	C	D
1	12	6			30
2	8	1			18
3	7	9	3		30
	27	16	10	25

jolloin viimeisen rivin viimeiseksi luvuksi tulee 30-7-9-3=11

	A	B	C	D
1	12	6			30
2	8	1			18
3	7	9	3	11	30
	27	16	10	25

Ensimmäisellä rivillä puuttuvien lukujen summa on 30-12-6=12, jonka ainoa mahdollinen ositus on 12=2+10 vieläpä niin, että luku 2 tulee sarakkeeseen C; 10 tuolla paikalla aiheuttaisi sarakesumman 10 ylityksen:

	A	B	C	D
1	12	6	2	10	30
2	8	1			18
3	7	9	3	11	30
	27	16	10	25

Ristikko saa nyt välittömästi lopullisen ratkaisunsa, joka edellä olevien päättelyjen mukaan on ainoa mahdollinen

	A	B	C	D
1	12	6	2	10	30
2	8	1	5	4	18
3	7	9	3	11	30
	27	16	10	25

Edellisen kaltaisista, helpoista Survo-ristikoista selviää peruslaskutaidolla ja yksinkertaisilla loogisilla päätelmillä.

Survo-ristikoiden ominaisuuksia

Survo-ristikkojen pelisäännöt ovat jopa yksinkertaisemmat kuin Sudokujen. Itse ristikko on aina neliömäinen tai suorakaiteen muotoinen ja yleensä huomattavasti Sudoku-ristikkoa suppeampi puhumattakaan Kakuro-ristikoista, joita Survo-ristikot ehkä hieman enemmän muistuttavat.

Ratkaisutavat vaihtelevat suuresti muun muassa ristikon vaikeusasteesta riippuen ja se lisää tehtävien kiinnostavuutta. Helpoimmillaan esimerkiksi 2×3-tapauksessa (vaikeusaste 0)

		3	9
	6		12
9	7	5

ne sopivat esimerkiksi koululaisille yhteen- ja vähennyslaskun harjoitustehtäviksi.

Sitä vastoin esimerkiksi 3×4-ristikko (vaikeusaste 150)

				24
				15
				39
21	10	18	29

jossa ei ole annettuna yhtään valmista lukua ja jollaista sanotaan avoimeksi Survo-ristikoksi, on jo melko hankala, vaikka silläkin on vain yksi ainoa ratkaisu. Tämänkin tehtävän voi muuntaa asteittain kevyemmäksi antamalla joitain lukuja valmiina esimerkiksi muodossa

7		5		24
	1		8	15
		11		39
21	10	18	29

jolloin siitä tulee varsin helppo (vaikeusaste 0).

Tehtävien vaikeusasteen arviointi

Arviointi perustuu Mustosen ensimmäisen (huhtikuussa 2006) tekemän ratkaisuohjelman tarvitsemien ”mutaatioiden” määrään. Tuossa ohjelmassa ristikon ratkaiseminen tapahtuu osittain satunnaistetun algoritmin avulla. Ohjelma aloittaa sijoittamalla puuttuvat luvut umpimähkään taulukkoon ja yrittää sitten systemaattisin vaihdoin saada lasketut rivi- ja sarakesummat mahdollisimman lähelle oikeita summia. Menettely johtaa joko oikeaan ratkaisuun tai (kuten yleensä) se päätyy pattitilanteeseen, jossa se ei enää pysty parantamaan ratkaisuksi kelpaamatonta tulosta. Jälkimmäisessä vaiheessa tapahtuu "mutaatio", jossa kaksi tai useampia lukuja vaihtaa paikkojaan satunnaisesti. Tämän jälkeen yritetään parantaa tulosta jälleen systemaattisesti, kunnes joko päädytään ratkaisuun tai joudutaan turvautumaan uuteen mutaatioon. Ristikon vaikeutta kuvaavaksi tunnusluvuksi on valittu tarvittujen mutaatiokertojen lukumäärän keskiarvo, kun ratkaisu toistetaan esimerkiksi 1000 kertaa lähtemällä joka kerran täysin satunnaistetusta ristikosta. Mutaatioiden lukumäärä näyttää noudattavan melko läheisesti geometrista jakaumaa. Nämä numeeriset vaikeusasteet on muunnettu ”tähtiasteikolle” esimerkiksi Ilta-Sanomissa julkaistuissa ristikoissa seuraavasti:

Vaikeusaste

0–30	*
31–150	**
151–600	***
601–1500	****
1500–	*****

Näin ilmaistu vaikeusaste on vain suuntaa antava ja se saattaa olla jopa varsin harhainen silloin, kun ratkaisuun pääsee ovelasti jollain hyvällä päätelmällä tai arvauksella.

Tämä mitta kuvaa tehtävän vaikeutta paremmin silloin, kun vaaditaan, että ratkaisija osoittaa samalla, ettei tehtävällä ole muita ratkaisuja, jolloin arvauksille ei jää sijaa.

Avoimet Survo-ristikot

Jos reunasummien lisäksi ei ole annettu yhtään ristikkoon tulevista luvuista 1,2,...,m*n, Survo-ristikkoa sanotaan avoimeksi. Kahta avointa m*n-ristikkoa pidetään olennaisesti erilaisina, jos niitä ei saa samoiksi vaihtamalla rivien ja sarakkeiden järjestystä eikä tapauksessa m=n myöskään vaihtamalla rivit sarakkeiksi (eli transponoimalla). Näissä ristikoissa kaikki rivisummat eroavat toisistaan ja samoin sarakesummat toisistaan. Olennaisesti erilaisten avoimien m*n-ristikoiden lukumäärää merkitään S(m,n).

Avoimiin Survo-ristikoihin kiinnitti ensimmäisenä huomiota Reijo Sund. Hän selvitti käymällä läpi Survo-ohjelmiston avulla kaikki 9!=362880 mahdollista ristikkoa, että S(3,3)=38. Tämän jälkeen Mustonen laski alkuperäisen Survo-ristikkojen ratkaisuohjelman avulla lähtien kaikista mahdollisista reunasummien jakaumista, että S(3,4)=583. Petteri Kaski sai tuloksen S(4,4)=5327 muuntamalla tehtävän täsmällisen peitteen (exact cover) ongelmaksi.

Mustonen laati kesällä 2007 toistaiseksi tehokkaimman ratkaisuohjelman, joka vahvistaa edelliset tulokset ja jolla on tähän mennessä saatu määrätyksi seuraavassa taulukossa olevat S(m,n)-arvot:

m/n	2	3	4	5	6	7	8	9	10
2	1	18	62	278	1146	5706	28707	154587	843476
3	18	38	583	5337	55815	617658
4	62	583	5327	257773
5	278	5337	257773
6	1146	55815
7	5706	617658
8	28707
9	154587
10	843476

Jo luvun S(5,5) laskeminen vaikuttaa nykytietojen valossa hyvin vaativalta tehtävältä.

Vaihtomenetelmä

Yhdistämällä Mustosen alkuperäisen ratkaisuohjelman periaate siihen, että varsinkin avoimen ristikon tapauksessa reunasummien tulot ennustavat usein melko hyvin lopullisessa ratkaisussa lukujen sijainnin, on kehitetty ns. vaihtomenetelmä. Siinä luvut 1,2,...,m*n asetetaan taulukkoon reunasummien tulojen osoittamassa järjestyksessä ja näin saadusta asetelmasta lasketaan reunasummat. Riippuen siitä, miten ne poikkeavat oikeista summista, pyritään vaihtamalla askeltaen aina kahden luvun paikkoja niin, että reunasummat saadaan täsmäämään. Vaihtomenettely muuntaa ratkaisun hiukan shakkitehtävää muistuttavaksi. Sen avulla on kuitenkin vaikea osoittaa ratkaisun yksikäsitteisyyttä.

Esimerkiksi varsin hankala avoin 4×4-ristikko (vaikeusaste 2050)

				51
				36
				32
				17
51	42	26	17

ratkeaa vaihtomenetelmällä 5 siirrolla. Alkuasetelma on tällöin

					Sum	OK	virhe
	16	15	10	8	49	51	-2
	14	12	9	4	39	36	3
	13	11	6	3	33	32	1
	7	5	2	1	15	17	-2
Sum	50	43	27	16
OK	51	42	26	17
virhe	-1	1	1	-1

ja ratkaisuun johtavat vaihdot (7,9) (10,12) (10,11) (15,16) (1,2). Survo-ohjelmistossa sukro /SP_SWAP hoitaa kaiken vaihtomenetelmässä tarvittavan kirjanpidon.

Pikapelit

Survo-ristikkoja voi ratkaista myös tietokoneavusteisesti pikapeleinä, jotka tarjoavat toisenlaisia haasteita. Vaativin pikapelimuoto toimii verkossa Java-sovelmana.

Siinä ratkaistaan avoimia 5x5-ristikoita pelkillä hiiren näpäytyksillä. Väärä valinta synnyttää musiikki-intervallin, jonka laajuus ja suunta kuvaavat virheen suuruutta. Tavoitteena kussakin pelissä on saavuttaa mahdollisimman korkea pistemäärä, jota kasvattavat oikeat valinnat ja vähentävät virhevalinnat ja käytetty aika.

Katso myös

• Sudoku
• Kakuro
• Taikaneliö

Aiheesta muualla

• Survo-ristikoita
• Suomalainen Survo-ristikko haastaa Sudokun
• Vaihtomenetelmästä
• Survo-ristikoiden ratkaisuohjelmista
• Pikapeli