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.

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

This page was written by Juris Stephrans and last modifiedon Wednesday, September 08, 1999 at 12:23:05.