Informatyka tiling

2

To pytanie zostało przeniesione z Mathematics Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 6 lat temu . Dominosa to stosunkowo nowa gra logiczna. Jest odtwarzany na siatce . Przed rozpoczęciem gry kości domina są umieszczane na siatce (tworząc idealne kafelki ). W następnym kroku …

26 complexity-theory np-hard board-games tiling

3

Ile ciasteczek w polu ciasteczek? - Dachówka gwiazd

W związku z nadchodzącym okresem świątecznym postanowiłem zrobić gwiazdy cynamonu . To było zabawne (a wynik smaczny), ale mój wewnętrzny kujon skurczył się, gdy włożyłem pierwszą tacę gwiazd do pudełka i nie zmieściłyby się w jednej warstwie: Prawie! Czy istnieje sposób, w jaki mogliby pasować? Jak dobrze potrafimy kafelkować gwiazdy? …

19 algorithms optimization computational-geometry tiling

1

Czy układanki „zero-jedynkowe” są kompletne NP?

Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka to ˉ k , dla niektórych k ∈ …

18 complexity-theory np-complete tiling

2

Układanie ortogonalnego wielokąta za pomocą kwadratów

Biorąc pod uwagę ortogonalny wielokąt (wielokąt, którego boki są równoległe do osi), chcę znaleźć najmniejszy zestaw kwadratów wewnętrznie rozłącznych, których zjednoczenie jest równe wielobokowi. Znalazłem kilka odniesień do nieco innych problemów, takich jak: Pokrycie prostopadłego wielokąta kwadratami - podobnie jak w moim problemie, ale zakrywające kwadraty mogą się pokrywać. Ten …

12 algorithms computational-geometry tiling

Pytania otagowane jako tiling