[Algorytmy][C] Znajdywanie unikalnej kombinacji

[miki999]

Witam,

mam mało ciekawy problem, z którym elegancko nie mogę sobie poradzić.

Dana jest tablica \(\displaystyle{ n \times m}\) o wartościach \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\). Należy znaleźć tablicę, w której w każdym wierszu znajduje się dokładnie 1 jedynka i ta jedynka również znajduje się w tablicy wejściowej i w żadnej kolumnie nie ma więcej niż 1 jedynki.


Przykład:
Tabela wejściowa:
\(\displaystyle{ \begin{tabular}{cccccc}
0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 \\
\end{tabular}}\)

Przykładowy wynik:
\(\displaystyle{ \begin{tabular}{cccccc}
0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
\end{tabular}}\)
Oczywiście dla wielu tabel rozwiązań może być więcej, ale chodzi mi o to, aby znaleźć jedno dowolne lub zwrócić informację, że nie ma takiej możliwości.


Jest jakiś algorytm określający ten problem, bądź prosty i niezbyt złożony sposób na obliczenie tego w aplikacji?

[Afish]

Trochę zmodyfikowany problem wież na szachownicy.

[miki999]

Dzięki za odpowiedź. Znalazłem nawet doprecyzowanie tego problemu nazwane "dziurawą szachownicą", chociaż i tak wykracza to poza moje umiejętności (chyba się starzeję ), ale może zapożyczę od kogoś w przyszłości algorytm.