Join Now

Sudoku med Proc Optmodel

by SAS Employee MichaelSperling on ‎03-31-2015 05:07 AM (253 Views)

Mange mennesker, inklusiv undertegnede, finder det sjovt og udfordrende fra tid til anden at løse sudokuer . Det er en god udfordring at udvikle sine egne heuristikker til at løse stadig sværere sudokuer. Men vidste du, at man kan bruge SAS/OR til at finde løsningen?

Nedenstående er en klassisk 9x9 sudoku, hvor hver celle skal udstyres med et og kun et tal mellem 1 og 9.

Sudoku.png

Med nedenstående lille datastep genereres sudokuens 81-cellede grundstruktur med ni rækker, ni søjler og ni kvadrater. Hertil er også indbygget sammenhængen mellem hvilke celler, der tilhører hvilke kvadrater. Således tilhører celle x11 - x33 kvadrat 1, x14 – x36 tilhører kvadrat 2, celle x17 – x39 tilhører kvadrat 3, x41 – x63 tilhører kvadrat 5, osv.

data sq;

do _row=3 to 1 by -1;

   do rep_row= 1 to 3;

         row = (3-_row )*3 + rep_row;

     do _col=3 to 1 by -1;

       do rep_col= 1 to 3;

         col = (3-_col )*3 + rep_col;

         sq = (3-_row)*3 + 4 - _col;

         output;

       end;

     end;

   end;

end;

keep row col sq;

run;

Dernæst startes Proc Optmodel og settet RowColSq defineres ud fra værdierne i datasættet sq. Hver celle kan indeholde tallet 1-9. Vi har altså en binær tildelingsvariabel, x(r,c,s,n) med fire indeks (række, kolonne, kvadrat og tal). x(r,c,s,n) har værdien 1, hvis der på den r´te rækker og c´te kollone (og deraf udledt s´te kvadrat) står tallet n; og 0 ellers.  Endelig låses enkelte celler til specifikke tal i henhold til tallene i ovenstående figur ved brug af fix-statementet i Proc Optmodel.

proc optmodel;

set <num,num,num> RowColSq;

read data sq into  RowColSq=[row col sq] ;

set <num> row = (setof{<r,c,s> in RowColSq} r) ;

set <num> col = (setof{<r,c,s> in RowColSq} c) ;

set <num> sq = (setof{<r,c,s> in RowColSq} s) ;

set <num> tal = 1..9;

set <num,num,num,num> sudoku = RowColSq cross tal;

var x{sudoku} binary init 0;

* række nr 1, søjle nr 3, kvadrat nr 1, tal=5 låses => første række, tredje kolonne skal der stå 5;

fix x[1,3,1,5] = 1;

fix x[1,4,2,2] = 1;

fix x[2,2,1,8] = 1;

fix x[2,8,3,2] = 1;

fix x[2,9,3,1] = 1;

fix x[3,1,1,4] = 1;

fix x[3,5,2,9] = 1;

fix x[3,6,2,8] = 1;

fix x[3,9,3,5] = 1;

* række nr 4, søjle nr 8, kvadrat nr 6, tal=3 => I række 4, kolonne 8 skal der stå 3;

fix x[4,8,6,3] = 1;

fix x[5,2,4,7] = 1;

fix x[5,4,5,5] = 1;

fix x[5,6,5,2] = 1;

fix x[5,8,6,1] = 1;

fix x[6,2,4,4] = 1;

fix x[7,1,7,3] = 1;

fix x[7,4,8,9] = 1;

fix x[7,5,8,6] = 1;

fix x[7,9,9,4] = 1;

fix x[8,1,7,6] = 1;

fix x[8,2,7,5] = 1;

fix x[8,8,9,7] = 1;

fix x[9,6,8,4] = 1;

fix x[9,7,9,2] = 1;

** Objektfunktion;

max Obj = sum{<r,c,s,n> in sudoku} x[r,c,s,n] ;

** Bibetingelser;

* kun et tal i hver celle;

con con_1 {r in row, c in col} : sum{<(r),(c),s,n> in sudoku} x[r,c,s,n] <= 1;

* Hver tal står kun én gang i hver række;

con con_row_tal {r in row, n in tal} : sum{<(r),c,s,(n)> in sudoku} x[r,c,s,n] = 1;

* Hver tal står kun én gang i hver kolonne;

con con_col_tal {c in col, n in tal} : sum{<r,(c),s,(n)> in sudoku} x[r,c,s,n] = 1;

* Hver tal står kun én gang i hver firkant;

con con_sq_tal {s in sq, n in tal} : sum{<r,c,(s),(n)> in sudoku} x[r,c,s,n] = 1;

solve with milp;

for {<r,c,s,n> in sudoku} x[r,c,s,n] = round (x[r,c,s,n]);

create data resultat from [row col sq tal] = {<r,c,s,n> in sudoku: x[r,c,s,n] ne 0} ;

quit;

Proc Optmodel løser assignmentproblemet og skriver løsningen til sas-datasættet resultat. Samtidig genereres nedenstående output, som beskriver det matematiske problem, samt hvor hurtigt SAS har løst problemet.

Objective Sense

Maximization

Objective Function

Obj

Objective Type

Linear

Number of Variables

729

Bounded Above

0

Bounded Below

0

Bounded Below and Above

705

Free

0

Fixed

24

Binary

729

Integer

0

Number of Constraints

324

Linear LE (<=)

81

Linear EQ (=)

243

Linear GE (>=)

0

Linear Range

0

Constraint Coefficients

2916

solution summary.png

Endelig kan man eksempelvis bruge Proc Tabulate til at præsentere løsningen.

Title "Print løsning";

Proc tabulate data=resultat ;

class row col ;

var tal;

table row="", col=""*tal=""*sum=""*format=6.;

run;

At danne et sas-program til at løse en sudoku er selvfølgelig i den lidt underholdende ende, men konceptuelt kan problemstillingen udbredes til en lang række af forretningsproblemer. Enhver form for skema- eller vagtplanlægning indeholder mange af de samme problemstillinger – vi skal finde den optimale plan under hensyntagen til bl.a. overenskomster og bemandingsbehov. Et andet eksempel er hvilken maskine, der skal knyttes til hvilken opgave, mens et tredje eksempel er at finde en sælgers optimale rute rundt til sine kunder.