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

MUHAMMAD TSAQIF AMMAR

Informasi Dasar

146 kali
23.04.6675
518.1
Karya Ilmiah - Skripsi (S1) - Reference

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.

Subjek

ALGORITHM ANALYSIS AND PROBLEM COMPLEXITY
 

Katalog

Design and Analysis of Algorithmic Approach for Solving Juosan Puzzles and Their Variants - Dalam bentuk pengganti sidang - Artikel Jurnal
 
p.: il,; pdf file
inggris

Sirkulasi

Rp. 0
Rp. 0
Tidak

Pengarang

MUHAMMAD TSAQIF AMMAR
Perorangan
Muhammad Arzaki, Gia Septiana Wulandari
 

Penerbit

Universitas Telkom, S1 Informatika
Bandung
2023

Koleksi

Kompetensi

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

Download / Flippingbook

 

Ulasan

Belum ada ulasan yang diberikan
anda harus sign-in untuk memberikan ulasan ke katalog ini