CMSC 330, Spring 2015

Organization of Programming Languages

Project 3 - Sliding Puzzle

Due 11:59pm Monday, March 30th, 2015

Errata

This version of the project now includes these corrections.

  1. 3/15
    • You do not have to implement set_n function. (Older version of puzzle.ml has an entry for set_n)
    • In function pos_of_xy, the example in comments was wrong.
    • It should be: pos_of_xy (2, 1) 3 => 5
    • In function pos_of_xy, the example in comments was wrong.
    • It should be: xy_of_pos 5 3 => (2, 1)
  2. 3/18: The type for remove in the comments of puzzle.ml was too specific; the type on the web page was the correct one.
  3. 3/20: The .submit file in p3.zip was incorrect. You can download just this file (replace the one in your p3/ directory): .submit

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) 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) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)
=
(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2)
=
0 1 2 3 4 5 6 7 8

Importantly: Notice that the origin (0,0) is in the upper left, and the coordinate pair (x,y) indicates the position x moves right and y moves to the down of the origin. If you don't follow this arrangement, some of your position functions below will produce the wrong answers.

Getting Started

Download the following archive file p3.zip and extract its contents.

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

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. In fact, you will need at least a couple of functions found here. You are not allowed to use library functions found in any other modules, particularly List and Array.

Part 1: Recursion

Write the following recursive functions:

Name Type Return value Example
get_val x n int list -> int -> int element of list x at index n (indexes start at 0)
-1 if n is outside the bounds of the list
get_val [5;6;7;3] 1 => 6
get_val [5;6;7;3] 4 =>-1
get_vals x y int list -> int list -> int list list of elements of list x at indexes in list y,
[] if any indexes in y are outside the bounds of x
elements must be returned in order listed in y
get_vals [5;6;7;3] [2;0] => [7;5]
get_vals [5;6;7;3] [2;4] => [ ]
distinct x 'a list -> 'a list list produced by removing all non-unique elements from list x
order of non-unique elements does not matter
Maintain relative order of elements in result.
distinct [5;6;7;3;7;5] => [6;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]
list_swap_val [5;6;3] 7 5 => [7;6;3]
index x v 'a list -> 'a -> int index of first occurrence of value v in list x
(indexes start at 0)
-1 if not found
index [5;6;7;3;7] 7 => 2
index [5;6;7;3;7] 8 => -1
remove x y 'a list -> int list -> 'a list list x after its elements at indexes in list y are removed.
Ignore indexes that are out of range.
remove [5;6;5;3;4] [0;2;3] => [6;4]
remove [5;6;5;3;4] [0;2;3;7] => [6;4]
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 elements in result
find_new [4;3;7] [5;6;5;3] => [4;7]
find_new [5;6;5;3] [4;3;7] => [5;6;5]
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
is_sorted [9;7;5] => false

Hint: The OCaml comparison functions (=,<=,>=,<, and >) are polymorphic, so you can give them any two arguments of the same type.

Part 2: Higher order functions

Write the following functions using the versions of map and/or fold provided in puzzle.ml:

Name Type Return value Example
grow_lists x y 'a list -> 'a list -> 'a list list a list of lists, where each element of x is prepended 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 a list consisting of the lists in x concatenated together
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]
concat_lists [[[1;2;3];[2]];[[7]]] => [[1;2;3];[2];[7]]

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 (that is, the length/width of a side) of board b represented as a list find_board_size [1;0;2;3;4;5;6;7;8] => 3
pos_of_xy (x, y) s (int * int) -> int -> int index of x, y coordinate in a list representing a board of size s
return -1 if x or y is out of bounds (i.e., less than 0 or greater than s^2-1)
pos_of_xy (2, 1) 3 => 5
xy_of_pos p s int -> int -> (int * int) x, y coordinate of index p in a list representing a board of size s
may assume p is a legal position between 0..(s^2-1)
xy_of_pos 5 3 => (2, 1)
move_pos b int list -> int list list of positions in board that can move to space in board
positions must be in sorted order, from smallest to largest
move_pos [0;8;7;6;5;4;3;2;1] => [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_moves [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]]
single_move x int list list list -> int list list list given list of list of boards, return list of list of boards with moves
from the head of list prepended to each list of boards, creating
multiple lists of boards if multiple moves are possible.
single_move [[[0;1;2;3]]] =>
[[[1;0;2;3];[0;1;2;3]];
[[2;1;0;3];[0;1;2;3]]]

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 (we will also test it on larger puzzles/solutions).

Name Type Return value Example
solve_board b n int list -> int -> int list list list return all solutions (see below) of board b
having length n or less, or [] if none exist.
The order of possible solutions does not matter
solve_board [1;2;0;3;4;5;6;7;8] 2 =>
[[[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]]]

A solution to solve_board is a list of boards produced by moves starting from b until the solved board is reached. The list is in reverse order: solved board first, b last. The length l of each solution is the number of moves (i.e., one less than the length of the list that represents the solution). Solutions are not permitted to contain the same intermediate board twice. For example, [[[0;1;2;3;4;5;6;7;8];[1;0;2;3;4;5;6;7;8];[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]]] is not a legal length-4 solution to [1;2;0;3;4;5;6;7;8].

Hints for solve_board: as you are required to produce all solutions up to length n, you are essentially doing an exhaustive search with a bit of smarts to prune out paths containing duplicate boards. That is, at each step you will want to enumerate all possible boards produced by legal moves from the current board of each path produced by prior steps. You will prune out paths that would be produced by repeating a previous board position. You should be making good use of the functions you have already defined above. If your solution is not using many of these functions, you are doing too much work!

Submission

You can submit your project in two ways:
  • 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

  • Be sure you have read and understand the project grading policies in the course syllabus. Do this well in advance of the project due date.

    Academic Integrity

    The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

    Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.

    Copyright Notice

    This course project is copyright of Dr. Michael Hicks. ©Michael Hicks [2015]. All rights reserved. Any redistribution or reproduction of part or all of the contents in any form is prohibited without the express consent of the author.

  • Web Accessibility