The program house_builder_backtrace.f is a Fortran program for solving the house building problem as described by Dr. James Grime (aka singingbanana).
If you have gfortran, you can compile the code with the following command:
gfortran -o hb -O3 house_builder_backtrace.f
then run the program with "hb" or "./hb", depending on your system.
The bounds that are printed are the minimum and maximum possible values of the coordinates of each point. You can enter any set of numbers that falls between each pair of bounds (up to machine precision), but you must ENTER THEM IN THE CORRECT ORDER.
To make your life easier, I also display the midpoints of each of these ranges. The problem can be quite picky, so be sure to enter enough decimal places.
=============================
How the Program Works
After playing the game a few times, you will quickly realize that the order in which you place the points is important, i.e. which points are to the left/right of which other points.
This can be described by a permutation of the first few natural numbers. This permutation and the range of possible point locations is much more important than the specific locations of the points. In fact, there are infinitely many valid specific locations for each valid permutation.
Given a permutation, it is fairly easy to check if a set of points in that order can be used to build houses. Simply divide the interval [0, 1] into [0, 1/2) and [1/2, 2] and check if the first two points can be placed in those ranges, then divide into [0, 1/3), [1/3, 2/3), [2/3, 1] and check the first three points, etc.
However, it is much harder to find a permutation that works. The first program that I wrote, house_builder.f, uses an exaustive search to try to find a solution. The second one, house_builder_backtrace.f, uses the backtrace technique to search more efficiently for the solution. The first program may take ~30 minutes to find a 14 point solution, while the second program can find every 17 point solution in ~1 second.
