Solver Algorithms and Tractable Subproblem Analysis of Suguru Puzzles

BUTRAHANDISYA

Informasi Dasar

47 kali
23.04.3530
518.172
Karya Ilmiah - Skripsi (S1) - Reference

This paper explores algorithmic and mathematical aspects of Suguru puzzles, a single-player pencil-and-paper puzzle introduced in 2001 and proven NP-complete in 2022. Two algorithmic approaches are presented for solving Suguru puzzles: the backtracking approach and the SAT-based approach. The backtracking approach demonstrates an asymptotic running time of (O(R \cdot (mn - H + 2)!)) for solving a Suguru puzzle of size (m \times n), (R) regions, and (H) hint cells. Furthermore, a SAT encoding of the puzzle rules into propositional formulas is proposed, where the number of variables and clauses are bounded above by (O(m^3n^3)) for an (m \times n) Suguru instance. In addition, it is proven that any Suguru puzzle of size (m \times n) with either (m = 1) or (n = 1) can be solved in linear time in terms of the puzzle size. Experimental results show that the backtracking approach is faster for solving Suguru puzzles of sizes (10 \times 10) or smaller, while the SAT-based technique is superior for solving larger puzzles.

Subjek

ALGORITHM ANALYSIS AND PROBLEM COMPLEXITY
Algorithm design-structured programming,

Katalog

Solver Algorithms and Tractable Subproblem Analysis of Suguru Puzzles
 
 
Indonesia

Sirkulasi

Rp. 0
Rp. 0
Tidak

Pengarang

BUTRAHANDISYA
Perorangan
Muhammad Arzaki, Gia Septiana Wulandari
 

Penerbit

Universitas Telkom, S1 Informatika
Bandung
2023

Koleksi

Kompetensi

  • CII2C2 - ANALISIS KOMPLEKSITAS ALGORITMA
  • CII2K3 - STRATEGI ALGORITMA

Download / Flippingbook

 

Ulasan

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