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 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.