Bagaimana saya bisa memastikan kisi-kisi dapat diisi dengan potongan seperti Tetris?

Saya sedang berpikir untuk membuat permainan puzzle di mana tujuannya adalah untuk mengisi kotak dengan potongan puzzle berbentuk (misalnya, bentuk Tetris klasik).

Bagaimana saya bisa menghasilkan seperangkat potongan yang dapat dijamin akan digunakan untuk mengisi grid, tanpa meninggalkan celah? Bagaimana saya bisa mengadaptasi algoritma ini untuk skala kesulitan puzzle yang dihasilkan?

Ini adalah masalah yang sulit diketahui, menentukan persegi panjang apa yang bisa diberi ubin dengan potongan-potongan tertentu.

Namun, jika Anda membuat puzzle dan dapat mengendalikan kepingannya, itu adalah kebalikannya, masalah konstruktif, dan lebih mudah ...

Bangun solusi secara konstruktif. Ambil beberapa potong yang Anda suka, dan isi teka-teki sesuka Anda. Kemudian masukkan cukup satu kotak untuk mengisinya, dan Anda telah memastikan bahwa setidaknya ada satu solusi. Atau lebih tepatnya, sertakan beberapa potongan kecil dalam set potongan yang diizinkan.

Adapun untuk memecahkan / meletakkan potongan-potongan, pendekatan brute force yang khas adalah mengisinya dari kiri ke kanan, kemudian dari atas ke bawah. Temukan sel terbuka pertama (LR bernomor, TB) dan coba masukkan potongan yang diizinkan dalam orientasi yang diizinkan (8 orientasi untuk bagian asimetris jika Anda mengizinkan pembalikan). Mungkin periksa dulu potongan besar yang diizinkan, dan gunakan yang lebih kecil jika perlu. Ketika Anda mencapai keadaan yang tidak Anda sukai (jalan buntu, terlalu banyak potongan kecil, atau apa yang tidak) kemudian mundur. Jika himpunan grid / piece tertentu tidak memenuhi kriteria Anda, yaitu, ia mundur sepenuhnya tanpa menyelesaikan, coba set persegi panjang dan piece yang berbeda.

Salah satu cara untuk membuat teka-teki "lebih mudah" bisa dengan menukar potongan yang lebih besar dengan potongan yang lebih kecil seperti monomino dan domino, karena ini akan meninggalkan lebih banyak cara untuk mengisi lubang terakhir. Atau, secara setara, membangun solusi yang mendukung potongan-potongan kecil.

Beberapa ahli polyominologi yang terkenal meliputi:

==> http://ee.usc.edu/faculty_staff/faculty_directory/golomb.htm Golomb awalnya menciptakan istilah "Polyomino"

==> http://www.eklhad.net/polyomino/ Dahlke telah memecahkan beberapa persegi panjang yang diisi dengan potongan identik (bentuk ubin yang sangat langka)

Artikel ini (halaman 11-13, penafian: Saya salah satu penulis) menjelaskan suatu algoritma yang menggunakan pemrograman dinamis untuk secara seragam menghasilkan daerah persegi panjang ubin sempurna lebar w dan tinggi h , dalam waktu yang linier dalam h setelah preprocessing yang membutuhkan sekitar 2 ^{( w . D )} waktu / ruang ( D menjadi dimensi terpanjang dari bentuk individu, misalnya 4 dalam kasus potongan Tetris).

Idenya mirip dengan yang dijelaskan oleh David di atas, dan berfokus pada strip atas , menempatkan potongan-potongan yang tidak membuat lubang . Kuncinya di sini adalah memulai dengan menghitung alternatif yang diizinkan untuk setiap keadaan strip atas, sehingga Anda tidak lagi membayar untuk ledakan kombinatorial ketika Anda menghasilkan daerah.

Algoritme berfungsi untuk setiap set bentuk (cembung).

Juga, aspek yang menarik dari generasi acak yang seragam adalah memastikan generasi maksimal yang beragam (tetapi Anda juga bisa membatasi generasi dengan cara apa pun yang Anda inginkan). Berikut adalah beberapa keluaran khas:

Jangan ragu untuk bertanya apakah Anda mengalami masalah dengan implementasi (saya bahkan mungkin memiliki implementasi cepat dan kotor Python di sekitar suatu tempat ...)

Berikut adalah teknik yang kami gunakan di masa lalu untuk sedikit menipu pada perangkat keras yang lebih terbatas. Ini tidak semurni solusi yang lebih kompleks, tetapi memiliki keuntungan yang berbeda yaitu menjadi lebih mudah untuk diimplementasikan dan bekerja setiap saat.

Alih-alih berfokus pada seluruh teka-teki, pecahkan menjadi unit yang lebih kecil dan seragam . Masing-masing unit ini terdiri dari sejumlah set potongan yang cocok bersama untuk membentuk kotak atau persegi panjang yang jauh lebih mudah untuk diisi menjadi puzzle. Pilih secara acak dari berbagai konfigurasi untuk mengisi lebar teka-teki (contoh di bawah, tetapi ada banyak, banyak konfigurasi). Di bawah ini adalah 4x4, 5x4, dan bahkan contoh 10x4.

Idenya adalah bahwa Anda "strip" teka-teki ... pilih lebar secara acak berdasarkan ruang tersisa yang tersedia. Setelah "strip" selesai, mulailah strip baru.

Anda melepaskan potongan satu strip pada satu waktu dengan mengacak dalam setiap set "stripe". Jika Anda ingin meningkatkan kesulitan, lepaskan secara acak dari dua garis atau lebih sekaligus.

Dengan menggunakan teknik ini, Anda tidak hanya memastikan bahwa puzzle dapat dipecahkan, Anda juga membantu "menipu" urutan rilis untuk membuatnya lebih mudah untuk tetap hidup. Tentu saja dalam latihan, pemain tidak dapat menyelesaikan setiap strip dengan sempurna dan kekacauan pun terjadi.

Terus menghasilkan garis sampai pemain kalah. Tentu saja, contoh saya adalah strip 4 blok tinggi, tetapi Anda dapat memilih sesuatu yang lebih besar dan lebih kompleks: