Programming Corner from Icon Newsletter 12

July 14, 1983; Icon Version 5

Solutions to the Problems in Newsletter 11

N Queens: Numerous solutions to the 8-queens problem have been presented to show different backtracking techniques. Icon lends itself nicely to such problems as illustrated by the following porgram.

procedure main()
    rite(q(1),q(2),q(3),q(4),q(5),q(6),q(7),q(8))
end
procedure q(c)
   suspend place(1 to 8,c)   # look for a row end
procedure place(r,c)
   static up, down, row

   initial {
      up := list(15,0)
      down := list(15,0)
      row := list(8,0)
      }
   if row[r] = down[r + c - 1] = up[8 + r - c] = 0
   then suspend row[r] <- down[r + c - 1] <-
      up[8 + r - c] <- r     # place if free end

The heart of this solution lies in the mutual goal-directed evaluation of q(1), q(2), ..., q(8). Each set of values for which these procedure calls mutually succeed corresponds to a solution. Note that all the queens are "equal".

Clearly, however, this type of solution does not lend itself to parameterization, since each of the q(i) must appear explicitly in the program.

One approach to the general problem is to use a list to contain the solutions and a hierarchical, recursive scheme in which each queen controls the invocation of the next one. Thus, the first queen dominates the second, and so on. A program of this kind, due to Steve Wampler, is

global n, solution
procedure main(x)\
   n := x[1]           # number of queens
   solution := list(n) # list of column solutions
   every q(1)          # start with queen in 1st col.
end

procedure q(c)
   local r
   static up, down, rows

   initial {
      up := list(2 * n - 1,0)
      down := list(2 * n - 1,0)
      rows := list(n,0)
      }

   every 0 = rows[r := 1 to n] = up[n + r - c] =
      down[ r + c - 1] & rows[r] <- up[n + r - c] <-
      down[r + c - 1] <- 1 do {
         solution[c] := r     # record placement
         if c = n then show() # all queens placed
         else q(c + 1)        # try to place next queen
      }
end
procedure show()
   every writes(!solution)
   write()
end

Here the value of n is supplied on the command line when the program is run. The version of the program given here is stripped down to conserve space. The complete program with error checking and a display of the queens on a chessboard is included in the Icon program library.

This approach can also be cast in terms of co-expressions, as illustrated by the following program by Steve Wampler:

global n, nthq, solution

procedure main(x)
   local i

   n := x[1]
   nthq := list(n + 2) # list of queens
   solution := list(n) # list of solutions
   nthq[1] := &main    # 1st queen is main routine
   every     i := 1 to n do    # 2 to n+1 are real queens
   placements nthq[i + 1] :=
      create q(i)      # one co-expression per column
   nthq[n + 2] := 
      create show( )   # n+2nd queen is display routine      @nthq[2]            # start with queen in col. 1
end

procedure q(c)
   local r
   static up, down, rows

   initial {
      up := list(2 * n - 1,0)
      down := list(2 * n - 1,0)
      rows := list(n,0)
      }

   repeat {
      every 0 = rows[r := 1 to n] = up[n + r - c] =
        down[r + c - 1] & rows[r] <- up[n + r - c] <-
        down[r + c - 1] <- 1 do { solution[c] :=
        r
      @nthq[c + 2]        # try to place next queen
      }
   @nthq[c]               # tell last queen try again
   }
end

procedure show()
   repeat {
      every writes(!solution)
      write()
      @nthq[n + 1] # tell last queen to try again
      }
end

A somewhat different form of solution -- and one that requires a better understanding of Icon -- is illustrated by the following solution to the n-rooks problem by Tom Slone.

global n

procedure main(x)
   n := x[1]             # number of rooks
   every show(rook(n))
end

procedure show(a)
   every writes(!a)
   write()
end

procedure rook(i)
   static a

   initial a := list(n)

   if i = 0 then return
   if i < n then suspend (a[i] := r()) & rook(i - 1)
   else suspend (a[i] := r()) & rook(i - 1) & a
end

procedure r()
   suspend place(1 to n)
end

procedure place(r)
   static col

   initial col := list(n,0)

   if col[r] = 0 then suspend col[r] <- r
