Algorithmus zur Verfügbarkeitsberechnung

[jfheins]

Ich schlage mal "intelligentes Duchprobieren" vor.

Es gibt ja 2 Zustände, 0 und 1. Die Spaltensumme soll immer 1 ergeben, die Zeilensumme einen definierten Wert. Jetzt werden erstmal alle Summen gebildet. Dann wird geschaut, wo zuviel ist. (Klar soweit?) Dann jeweils die Zeile und die Spalte mit der größten Summe hernehmen und den Wert in der Zelle durch eine 0 ersetzen. Dann prüfen ob alle Bedingunen erfüllt wurden. Wenn nicht, den gleichen Algorithmus rekursiv anwenden, wenn das auch nicht hilft eine alternative Zelle auf 0 setzen.

Also eine (einfache) Heuristik und Backtracking. Könnte ganz gut funktionieren, und liefert garantiert ein Ergebnis wenn es eines gibt. Die Frage ist nur, wie lange es braucht - das kann ich jetzt nicht genau abschätzen. Für das Beispiel tippe ich mal auf eine Laufzeit unter 100ms.