1
$\begingroup$

Constraints: The blocks must be adjacent to each other. i.e. A pair of blocks must have a common edge or vertex. Any shapes that are formed by flipping or rotating or mirroring should be considered to be the same shape.

By manual inspection, for example, For N=2, there are 2 unique shapes in a 2x2 grid

[][]

[]
  []

For N=3, there are 5 unique shapes in a 3x3 grid

[][][]


[][]
[]


[]
  [][]


[]  []
  []


[]
  []
    []

I can find the total number of shapes using the combination formula, nCr

For r=2 and n=2x2=4, we get 4C2 = 6 shapes (4+2)

For r=3 and n=3x3=9, we get 9C3 = 84 shapes (6+16+16+8+2) + 36 non-adjacent

Need help in finding out mathematically or algorithm-wise,

  • how to identify non-adjacent blocks
  • how to identify mirror patterns
  • how to identify rotating/flippable patterns

Similar questions were asked in the following links but I wasn't able to extrapolate any concrete solutions.

link1

link2

I tried researching graph theory for ways to identify identical shapes (mirror, rotate, flip).

$\endgroup$
  • $\begingroup$ I am not sure I understand the question correctly but there would appear to be a near perfect duplicate at this MSE link. $\endgroup$ – Marko Riedel Jul 19 '16 at 20:35
  • $\begingroup$ By your stated rules, there are $5$ unique shapes for $N=2$: You omit the single block, the $L$ shape, and the full grid. Did you mean the queivalent of "How many distinguishable length-$N$ non-self-intersecting paths are there in an $N\times N$ square grid such that for all $k$, the $k+1$-st vertex on the path is adjacent or diagonally adjacent to the $k$-th entry? $\endgroup$ – Mark Fischler Jul 19 '16 at 20:37
  • $\begingroup$ I see the adjacency constraint now, so no duplicate. $\endgroup$ – Marko Riedel Jul 19 '16 at 20:50
  • $\begingroup$ I don't understand yet, some shapes seem to be missing in the list for $3$. $\endgroup$ – André Nicolas Jul 19 '16 at 20:55
  • $\begingroup$ For N=2, there are just 2 unique shapes. You cant form a L with 2 blocks, nor can you occupy the full grid (you need 4 blocks!). $\endgroup$ – embedded_developer Jul 19 '16 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.