Algoritmia - Cota Optimista

Dado un tablero de NxN casillas, tenemos que poner el minimo de torretas posible para cubrir todas las casillas del tablero utilizando ramificación y poda. La torreta va a cubir todas las diagonales hacia arriba, abajo izquierda y derecha (Como una reina en el ajedrez), hasta que no quede ninguna casilla por cubrir.

El problema que tengo, es que no se encontrar una cota optimista para cada estado. Alguien tiene alguna idea?

No deberias poner mas de N-2 reinas, pues se puede cubrir todo con N-2 reinas siempre.