At first sight, this may look like a backtracking problem, in which the program systematically tries move sequences until one is found that turns the dials to the desired state (~12~ o'clock). There is, however, a difficulty in this approach.

In which order should we try the move sequences? We need to make sure that we do not miss the right one(s). If we cannot give an upper bound on the length of candidate move sequences, then we should, for instance, try them in order of increasing length. First we deal with all move sequences of length zero (only one), next all of length one (only nine), then length two, etc. This is called a breadth-first search. It is often more complicated than a depth-first search (where the move sequences are tried in some lexicographic order).

If the desired move sequence is sufficiently short, then it can be found quickly by a breadth-first search. But the problem statement did not say that all input would result in short move sequences. We have to take longer sequences into account as well.

Let us assume for a moment that we need no more than ~k~ moves of each of the nine move types. In that case the maximum length of a move sequence is ~9k~ and there are ~\frac{(9k)!}{(k!)^9}~ such maximal move sequences. For ~k = 1~ this equals ~9! = 3.6 \times 10^5~, for ~k = 2~ we get ~\frac{18!}{2^9} = 1.3 \times 10^{13}~, and for ~k = 3~ it is ~\frac{27!}{6^9} = 1.1 \times 10^{21}~. Of course, all the shorter move sequences should be considered as well. Therefore, these numbers do not look promising. For ~k = 3~ we cannot hope to try all sequences within the time limit. Even for ~k = 2~ we are hard pressed. Hoping for ~k = 1~ is wishful thinking.

We need a better idea. The effect of a move is to turn a subset of the dials over ~90~ degrees (clockwise). The net effect of two moves executed one after the other is cumulative. If move ~1~ turns clocks ~A~ and ~B~ over ~90~ degrees, and move ~2~ turns ~B~ and ~C~ over ~90~ degrees, then their combination turns ~A~ and ~C~ over ~90~ degrees and ~B~ over ~2 \times 90 = 180~ degrees. Therefore, the net effect does not depend on the order of execution. (This resembles the superposition principle for waves, fields, etc. in physics.) Consequently, for determining the net effect of a move sequence on the dials, we need to know only how many moves of each type are involved and not in what order the moves are made.

The observation above drastically reduces the number of candidate move sequences to be considered. First of all, it is now obvious that each move type need not appear more than three times, because four quarter turns is the same as no turn at all. Secondly, since each of the ~9~ move types can appear from ~0~ to ~3~ times, the number of candidate move sequences equals ~4^9 = 262\,144~. This can be accomplished in the given time.

Program 1

procedure ComputeAnswer ;
  label 99;
  var
    t1, t2, t3, t4, t5, t6, t7, t8, t9: integer; { move i occurs ti times }
  { N.B. We have not used an array t[1..9] because some Pascal compilers }
  { do not allow array elements as control variables in for-loops. }

  procedure Solution ;
    var m: integer;
    begin
    n := 0 ;
    for m := 1 to t1 do begin inc(n) ; move[n] := 1 end ;
    for m := 1 to t2 do begin inc(n) ; move[n] := 2 end ;
    for m := 1 to t3 do begin inc(n) ; move[n] := 3 end ;
    for m := 1 to t4 do begin inc(n) ; move[n] := 4 end ;
    for m := 1 to t5 do begin inc(n) ; move[n] := 5 end ;
    for m := 1 to t6 do begin inc(n) ; move[n] := 6 end ;
    for m := 1 to t7 do begin inc(n) ; move[n] := 7 end ;
    for m := 1 to t8 do begin inc(n) ; move[n] := 8 end ;
    for m := 1 to t9 do begin inc(n) ; move[n] := 9 end ;
    goto 99
    end { Solution } ;

  begin { ComputeAnswer }
  for t1 := 0 to 3 do begin
    for t2 := 0 to 3 do begin
      for t3 := 0 to 3 do begin
        for t4 := 0 to 3 do begin
          for t5 := 0 to 3 do begin
            for t6 := 0 to 3 do begin
              for t7 := 0 to 3 do begin
                for t8 := 0 to 3 do begin
                  for t9 := 0 to 3 do begin
                    if (a=0) and (b=0) and (c=0) and
                       (d=0) and (e=0) and (f=0) and
                       (g=0) and (h=0) and (i=0) then Solution ;
                    inc4(e) ; inc4(f) ; inc4(h) ; inc4(i)
                    end { for t9 } ;
                  inc4(g) ; inc4(h) ; inc4(i)
                  end { for t8 } ;
                inc4(d) ; inc4(e) ; inc4(g) ; inc4(h)
                end { for t7 } ;
              inc4(c) ; inc4(f) ; inc4(i)
              end { for t6 } ;
            inc4(b) ; inc4(d) ; inc4(e) ; inc4(f) ; inc4(h)
            end { for t5 } ;
          inc4(a) ; inc4(d) ; inc4(g)
          end { for t4 } ;
        inc4(b) ; inc4(c) ; inc4(e) ; inc4(f)
        end { for t3 } ;
      inc4(a) ; inc4(b) ; inc4(c)
      end { for t2 } ;
    inc4(a) ; inc4(b) ; inc4(d) ; inc4(e)
    end { for t1 } ;
  if Test then writeln('No solution found') ;
  99:
  end { ComputeAnswer } ;

Program 1 tries all candidate move sequences in nine nested for-loops until a solution is found. Program 1 relies on the fact that doing one type of move four times is the same as doing nothing.

This program has not been optimized in any way. It shows that a rough idea may work all right. Anything you do to improve it is a waste of (your) time, since Program 1 provides the solution well within the time limit.

However, Program 1 leaves a number of interesting questions unanswered. Furthermore it is still not very efficient, even though it is fast enough for our purpose. There are two questions that the jury needed to answer in order to judge the programs:

• Can every starting configuration be solved?
• How many solutions (~\bmod 4~) does a solvable starting configuration have?

Observe that the number of starting configurations is ~4^9~, because for each of the nine clocks there is a choice among four states. This is the same as the number of candidate move sequences for a solution. Therefore, either (i) each starting configuration has a unique solution, or (ii) there are some starting configurations without solution and some with multiple solutions.

Exercise: Modify Program 1 to generate all solutions. Because the problem statement does not restrict the input, we have assumed in Program 1 that each starting configuration has a solution, which then is unique ~\bmod 4~.

Given a move sequence it is easy to compute its net effect on the dials. Assume move type ~j~ occurs ~t_j~ times in the sequence. Figure 2 in the problem statement implicitly tells us how clock ~A~ is affected by the moves. Here is that table again in a slightly different format:

Move   Affected clocks

 1     A B . D E . . . .
 2     A B C . . . . . .
 3     . B C . E F . . .
 4     A . . D . . G . .
 5     . B . D E F . H .
 6     . . C . . F . . I
 7     . . . D E . G H .
 8     . . . . . . G H I
 9     . . . . E F . H I

We conclude that the net effect on dial ~A~ is ~t_1 + t_2 + t_4~ quarter turns. Here is a complete table giving for each clock the moves that affect it (essentially obtained by reflecting the matrix above in the upper-left-to-lower-right diagonal, also called transposition):

Clock   Affected by moves

 A      1 2 . 4 . . . . .
 B      1 2 3 . 5 . . . .
 C      . 2 3 . . 6 . . .
 D      1 . . 4 5 . 7 . .
 E      1 . 3 . 5 . 7 . 9
 F      . . 3 . 5 6 . . 9
 G      . . . 4 . . 7 8 .
 H      . . . . 5 . 7 8 9
 I      . . . . . 6 . 8 9

Let us denote the state of dial ~V~ before the move sequence by ~v~ and its new state after executing the sequence by ~v'~. The new states are related to the old states by the following equations (where addition is taken ~\bmod 4~):

a' = a + t1 + t2 + t4
b' = b + t1 + t2 + t3 + t5
c' = c + t2 + t3 + t6
d' = d + t1 + t4 + t5 + t7
e' = e + t1 + t3 + t5 + t7 + t9
f' = f + t3 + t5 + t6 + t9
g' = g + t4 + t7 + t8
h' = h + t5 + t7 + t8 + t9
i' = i + t6 + t8 + t9

Consequently, the problem our program has to solve is now translated into solving a system of nine linear algebraic equations with nine unknowns ~(t_1, \dots, t_9)~, where the vector ~(a, \dots, i)~ is the given initial state and the final state ~(a', \dots, i')~ is the all-zero vector. All the coefficients of the unknowns are apparently either ~0~ or ~1~. We have put the coefficient matrix below.

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

Program 2

procedure Solve ; { by Gauss-Jordan elimination with `partial pivoting' }
  var h, i, j, k: integer;
  begin
  { transform A into the unit matrix and b into a solution vector }
  for i := 1 to 9 do begin { process column i }
    { find pivot by bounded linear search for first 1 or 3 in column i }
    k := i ; h := 10 ;
    while k <> h do
      if A[k, i] in [1, 3] then h := k else inc(k) ;
    if k = 10 then begin
      writeln('Pivot not found in step ', i:1) ;
      halt
      end { if } ;
    if Test then writeln('Pivot for column ', i:1, ' found in row ', k:1) ;
    { swap rows i and k }
    for j := i to 9 do begin
      h := A[i, j] ; A[i, j] := A[k, j] ; A[k, j] := h
      end { for j } ;
    h := b[i] ; b[i] := b[k] ; b[k] := h ;
    { normalize row i, yielding A[i, i] = 1 }
    h := A[i, i] ; { h * A[i, i] = 1 (mod 4) }
    for j := i to 9 do
      A[i, j] := (h * A[i, j]) mod 4 ;
    b[i] := (h * b[i]) mod 4 ;
    { sweep column i to zeroes in rows other than i }
    for k := 1 to 9 do begin { take care of row k }
      if k <> i then begin
        h := 3*A[k, i] ;
        for j := i to 9 do
          A[k, j] := (A[k, j] + h*A[i, j]) mod 4 ;
        b[k] := (b[k] + h*b[i]) mod 4
        end { if }
      end { for j } ;
    if Test then begin
      writeln('Situation after step ', i:1) ;
      WriteMatrix
      end { if }
    end { for i }
  end { Solve } ;

There are numerous ways to solve a system of linear algebraic equations. Program 2 is based on a straightforward method often learned in school, called Gauss-Jordan elimination.

Note that the execution time of Program 1 depends on the actual input (in the worst case it takes ~4^9~ steps through the inner loop, in the best case only one). The execution time of Program 2 is almost independent of the input (procedure Solve takes on the order of ~9^3 = 729~ steps because there are three nested for-loops with at most ~9~ steps each). Program 2 is often faster than Program 1, but it is also more complicated and offers more opportunities for making mistakes when implementing it. Therefore, I cannot recommend it in the context of IOI'94.

Program 2 does help answer the above questions. The method it uses to solve the system of linear equations depends only in part on the input. The manipulations with the matrix A of coefficients (in procedure Solve) are independent of the input (only array ~b~ depends on the input). If the program is able to solve the problem for one particular input, then we know that it will also succeed in solving the problem for every other input. A simple trial run reveals that Program 2 works for the example input. This proves that each input has a solution and hence we know that the solutions are unique (~\bmod 4~).

Program 3

Because the manipulations with the coefficient matrix ~A~ do not depend on the input, they can be done in a separate pre-processing phase. In particular, the coefficient matrix for the system of linear equations can be inverted. The inverse matrix can then be used to compute solutions very quickly. Using the matrix coefficients, a program can invert the matrix. It is obtained from Program 2 by replacing the linear array ~b~ in procedure Solve by a square array ~B~ initialized to the identity matrix.

Program 3 uses this inverse matrix to compute a solution by a single matrix-vector multiplication (which takes on the order of ~9^2 = 81~ steps). This solution is extremely fast. It would be even faster if the coefficients were incorporated in the program to initialize the matrix. In Turbo Pascal this is not so difficult, but for other Pascal versions that may require ~81~ assignment statements. In fact, if you strip the program to the bone (you don't have to use an array) you can squeeze it into a few lines. Here is a solution to the above system of nine equations in ~(t_1, \dots, t_9)~ for given ~(a, \dots, i)~ and ~(a', \dots, i') = (0, \dots, 0)~ derived from the inverse matrix (addition and multiplication are ~\bmod 4~):

t1 = 8+ a+2b+ c+2d+2e -f+ g -h
t2 =    a+ b+ c+ d+ e+ f+2g+   2i
t3 = 8+ a+2b+ c -d+2e+2f    -h+ i
t4 =    a+ b+2c+ d+ e+    g+ h+2i
t5 = 4+ a+2b+ c+2d -e+2f+ g+2h+ i
t6 =   2a+ b+ c+    e+ f+2g+ h+ i
t7 = 8+ a -b+   2d+2e -f+ g+2h+ i
t8 =   2a+   2c+ d+ e+ f+ g+ h+ i
t9 = 8    -b+ c -d+2e+2f+ g+2h+ i