Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a method to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions?

1- No vertical line crosses any horizontal line and vice versa.

2- Each vertical line touches exactly three horizontal lines and each horizontal line touches exactly three vertical lines.

Here is an example when $n=4$:

example for n = 4

share|cite|improve this question
Is this possible if $n \ge 3$? – Henry May 6 '11 at 16:29
Yes, it is possible. – Mohammad Al-Turkistany May 6 '11 at 16:33
I still cannot see it. Can you add an example picture to your question? – Henry May 6 '11 at 16:49
I would say that your picture has two horizontal and two vertical partitioning lines, each touching two of the other orientation; modulo symmetry I thing there are four such cases. If you regard it as four horizontal and four vertical partitioning lines, each touching three of the other orientation, then (ignoring its reflection) this may be the only case. – Henry May 6 '11 at 17:20
Isn't your picture for n=2? (two vertical and 2 horizontal lines added inside the square? Also, do you count a line touching a side of the square (perpendicular to it) as one of the three lines it touches? That seems to be the case in your picture – amWhy May 6 '11 at 17:21

Look into work about what are called fault free tilings. Here is one paper of this kind:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.