« Fler MiniZinc modeller kring recreational mathematics | Main | En vecka med Asus Eee Pc 900 »

juli 20, 2008

Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life

Här är några fler MiniZinc modeller som skapats sedan sist. För en fullständig lista över samtliga publicerade modeller, se My MiniZinc page.

I samtliga modeller anges referenser, inspiration etc.

Personligen tycker jag följande modeller är lite kul:
* Minesweeper (som presenteras speciellt nedan)
* Game of Life
* Quasigroup completion problem (se nedan för ett antal testproblem)
* Födelsedagsproblemet


Minesweeper


Tänkte nämna något mer om Minesweeper.

Modellen till Minesweeper är - möjligen förvånansvärt - enkel. Notera att man s.a.s. "räknar baklänges": genom att summera minorna (mines) för att få de värden som ges i problemet (game). Sådant är typiskt i constraint programming.


% MiniZinc model for Minesweeper.
int: r; % rows
int: c; % column
int: X = -1; % the unknowns

% encoding: -1 for unknown, >= 0 for number of mines in the neighbourhood
array[1..r, 1..c] of -1..8: game;
array[1..r, 1..c] of var 0..1: mines;

constraint
forall(i in 1..r, j in 1..c) (
(
(game[i,j] >= 0 )
->
game[i,j] = sum(a,b in {-1,0,1} where
i+a > 0 /\ j+b > 0 /\
i+a <= r /\ j+b <= c
)
(mines[i+a,j+b])
)
/\
(game[i,j] > X -> mines[i,j] = 0)
/\
(game[i,j] = X <- mines[i,j] = 1)
)
;

Ett exempelproblem, där ett tal anger hur många bomber det finns som grannar och X att vi inte vet något om rutan (det kan vara en bomb men behöver inte vara det).

% Minesweeper example
r = 6;
c = 6;
game = array2d(1..r, 1..c, [
X,X,2,X,3,X,
2,X,X,X,X,X,
X,X,2,4,X,3,
1,X,3,4,X,X,
X,X,X,X,X,3,
X,3,X,3,X,X,
]);

Lösningen - som kommer blixsnabbt - är följande. Positionerna av bomberna markeras med 1.

1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1

Minesweeper har visats vara ett s.k. NP-komplett problem, dvs ohyggligt svårt att lösa generellt för godtyckligt stora problem. De exempel som används i modellen är dock så (förhållandevis) små att lösningen kommer direkt.

Se vidare
Richard Kaye's Minesweeper Pages
Minesweeper (Wikipedia)
Ian Stewart on Minesweeper
The Authoritative Minesweeper: Articles and Announcements

Automatisk "lösning" av Minesweeper i Mozart/Oz där fler referenser ges.

Övriga modeller

Här är de övriga modellerna, grupperade enligt samma princip som på My MiniZinc page.

Puzzles, small and large

Global constraints

Operations research, linear programming, integer programming

Combinatorial problems

Other models


Posted by hakank at juli 20, 2008 08:23 EM Posted to Constraint Programming | Matematik | Pyssel