Perbandingan Answer Set Programming dan Iterative Deepening Search dalam Menyelesaikan Game N-puzzle

Abstract

N-puzzle is one of the known NP-complete problems in the field of puzzles and games. The purpose of N-puzzle is to arrange numbers from 1 to (n2-1) in an n x n grid, with one grid contains a blank square. The research aims to compare the use of Answer Set Programming (ASP), as one of the currently used formalism to express and solve hard computational problems, with the traditional Iterative Deepening Search (IDS) in solving the N-puzzle. An encoding of N-puzzle problem and solver was devised and executed using the DLV system, while IDS is implemented as an ad-hoc program solving the N-puzzle problem. The result of experiment shows that the ASP using DLV is more effective in finding solutions, because it requires no depth parameters to find solutions, while IDS does. On the other hand, the IDS implementation was more efficient in terms of execution time.