Cut a triangle into equal-sized parts!

JavaScript (ES7),  367 362 359  357 bytes

^{Saved 1 byte thanks to @Shaggy}

Expects (n)(m).

n=>m=>(T=Array(n*n).fill(N=0),g=(A,P=[-1],k=T.findIndex(v=>!v),B=[...A,P[S='sort']()][S]())=>g[B]?0:~[1,1,0,1,1,0][M='map'](r=>g[B=B[M](P=>P[M](i=>~i?(y=i**.5|0)*y-i-(r?1-((~y*~y+~i>>1)-n)**2:y*~-~y):i)[S]())[S]()]=1)/P[m]?~k?g(B):++N:T[M]((v,j)=>v||(~P?P.every(i=>(y=i**.5|0)^j**.5|(i-j)**2-1&&j-i+2*(i+y&1?y:~y)):j-k)||T[T[j]++,g(A,[...P,j]),j]--))([])&&N

Try it online!

How?

TL;DR

This is a recursive search that keeps track of all the patterns that were already tried, transformed in all possible ways, in order to prune the search as soon as possible when a collision is found. This allows it to perform at a decent speed on small triangles despite an otherwise inefficient piece-building method.

Triangle description and cell indexing

A size-\$n\$ triangle is simply stored as an array of \$n^2\$ binary values. Empty cells are marked with \$0\$'s and occupied cells are marked with \$1\$'s.

JS initialization:

T = Array(n * n).fill(0)

By convention, the cells are numbered from \$0\$ to \$n^2-1\$, from left to right and top to bottom.

Below are some basic formulas:

• The 0-indexed row of the cell \$c\$ is \$y_c=\lfloor\sqrt{c}\rfloor\$
• The 0-indexed position of the cell \$c\$ within its row is \$c-{y_c}^2\$
• The 0-indexed distance of the cell \$c\$ from the last cell in its row is \${(y_c+1)}^2-c-1\$

Testing whether 2 cells are neighbors

Two cells \$c\$ and \$d\$ are horizontal neighbors if \$y_c=y_d\$ and \$|c-d|=1\$ (e.g. \$c=10\$ and \$d=11\$, or the other way around).

Two cells \$c\$ and \$d\$ are vertical neighbors if either:

• \$c+y_c\$ is even and \$d=c+2\times(y_c+1)\$ (e.g. \$c=3\$ and \$d=7\$)
• \$c+y_c\$ is odd and \$d=c-2\times y_c\$ (e.g. \$c=7\$ and \$d=3\$)

Hence the following JS expression which is truthy if the cells i and j are not neighbors:

(y = i ** .5 | 0) ^ j ** .5 | (i - j) ** 2 - 1 && j - i + 2 * (i + y & 1 ? y : ~y)

Reflections

A vertical reflection is applied by doing:

$$d=2\times y_c\times (y_c+1)-c$$

Examples:

$$2\times y_{10}\times (y_{10}+1)-10=2\times 3\times 4-10=14\\ 2\times y_{14}\times (y_{14}+1)-14=2\times 3\times 4-14=10$$

Rotations

A 120° rotation is applied by doing:

$$d=\left(n-\left\lfloor\dfrac{(y_c+1)^2-c-1}{2}\right\rfloor\right)^2+{y_c}^2-c-1$$

Examples:

• \$c=0\$ is turned into \$d=15\$
• \$c=7\$ is turned into \$d=12\$

Combining reflections and rotations

In the JS implementation, both formulas are combined into the following expression. This code applies a reflection to the cell i when r = 0 or a rotation when r = 1.

(y = i ** .5 | 0) * y - i - (
  r ?
    1 - ((~y * ~y + ~i >> 1) - n) ** 2
  :
    y * ~-~y
)

To get all possible transformations of a tiling, we apply 2 rotations, followed by a reflection, followed by 2 rotations, followed by a reflection.

Hence the loop:

[1, 1, 0, 1, 1, 0].map(r =>
  /* ... apply the transformation to each cell of each piece of the tilling ... */
)

Describing the tiling

Each piece of the tiling is stored in an array of \$m+1\$ entries consisting of a leading -1 followed by \$m\$ indices corresponding to the cells it contains.

The current piece is stored in P[]. The array A[] contains the previous pieces. The array B[] contains the previous pieces and the current piece, with all pieces sorted in lexicographical order and all indices also sorted in lexicographical order within each piece.

Example:

The following tiling:

would be described with:

B = [
  [ -1, 0, 1, 2, 3 ],
  [ -1, 10, 11, 4, 9 ],
  [ -1, 12, 5, 6, 7 ],
  [ -1, 13, 14, 15, 8 ]
]

Once coerced to a string, this gives a unique key that allows us to detect whether a similar configuration was already encountered and prune the search.

"-1,0,1,2,3,-1,10,11,4,9,-1,12,5,6,7,-1,13,14,15,8"

The purpose of the -1 markers is to make sure that an incomplete piece followed by another piece in the key is not mixed up with another complete piece.

The keys are stored in the underlying object of the function g.

Main algorithm

The recursive search function goes as follows:

• find the position k of the first empty cell in the triangle
• update B[]
• abort if B[] was already encountered
• apply all transformations to B[] and mark them as encountered
• if P[] is complete:
  • if the triangle is full (k is set to -1): we've found a new valid tiling, so increment the number of solutions N
  • otherwise, append P[] to A[] and start building a new piece
• if P[] is not yet complete:
  • if P[] does not contain any tile, append k to it
  • otherwise, try to append the index of each tile that has at least one neighbor in P[]

Scala 3, 526...358 357 bytes

n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

