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
}
```
