zenob
3/20/2007 9:27:00 PM
Mam takie zagadnienie do rozwi?zania :
Dana jest szachownica o rozmiarach X na Y , na k polach znajduj? sie
figury. Nale?y pokrya wszyskie pozosta3e pola kostkami domina, przy
czym ka?da kostka zajmuje 2 pola szachwnicy.
Pytanie: czy da sie rozwi?zaa ten problem przy z3o?ono?ci wielomianowej?
Jedyne co mi przychodzi do g3owy to sprawdzanie kolejnych permutacji
u3o?en klocków, co daje z3o?ono?a wyk3adnicz? . Z zasady dualno?ci(?)
mo?na na samym pocz?tku odrzucia wszyskie problemy dla k nieparzystego,
jednak to nie zmienia typu z3o?ono?ci.
Z góry dziekuje za odpowied?,
pozdrawiam Zenob