 |
Description language ConStrukt The ConSolve system solves combinatorial optimization problems. Problem descriptions are defined in the special specification language ConStrukt and then are passed on to the ConSolve® runtime system.
The language ConStrukt was designed in order to describe logical and combinatorial problems as simple as possible ("domain-specific language"). Therefore the description of the problem is very close to the given problem, it is easy to understand and less errors are made. Beyond that, it is possible to find a description for a problem within a short time.
In the language ConStrukt you do not describe solution methods (or algorithms) but only problem definitions. The selection of the algorithms used for solving the problem is made by the ConSolve runtime system. Thus, ConStrukt is a "declarative language" as well.
On the basis of the so called n-queens-problem the language Construkt is examplarily introduced:
Put n queens of a chess game on a chess board of the size n*n in such a way that the queens cannot strike each other.
01 // The n-queens-problem in ConStrukt
02 export chessboard, size > c,cpp;
03
04 // The parameter is allowed in this interval.
05 size : {4..100};
06
07 // Default size of the chess board
08 size := 8;09
10 concept table
11 begin
12 entail L[{1..size:Z} : {1..::size :Z}];
13 // The selector for retrieval
14 export entry(column: {1.. :Z}) : T
15 := this[column];
16 end table;
17
18 concept chessboard
19 begin
20 inherit table;
21 entail
22 forall column:{1..size :Z}
23 ensure different this[column];
24 entail
25 forall column:{1..size :Z}
26 ensure different this[column] + (column-1);
27 entail
28 forall column:{1..size :Z}
29 ensure different this[column] - (column-1);
30 end chessboard;
With "export... > C, cpp" the concepts "chessboard" and "size" (which will be introduced later) are released for the access from a C/C++ application. The solutions can be enumerated by the application system by use of a so-called iterator. In our example, furthermore, the size of the board can be specified at runtime.
The concept "board" defines the chessboard as a one dimensional array of columns. Each variable defines the line position of a queen in the respective column. The selector "entry" permits access to the position of a queen from the application system, where "this[column]" refers to the queen in the respective column.
The concept "chessboard" defines the actual problem. "chessboard" is a table ("inherit board"), which must fulfill additional conditions. To solve the n-queens-problem, it must be provided that - in each column there is not more than one queen,
- in each line there is no more than one queen, and
- from the position of each queen there must be not more than one queen on the diagonals.
The first condition is already fulfilled by modelling the problem in the concept "board". The second condition is guaranteed by the lines 21 to 23. The third condition is specified by the lines 24 to 29.
The n-queens-problem is now described in the language ConStrukt in a scalable way and can be integrated into an application. |
|
About
