I am trying to write an algorithm to solve the following problem.
Let’s say we have n buckets each with capacity 4. There would be exactly n-2 type of objects. The initial state being that the (n-2)*4 objects are randomly distributed among n-2 objects with exactly two empty buckets. The desired end state we are trying to reach is to group similar type of objects into a single bucket.
Only the following operation are permitted
- Move object from top of bucket to an empty bucket or a bucket having same type of object on top.
Constraints
- The buckets can never exceed the capacity of 4.
- We cannot partially transfer the objects of similar type as long as there is capacity.
I am trying to code how to find the sequence of operations to reach the desired end state.
Example
Bucket 1: C B A Bucket 2: A B C Bucket 3: A B C Bucket 4: Bucket 5: Move C from bucket 2,3 to 4 (two steps) Move B from bucket 2,3 to 5 (two steps) Bucket 1: C B A Bucket 2: A Bucket 3: A Bucket 4: C C Bucket 5: B B Move A from bucket 1 to 2 Move A from bucket 3 to 2 Bucket 1: C B Bucket 2: A A A Bucket 3: Bucket 4: C C Bucket 5: B B Move B from Bucket 1 to 5 Move C from Bucket 1 to 4 Bucket 1: Bucket 2: A A A Bucket 3: Bucket 4: C C C Bucket 5: B B B
I was thinking of solving it by backtracking. Trying to move the top of bucket to another bucket backtrack if there are no possible moves.
Is there a better approach to solve this problem more efficiently.