Project 3 - Sliding Puzzle

Introduction

For this project you will need to implement a number of functions in OCaml that together can be used to find solutions for a sliding puzzle. This project will provide experience dealing with recursion, lists, and higher order functions, as well OCaml's type inference system.

Sliding Puzzle

A sliding puzzle (or n-puzzle) is consists of a frame of numbered square tiles in random order with one tile missing. Tiles adjacent to the space may be moved into the space, rearranging tiles until the tiles are all in order.

For this project we represent the tiles in a sliding puzzle as numbers in a list, with 0 as the space. We'll assume all puzzles are square. For this project we'll assume a puzzle is solved when the space is in the top left corner of the puzzle, with tile numbers sorted in order from left to right and top to bottom.

Positions in the 2-D puzzle are linearized to a 1-D list so that rows are contiguous (row-major). For instance, the following solved 3x3 puzzle is linearized as [0;1;2;3;4;5;6;7;8].

	1	2
3	4	5
6	7	8

In other words, the x,y coordinates of a position in the n-puzzle are assigned as follows:

(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)

=

(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)

=

0 1 2 3 4 5 6 7 8

Getting Started

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

• Your OCaml program - puzzle.ml
• Test utilities - testUtils.ml
• Public tests
  • testRecursion1.ml
  • testRecursion2.ml
  • testHigherOrder1.ml
  • testPuzzle1.ml
  • testPuzzle2.ml
  • testSolve1.ml
• Expected outputs for public tests
  • testRecursion1.out
  • testRecursion2.out
  • testHigherOrder1.out
  • testPuzzle1.out
  • testPuzzle2.out
  • testSolve1.out
• Ruby script to run public tests- goTest.rb

You may use functions from testUtils.ml for printing debugging messages, but do not modify the file. Your actual submission should not print any output.

To test your utility functions and puzzle solver implementation, you can execute the public tests from the command line by typing commands like ocaml testRecursion1.ml.

The puzzle.ml file you downloaded contains a number of utility functions, and comments describing the functions you are required to implement.

Note that you must implement your functions with the exact parameter and return type specified, or else the submit server tests will fail.

In general just assume your code will be invoked only for legal inputs (though note "index (x,v)" not finding v in x and returning -1 is considered to be legal). We haven't reached how OCaml can throw exceptions yet.

For this project the only OCaml libraries you are allowed to use are those defined in the Pervasives module loaded by default. You are not allowed to use library functions found in any other modules, particularly List and Array.

Part 1: Recursion

Name	Type	Return value	Example
get_val (x, n)	int list * int -> int	element of list x at index n -1 if not found elements	get_val ([5;6;7;3],1) => 6
get_vals (x, y)	int list * int list -> int list	list of elements of list x at indices in list y, [] if none found elements must be returned in order listed in y	get_vals ([5;6;7;3],[2;0]) => [7;5]
set_n (x, n, v)	'a list * int * 'a -> 'a list	list produced by setting n'th element of list x to value v no effect if n out of range of list	set_n ([5;6;7;3],1,9) => [5;9;7;3]
list_swap_val (b, u, v)	'a list * 'a * 'a -> 'a list	list b with values u,v swapped change value of multiple occurrences of u and/or v, if found change value for u even if v not found in list, and vice versa	list_swap_val ([5;6;7;3],7,5) => [7;6;5;3]
index (x, v)	'a list * 'a -> int	index of value v in list x -1 if not found	index ([5;6;7;3],7) => 2
uniq x	'a list -> 'a list	list of uniq elements in x order of unique elements does not matter	uniq [5;6;5;3] => [6;5;3]
find_new (x, y)	'a list * 'a list -> 'a list	list of members of list x not found in list y maintain relative order of new elements in result	find_new ([4;3;7],[5;6;5;3]) => [4;7]
is_sorted x	'a list -> bool	true if elements in x are in sorted order, false otherwise return true for []	is_sorted ([5;5;7;9]) => true

Part 2: Higher order functions

Name	Type	Return value	Example
grow_lists (x, y)	'a list * 'a list -> 'a list list	given list of elements x and list y, prepend every element of x to y resulting lists must be in same order as in x	grow_lists ([1;2], [3;4]) => [[1;3;4]; [2;3;4]]
concat_lists x	'a list list -> 'a list	given list of lists x, return list of concatenated lists in x note just top level of lists is concatenated, unlike List.flatten	concat_lists [[1;2];[7];[5;4;3]] => [1;2;7;5;4;3]

Part 3: Puzzle functions

Write the following helper functions for the puzzle solver:

Name	Type	Return value	Example
find_board_size b	'a list -> int	size of board b, assuming board is square, given b as a list of elements	find_board_size [1;0;2;3;4;5;6;7;8] => 3
pos_of_xy (x, y, s)	int * int * int -> int	position of x, y coordinate in board of size s may assume (x,y) is a legal coordinate	pos_of_xy (1, 2, 3) => 5
xy_of_pos (p, s)	int * int -> int * int	x, y coordinate of position p in board of size s may assume p is a legal position between 0..s-1	xy_of_pos (5, 3) => (1, 2)
move_pos b	int list -> int list	list of positions in board (in order) that can move to space in board positions must be in sorted order, from smallest to largest	move_pos [0;1;2;3;4;5;6;7;8] => [1;3]
make_move (b,x)	int list * int -> int list	configuration of board after moving number at position x to space may assume position x is adjacent to space	make_move ([0;1;4;5;2;3;6;7;8], 3) => [5;1;4;0;2;3;6;7;8]
make_moves b	int list -> int list list	boards produced after all possible 1-step moves for board b boards must be in sorted order, with space in smallest position to largest	make_move [0;1;2;3;4;5;6;7;8] => [[1;0;2;3;4;5;6;7;8];[3;1;2;0;4;5;6;7;8]]

Part 4: Puzzle solver

Write the following function for solving a sliding puzzle. Your solution must be efficient enough to solve 4x4 puzzles under 10 moves within 3 seconds on the submit server.

Name	Type	Return value	Example
solve_board (x,n)	int list * int -> int list list list	given board x, return all solutions (list of boards from solved board to x) within n moves, or [] if none exists, must eliminate all solutions with duplicate board positions (in same solution), order of possible solutions does not matter	solve_board ([1;2;0;3;4;5;6;7;8],3) => [[[0;1;2;3;4;5;6;7;8];[1;0;2;3;4;5;6;7;8];[1;2;0;3;4;5;6;7;8]]]

Submission

• Submit your puzzle.ml file directly to the submit server by clicking on the submit link in the column "web submission".

  

  Next, use the submit dialog to submit your puzzle.ml file directly.

  

  Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file. Some students have mentioned problems with using Internet Explorer, because submissions being extracted in directories (e.g., "C:\My Documents\330\puzzle.ml") where the submit server could not find them. The problems went away when switching to the Mozilla Firefox browser.

• Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p3.zip, To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:
  java -jar submit.jar

  You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

  Successful submission # received for project 3

Hints and Tips