Solving the Challenger puzzle
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.
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 has 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. Using methods developed in
the first part, try 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.
Instructor
Juris Steprans
email address: steprans@mathstat.yorku.ca
Department of Mathematics and Statistics.
Ross 536 North, ext. 33921
York University
Back to Department's Public Page
