RAC UNALNI STVO Sudoku kot poseben primer problema prevoza Dragana Božovič -> Čeprav je Sudoku na Japonskem postal priljubljen leta 1980, se je na zahod razširil šele leta 2004. Hitro je postal ena izmed najbolj uspešnih in priljubljenih ugank. Sudoku 9 x 9 mreža je danes vsakdanji del številnih časopisov. V svetu, kjer obstajajo aplikacije že za skoraj vse, tudi za Sudoku najdemo digitalne različice. V prejšnji številki Preseka [5] smo se naučili nekaj o problemu prevoza, tokrat se bomo poglobili v problem, ga povezali s Sudoku uganko in obravnavali Sudoku kot poseben primer problema prevoza. Igra Sudoku Spomnimo se najprej, kako je Sudoku uganka sploh sestavljena. Sudoku kvadrat lahko definiramo kot mrežo velikosti 9 x 9, pri cemer vsaka vrstica, vsak stolpec in vsak od devet označenih 3 x 3 blokov oz. kvadratov (slika 1) vsebujejo števila od 1 do 9, vsako natanko enkrat. Sudoku uganka je uganka, pri kateri so na zacetku nekatera polja zapolnjena, nekatera pa prazna. Cilj reševalca je, da izpolni prazna polja tako, da je rezultat pravilen Sudoku kvadrat. Sudoku uganke delimo glede na težavnost na stopnje od 1 do 5 [2]. Med težavnostjo Sudokuja in številom zacetnih števil, podanih v Sudoku mreži, ni nikakršne povezave. Obstajajo zelo težki Sudokuji, ki imajo zelo veliko podanih zacetnih števil, in tudi zelo lahki, ki jih imajo zelo malo [3]. S priljubljenostjo igre so se pojavile še razlicne (drugacne in težje) vrste Sudokuja, med njimi [4]: ■ Sudoku-X Pri tem Sudokuju moramo upoštevati še, da se morajo števila od 1 do 9 v diagonalah pojaviti le en- krat - tako nekateri Sudokuji pridobijo enolicno rešitev. Sodo-lihi Sudoku Tak Sudoku ima dolocena polja osencena. Na podlagi podane uganke razberemo, ali v osencena polja vpisujemo soda ali liha števila. Geometrijski Sudoku Kvadrat tega Sudokuja je sestavljen iz razlicnih geometrijskih likov, imenovanih nonomine. Razmejeni so z debelejšo crto. Sestavlja jih devet polj, v katere je potrebno vpisati števila od 1 do 9. BarvniSudoku To je Sudoku, pri katerem moramo upoštevati še, da se smejo števila od 1 do 9 v oznacenih obarvanih likih pojaviti le enkrat. SLIKA 1. Označeni 3 x 3 bloki oz. kvadrati 22 PRESEK 41 (2013/2014) 3 RACUNALNIŠ TVO Sudoku kot poseben problem prevoza Spomnimo se osnovne formulacije problema prevoza [5], s katerim minimiziramo stroške prevoza dobrin iz različnih izvornih tock (npr. skladišč) v različne končne točke (npr. trgovine): m n ■ minimiziraj z = X X ci,j • xi,j i=1j=l pri pogojih: n X xij < si za i = 1,... ,m j=i m X xitj > dj za j = 1,... ,n i=1 xi j > 0 za i = 1, ...,m in j = 1, ...,n ■ Število si predstavlja zalogo enot v izvorni točki i, kjer je i = 1 , . . . , m. ■ Število dj predstavlja, koliko enot naroča končna točka j, kjer je j = 1,...,n. S številom cij označimo, koliko stane prevoz ene enote od izvorne točke i do končne točke j, za i = 1,...,m in j = 1,...,n. S številom xi}j označimo, koliko enot pošljemo od izvorne točke i do končne točke j, za i = 1,...,m in j = 1 , . . . , n. Za podrobnejšo razlago si poglejte prejšnjo številko Preseka [5]. Reševanje uganke Sudoku zahteva, da 81 števil razporedimo v 81 čelič Sudoku mreže (oštevilčenje čelič vidimo na sliki 2). Zato v preoblikovanju Sudoku uganke v problem prevoza uporabimo 81 končnih točk, ki jih moramo upoštevati, vsaka s povpraševanjem ene enote (v vsako čeličo zapišemo natanko eno število). Na voljo imamo 81 števil, in sičer števila od 1 do 9, vsako natanko devet krat. V enačbi 1 torej velja m = 9 in n = 81. Naj bosta s množiča izvornih točk (v prejšnji številki Preseka [5] množiča skladišč) in d množiča končnih točk (v prejšnji številki Preseka [5] množiča trgovin) takšni, da je si = 9, za i = 1,..., 9 (vsako od devetih števil se pojavi devet krat), in dj = 1, za j = 1,..., 81 (vsak kvadratek Sudoku matrike 9 x 9 prejme eno število od omenjenih 81). Vsaka od devetih izvornih točk i lahko pošlje k vsaki od 81 končnih točk j eno enoto po čeni ci j. Ilustračija opisanega je prikazana na sliki 3. V nadaljevanju bomo opisali, kako določimo matriko čen, ki je prisotna pri vseh oblikah problema prevoza. Postopek izračuna matrike čen je povzet po [1]. Pri modeliranju različnih Sudoku ugank, množiči izvornih točk s in končnih točk d ostajata nespremenjeni. Strošek za čeno cij nastane pri prevozu ene enote od izvorne točke i do končne točke j. Zato je potrebno oblikovati matriko čen c, ki določi čeno prevoza ene enote od izvorne do končne točke. S pomočjo osnovne Sudoku matrike bomo najprej definirali devet pomožnih matrik n i, i = 1,..., 9 (za vsako število od 1 do 9 eno), velikosti 9 x 9, nato bomo iz teh matrik sestavili končno matriko čen. Matriko n1 ustvarimo na naslednji način: 1. Začnemo z matriko (i = 1) 1= 0 0 2. Poiščemo število 1 v osnovni matriki (če le-to obstaja). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 SLIKA 2. Oštevilčenje celic. 0 0 23 PRESEK 41 (2013/2014) 3 RAČUNALNIŠ TVO —^ 3. Na mesto, kjer smo v osnovni matriki našli število 1, damo v matriko rii število -1, vsa ostala mesta v isti vrstici, istem stolpcu in 3 x 3 kvadratu, v katerem se število nahaja, pa povečamo za 1. 4. Točki 2 in 3 ponovimo za vsako število 1 v osnovni matriki. Na enak način ustvarimo vse preostale matrike ni, i = 2,..., 9. Poglejmo si, kako postopek deluje na konkretnem primeru. Vzemimo Sudoku uganko s slike 4 in izra-čunajmo n9 (opazujemo torej mesta, kjer se v osnovni matriki nahaja število 9). Končno matriko cen sestavimo tako, da posamezna manjša matrika predstavlja eno vrstičo velike matrike. Torej i-ta vrstiča končne matrike je matrika ni, pri čemer vrstiče matrike ni postavimo zaporedoma eno zraven druge in dobimo vrstičo dolžine 81. Tako je dimenzija matrike čen, ki jo dobimo, enaka 9 x 81. Izkaže se, da ima za tako določeno matriko čen vsaka optimalna rešitev vrednost čiljne funkčije enako z = -N, kjer je N število števil, podanih v začetni Sudoku uganki. Sedaj, ko imamo določeno tudi matriko čen, lahko zapišemo Sudoku kot poseben problem prevoza. Naj bo M = {1, 2,..., 9},N = {1, 2,..., 81}, R = {1, 2, 3}. Formulirajmo omejitve našega problema prevoza: 9 81 minimiziraj z = i=1j=1 i,J 81 1- I Xi,J = si j=1 9 2- X x i=1 i,J = dJ i G M J G N 3- Xij G {0,1} i G M, J G N Te tri točke smo razložili in opisali v prejšnji številki Preseka [5]. Za pravilno Sudoku rešitev manjkajo še dodatne omejitve: V vsaki vrstiči se vsako število od 1 do 9 pojavi natanko enkrat: 4- X xK (J-1) -9+i = 1 J G M, k G M i=1 s1 = 9 1 Število k nam pove, za katero število preverjamo pogoj; k G M, ker moramo preveriti za vsa števila. Število j nam pove, za katero vrstičo preverjamo pogoj; j G M, ker moramo preveriti za vse vrstiče. Vsota, ki gre od i = 1 do i = 9, označuje sprehod čez čelotno vrstičo. si = 9 i Xi,J s9 = 9 9 1 d1 = 1 dJ = 1 81 d81 = 1 SLIKA 3. Prevozni model Sudoku uganke. J 24 PRESEK 41 (2013/2014) 3 24 RAČUNALNIŠ TVO Primer. k = 1, j = 3: preverjamo, ali pogoj velja za število 1 za 3. vrstico. Vsota opiše sprehod cez celice 19, 20, 21, 22, 23, 24, 25, 26, 27 (kot vidimo na sliki 2, so to celice 3. vrstice). V vsakem stolpcu se vsako število od 1 do 9 pojavi natanko enkrat: Primer. k = 1, j = 1: preverjamo, ali pogoj velja za število 1 za 1. stolpec. Vsota opiše sprehod cez celice 1, 10, 19, 28, 37, 46, 55, 64, 73 (kot vidimo na sliki 2, so to celice 1. stolpca). V vsakem od devetih označenih kvadratov se vsako število od 1 do 9 pojavi natanko enkrat: 5. X xk,(i-1)-9+j = 1 i=1 j G M, k G M Število k nam pove, za katero število preverjamo pogoj; k G M, ker moramo preveriti za vsa števila. Število j nam pove, za kateri stolpec preverjamo pogoj; j G M, ker moramo preveriti za vse stolpce. Vsota, ki gre od i = 1 do i = 9, oznacuje sprehod cez celotni stolpec. 6. X X xk,(a-1)-27+(b-1)-3 + (i-1)-9+j = 1 i=1j=1 k G M, a G R,b G R Število k nam pove, za katero število preverjamo pogoj; k G M, ker moramo preveriti za vsa števila. Števili a in b nam povesta, za kateri 3 x 3 kvadrat preverjamo pogoj; a G R, b G R, da tvorimo devet razlicnih parov (saj imamo devet razlicnih kvadratov). 4 2 1 0 6 3 4 7 8 2 6 3 6 1 5 8 5 2 3 7 9 1 8 4 1 5 4 2 1 9 6 3 4 7 8 2 6 3 6 1 5 8 5 2 3 7 (93 1 8 4 1 5 O O 1 1 1 1 1 1 1 1 -1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 2 1 1 1 1 -1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 -1 1 1 1 1 2 0 0 0 1 1 1 0 0 1 SLIKA 4. Primer matrike n PRESEK 41 (2013/2014) 3 25 RAČUNALNIŠ TVO ■ Dvojna vsota označuje sprehod cez celoten kvadrat. Primer. k = 1, a = 3, b = 1: preverjamo, ali pogoj velja za število 1 za 3 x 3 kvadrat v levem spodnjem kotu (glej sliko 1). Vsota opiše sprehod čez celice 55, 56, 57, 64, 65, 66, 73, 74, 75 (kot vidimo na sliki 2, so to celice kvadrata v levem spodnjem kotu). Sedaj je možno rešiti Sudoku uganko tako, da rešimo problem prevoza, predstavljenega z izvornim vektorjem 5, koncnim vektorjem d in matriko cen c ter z dodatnimi omejitvami (kot je definirano zgoraj). To lahko naredimo s pomocjo jezika za modeliranje v matematicni optimizaciji, kot je recimo AMPL. Pokazali smo, da lahko Sudoku uganko oblikujemo kot poseben primer problema prevoza. Primer reševanja Poglejmo delovanje metode na primeru. Naj bo podana naslednja Sudoku uganka A: A = 4 2 1 9 6 3 4 7 8 2 6 3 6 1 5 8 5 2 3 7 9 1 8 4 1 5 Najprej za vsa števila od 1 do 9 tvorimo matrike Ui. Za lažjo predstavo si poglejmo matriko za i = 3: n<3> = 1 0 0 0 0 0 1 1 2 2 1 1 1 1 1 -1 1 2 1 0 0 0 0 0 1 1 2 2 1 1 1 1 1 2 1 -1 1 0 0 0 0 0 2 1 1 1 0 0 0 0 0 2 1 1 1 1 1 0 0 0 1 0 1 -1 1 1 1 1 1 2 1 2 1 1 1 0 0 0 1 0 1 Iz matrik n i, i = 1,..., 9, sestavimo matriko cen c, velikosti 9 x 81, zapisano v tabeli 1. Odebeljeno označen del matrike ri3 vidimo na začetku tretje vrstice matrike c. V jeziku AMPL ustvarimo datoteke .mod, .dat in .txt (pomen in sestavo teh smo pojasnili v prejšnji številki Preseka [5]). Algorithm 1 AMPL model (.mod) set M := {1. ■ 9}; set N := {1. .81}; set R := {1. ■ 3}; param c {M,N}; param s {i in M}; param d {j in N}; var x {i in M,j in N} binary; minimize Sudoku: sum {i in M, j in N} c [i,j]*x[i,j]; subject to ponudbe {i in M}: sum {j in N} x[i,j] = s[i]; subject to povpraševanje {j in N}: sum {i in M} x[i ,j] = d[j]; subject to vrstica {i in M, sum {n in M} x[k,(i-1)*9+n] subject to kvadrat {i in R, sum {l in R, n in R} x[k,((i-1)*27+(j-1)*3+ (1-1)*9+n)] = 1; subject to stolpec {i in M, sum {n in M} x[k,(n-1)*9+i] k in M}: = 1; j in R, k in M}: k in M}: = 1; Algorithm 2 AMPL model (.dat) param s := Q ■ 19 2 93 9 4 9 596 9 7 9899 9; param d := 11 2 13 14 1 516 1 7 1819 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61 1 62 1 63 1 64 1 65 1 66 1 67 1 68 1 69 1 70 1 71 1 72 1 73 1 74 1 75 1 76 1 77 1 78 1 79 1 80 1 81 1; 1; param c: # matri ka cen c Algorithm 3 AMPL model (.txt) so1ve; di splay x; 26 PRESEK 41 (2013/2014) 3 26 RAČUNALNIŠ TVO S pomočjo AMPL reševalnika kot rezultat dobimo matriko velikosti 9 x 81, zapisano v tabeli 2. Iz nje moramo razbrati rešitev. Indeksi stolpcev označujejo številke celic (oštevilčenje celic je prikazano na sliki 2), indeksi vrstic pa števila od 1 do 9, ki jih vpisujemo v Sudoku mrežo. Ce je v stolpcu j v vrstici i število 1, to pomeni, da imamo v celici številka j v Sudoku mreži število i. Kot vidimo, imamo v stolpcu 6 v vrstici 7 število 1. To pomeni, da se v celici številka 6 v Sudoku mreži nahaja število 7. Na ta nacin preberemo naslednjo rešitev Sudoku uganke A: A = Literatura [1] M. Mansour, Sudoku as a special transportation problem (online), 28. 6. 2013. http://arxiv.org/pdf/1210.2584v1.pdf. [2] J. Rosenhouse, L. Taalman, Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle, Oxford University Press, New York, 2011. [3] D. Green, Conceptis Sudoku difficulty levels explained (online), 28. 6. 2013. http://www.concepti spuzzles.com/i ndex. aspx?uri=i nfo/arti cle/2. [4] Wikipedia: Sudoku (online), 28. 6. 2013. http://sl.wiki pedi a.org/wi ki/Sudoku. [5] D. Bozovic in A. Taranenko, Linearni problem prevoza, Presek 41, st. 2, 24-27. 4 2 3 1 6 7 5 8 9 1 5 6 2 9 8 3 4 7 7 9 8 5 3 4 2 1 6 8 4 5 7 2 6 1 9 3 9 3 7 8 4 1 6 5 2 2 6 1 3 5 9 8 7 4 5 1 4 6 7 3 9 2 8 3 7 2 9 8 5 4 6 1 6 8 9 4 1 2 7 3 5 c = 1 1 2 -1 2 1 1 1 2 0 0 1 2 2 2 1 -1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 2 2 1 1 1 0 1 -1 1 1 2 1 1 2 2 2 2 2 2 1 2 1 1 0 0 0 1 0 0 0 1 1 0 0 1 1 -1 1 1 1 0 0 1 1 0 0 1 1 -1 1 0 0 1 0 0 0 0 1 1 1 1 2 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 2 1 1 1 1 1 2 1 1 1 1 -1 0 0 0 0 0 1 TABELA 1. x = 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 TABELA 2. _XXX PRESEK 41 (2013/2014) 3 27