Pfade bei 4 Damen II

Es gibt insgesamt
16!
12!
= 43.680
Möglichkeiten, 4 Damen auf einem 4 x 4-Brett unterzubringen.

Wenn beim Setzen der k-ten Dame nur die k-te Zeile berücksichtigt wird, reduziert sich die Zahl auf nⁿ Möglichkeiten. Hier sind dies 4⁴ = 256.

Wenn zudem sofort die Positionen verworfen werden, bei denen sich schon weniger als n Damen bedrohen, sind für n = 4 insgesamt 17 Zustände zu untersuchen, worunter 2 Lösungen und 4 Sackgassen sind.