Four color theorem

The Four color theorem is the challenge to draw first a map consisting of different 'countries' and then to color the different countries with a minimum number of colors. The minimal number is 4.
The line between each country is called a boundary. There is one constrain involved.
  1. The constrain is that the maximum number of countries involved at each point on the boundary is three. This meant there can be no point where 4 countries meet.
For more detail select: https://en.wikipedia.org/wiki/Four_color_theorem For the source of the program select: Four_color_theorem.xls.zip
This zip file consists of two copies of the program:
  1. Four_color_theorem.xls This program is the real program and contains 10 simulations.
  2. Four_color_theorem_test.xls This is the same as above, but is more meant to try your own examples.

Page description and operation

Each Page or Blad consits of 2 parts: A left part and a right part.
The left part contains 2 Maps: Top Map and a Bottom Map and 3 command buttons: Calculate , Mode and Switch.
  • The Top Map is called the Target Map and shows all the countries used. Each country is identified with a number. The primary purpose is to define each country and draw the borders of each country.
  • The Bottom Map is called the Result Map and also shows all the countries but know with its color.
  • The Calculate Button is used to perform a simulation and to calculate, based on the Target Map drawn, the actual colors in the Result Map.
  • The Mode Button has four values: "Continuous", "Auto", "Manual" and "Step".
    There is also an aditional mode called the "Wait" mode. During each calculation or simulation the calculation can temporarily stop and go into the "Wait" state. When the "Wait" mode button is selected the calculation will continue. The normal mode is the "Auto" mode. When the "Auto" mode the calculation will go into the "Wait" state each time when the complete map is colored. This defines one solution.
  • The central program in the simulation is called Maximum2. This is a recursive program which calls itself. When this program calls itself the parameter level is increased. When the program is finised the parameter level is decreased.
    When the "Manual" mode is selected each time when the level parameter is increased the calculation will go into the "Wait" state.
    The "Step" mode is the most accurate mode to investigate what the calculation does.
  • There is also an extra mode called the Continues mode. When this mode is selected the calculation will go through all the possible solutions, without stopping.
  • The End mode button is used to terminate the simulation. This mode is normally selected when you are in "Auto" mode and when a soltion is found, which will bring the calculation in the "Wait" state. When the End mode button is selected the simulation will finish and the Calculation button, will be shown
  • The Switch mode allows you to switch the numbers of individual countries. This can have influence about the actual solution selected.

The right side shows the results of each simulation and is subdivided in 4 sections.
Section 1 consists of 2 columns. Section 2 of 4. Section 3 of 4 and Section 4 of 1.

Program Four_color_theorem.xls

The Program Four_color_theorem.xls contains 10 simulations.
The first time user is adviced to select each simulation in succession. Generally speaking the higher examples are the most difficult.
When you observe the results you will see that below each result you will see two fields. One indified as "lvl" and the second as "Err".
In Blad1 the values are: 1 and 0. In Blad2: 1 and 0: In Blad3 1 and 0: In Blad4 3 and 0: In Blad5 9 and 0: IN Blad6 6 and 0. In Blad7 4 and 1. In Blad8 4 and 8 and in Blad9 11 and 14.
When you study Blad7, Blad8 and Blad9 you can easily see that there is an increase in complexity.
The next step is to Select "Calculate" and keep the mode "Auto". What follows is a short description of each simulation or "Blad"
  1. "Blad1" is used to demonstrate a situation where four countries meet each other. In fact there are two of these simulations.
  2. "Blad2" is used to demonstrate the simulation discussed in https://en.wikipedia.org/wiki/Four_color_theorem#False_disproofs
  3. "Blad3"

Program Four_color_theorem_test.xls

The program Four_color_theorem_test.xls also contains 10 simulations.
In the program Four_color_theorem.xls each simulation always shows two maps: The "Target map" and the "Result map".
The Four_color_theorem_test.xls program sometimes contains a third map called the "User map". The "User map" is a copy of the original "Target map" as original build, including some errors.
When you want to perform any simulation which also contains a "User map" you should first check that the "Target map" is the same as the "User map". When that is not the case you should copy the "User map" onto the "Target map".
To get an impression about each simulate use the "Auto" mode.

What follows is a short description of each simulation or "Blad"

  1. "Blad1" contains a "User map" and is used to demonstrate a situation where four countries meet each other at one point. There are two of these situations. The demonstration also shows a third situation where four countries meet, when two countries have the same number.
    The user should perform a simulation (Select Calulate) and observe the three errors. Next to make the necessary modifications in the "Target map" and try again.
  2. "Blad2" is used to demonstrate the simulation discussed in https://en.wikipedia.org/wiki/Four_color_theorem#False_disproofs
  3. "Blad3"

Excel Program description

The excel program more or less consists of two parts.
     Main          
        Initialize
            Init
            Store
            Macro_Right
            Macro_Bottom
            CrossTest
            Optimize_mat
            Optimize_mat1
                Replace
            Optimize_game 
                Tgame
        Calculate1
            Maximum1 
            Wait             
            Maximum2
                Process 
                Clearmap
                Exit sub
                ' one choice
                Test_Mat_kleur 
                Map_kleur
                Exit sub
                ' two choices
                Do
		     Test_mat 
                     Test_Mat_kleur
                     Map_kleur
                     Error --> Exit
                     Maximum2
                Loop
                Maximum3
                    Test_mat
                    Test_Mat_kleur
                    Map_kleur 
                Maximum2 
           Wait  

The three most important subroutines are Maximum1, Maximum2 and Maximum3.
  • Subroutine Maximum1 calculates the first three countries.
  • Subroutine Maximum2 is a recursive subroutine.
    This subroutine calls the subroutine Process. Next it selects countries based on two criteria. When these criteria are not enough it calls the sub Maximum3.
  • Subroutine Maximum3 is called to make a more complex choice
  • Subroutine Process selects countries

Reflection part 1


Reflection part 2


Feedback

None


Created: 12 April 2018

Back to my home page Contents of This Document