Part A is about exhaustive search, part B is about breadth first search. You'll find at the bottom of the page links to the document versions of the questions (since I had minor problems with presenting the questions properly on this page. The document versions are exact), as well as my solutions in Java. My programs work, but I don't guarantee anything.

Enjoy!!!

Part A> Exhaustive Search:

Given N integers and a target integer V, write a program to find in how many ways we can arrange these integers into a sequence X(1)X(2)…X(N) such that the summation (i -> N) of iX(i) = V.

For example, Let N=3, V=25 and the integers be 3, 4 and 5 then there is 1 solution which is 4 3 5 since 4*1 + 3*2 + 5*3 = 25.

Solve this problem by checking all the permutations of the N integers.

(Bonus) Given N integers, write a program to find in how many ways can these integers be partitioned into 2 parts such that the sum of the elements of the 2 parts are equal.

Solve this problem by generating all possible cases in a systematic way.

Part B> Breadth first search: A 2D Rubik’s Square!

Initial State                                                                                                               Default Goal State

 Any row or column of a 4 by 4 square grid can be reversed. This is the only rule of the Rubik’s Square Puzzle.

This puzzle is solved if a series of operations of the form: Reverse [Row or Column] N is found that transfers a certain initial state to the default goal state (shown above at the right).    For example, the solution of the initial state shown above at the left is:
Reverse Column 2 – Reverse Row 1.

Write a program that constructs the search tree and applies breadth first search until the final state is found. State the maximum depth that can be reached in your experiments.

Hint: The nodes of the search tree should not have any children fields. Instead, it should have a parent field, where the parent of the root is Nil.

Here is an example of a 1-level search tree on a 2 by 2 square:
(however, your program should work on a 4 by 4 square)                              

                                                                                                                               
                                                                                                                   
                                                                                                                          Initial State
                                                                                                              Nil       (The Root)

                                                                                                             A  D
                                                                                                             B  C

                                                          D A               A D           B D                       A C 
                                                          B C               C B           A C                       B D

My Programs:-

Home | My Work | Links | Photo Gallery | About Me | Sign Guest Book | View Guest Book

This site was last updated Sunday March 23, 2003