Mines

Task description

Given is a rectangular board composed of n*m fields. Each field may contain a number between 0 and 8. Fields containing numbers are called numbered fields. The task is to place mines onto the board while satisfying the following conditions:

1. the total number of the mines on the board is i;
2. the number of mines on the (at most eight) neighbours of any numbered field equals to the value contained in that field;
3. numbered fields contain no mines;
4. any non-numbered field contains at most one mine.

Tasks may have more than one solution.

Figure 1 shows a task, and figure 2 shows its (only) solution. Mines are depicted as * in the solution.

  +---+---+---+---+---+
  |   |   | 0 |   |   |
  +---+---+---+---+---+
  |   |   |   |   | 1 |
  +---+---+---+---+---+
  | 3 |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   |   |   | 1 |
  +---+---+---+---+---+
  |   | 1 |   |   |   |
  +---+---+---+---+---+

  +---+---+---+---+---+
  |   |   | 0 |   |   |
  +---+---+---+---+---+
  | * |   |   |   | 1 |
  +---+---+---+---+---+
  | 3 | * | 1 |   | * |
  +---+---+---+---+---+
  | * |   |   |   | 1 |
  +---+---+---+---+---+
  |   | 1 |   |   |   |
  +---+---+---+---+---+

Task specification

Write an SML function, called mines, to produce all solutions. The parameter of this function is the triple ((R,C), N, RefPL) where

• R is the number of rows and C is the number of columns on the board, i.e. they define the size of the board where the upper left field of the board is in its first row and first column,
• N is the total number of mines on the board,
• RefPL is the list reference points where each reference point is a (Row,Col,Value) triple, describing the coordinates and the value of the fields contaning numbers; this is an increasing list sorted lexicographically.

For the task shown in figure 1 the parameter of the SML function is:

    ((5,5), 4, [(1,3,0),(2,5,1),(3,1,3),(3,3,1),(4,5,1),(5,2,1)])

The result of the SML function is a list containing all solutions of the task, exactly once each solution. If the task has no solution the result is the empty list. The solution should be a list of coordinates (i.e. pairs). The enumeration order of the mines is indifferent.

The solution shown in figure 2 is described by the following solution list (containing the single solution):

    [[(2,1),(3,2),(3,5),(4,1)]]

Function specification

The types of the parameters and the result of the function mines is described by the following type synonyms:

type row       = int;
type col       = int;
type value     = int;
type nummines = int;
type size      = row * col;
type point     = row * col;
type refpoint  = row * col * value;
type board     = size * nummines * refpoint list;
type minefield = point list;

val mines : board -> minefield list

The parameter of type board of the function mines satisfies the following conditions:

fun validTask (size, noOfMines, refPL) =
    let
        val (maxR, maxC) = size
        val area = maxR * maxC
        val noOfRefPoints = length refPL
        fun validPoint (row, col) =
              1 <= row andalso 1 <= col andalso
              row <= maxR andalso col <= maxC
        fun validRefPoint (row, col, Value)  =
              validPoint (row, col) andalso
              0 <= Value andalso Value <= 8;
        fun compareLexicographically ((x1,y1,_), (x2,y2,_)) =
              if      x1 < x2 orelse x1 = x2 andalso y1 < y2 then LESS
              else if x1 > x2 orelse x1 = x2 andalso y1 > y2 then GREATER
              else EQUAL
        fun differentNeighbours (rp1::(rps as rp2::_)) =
              compareLexicographically (rp1, rp2) <> EQUAL
              andalso differentNeighbours rps
          | differentNeighbours _ = true
    in 
        (* size of board and number of mines are valid: *)
        1 <= maxR andalso 1 <= maxC andalso
        area - noOfRefPoints >= noOfMines andalso
        (* all elements of refPL are valid: *)
        (List.all (fn x => x) (map validRefPoint refPL)) andalso
        (* refPL is lexicographically sorted: *)
        sorted compareLexicographically refPL andalso
        (* each element of refPL refers to different coordinates; only
           neighbour elements should be compared for refPL is sorted: *)
        differentNeighbours refPL
    end;

The data that will be used to test your solution will satisfy the predicate validTask.

You have to write two implementations:

• a functional solution, called mines.sml, to run under the MOSML interpreter,
• a constrained solution, called mines.aml, to run under the Alice interpreter, and making use of the Gecode library.

Implementation hints

Frame program

To execute and test your program you may use several functions and test cases that can be downloaded in a zipped archive.

The input to the frame program is a text file containing

• the number of rows and columns in its first line,
• the number of mines in its second line, and
• a series of triples in the following lines.
  The first two elements of a triple are the coordinates and the third one is the value of a numbered field.

5 5
4
1 3 0
2 5 1
3 1 3
3 3 1
4 5 1
5 2 1

The output of the frame program is a text file whose content depict each solution in a form similar to the one used in figure 2.

The frame program defines and exports the following five functions:

validTask b

true, if the board b is valid;

minesIn fi

the board produced from the content of the text file fi;

minesOut(fo, b, sss)

converts the solutions list sss of the board b to human readable form, and then writes this into the text file fo;

solve(fi, fo)

reads a task from the text file fi, and writes its solutions into the text file fo, while it makes use of the function mines to solve the task;

timer(fi, fo)

reads a task from the text file fi, and writes its solutions into the text file fo, while it makes use of the function mines to solve the task; the function returns a string composed of the name fi, the number of solutions, and the time needed to solve the task in seconds. This function is not implemented in the Alice version of the frame program.

The input file can be the standard input: /dev/stdin under Unix/Linux, con under MS DOS/Windows; the output file can be the standard output: /dev/stdout under Unix/Linux, con MS DOS/Windows.

Usage under MOSML

First read in the program mines.sml, then the program fmines.sml, finally apply the selected function to the proper parameters, e.g.

Moscow ML version 2.01 (January 2004)
Enter `quit();' to quit.
- use "mines.sml";
> val it = () : unit
- use "fmines.sml";
> val it = () : unit
- solve ("test0.txt", "/dev/stdout");
...

When you modify your program mines.sml, you have to reread it and then also the frame program "fmines.sml". Sometimes it is advisable to restart the MOSML interpreter.

Usage under Alice

First read in the program mines.aml, then the program fmines.aml, finally apply the selected function to the proper parameters, e.g.

Alice 1.3 ("Kraftwerk 'Propa Gators' Album") mastered 2006/08/24
### loaded signature from x-alice:/lib/system/Print
### loaded signature from x-alice:/lib/tools/Inspector
### loaded signature from x-alice:/lib/system/OS
- use "mines.aml";
val it : unit = ()
### evaluating file /home/peter/edu/mfp/hfp06a/hwks/bhw/mines.aml
### loaded signature from x-alice:/lib/gecode/Modeling
### loaded signature from x-alice:/lib/gecode/Space
### loaded signature from x-alice:/lib/gecode/FD
### loaded signature from x-alice:/lib/gecode/Search
...
- use "fmines.aml";
val it : unit = ()
### evaluating file /home/peter/edu/mfp/hfp06a/hwks/bhw/fmines.aml
### loaded signature from x-alice:/lib/data/ORDERED-sig
### loaded signature from x-alice:/lib/data/MkRedBlackMap
### loaded signature from x-alice:/lib/data/MAP-sig
...
- solve("test0.txt","/dev/stdout");
...

When you modify your program mines.aml, you have to reread it and then also the frame program "fmines.aml". Sometimes it is advisable to restart the Alice interpreter.