Začíname s YALMIPom: 05. Sudoku

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 3×3 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 9×9, 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 9×9, 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ý 3×3 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) ];  endend

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.1323solvertime: 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)) ];endfor i = 1:3  for j = 1:3    blok = sudoku((i-1)*3+(1:3),(j-1)*3+(1:3));    ohranicenia = ohranicenia + [ alldifferent(blok) ];  endendoptimize(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.