NPuzzle Problem In Java, Lisp & Prolog

Essay by chinweiUniversity, Bachelor'sA-, November 2004

download word file, 18 pages 3.7

ABSTRACT

The well known N-puzzle problem consists of a square board containing N square tiles and an empty position called the "blank". Authorized operations like up, down, left and right slide any tile adjacent to the blank into the blank position. The task is to rearrange the tiles from some random initial configuration into a particular designed goal configuration. A* search is used to solve the N-puzzle in this paper. This application has been implemented in three different kinds of programming languages which are the Object-oriented, functional and logic programming languages. Java(JDK1.3.1), Lisp(Corman Lisp 2.0) and Prolog(SWI-Prolog version 5.0.9) are the versions of each of the chosen languages. A brief introduction of each programming language is given. The structure of this paper is as follows. A short introduction for each of the chosen programming language. Then an explanation is given on a few of the main variables used in the programs.

This is followed by the advantages and disadvantages of using the chosen languages for the application. And finally, a short conclusion to wrap the paper up.

1. INTRODUCTION

1.1 The N-Puzzle Problem

The well known N-puzzle problem consists of a square board containing N square tiles and an empty position called the "blank". Authorized operations like up, down, left and right slide any tile adjacent to the blank into the blank position. The task is to rearrange the tiles from some random initial configuration into a particular designed goal configuration. A* search is used to solve the N-puzzle in this paper. A* search is optimal. So, we can find the smallest number of steps from the initial state to the goal state.

Evaluation function, f(n) = g(n) + h(n)

g(n) = cost so far to reach n

h(n) = estimated cost from n to goal

= number of misplaced...