Description
1. The 3-digit puzzle
In this assignment, you will implement a number of search algorithms to solve the 3-digit puzzle.
Given are two 3-digit numbers called (start) and (goal) and also a set of 3-digit numbers called . To solve the puzzle, we want to get from to in the smallest number of moves. A move is a transformation of one number into another number by adding or subtracting 1 to one of its digits. For example, a move can take you from 123 to 124 by adding 1 to the last digit or from 953 to 853 by subtracting 1 from the first digit. Moves must satisfy the following constraints:
-
You cannot add to the digit 9 or subtract from the digit 0;
-
You cannot make a move that transforms the current number into one of the forbidden numbers;
-
You cannot change the same digit twice in two successive moves.
Note that since the numbers have 3 digits, at the beginning there are at most 6 possible moves from . After the first move, the branching factor is at most 4, due to the constraints on the moves and especially due to constraint 3.
mcc -m -o ThreeDigits -R -nodisplay -R -nojvm ThreeDigits ./run_ThreeDigits.sh <MATLAB_install_directory> A sample.txt
Note: MATLAB must be run this way (compiled first) to speed up MATLAB running submissions. The arguments are passed to your ThreeDigits
function as strings. For example, the example above will be executed as a function call like this:
ThreeDigits(‘A’, ‘sample.txt’)
Output
You program will output two lines only. The first line will contain the solution path found from the start node to the goal node (inclusive), in the form of states separated by commas. If no path can be found with the given parameters, then the first line should be “No solution found.”.
The second line should be the order of nodes expanded during the search process, in the form of states separated by commas. If no path was found, this should still print the list of expanded nodes. Remember that this list should never exceed 1000 states (point 5 in the Tasks section).
Examples
sample.txt:
320
110
Note that the outputs of BFS and IDS here are quite long, and so the second line has wrapped. These outputs are still only two lines.
Search Method Output
320,220,210,110
BFS 320,220,420,310,330,321,210,230,221,410,430,421,210,410,
311,230,430,331,221,421,311,331,110
DFS 320,220,210,110
320,220,210,110
320,220,210,110
IDS 320,320,220,420,310,330,321,320,220,210,230,221,420,410, 430,421,310,210,410,311,330,230,430,331,321,221,421,311, 331,320,220,210,110
Greedy 320,310,210,211,111,110
320,310,210,211,111,110
|
Hill-Climbing |
No solution |
found. |
|
320,310,210 |
A* 320,220,210,110
320,310,210,220,210,110
4. Submission Details
This assignment is to be submitted electronically via the PASTA submission system.
Your submission files should be zipped together in a single .zip file and include a main program called ThreeDigits. Valid extensions are .java, .py, .c, .cpp, .cc, and .m. Zip only the submission files, not the folder – when your zip file is unzipped there should be only submission files, not a folder with submission files. Only
.zip format is accepted; do not use any other format, e.g. .rar or .7z. If your program contains only a single file, then you can just submit the file without zipping it.
Upload your submission on PASTA under Assignment 1.
Page 4 of 4
