Title :
A Tabled Prolog Program for Solving Sokoban
Author :
Neng-Fa Zhou ; Dovier, A.
Author_Institution :
Dept. of Comput. & Inf. Sci., CUNY Brooklyn Coll. & Grad. Center, Brooklyn, NY, USA
Abstract :
This paper presents our program in B-Prolog submitted to the third ASP solver competition for the Sokoban problem. This program, based on dynamic programming, treats Sokoban as a generalized shortest path problem. It divides a problem into independent sub problems and uses tabling to store sub problems and their answers. This program is very simple but quite efficient. Without use of any sophisticated domain knowledge, it easily solved 11 of the 15 instances used in the competition.
Keywords :
PROLOG; computational complexity; dynamic programming; search problems; ASP solver competition; B-Prolog; Sokoban problem; dynamic programming; generalized shortest path problem; tabled Prolog program; Benchmark testing; Conferences; Dynamic programming; Information science; Programming; Shortest path problem; System recovery; Dynamic programming; Prolog; Tabling; Th Sokoban puzzle;
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2011 23rd IEEE International Conference on
Conference_Location :
Boca Raton, FL
Print_ISBN :
978-1-4577-2068-0
Electronic_ISBN :
1082-3409
DOI :
10.1109/ICTAI.2011.145
