Una forma de hacerlo sería comprobando que todas las posiciones están unidas a un único árbol.

Puedes meter todas las posiciones en una lista, y las vas sacando a medida que el algoritmo de recorrido del laberinto encuentra una nueva posición.

O de otra forma: partiendo de una posición cualquiera, generar llamadas recursivas por cada desviación posible y que no haya sido ya visitado. En cada nueva posición, agregamos la celda a un diccionario. Si llegamos a un camino sin salida, terminamos. Al final, en el diccionario quedan todas las posiciones alcanzables desde la posición inicial. Si el número de celdas es igual al de posiciones disponibles, está conseguido.

Hay muchas más formas de hacerlo, desde luego.