Design and Analysis of Algorithmic Approach for Solving Juosan Puzzles and Their Variants - Dalam bentuk pengganti sidang - Artikel Jurnal
MUHAMMAD TSAQIF AMMAR

Informasi Umum

Kode

23.04.6675

Klasifikasi

518.1 - Algorithms

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Algorithm Analysis And Problem Complexity

Dilihat

26 kali

Informasi Lainnya

Abstraksi

<p>This final project investigates several algorithmic and mathematical aspects of the Juosan puzzle--- a one-player pencil-and-paper puzzle introduced in 2014 and proven NP-complete in 2018. In this paper, two approaches are introduced to solving this puzzle. The first approach is a backtracking technique optimized by considering invalid subgrid configurations, capable of solving any Juosan instance of size m x n in O(2^{mn}) time. Furthermore, a SAT-based approach is proposed, which involves efficiently encoding the puzzle rules into propositional formulas for a SAT solver. This final project shows that an m x n Juosan puzzles can be encoded to propositional formulas in CNF with O(m^2n^2) clauses and variables. Through comparative experiments, the results indicate that the backtracking technique excels for small puzzles (up to 144 cells), while the SAT-based approach is efficient for larger puzzles (e.g., 1350 cells in <1 second). Additionally, this paper investigates special cases of Juosan puzzles, namely those without numerical constraints and puzzles with dimensions m x n, where either m or n is less than 3. It is shown that these particular puzzles are solvable in polynomial time relative to their size. Furthermore, this final project establishes an upper bound on the number of solutions for Juosan puzzles of size 1 x n.</p>

• CII2C2 - ANALISIS KOMPLEKSITAS ALGORITMA
• CII1B3 - LOGIKA MATEMATIKA
• CII1G3 - MATEMATIKA DISKRIT
• CII2K3 - STRATEGI ALGORITMA

Koleksi & Sirkulasi

Tersedia 1 dari total 1 Koleksi

Pengarang

Penerbit

Sirkulasi

Download / Flippingbook