Algorytm ustawienia figur na szachownicy

Question

Czesc,

Potrzbuje algorytmu który ustali czy mozliwe jest takie ustawienie K figur szachowych na planszy o wymiarach W na K że "nie bedzie żadnych bić".

Zrobiłem algorytm rekurencyjny z powrotami jednak jest on bardzo nieoptymalny. Polega on na tym że ide po kolei po planszy jesli pole jest wolne to ustawiam tam figurę i rekurencyjnie wywołuje ta sama funkcje dla planszy juz z tym pionkiem. jeśli dla tej nowej planszy funkcja zwróci prawdę czyli można tak ułożyć pozostałe figury żeby nie było bic to znaczy ze obecna figura (ostatnia postawiona) jest ok. Jeśli nie to cofam postawienie tej figury i daje ja gdzie indziej.

Sam ten algorym ma juz duza złożoność a dochodzi jescze to że musze sprawdzac te bicia. Na szybko zrobiłem tak że sprawdzam po kolei kazda figure na planszy czy ma jakies bicie, ale poniewaz program długo sie wykonuje wiem ze bedzie trzyba to zmienic.

Macie jakies pomysły jak znacząco ograniczyć złożoność?

Myslalem nad jakas tablica która będzie zapisywała na które pola wiemy ze nie warto próbować bo juz raz tam bylismy, ale to chyba nie zadziała bo sytuacje mogą być rożne (zależnie od liczby i rodzaju figur)

 

Dzieki za kazda rade.