end

A Puzzle: In the last Newsletter, the behavior of the following program was posed:

procedure main()
   write("abcde" ? {
      p() := "x"
      write(&subject) &subject
      }
   )
end

procedure p()
   suspend &subject[2:3]
end

In the first place, the argument of write in main is a scanning expression. The scanning expression consists of three sub-expressions. The first is a call to p that returns a substring of &subject. Since this is a substring of a global variable (&subject), it is not dereferenced when p returns, and the subsequent assignment changes the value of &subject to "axcde", which is written. The last sub-expression of the scanning expression is simply &subject; this is the result of the scanning expression and hence the argument of the outer write. Since &subject is a global variable, it is not dereferenced when it is produced by the scanning expression. Hence write gets the variable &subject. However, when the scanning expression returns, it restores the former value of &subject (in this case, the empty string, the initial default value of &subject). So, by the time write dereferences &subject, its value is the empty string. Thus, this program writes axcde followed by an blank line!

This example illustrates two things: (1) dereferencing is a serious language design problem, and (2) programmers may encounter some mysterious results if they write programs that rely on the side effects of assignment to global variables like &subject.

Superficially, this program looks like it ought to write axcde twice (actually, the write in the scanning expression got there as a result of trying to find out why the outer write produced a blank line). The problem can be solved by explicitly dereferencing &subject in the scanning expression, as in

procedure main()
   write("abcde" ? {
      p() := "x"
      write(&subject)
      .&subject
      }
      )
end

Now the value returned by the scanning expression is "axcde" -- the value of &subject before its former value is restored at the end of scanning.

New Problems

Scanning an Entire File: Since Icon has a string data type and many operations on strings, it is natural to process strings as whole objects, rather than character by character as in most lower-level languages. String scanning raises the operations on strings to an even higher level, providing a subject on which scanning functions operate, matching functions that move the position of attention in the subject, and backtracking to the previous position in case a matching function fails.

One annoying problem in trying to process strings as whole objects occurs in situations like lexical analysis, in which the object to be processed is really a file with interspersed line terminators. The result of read in Icon is a string consisting of a line up to a line terminator. Therefore it is natural to process files in terms of their lines. However, a construction to be processed may span several lines (comments are typical). Thus, the natural input to string scanning may not contain the whole string to be processed. Although it is possible to make the entire input into a single string, this is generally inefficient and often impractical.

There is a device that often can be used to overcome these problems. If an expected match fails (for example, searching for the closing token of a comment), the subject of scanning can be reset during scanning to be the next line of input. This is illustrated by the following program by Tom Slone for stripping "white space" out of Pascal programs:

procedure main()
   local line

   while line := read() do
      line ? {
         remwhite()
         write("" ~== tab(0))
         }
end

procedure remwhite()
   while tab(many(' \t')) | (="(*" & comment()) |
      (pos(0) & newline())
end

procedure comment()
   while not ="*)" do
      if pos(0) then
         newline()
      else move(1) & tab(many(~'*'))
  return
end

procedure newline()
   (&subject := read()) | stop("unexpected end-of-file.") return end

This technique is applicable only if the part of the subject already scanned can be discarded -- once a new value has been assigned to the subject, the old value of the subject is lost and the automatic backtracking in string scanning does not apply to it.

The program above is not complete -- it has at least two defects. Correcting these is left as an exercise.

Random Numbers: A linear congruence method is used for generating pseudo-random numbers, and elements of strings and structures. Thus, the operation ?x is valid for values of x of different types. The pseudo-random sequence is computed from the value of &random, which is initially zero and which changes with each use of ?x. &random also can be set, so that a sequence can be repeated or started at an arbitrary place. A problem arises, however, if two or more independent random sequences are needed -- the use of one inevitably affects the other - or does it?

For starters, write a procedure random() whose result sequence consists of the successive values of &random as they are produced by successive uses of ?x (note that is it not necessary to know how Icon actually performs the pseudo-random computation). Assume that there is no other use of random generation in the program in which random() is used.

Now remove the assumption, so that the result sequence produced by random() is not affected by uses of ?x elsewhere in the program.

Icon home page