Cutting down brute-force with heuristics

This is a solution for ACM problem http://acm.tju.edu.cn/toj/showp1022.html. This seems to be a variation of the knapsack problem, where the use of dynamic programming might do the trick, but I opted for a brute-force with some heuristic to cut down the search considerably. The strategy is the following: have a list of parcels; try to fit each square into the current parcel, if the current parcel is full or if it cannot fit into the current parcel, create an extra one and repeat the process. Encapsulating the operations on the parcel within a class helps. My first implementation ran forever. Then the following hypothesis (heuristic?) made all the difference: start with the largest squares first, and if you ever find a set of parcels that fit them all, stop – that will be your minimal set. Now I can’t prove mathematically that the hypothesis is valid, but it seems intuitive and it worked for all the inputs I tried. In the end, a simple line change to go from the largest to the smallest square (instead of the other way around) made all the difference.

Program.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Packets
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] order = new int[6];
            order[0] = 0;
            order[1] = 0;
            order[2] = 4;
            order[3] = 0;
            order[4] = 0;
            order[5] = 1;
            /*
            order[0] = 7;
            order[1] = 5;
            order[2] = 1;
            order[3] = 0;
            order[4] = 0;
            order[5] = 0;
            order[0] = 20;
            order[1] = 21;
            order[2] = 22;
            order[3] = 23;
            order[4] = 24;
            order[5] = 25;
             * */
            Parcel p = new Parcel(6);
            LinkedList<Parcel> currentParcel = new LinkedList<Parcel>();
            currentParcel.AddLast(p);
            LinkedList<Parcel> bestParcel = new LinkedList<Parcel>();
            Process(6, order, currentParcel, ref bestParcel);
            Console.WriteLine("{0}", bestParcel.Count);
            Console.WriteLine();
           
            /*debug only
            int parcelIndex = 0;
            foreach (Parcel bestP in bestParcel)
            {
                Console.WriteLine("Parcel #{0}:", ++parcelIndex);
                bestP.Print();
            }
             * */
        }
        static bool Process(int maxSizeSquare,
                            int[] order,
                            LinkedList<Parcel> currentParcels,
                            ref LinkedList<Parcel> bestParcels)
        {
            if (IsOrderEmpty(order))
            {
                CheckAndCopyLists(currentParcels,
                                  ref bestParcels);
                return true;
            }
            for (int iOrder = order.Length-1; iOrder >= 0; iOrder--)
            {
                if (order[iOrder] > 0)
                {
                    bool allCurrentParcelsFull = true;
                    LinkedListNode<Parcel> nodeParcel= currentParcels.First;
                    while(nodeParcel != null)
                    {
                        Parcel p = nodeParcel.Value;
                        if (!p.IsFull)
                        {
                            bool fitsInThisParcel = false;
                            for (int r = 0; r < maxSizeSquare; r++)
                            {
                                for (int c = 0; c < maxSizeSquare; c++)
                                {
                                    if (p.CanAddSquareAtPosition(r, c, iOrder + 1))
                                    {
                                        fitsInThisParcel = true;
                                        order[iOrder]--;
                                        if (Process(maxSizeSquare, order, currentParcels, ref bestParcels))
                                        {
                                            return true;
                                        }
                                        order[iOrder]++;
                                        p.ClearSquareAtPosition(r, c, iOrder + 1);
                                    }
                                }
                            }
                            if (fitsInThisParcel)
                            {
                                allCurrentParcelsFull = false;
                            }
                        }
                        nodeParcel = nodeParcel.Next;
                    }
                    if (allCurrentParcelsFull)
                    {
                        Parcel newParcel = new Parcel(maxSizeSquare);
                        currentParcels.AddLast(newParcel);
                        newParcel = currentParcels.Last.Value;
                        for (int r = 0; r < maxSizeSquare; r++)
                        {
                            for (int c = 0; c < maxSizeSquare; c++)
                            {
                                if (newParcel.CanAddSquareAtPosition(r, c, iOrder + 1))
                                {
                                    order[iOrder]--;
                                    if (Process(maxSizeSquare, order, currentParcels, ref bestParcels))
                                    {
                                        return true;
                                    }
                                    order[iOrder]++;
                                    newParcel.ClearSquareAtPosition(r, c, iOrder + 1);
                                }
                            }
                        }
                    }
                }
            }
            return false;
        }
        static void CheckAndCopyLists(LinkedList<Parcel> list1,
                                      ref LinkedList<Parcel> list2)
        {
            if (list1 == null)
            {
                return;
            }
            if (list2 == null || list2.Count == 0 || list1.Count < list2.Count)
            {
                list2 = new LinkedList<Parcel>();
                LinkedListNode<Parcel> nodeParcel = list1.First;
                while(nodeParcel != null)
                {
                    Parcel p = new Parcel(nodeParcel.Value);
                    list2.AddLast(p);
                    nodeParcel = nodeParcel.Next;
                }
            }
        }
        static bool IsOrderEmpty(int[] order)
        {
            if (order == null)
            {
                return true;
            }
            for (int i = 0; i < order.Length; i++)
            {
                if (order[i] > 0)
                {
                    return false;
                }
            }
            return true;
        }
    }
}

Parcel.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Packets
{
    class Parcel
    {
        private int[,] square;
        private int size;
        private int remainingSquaresLeft;
        public bool IsFull
        {
            private set { }
            get
            {
                return this.remainingSquaresLeft == 0;
            }
        }
        public Parcel(Parcel p)
        {
            this.size = p.size;
            this.square = new int[size, size];
            this.remainingSquaresLeft = p.remainingSquaresLeft;
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    this.square[r, c] = p.square[r, c];
                }
            }
        }
        public Parcel(int size)
        {
            this.size = size;
            this.square = new int[size, size];
            this.remainingSquaresLeft = size * size;
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    this.square[r, c] = 0;
                }
            }
        }
        public bool CanAddSquareAtPosition(int r, int c, int squareSize)
        {
            if (this.remainingSquaresLeft < squareSize * squareSize)
            {
                return false;
            }
            for (int ir = 0; ir < squareSize; ir++)
            {
                for (int ic = 0; ic < squareSize; ic++)
                {
                    if (ir + r >= this.size ||
                        ic + c >= this.size ||
                        this.square[ir + r, ic + c] > 0)
                    {
                        return false;
                    }
                }
            }
            _MarkSquareAtPosition(r, c, squareSize, squareSize);
            return true;
        }
        public void ClearSquareAtPosition(int r, int c, int squareSize)
        {
            _MarkSquareAtPosition(r, c, squareSize, 0);
        }
        //Debug only
        public void Print()
        {
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    Console.Write("{0} ", this.square[r,c]);
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
        private void _MarkSquareAtPosition(int r, int c, int squareSize, int unit)
        {
            int squaresModified = 0;
            for (int ir = 0; ir < squareSize; ir++)
            {
                for (int ic = 0; ic < squareSize; ic++)
                {
                    if (ir + r < this.size &&
                        ic + c < this.size)
                    {
                        this.square[ir + r, ic + c] = unit;
                        squaresModified++;
                    }
                }
            }
            if (unit == 0)
            {
                this.remainingSquaresLeft += squaresModified;
            }
            else
            {
                this.remainingSquaresLeft -= squaresModified;
            }
        }
    }
}