Pytania otagowane jako integer-lattice

1
Losowy sam unikający się cykl kratowy w obrębie danego obwiedni
W związku z układanką Slither Link zastanawiałem się: Załóżmy, że mam siatkę kwadratowych komórek i chcę znaleźć prosty cykl krawędzi siatki, równomiernie losowy wśród wszystkich możliwych prostych cykli.n × nn×nn\times n Jednym ze sposobów na to byłoby użycie łańcucha Markowa, którego stanami są zbiory kwadratów, których granice są prostymi cyklami …



2
Złożoność ukrytej łamigłówki wielokątów na kwadratowych siatkach?
Hiroimono jest popularną łamigłówką . Interesuje mnie złożoność obliczeniowa powiązanej układanki.N.P.NPNP Problemem jest: Dane wejściowe : Biorąc pod uwagę zestaw punktów na siatce kwadratowej x i liczbie całkowitejn knnnnnnkkk Pytanie : Czy istnieje wielokąt prostoliniowy (jego boki równoległe do osi lub ) taki, że liczba punktów na rogach wielokąta wynosi …

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.