Home

First part

Specification (what you need to do): You will build a computer program in C++ to demonstrate strategies for simulating a variation of the 15-Puzzle problem

The rules governing the simulation There is space for 16 blocks to be placed together in a square Only 15 blocks are present and are labelled with numbers (e.g., 1 - 15 in diagram) A “move” is represented as placing a block adjacent to the space into the space A “turn” is a number of “moves” with the space ending up in the bottom right corner A “turn” is shown in the diagram A starting position ensures the space is always located in the bottom right hand corner After a “turn” there will be a number of blocks that are “continuous” Continuous row = numbers incremented by 1 from left to right for each column that has a block in it All the rows are continuous in the first configuration of blocks in the diagram Continuous column = numbers incremented by 1 from top to bottom for each column that has a block in it No columns are continuous in any of the configurations in the diagram Reverse continuous row = numbers incremented by 1 from right to left for each row that has a block in it There exists no reverse continuous rows in any of the configurations in the diagram Reverse continuous column = numbers incremented from bottom to top for each column that has a block in it There exists no reverse continuous columns in any of the configurations in the diagram Blocks can be labelled with numbers 1 through to 20 with no one block sharing the same number with any other block in the same configuration

The requirements Create a program that will allow a user to manually type in a 15-puzzle configuration using numbers 1 through 20 (inclusive) Make sure not to allow repeated numbers for the blocks Create a program that will create 15-Puzzle configurations using numbers 1 through 20 (inclusive) in a pseudo random way The number of these configurations can be chosen by the user Produce a text file (the 15-File) that stores 15-Puzzle configurations that your program generates Text file format should start with a single number (indicating the number of 15-Puzzle squares) followed by the squares themselves (see below). Block labels should be separated by a space and each row should be on a new line

2 1 2 3 4 5 6 7 8 9 10 11 12 13 20 15

1 3 2 4 5 6 7 8 9 10 11 12 13 20 15

Allow your program to read in a file (the 15-File) and deduce how many continuous rows, continuous columns, reverse continuous rows and reverse continuous columns are possible for all turns from the given configuration and print this to screen

1 1 2 3 4 5 6 7 8 9 10 11 12 13 20 15 row = 2302 column = 2344 reverse row = 2341 reverse column = 2341

Allow your program to output its findings to a text file (the Solution-File) shown using the format above Compare your results with your friends and colleagues in class to ensure your program is correct Read in the 15-Puzzle files of your colleagues and check their answers against your own (Solution-Files) (the numbers shown here in this document may be indicative only and not a true representation of an accurate solution)

Second Part

Specification (what you need to do): You will extend your computer program from coursework 1 to demonstrate strategies for simulating advanced features of the 15-Puzzle problem

Additional rules governing the simulation Include all the rules from coursework 1 Partial continuous denoted with a constant numeric value indicates a shortened validity for orderings. For example, there are 11 2-partial continuous row orderings for the first configuration in the diagram from coursework 1 (repeated here for your convenience)

The Requirements Using a method of your choice, extend your solution from coursework 1 to identify all 3-partial continuous row and 3-partial continuous column (including reverse) in any given 15-Puzzle configuration Extend your solution to identify all 3-partial continuous row and 3-partial continuous column (including reverse) in all reachable 15-Puzzle configurations using valid “turns” from any given valid 15-Puzzle configuration Ensuring your user interface still allows manual and random 15-Puzzle generation, extend your interface to allow a user to request the finding of either 2, 3, or 4 -partial continuous row/column (including reverse) in any given 15-Puzzle configuration (as requested by a user - random or manual) Allow your user to request the finding of 2, 3, or 4 -partial continuous column/row (including reverse) 15-Puzzle configurations reachable using valid “turns” from any given valid 15-Puzzle configuration Enhance your Solution-File to add the values for partial continuous solutions (the numbers shown here may be indicative only and not a true representation of an accurate solution):

2 1 2 3 4 5 6 7 8 9 10 11 12 13 20 15 row = 2302 column = 2344 reverse row = 2341 reverse column = 2341 (total for row & column, including reverse, in this configuration) 2 = 22 3 = 14 4 = 8 (total for row and column, including reverse, for all valid turns) 2 = 235223 3 = 34563 4 = 456

Check your solution for correctness with friends and colleagues in the class Update your solution to allow the user to specify the size of the 15-Puzzle problem (e.g., 25-Puzzle, 36-Puzzle, 49-Puzzle)