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 /
ITSITS The first group (brown) is influenced by the percentage of women who give birth with the assistance of health workers (X1) and the female Human DevelopmentThe first group (brown) is influenced by the percentage of women who give birth with the assistance of health workers (X1) and the female Human Development
ITSITS Searching all possible solution and finding the minimum number of clues to make uniquely solvable puzzle always been a natural question for puzzle enthusiast.Searching all possible solution and finding the minimum number of clues to make uniquely solvable puzzle always been a natural question for puzzle enthusiast.
ITSITS From the residuals of the ARIMA (1,1,1) model, there were signs of heteroscedasticity, so the GARCH model with the best GARCH (0,1) model was used. InFrom the residuals of the ARIMA (1,1,1) model, there were signs of heteroscedasticity, so the GARCH model with the best GARCH (0,1) model was used. In
ITSITS Graf triple idempoten dari cincin Zn adalah graf terhubung jika n adalah bilangan prima dan n ≥ 7. Hal ini dibuktikan dengan menggunakan dua kasus. pertama,Graf triple idempoten dari cincin Zn adalah graf terhubung jika n adalah bilangan prima dan n ≥ 7. Hal ini dibuktikan dengan menggunakan dua kasus. pertama,
ITSITS From this research, the exact values of a bi-edge metric dimension are obtained for several special graphs, namely cycle, complete, star and path. BasedFrom this research, the exact values of a bi-edge metric dimension are obtained for several special graphs, namely cycle, complete, star and path. Based
ITSITS Graphical simulations of drug concentration versus time are also performed in this article to view not only the dynamics of drug delivery in the body,Graphical simulations of drug concentration versus time are also performed in this article to view not only the dynamics of drug delivery in the body,
ITSITS The research derives control signals and update schemes that ensure the stability of the closed-loop NCS even in the presence of DoS attacks, providingThe research derives control signals and update schemes that ensure the stability of the closed-loop NCS even in the presence of DoS attacks, providing
UBUB Melalui pemodelan matematis, dampak sistem pemeliharaan ini dapat disimulasikan. Berdasarkan analisis model, ditentukan bahwa maksimal 15% anjing peliharaanMelalui pemodelan matematis, dampak sistem pemeliharaan ini dapat disimulasikan. Berdasarkan analisis model, ditentukan bahwa maksimal 15% anjing peliharaan
Useful /
ALSHOBARALSHOBAR Negara berperan penting dalam mengintegrasikan kedua sistem hukum ini ke dalam hukum formal, menciptakan formulasi hukum yang mencerminkan nilai-nilaiNegara berperan penting dalam mengintegrasikan kedua sistem hukum ini ke dalam hukum formal, menciptakan formulasi hukum yang mencerminkan nilai-nilai
UNRUNR Namun, di tingkat daerah, pemanfaatan layanan digital ini belum berjalan secara maksimal karena masih terdapat kesenjangan kemampuan digital (digital divide)Namun, di tingkat daerah, pemanfaatan layanan digital ini belum berjalan secara maksimal karena masih terdapat kesenjangan kemampuan digital (digital divide)
ITSITS It is found that all materials in group-IV are topological insulators. The evaluation of Z2 invariant v in group-V found that the phosphorene and bismutheneIt is found that all materials in group-IV are topological insulators. The evaluation of Z2 invariant v in group-V found that the phosphorene and bismuthene
UBUB The study successfully developed a mathematical model of COVID-19 transmission incorporating the role of viruses in the environment. The model identifiedThe study successfully developed a mathematical model of COVID-19 transmission incorporating the role of viruses in the environment. The model identified