## 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.

Juris Steprans