In the pattern lock system below,

- all of the 9 nodes have to be connected without any cycle, and
- any connection using one or more diagonal edges is not allowed.

For example, pattern #1 below is good.

Pattern #2 is invalid because it includes a cycle, as indicated by the red square. Pattern #3 is invalid because it contains an implicit cycle, i.e. the red segment must be traveled twice to go from the lower left corner to the lower right corner. Pattern #4 is invalid because a diagonal edge is used to connect 2 nodes.

So, how many different patterns can be generated for this system?

**Bonus**: What if using diagonal edges is allowed while intersections between 2 or more diagonal edges are prohibited. Can you find the number of different patterns in this case?

×

Problem Loading...

Note Loading...

Set Loading...