Try it in Scastie!

Dotty's tupled parameter destructuring save a few bytes, but it's pretty much the same as the approach below.

Scala 2, 548...362 361 bytes

n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{case(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

Try it online

Ungolfed version

To see the individual triangles

Explanation

Each point is represented by an x-y pair (Int,Int). The x-position starts out at 1 at the left and increases as it goes to the right. The y-position starts out at 1 at the top and increases as it goes to the bottom. A piece of the triangle is represented as a set of points (Set[(Int,Int)]), and a triangle (possible solution) is represented as a set of those pieces (Set[Set[(Int,Int)]])

The first line defines c, a Set which will hold all possible solutions (and currently just holds a single partially completed triangle that holds a single piece that holds a single point (\$(1,1)\$, the top of the triangle)). d says how many of those triangles are completed. This is the variable that will be returned at the very end.

The bulk of the function is taken up by a while loop that runs as long as d is 0 and c is not empty (if d is more than 0, it means we've found all the triangles we're ever going to find, and if c is empty, it means there aren't any possible solutions).

Each iteration, d is set to the number of triangles in c that have has \$\frac{n*n}{m}\$ pieces and all their pieces are of size m. For that, the expression c.count{t=>t.size*m==n*n&t.forall(_.size==m)} can be used.

Then, we find the next value of c. The code creates new triangles by adding neighbors to the old triangles in c, and to ensure only unique triangles are kept, it first creates a set of all 6 permutations for each of the new triangles. Because c is a Set, it removes duplicates by default without us having to do any work. After the permutations have been generated and the duplicates remove, it's simple to extract a single permutation with <all_permutations>map(_.head).

When the while loop ends, we simply return d.

Specifics:

Generating new triangles

For every shape in a triangle, we take all its neighbors, and remove the ones that are already in the triangle. Then, if the shape already has \$m\$ cells, we make a new shape containing only the neighbor and add it to the triangle, otherwise we add the neighbor to the shape. For comprehensions make this part easy:

for { 
  t <- c              //For every triangle t in c
  s <- t              //For every piece/shape s in t
  a -> b <- s         //For every point (a, b) in s
  e = a % 2 * 2 - 1   //This is just to reuse
  //The cell to the left, the cell to the right, and the cell above/below
  neighbors <- Set( (a - 1, b) , (a + 1, b) , (a + e, b + e) )
  //x and y are the coordinates of the neighbor
  x -> y <- neighbors -- t.flatten //Remove neighbors already in the triangle
  //Make sure the neighbor is within bounds of the triangle
  if 0 < y & y <= n & 0 < x & x < y * 2 
} yield (
  if (s.size < m) t - s + (s + (x -> y)) //If s is not full, add the neighbor to s
  else t + Set(x -> y) //Otherwise, make a new shape containing just (x, y)
)

^{The new triangles are not directly yielded, this is just an example.}

Generating all permutations

Each triangle has 6 different permutations, which can be found by alternating between reflecting over the y-axis and rotating 60 degrees clockwise + reflecting it over the y-axis. We can scanLeft over a range of numbers, doing the first transformation when the element is even, and the second when it's odd.

Assuming we already have a triangle <new_triangle>, we can scan left over a range of 5 numbers, leaving us with 6 triangles:

0.to(4).scanLeft(<new_triangle>){ 
  (t, i) => //i is the current index/element, t is the triangle to transform
  t.map { s => //Transform every shape s in t
    s.map {
      case (x, y) => //Transform every point in s (x, y)
        //If i is even, it will rotate+reflect, if it's odd, it will reflect
        Seq( (x, n + 1 - y + x / 2) , (y * 2 - x, y) )(i%2)
    }
  }
}

Reflecting a point over the y-axis:

For a point \$(x,y)\$, the y-coordinate stays the same after reflecting, and the x-coordinate becomes \$y * 2 - x\$, since \$y * 2\$ is the biggest possible x-coordinate for a given y-coordinate.

Rotating a point 60 degrees clockwise + reflecting it over the y-axis:

You can rotate and reflect a point at once if you keep the x-coordinate the same and set the y-coordinate to \$n + 1 - y + x / 2\$.

Commented:

//Take n and m, curried
n => m => {
  val S = Set //The Set companion object, to reuse later
  //c holds all our possible solutions/triangles as we build them
  //d holds how many of the triangles in c are complete
  var (c, d) = S(S(S(1 -> 1))) -> 0

  //While we haven't found any complete triangles and 
  //the set of possible solutions is nonempty, keep going
  while (d < 1 & c != S()) {
    //Count how many of c's triangles have n*n/m pieces, each with m cells
    d = c.count { t => t.size * m == n * n & t.forall(_.size == m) }
    //This for comprehension adds a cell to each triangle and
    //generates all permutations of each new triangle
    c = (for { 
      t <- c
      s <- t
      a -> b <- s
      c = a % 2 * 2 - 1
      x -> y <- S(a - 1 -> b, a + 1 -> b, (a + c, b + c)) -- t.flatten
      if 0 < y & y <= n & 0 < x & x < y * 2
    } yield 
      S(0 to 4:_*).scanLeft(
         if (s.size < m) t - s + (s + (x -> y))
         else t + Set(x -> y)
      ) { (t, i) =>
         t.map(_.map { case (x, y) =>
           Seq((x, n + 1 - y + x / 2), y * 2 - x -> y)(i % 2)
         })
      }
      //Convert the Seq of permutations to a set so duplicates can be compared out of order and removed
     )  //End of massive for-comprehension 
     map (_.head) //Extract only the first permutation from each set of permutations
  }
  d
}
```