Maximisation du nombre de carrés sélectionnés dans une grille

Question

Nous avons une grille de carrés $ N Times N $, chaque carré a un entier non négatif. Deux carrés distincts sont des voisins s'ils partagent une ligne ou une colonne. Une sélection de carrés est bonne si chaque carré sélectionné a un certain nombre de voisins sélectionnés inférieurs ou égaux à son nombre.

Existe-t-il un moyen connu de trouver le nombre maximum d'éléments dans une bonne sélection? De toute évidence, il y a un $ mathcal o (2 ^ {n ^ 2} n ^ 2) $ algorithme de force brute (nous pouvons tester la bonté d'une sélection dans le temps $ Mathcal o (n ^ 2) $ en précompossant le nombre de sélectionnés sélectionnés carrés dans chaque ligne et colonne).