Counting overlapping objects

Question

Consider a NxN pixel grid with up to M objects drawn on it, either squares or diamonds:

square    diamond

The objects may overlap, so recognition is hard. The task is to give the minimal possible numbers of objects per shape that can be "seen" in the picture and tell how many squares, how many diamonds, and how many objects with unknown shape there are.

You can find a reference algorithm that solves the problem here.

Here are some examples with their intended numbers (n_square, n_diamond, n_unknown). The examples with n_unknown = 1 are those with pixels that may either come from a square or a diamond (highlighted in black, but not bearing any information that may be used).

The program with shortest mean runtime in terms of grid size N wins!

And this is a simple test case generator:

let N = 10

// initialize the grid
let grid = Array.from(Array(N), () => new Array(N));

// choose a random number of objects <= M
let n = Math.ceil(Math.random()*M)

// create objects
while (n-- > 0) {

    // choose random position, but not on the border of the grid
    var i = Math.ceil((N-2)*Math.random())
    var j = Math.ceil((N-2)*Math.random())

    if (Math.random() > 0.5) {
        // draw a square
        for (var k = -1; k <=1; k++) {
            for (var l = -1; l <=1; l++) {
                grid[i+k][j+l] = 1
            }
        }
    } else {
        // draw a diamond
        for (var k = -1; k <=1; k++) {
            for (var l = -1; l <=1; l++) {
                if (!(k && l)) {
                    grid[i+k][j+l] = 1
                }
            }
        }
    }
}

Some small test cases:

Answer 1

Haskell, O(2ⁿ)

import Data.Bits
import Data.List
listFromPair=uncurry((.pure).(:))
s`isSubsetOf`p=s.&.p==s
bsum=foldl(.|.)0::[Integer]->Integer
numbers n p=let
 w=[0..n-3]
 diamond=[1,n+0,n+1,n+2,2*n+1]
 square=diamond++[0,2,2*n,2*n+2]
 solutions=sortOn length$filter((p==).bsum)$subsequences$
   filter(`isSubsetOf`p)[bsum[bit(r*n+c+d)|d<-s]|r<-w,c<-w,s<-[diamond,square]]
 minlength=length$solutions!!0
 best=takeWhile((minlength==).length)solutions
 numb=map minimum.transpose$map(map length.listFromPair.partition((9==).popCount))best
 in numb++[minlength-sum numb]

Try it online!