Production rules and LEFs (local evaluation functions) are used for solving problems in CCM. A combination of one production rule and one LEF is used for finding a magic square.
A production rule changes a state of data by an application. The most simple rule used in the applet page is the ``swapping rule.'' This rule swaps the integers in two unit squares. Make sure the meaning of square ``swapping'' by pushing the button in the applet in the right. (The source program of the applet.)
To find a solution using the above rule, the above simple operation is repeatedly applied to different pair of squares. A pair of squares is selected randomly (using a random number). However, whether to apply the rule to the selected squares or not is decided using the LEF shown below. The method of decision is explained later.
The ``rotation rule'' rotates the integers in three squares. The rotation is repeatedly applied to different set of squares, as the same way as the two-square swapping. Make sure the meaning of ``rotation'' by pushing the button in the applet in the right. (The source program of the applet.)
A LEF (local evaluation function) is defined for each squares. The value of the LEF o(x), where x is a square, is defined as the negated sum of square of difference between the objective value and the sum of a row, column or diagonal. (I want to create an applet that explains the definition of LEF, but I have not yet develop it because it is much more complicated than the applet for explanation of rules.) For example, the center square of a 3-dimension magic square, which contains 5, is used for computing four sums, i.e, the sum of the second row, that of the second column, and that of the two diagonals. The objective value is 15. If the sums are s51, s52, s53, and s54, then the LEF are defined as follows:
o(x5) = - (s51 - 15)2 - (s52 - 15)2 - (s53 - 15)2 - (s54 - 15)2.
This function takes the maximum value, 0, when all the sums, s51, s52, s53, and s54 are equal to the objective value, 15. (The value of LEF is between 0 and 1 in the N queens problem and sort, or the coloring problem. However, the range of LEF is different in this program.)
The data structure shown in the right is used in the program shown in the applet page for the sake of computing the value of LEF faster. The sum of a row, column or diagonal is computed before rule applications, and the sums related to a unit square are corrected by the reaction rule when the integer in the unit square is changed.
Squares to apply rules are randomly selected when executing the prigram. Whether to apply rules to the selected squares is decided using LEFs between them. The sum of the LEFs of all the squares is calculated. The rule is applied when the sum is increased by the rule application, but it is not applied when the sum is decreased. (To apply the rule or not when the sum is not changed is decided before the execution.) That is, the rule is applied when the application make the state of the chess board better locally, and it is not applied when the application make the state worse. However, the global state may become worse when the local state becomes better, and vice versa.