The Highway Puzzle


On the checkerboard below, suppose each numbered square represents the capital city of a country, and that the value of the number is the number of other squares belonging to that country. From each capital city, up to four highways may exit, going up, down, left and right. All the squares belonging to a capital city will lie along one of these roads, and then the road ends. No "foreign" squares are allowed along a road. Can you draw the entire road map? The two squares labeled X are mountains. They don't belong to any country, and no road can pass through them.

        +---+---+---+---+---+---+---+---+
        |   |   |   |   | 3 |   | 4 |   |
        +---+---+---+---+---+---+---+---+
        | 7 |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+
        |   |   | X |   |   | 5 |   |   |
        +---+---+---+---+---+---+---+---+
        |   |   |   | 4 |   |   |   |   |
        +---+---+---+---+---+---+---+---+
        |   | 4 |   |   |   |   |   | 9 |
        +---+---+---+---+---+---+---+---+
        |   |   | 2 |   |   | X |   |   |
        +---+---+---+---+---+---+---+---+
        |   |   |   |   | 5 |   |   |   |
        +---+---+---+---+---+---+---+---+
        | 2 |   |   |   |   |   | 6 |   |
        +---+---+---+---+---+---+---+---+
      

I give up, show me the solution.


Last revised on 10 February 2000.