V sudoku je cieľom doplniť hrací plán číslami od 1 do 9 tak, aby v každom riadku, v každom stĺpci, ako i v každom 3x3 bloku sa nachádzalo každé číslo práve raz. Dnes si ukážeme, ako vyriešiť každé sudoku použítím YALMIPu.
Začneme definíciou hracieho plánu ako matice 9x9, pričom nevyplnené polia označíme nulou:
plan = [5, 3, 0, 0, 7, 0, 0, 0, 0; ...
6, 0, 0, 1, 9, 5, 0, 0, 0; ...
0, 9, 8, 0, 0, 0, 0, 6, 0; ...
8, 0, 0, 0, 6, 0, 0, 0, 3; ...
4, 0, 0, 8, 0, 3, 0, 0, 1; ...
7, 0, 0, 0, 2, 0, 0, 0, 6; ...
0, 6, 0, 0, 0, 0, 2, 8, 0; ...
0, 0, 0, 4, 1, 9, 0, 0, 5; ...
0, 0, 0, 0, 8, 0, 0, 7, 9];
Teraz povieme YALMIPu, že optimalizovanou premennou je matica 9x9, ktorej prvky môžu byť iba celé čísla. Na to slúži príkaz intvar, ktorý vytvorí celočíselnú optimalizovanú premennú:
sudoku = intvar(9, 9, 'full');
A môžeme začať tvoriť ohraničenia. Najskôr ohraničíme hodnoty optimalizovaných premenných iba na čísla z itervalu 1 až 9:
ohranicenia = [ 1 <= sudoku <= 9 ];
Následne zafixujeme známe (nenulové) prvky z hracieho plánu:
zname = find(plan);
ohranicenia = ohranicenia + [ sudoku(zname) == plan(zname) ];
Tiež chceme, aby sa v každom riadku a v každom stĺpci objavilo každé číslo práve raz. Ide o veľmi komplikované ohraničenie, na ktoré má však YALMIP skratku v podobe príkazu alldifferent:
for i = 1:9
ohranicenia = ohranicenia + [ alldifferent(sudoku(i, :)) ];
ohranicenia = ohranicenia + [ alldifferent(sudoku(:, i)) ];
end
Ešte musíme pridať podobné ohraničenie na každý 3x3 blok:
for i = 1:3
for j = 1:3
blok = sudoku((i-1)*3+(1:3),(j-1)*3+(1:3))
ohranicenia = ohranicenia + [ alldifferent(blok) ];
end
end
Ostáva už len nájsť riešenie (t.j. prvky matice sudoku), ktoré vyhovuje všetkým ohraničeniam (teda nemáme žiadnu účelovú funkciu):
optimize(ohranicenia, [], sdpsettings('solver', 'gurobi'))
ans =
yalmiptime: 1.1323
solvertime: 0.0157
info: 'Successfully solved (GUROBI-GUROBI)'
problem: 0
Ako vidíme, kvalitnému solvru GUROBI trvá vyriešenie celého sudoku zhruba stotinu sekundy.
Celé riešenie zobrazíme pomocou príkazu value:
value(sudoku)
ans =
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
Na záver ešte celý kód v podobe funkcie, ktorá ako svoj vstup berie hrací plán a vráti vyriešené sudoku:
function sudoku = yalmip_sudoku(plan)
sudoku = intvar(9, 9, 'full');
ohranicenia = [ 1 <= sudoku <= 9 ];
zname = find(plan);
ohranicenia = ohranicenia + [ sudoku(zname) == plan(zname) ];
for i = 1:9
ohranicenia = ohranicenia + [ alldifferent(sudoku(i, :)) ];
ohranicenia = ohranicenia + [ alldifferent(sudoku(:, i)) ];
end
for i = 1:3
for j = 1:3
blok = sudoku((i-1)*3+(1:3),(j-1)*3+(1:3));
ohranicenia = ohranicenia + [ alldifferent(blok) ];
end
end
optimize(ohranicenia);
sudoku = value(sudoku);
end
Treba podotknúť, že uvedená formulácia úlohy sa dá ďalej zefektívniť v zmysle zníženia výpočtového času. Bližšie informácie nájdete na YALMIP wiki.