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 combination of Markov Switching and Asymmetric Generalized Seasonal Autoregressive Moving Average Conditional Heteroscedasticity (MS-AGSARMACH) modelsThe combination of Markov Switching and Asymmetric Generalized Seasonal Autoregressive Moving Average Conditional Heteroscedasticity (MS-AGSARMACH) models
SEMINAR IDSEMINAR ID Metode stepping stone digunakan untuk mendapatkan solusi optimal dalam menyelesaikan masalah transportasi (biaya total minimum), dengan pendekatan trialMetode stepping stone digunakan untuk mendapatkan solusi optimal dalam menyelesaikan masalah transportasi (biaya total minimum), dengan pendekatan trial
UPN VeteranUPN Veteran Penelitian ini menggunakan metode kualitatif dengan pendekatan deskriptif analitis. Hasil penelitian menunjukkan bahwa adopsi sistem pembayaran digitalPenelitian ini menggunakan metode kualitatif dengan pendekatan deskriptif analitis. Hasil penelitian menunjukkan bahwa adopsi sistem pembayaran digital
UPN VeteranUPN Veteran Untuk menjaga keberlanjutan dan mengoptimalkan peran sektor-sektor ini, khususnya perikanan, Pemerintah perlu mendorong perlindungan ekosistem laut dariUntuk menjaga keberlanjutan dan mengoptimalkan peran sektor-sektor ini, khususnya perikanan, Pemerintah perlu mendorong perlindungan ekosistem laut dari
ITSITS In this study, the best ARIMA (1,1,1) model was obtained with a MAPE value of 13.2082%. From the residuals of the ARIMA (1,1,1) model, there were signsIn this study, the best ARIMA (1,1,1) model was obtained with a MAPE value of 13.2082%. From the residuals of the ARIMA (1,1,1) model, there were signs
ITSITS In this case, what is meant by bi-edge metric and edge detour. If there is a set in G that causes every edge in G has a different bi-edge metric representationIn this case, what is meant by bi-edge metric and edge detour. If there is a set in G that causes every edge in G has a different bi-edge metric representation
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
UGMUGM Untuk pengembalian IDR/AUD dan IDR/SGD, estimasi parameter menunjukkan korelasi negatif dan signifikan antara pengembalian dan varian bersyaratnya. BerdasarkanUntuk pengembalian IDR/AUD dan IDR/SGD, estimasi parameter menunjukkan korelasi negatif dan signifikan antara pengembalian dan varian bersyaratnya. Berdasarkan
Useful /
UPN VeteranUPN Veteran Penelitian ini menunjukkan bahwa terdapat hubungan signifikan antara kesehatan BPR dan kepercayaan masyarakat, yang tercermin dalam Dana Pihak Ketiga (DPK).Penelitian ini menunjukkan bahwa terdapat hubungan signifikan antara kesehatan BPR dan kepercayaan masyarakat, yang tercermin dalam Dana Pihak Ketiga (DPK).
UIN SGDUIN SGD Faktor yang melatarbelakangi terjadinya interferensi bahasa pada santriwati tingkat SMA Pondok pesantren Darurrahmah di antaranya adalah para santriwatiFaktor yang melatarbelakangi terjadinya interferensi bahasa pada santriwati tingkat SMA Pondok pesantren Darurrahmah di antaranya adalah para santriwati
UPN VeteranUPN Veteran Bonus demografi secara parsial berpengaruh negatif namun tidak signifikan terhadap tingkat kemiskinan di Gerbangkertosusila selama tahun 2017–2020. IPMBonus demografi secara parsial berpengaruh negatif namun tidak signifikan terhadap tingkat kemiskinan di Gerbangkertosusila selama tahun 2017–2020. IPM
UGMUGM The results reveal that career advancement, job characteristics and subjective norms are positively and significantly related to knowledge sharing behavior.The results reveal that career advancement, job characteristics and subjective norms are positively and significantly related to knowledge sharing behavior.