ITSITS
(IJCSAM) International Journal of Computing Science and Applied Mathematics(IJCSAM) International Journal of Computing Science and Applied MathematicsPuzzle Suguru (juga dikenal sebagai Nanbaburokku) adalah teka-teki kertas dan pensil untuk satu pemain yang diperkenalkan pada tahun 2001 dan baru-baru ini terbukti NP-lengkap oleh Robert dan lainnya pada tahun 2022. Seperti Sudoku yang terkenal, pemain harus mengisi sel kosong dalam grid persegi panjang, mematuhi beberapa aturan teka-teki. Permainan ini dimainkan di grid m x n yang dipartisi menjadi region. Sebuah region adalah kumpulan sel yang terhubung secara tegak lurus. Tujuannya adalah mengisi semua sel dengan angka sehingga: (1) tidak ada dua sel dalam region yang sama dapat mengandung angka yang sama; (2) tidak ada dua sel yang berdekatan, baik secara tegak lurus atau diagonal, dapat mengandung angka yang sama; dan (3) angka dalam sel harus antara 1 dan ukuran region yang dimilikinya, di mana ukuran region didefinisikan sebagai jumlah sel di dalamnya. Puzzle telah lama dianggap sebagai tantangan mental yang menarik yang telah menghibur dan melibatkan individu sepanjang sejarah. Mereka menyediakan kesempatan rekreasi dan hiburan serta merangsang keterampilan kognitif seperti berpikir kritis dan pemecahan masalah. Selain itu, aspek teoritis puzzle telah menarik minat yang signifikan dari komunitas ilmiah dalam dua puluh tahun terakhir karena hubungan mendalamnya dengan masalah penting dalam matematika dan teori komputasi, yang menghasilkan penyelidikan ekstensif tentang aspek matematika dan komputasinya (lihat [4]–[6] untuk penyelidikan yang luas). Artikel ini membahas pendekatan elementer, metode backtracking, yang ditingkatkan dengan optimasi pruning. Kami menunjukkan bahwa pendekatan ini dapat menyelesaikan puzzle Suguru apa pun, dengan catatan bahwa waktu penyelesaian meningkat dalam faktor faktorial sehubungan dengan ukuran puzzle dan jumlah petunjuk. Selain itu, kami menyelidiki varian yang dapat diselesaikan dari puzzle Suguru. Menyelidiki varian seperti masalah NP-lengkap memiliki pentingnya yang signifikan dalam teori kompleksitas komputasi.
Kami menyajikan algoritma yang memverifikasi solusi puzzle Suguru ukuran m x n dalam waktu O(mn) dan mengusulkan teknik backtracking untuk menyelesaikan instance puzzle Suguru ukuran m x n dengan H petunjuk sel dan R region dalam waktu O(R · (mn - H 2).Meskipun batas atas faktorial ini untuk waktu berjalan, implementasi C dari algoritma yang diusulkan berhasil menyelesaikan semua instance Suguru dengan sel tidak lebih dari 100 menggunakan komputer pribadi dalam waktu kurang dari 0,5 detik.Kami juga membuktikan bahwa setiap instance Suguru ukuran m x n di mana m = 1 atau n = 1 dapat diselesaikan dalam waktu linear sehubungan dengan ukuran puzzle.Namun, kami berpendapat bahwa menemukan semua solusi untuk puzzle Suguru yang dapat diselesaikan mungkin memerlukan langkah komputasi non-polinomial.Kami menyimpulkan dengan menyarankan lebih banyak penyelidikan tentang penggunaan pemecah SAT dalam menyelesaikan puzzle Suguru.Penerapan pemecah SAT telah terbukti sangat efektif dalam menyelesaikan masalah NP-lengkap lainnya, seperti masalah n-queen, dan juga dapat menjadi pendekatan yang menjanjikan untuk puzzle Suguru.
1. Mengembangkan teknik backtracking yang diusulkan untuk menangani instance puzzle Suguru yang lebih besar dengan lebih banyak region dan petunjuk sel. 2. Menjelajahi penggunaan pemecah SAT dalam menyelesaikan puzzle Suguru, yang telah terbukti efektif dalam menyelesaikan masalah NP-lengkap lainnya. 3. Meneliti lebih lanjut tentang varian yang dapat diselesaikan dari puzzle Suguru, yang dapat memberikan wawasan berharga tentang struktur dan sifat dasar puzzle Suguru.
| File size | 835.85 KB |
| Pages | 15 |
| DMCA | Report |
Related /
SEMINAR IDSEMINAR ID Kelemahan utama metode ini terletak pada proses pencarian nilai indeks perbaikan untuk setiap sel kosong yang memerlukan penelusuran loop tertutup padaKelemahan utama metode ini terletak pada proses pencarian nilai indeks perbaikan untuk setiap sel kosong yang memerlukan penelusuran loop tertutup pada
UPN VeteranUPN Veteran Temuan ini memperkuat literatur yang menyatakan bahwa digitalisasi keuangan mendukung inklusi keuangan dan tujuan pembangunan berkelanjutan, khususnyaTemuan ini memperkuat literatur yang menyatakan bahwa digitalisasi keuangan mendukung inklusi keuangan dan tujuan pembangunan berkelanjutan, khususnya
UPN VeteranUPN Veteran Hasil penelitian menunjukkan bahwa pertumbuhan penduduk secara tidak langsung berkontribusi signifikan pada alih fungsi lahan di perkotaan. PermintaanHasil penelitian menunjukkan bahwa pertumbuhan penduduk secara tidak langsung berkontribusi signifikan pada alih fungsi lahan di perkotaan. Permintaan
ITSITS The minimum cardinality of the bi-edge metric resolving set graphs is called the bi-edge metric dimension of G graph, denoted by e dimb(G). The specificThe minimum cardinality of the bi-edge metric resolving set graphs is called the bi-edge metric dimension of G graph, denoted by e dimb(G). The specific
ITSITS The comparison of EGARCH and GJR-GARCH models was carried out to address the asymmetric residual data pattern. Based on the research results, the bestThe comparison of EGARCH and GJR-GARCH models was carried out to address the asymmetric residual data pattern. Based on the research results, the best
ITSITS An alternative method of integration-based parameter estimation applied in pharmacokinetics problems is proposed here. The method, introduced by HolderAn alternative method of integration-based parameter estimation applied in pharmacokinetics problems is proposed here. The method, introduced by Holder
ITSITS Hal ini dibuktikan dengan menggunakan dua kasus. pertama, jika uv = 1, maka u dan v tidak berdekatan. Kedua, jika uv = x ≠ 1, di mana x = u−1 atauHal ini dibuktikan dengan menggunakan dua kasus. pertama, jika uv = 1, maka u dan v tidak berdekatan. Kedua, jika uv = x ≠ 1, di mana x = u−1 atau
UGMUGM Hasil empiris menunjukkan hubungan positif dan signifikan antara pengembalian IDR/CHF, IDR/JPY, dan IDR/USD dengan varian bersyaratnya. Untuk pengembalianHasil empiris menunjukkan hubungan positif dan signifikan antara pengembalian IDR/CHF, IDR/JPY, dan IDR/USD dengan varian bersyaratnya. Untuk pengembalian
Useful /
UPN VeteranUPN Veteran Oleh karena itu, pengelolaan likuiditas dan risiko kredit yang prudent menjadi kunci untuk menjaga kepercayaan masyarakat dan mendukung peran BPR dalamOleh karena itu, pengelolaan likuiditas dan risiko kredit yang prudent menjadi kunci untuk menjaga kepercayaan masyarakat dan mendukung peran BPR dalam
POLTEKMUPOLTEKMU Masyarakat juga mengerti cara pembuatan dan penggunaan lubang resapan biopori. Teknologi tepat guna ini akan menjadi solusi banjir di Kelurahan ManggalaMasyarakat juga mengerti cara pembuatan dan penggunaan lubang resapan biopori. Teknologi tepat guna ini akan menjadi solusi banjir di Kelurahan Manggala
UGMUGM 736 perusahaan di wilayah Asia selama periode 2005-2015 disajikan. Hasil penelitian mengungkapkan bahwa perusahaan yang fleksibel secara finansial menghabiskan736 perusahaan di wilayah Asia selama periode 2005-2015 disajikan. Hasil penelitian mengungkapkan bahwa perusahaan yang fleksibel secara finansial menghabiskan
UGMUGM Selain itu, studi bisa mengeksplorasi apakah frekuensi kunjungan pelanggan memengaruhi sensitivitas mereka terhadap keadilan harga atau interaksi staf,Selain itu, studi bisa mengeksplorasi apakah frekuensi kunjungan pelanggan memengaruhi sensitivitas mereka terhadap keadilan harga atau interaksi staf,