Problem 1004
A checkerboard of three squares by one is drawn with black outline lines. We want to highlight in red some edges so as to connect, in a unique way, any vertex of the squares that compose it to any other, by following red edges only. (Note: for a checkerboard of two squares by one, there are 15 ways of coloring it)- 1A. How many different ways can red lines be drawn?
- 2A. Same question with a checkerboard of six squares by one.
- 3A. Same question with a checkerboard of two squares by two.
The idea of the program is to make an exhaustive enumeration of all the ways to take the edges, and then to see if the configuration obtained meets the defined criteria, namely that there is a single path connecting each pair of vertices.
There are several ways to model vertices and edges, but given the static aspect of the graph and its 2D mesh topology, the most effective one is to use a 2-dimensional array. In this array, some elements have an edge type, and others a vertex type.
The exploration of the configurations of the edges is made recursively, by calculating, in a defined order, the coordinates of the squares containing the next edge to take or not. Once all the edges are taken or not taken, it is necessary to test the configuration. The program starts by checking that all vertices are incident at a taken edge. This step can possibly be avoided, but allows not to perform the most expensive part - counting the paths - on configurations where vertices are unreachable.
Finally, counting the paths is done for all the pairs of vertices (source, destination), recursively, following the edges taken in the configuration to go to the vertices not taken, that is to say, passing at most once by a summit. The value obtained by this count is not correct when there is a cycle in the middle of the path, but in this case there will necessarily be pairs of points for which there will be more than one path (see figure).
The figure on the left represents the edges taken in green, and two vertices A and B. When counting the number of paths between A and B, the program will only find one (red edges in the figure on the right) instead of 3, because the summit C can only be taken once. However, in this case (when there is a cycle), the program will find two paths between each pair of vertices of the cycle (for example C and D in the figure). There is therefore an equivalence between counting exactly one path between each pair of vertices, and the fact that there is actually a single path between each pair of vertices.
To have the exact number of paths, it would be necessary to mark the edges and not the vertices during the count, but this would unnecessarily increase the number of cases to explore.
The code of the program can be found here.
There are several ways to model vertices and edges, but given the static aspect of the graph and its 2D mesh topology, the most effective one is to use a 2-dimensional array. In this array, some elements have an edge type, and others a vertex type.
The exploration of the configurations of the edges is made recursively, by calculating, in a defined order, the coordinates of the squares containing the next edge to take or not. Once all the edges are taken or not taken, it is necessary to test the configuration. The program starts by checking that all vertices are incident at a taken edge. This step can possibly be avoided, but allows not to perform the most expensive part - counting the paths - on configurations where vertices are unreachable.
Finally, counting the paths is done for all the pairs of vertices (source, destination), recursively, following the edges taken in the configuration to go to the vertices not taken, that is to say, passing at most once by a summit. The value obtained by this count is not correct when there is a cycle in the middle of the path, but in this case there will necessarily be pairs of points for which there will be more than one path (see figure).
The figure on the left represents the edges taken in green, and two vertices A and B. When counting the number of paths between A and B, the program will only find one (red edges in the figure on the right) instead of 3, because the summit C can only be taken once. However, in this case (when there is a cycle), the program will find two paths between each pair of vertices of the cycle (for example C and D in the figure). There is therefore an equivalence between counting exactly one path between each pair of vertices, and the fact that there is actually a single path between each pair of vertices.
To have the exact number of paths, it would be necessary to mark the edges and not the vertices during the count, but this would unnecessarily increase the number of cases to explore.
The code of the program can be found here.
- 1A : For 3 squares by one, there are 56 red networks.
- 1B : For 6 squares by one, there are 2911 red networks.
- 1C : For a checkboard of size 2 × 2, there are 192 red networks.