The *Challenger *puzzle can be found syndicated
in various newspapers. It involves filling in the entries of a 4 by 4 grid
with integers between 1 and 9 so that all columns, rows and diagonals add
up to numbers given in the puzzle. The two examples provided show *Challenger
*puzzles
as well as the solution to one completed puzzle.
Some of the numbers are already filled
in the grid so these act as a constraint on the other solutions. Write
a procedure, or simply develop a general method, which will solve any *Challenger
*puzzle.
(A C++ program
written
by Brian McBride for solving this puzzle is availalable for downloading
if you are interested.) Remember that the solutions can only be integers
between 1 and 9; this means that you must do more than simply solve the
system of equations because not all solution will use only integers.

It may be useful for you to have a Maple function which creates a random challenger puzzle so you have something to test your procedures on.

Once you have finished the solution to the *Challenger* you will
have an idea of how tomography works. Tomography is the technology which
allows the imaging of a crosssection of an object without cutting the object
apart. The most well known application is in medical diagnosis. Crosssections
of the human body can be obtained by taking X-rays along a plane perpendicular
to the body from various angles. The data from these various X-rays can
then be analysed using linear algebra and computer programs to reproduce
a picture of the body's crosssection.

To get an idea of how this might be done consider the following picture:

In this simplified version, it is being assumed that X-rays have been
taken at angles indicated by the black, red, green and blue lines. It is
also assumed that the object being imaged consist of a homogeneous material
partially impenetrable by X-rays, and, the coarsness of the X-ray film
corresponds approximately to the distance between the lines shown in the
direction of the X-rays. The result of these assumptions is that each ray
will be attenuated by an amount proportional to the number of square regions
intersecting the object. The amount each region attenuates the X-ray depends
on how much of the X-ray crosses the square region as indicated in the
diagram. Hence, the darkness of the film will be 0 if the ray misses the
object, 1 if it passes through only 1 square area contained in the object,
2 if it passes through 2 such regions and so on. Fractional values arise
when the ray passes through only part of a square region. There may also
be some inaccuracy due to the equipment used. spot of darkness 2 because
it passes through only 2 regions.

The raw data presented from a tomographic picture might look something
like this:

The numbers at the end of each ray represent the darkness of the image
and, consequently, the number of square regions in the object which have
been traversed by that ray. The problem of trying to decode an image from
such X-ray data is similar to solving the *Challenger* puzzle, except
that in the simplified version of tomography under consideration each cell
can only have values either 0 or 1. It is possible, in theory, to use the
methods developed in the first part, to determine the image encoded by
the data given above. You should keep in mind that your solutions will
only be close to 0 and 1 **but not exact.** Moreover, the amount of
computation required will be significant and probably beyond the limits
of what is feasible on the machines available.

Probabilistic algorithms can reduce the time required to find a *reasonably*
good solution. One approach is to simply randomly replace the values of
the variables with values of 0 or 1. This might hit upon a solution,
but it is unlikely that it will be faster than the algebraic search procedure.
A slightly better strategy is to choose values for the variables at random,
but, to discard those that do not improve the *fit *to the given equations.
This will be a faster procedure but it is unlikely to find an optimal solution
since it may start off on the road to a bad solution and never turn back
to look for a better solution. An improvement on this is to choose
values at random and select those which improve the fit to the equations
** or**
do not deviate too much from the fit. In other words, the procedure is
allowed to change its mind, however, as time progresses it should be restricted
to change its mind less and less. This process, known as simulated annealing,
is more likely to find an optimal solution. Write a procedure for solving
the X-ray data problem using this strategy.

If you would like other tomographic problems, you can write functions that create a random puzzle of this type.

Mike Zabrocki

Math 2042

zabrocki@yorku.ca