Best way to performance permutations

Question

This has been my white whale for a while, the idea is convert all the symbols to the goal symbol using all the pieces.

I did an algorithm like 5 years ago (now is lost) and reach lvl 48 but got stuck here and drop. After I watch The Imitation Game and see how Turin solve enigma using a Heil Hitler to reduce the space search I decide give it a second try.

I try solve row by row. First you have to see how many flips each row need and then found a set of pieces with enough squares to flip all symbols or a multiple of the symbol cycle (in this case 3)

In the orginal version when I found a set I try to place the pieces on each column to see if can solve the row if that happen then can go to the next row. Now I dont try to solve it but directly try to go to the next row with less pieces. Not sure what is the best aproach.

With those 18 pieces you 6.5E25 combinations to place them on the board (consider engima machine has 15E18). But if you try to solve only the flips on the first row you have 2^18 = 262k set combinations, of those only 84k has the correct amount of flips. That is the biggest prunning I could found.

My hope is there is some algorithm to allow me reduce even more the search space or some optimization I can use to improve the search speed.

How I model the problem:

First I define pieces/shape as an array of how many flips can the piece do for each row. So the first piece (the one looking like a sail boat) has 2 flips in 1st, 2nd and 3rd row. The second piece (machine gun) has 2 flips on 1st row, 4 on second row and 1 on 3rd and 4th.

I convert the board to number of flips for each row. The crown need 2 flips to reach sword (goal) cups need one flip.

I assign to each piece an ID = 2^0, 2^1, 2^2, 2^3, ..... 2^18

Here is the prunning I came with. I create set of pieces (in total you have 2^18 = 265k combinations of pieces) where the sum of flips on the pieces match the number of flips for the row.

Is possible you can have a solution with the right amount of flips but there isnt possible place them on the board in a way to reach goal for all the row. That testing should be done in a later process rigth now just try to discard solution doesnt even have the right amount of flips.

Of course if you use 0 pieces you can't solve 1st row, and if you use all the pieces on 1st row you wont have pieces to solve the bottom rows.

So lets analyze 1st row: You need a solution with at least 6 flips or (6 + 3*x) flips. If you spend one extra flip on a sword that become crown and then need 2 more to return to sword.

One possible combination with 6 flips is {5,6,9}:

But those pieces can't reach the first crown on the row. One posible solution using pieces {1,3,4}

With the first piece convert the 2 crowns to cups and with the other 2 form a line to convert all 4 to swords. In this case my solution now has id = 2^0 + 2^3 + 2^4 = 25

Now we start looking the second row we need 7 flips, but from previous solution we already have 7 flips beign apply to second row so now we start looking for solution for the second row need to have 0 flips or 3*x flips.

I keep adding pieces to each row until I "flip solve" each row. If i reach last row, use all pieces and every row has the right amount of flips then I proced to test each position. ( I didnt reach this point )

Now another filter is if are trying to solve the 6th row and you realize you havent place the 2nd piece (heigh = 4) you know wont be a valid solution because you wont be able to place that piece.

If want you can see the game in action here: http://www.neopets.com/medieval/shapeshifter.phtml, need create an user first levels doesnt even need a program you can solve by hand.

Shape

[Serializable()]
public class Shape : ICloneable
{
    public int Height { get; set; }
    public int Width { get; set; } // I will use Width to test by column later
    public int[] Changes { get; set; } // How many flips 
    public long Id { get; set; }
    public int RowPosition { get; set; } // In what Row Im using the piece
    public int MaxRow { get; set; } // What is the last row where can fit 

    public Shape(double id, int[] piece, int height)
    {
        Changes = piece;
        Height = height;
        Id = (long)id;
        RowPosition = -1;
        MaxRow = 8 - height;
    }

    public object Clone()
    {
        return this.MemberwiseClone();
    }
}

Solution

[Serializable()]
public class Solution : ICloneable
{
    private readonly int[] Game = new int[8] { 3, 8, 6, 7, 7, 8, 9, 7 };
    public List<Shape> Pieces { get; set; }
    public long Id { get; set; }

    public Solution()
    {
        Pieces = new List<Shape>();
    }

    // Return a deep clone of an object of type T.
    public object DeepClone()
    {
        using (MemoryStream memory_stream = new MemoryStream())
        {
            // Serialize the object into the memory stream.
            BinaryFormatter formatter = new BinaryFormatter();
            formatter.Serialize(memory_stream, this);

            // Rewind the stream and use it to create a new object.
            memory_stream.Position = 0;
            return (Solution)formatter.Deserialize(memory_stream);
        }
    }

    public bool TestRowFlips(int row)
    {
        int[] Changes = new int[8] { 0, 0, 0, 0, 0, 0, 0, 0 };

        foreach (Shape p in Pieces)
        {
            for (int i = 0; i < p.Height; i++)
            {
                Changes[ i + p.RowPosition ] += p.Changes[i];
            }
        }

        if ((Changes[row] - Game[row]) % 3 == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public bool ExistPiece(long id)
    {
        return Pieces.Any(x => x.Id == id);
    }
}

Recursive

class Recursive
{
    private List<Shape> Pieces { get; set; }

    public void Setup()
    {
        Pieces = new List<Shape>
        {
            new Shape(Math.Pow( 2, 0 ), new int[5] { 2, 1, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 1 ), new int[5] { 2, 1, 0, 0, 0 }, 2),
            new Shape(Math.Pow( 2, 2 ), new int[5] { 2, 2, 2, 0, 0 }, 3),

            new Shape(Math.Pow( 2, 3 ), new int[5] { 3, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 4 ), new int[5] { 4, 3, 3, 3, 0 }, 4),
            new Shape(Math.Pow( 2, 5 ), new int[5] { 3, 0, 0, 0, 0 }, 1),

            new Shape(Math.Pow( 2, 6 ), new int[5] { 3, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 7 ), new int[5] { 3, 4, 1, 2, 2 }, 5),
            new Shape(Math.Pow( 2, 8 ), new int[5] { 1, 0, 0, 0, 0 }, 1),

            new Shape(Math.Pow( 2, 9 ), new int[5] { 2, 2, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 10 ), new int[5] { 2, 3, 4, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 11 ), new int[5] { 1, 3, 1, 3, 2 }, 5),

            new Shape(Math.Pow( 2, 12 ), new int[5] { 1, 2, 2, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 13 ), new int[5] { 2, 4, 1, 1, 0 }, 4),
            new Shape(Math.Pow( 2, 14 ), new int[5] { 1, 2, 1, 0, 0 }, 3),

            new Shape(Math.Pow( 2, 15 ), new int[5] { 1, 1, 3, 0, 0 }, 3),
            new Shape(Math.Pow( 2, 16 ), new int[5] { 3, 2, 3, 1, 0 }, 4),
            new Shape(Math.Pow( 2, 17 ), new int[5] { 1, 3, 2, 2, 0 }, 4)
        };
        // try to solve first row
        for (long PieceSet = 0; PieceSet < Math.Pow(2, 18); PieceSet++)
        {
            Solution solution = new Solution();
            foreach (Shape piece in Pieces)
            {
                if ((piece.Id & PieceSet) > 0)
                {
                    Shape p = (Shape)piece.Clone();
                    p.RowPosition = 0;
                    solution.Pieces.Add(p);
                }
            }

            if (solution.TestRowFlips(0))
            {
                solution.Id = PieceSet;
                Solve_Row(solution, 1);
            }
        }
    }

    public bool Solve_Row(Solution solution, int rowToSolve)
    {
        // Check the unused pieces to see if are too big to be used on any other row.
        if (Pieces.Any(x => (x.Id & solution.Id) == 0 && x.MaxRow < rowToSolve))
        {
            return false;
        }

        for (long pieceSet = 0; pieceSet < Math.Pow(2, 18); pieceSet++)
        {          
            if ((pieceSet & solution.Id) == 0)
            {
                Solution newSolution = (Solution)solution.DeepClone();

                foreach (Shape piece in Pieces.Where(x => (x.Id & pieceSet) > 0)
                                              .ToList())
                {
                    Shape p = (Shape)piece.Clone();
                    p.RowPosition = rowToSolve;
                    newSolution.Pieces.Add(p);
                }

                newSolution.Id = newSolution.Id | pieceSet;

                if (newSolution.Id == Pieces.Sum(x => x.Id))
                {
                    Debug.Print("Found a Solution");
                    return true;
                }

                if (newSolution.TestRowFlips(rowToSolve))
                {
                    Solve_Row(newSolution, rowToSolve + 1);
                }
            }
        }
        return false;
    }


}

Answer 1

Shape

    [Serializable()]

The () is unnecessary and it's usual to omit it for readability.

---

    public class Shape : ICloneable

ICloneable is from the very early days of C# before they added generics (for which read "a half-decent type system"). I would strongly recommend never using it in new code. Make your own

public interface ICloneable<T>
{
    T Clone();
}

so that you can avoid all the casts. Or just add the Clone method without a marker interface.

---

        public int Height { get; set; }
        public int Width { get; set; } // I will use Width to test by column later
        public int[] Changes { get; set; } // How many flips 
        public long Id { get; set; }
        public int RowPosition { get; set; } // In what Row Im using the piece
        public int MaxRow { get; set; } // What is the last row where can fit 

Why are these all settable? As far as I can see, RowPosition is the only one that is set anywhere outside the constructor, so I think that they should either have private set; or (if you're using a recent enough version of C#) use the public int Height { get; } = height syntax.

Why is Changes an int[]? That allows callers to modify it. I think that IReadOnlyList<int> would probably convey the intent more clearly.

I said that RowPosition is the only one of these that is set anywhere outside the constructor. In fact, it's only ever set immediately after cloning. I suggest replacing Clone() with a copy constructor. (This may force using private set or a backing readonly field: I don't think it plays well with { get; } =).

Alternatively, go for a purer object model: the RowPosition is not strictly a property of the shape. You could factor it out and work with some kind of tuple (Shape, Location) or Dictionary<Shape, Location>.

Changes and Id could use documentation on their interpretation. If I've understood correctly, both are bitmasks: state that clearly. It might be a good idea to make the constructor validate that Id is a single bit:

if (id == 0 || (id & (id - 1)) != 0) throw new ArgumentOutOfRangeException(nameof(id));

---

        public Shape(double id, int[] piece, int height)

id should be a long, not a double.

---

Solution

Some previous comments apply.

---

        public long Id { get; set; }

I think this is a mask indicating which pieces are present. The name should reflect that.

---

        public object DeepClone()
        {
            using (MemoryStream memory_stream = new MemoryStream())
            {
                // Serialize the object into the memory stream.
                BinaryFormatter formatter = new BinaryFormatter();
                formatter.Serialize(memory_stream, this);

                // Rewind the stream and use it to create a new object.
                memory_stream.Position = 0;
                return (Solution)formatter.Deserialize(memory_stream);
            }
        }

This is quite clever and robust to changes, but also slow. Given that time is your biggest enemy, I think it might be better to use a more brittle but faster approach.

---

            if ((Changes[row] - Game[row]) % 3 == 0)
            {
                return true;
            }
            else
            {
                return false;
            }

This is more readable as

        return (Changes[row] - Game[row]) % 3 == 0;

Also, this method calculates Changes to then ignore all but Changes[row]. That's an easy place to optimise.

---

        public bool ExistPiece(long id)
        {
            return Pieces.Any(x => x.Id == id);
        }

I think this should be called ContainsPiece, and I also think that it could be optimised to return (this.Id & id) != 0;, assuming that I've correctly understood the invariants about Solution.Id.

---

Recursive

                new Shape(Math.Pow( 2, 0 ), new int[5] { 2, 1, 2, 0, 0 }, 3),

(and lots of similar lines). Firstly, don't use Math.Pow unless you're dealing with doubles. For bitmasks << and >> should be enough. Secondly, why the trailing zeroes and a separate argument to say how long it is? This looks to me like it should be

                new Shape(1L << 0, new int[] { 2, 1, 2 }),

---

            // try to solve first row

Is there any reason why this can't be done with a line or two of setup and a call to Solve_Row(solution, 0)?

---

        public bool Solve_Row(Solution solution, int rowToSolve)
        {
            ...

            for (long pieceSet = 0; pieceSet < Math.Pow(2, 18); pieceSet++)
            {          
                if ((pieceSet & solution.Id) == 0)
                {
                    ...
                }
            }
            return false;
        }

This is extremely inefficient. I suggest that you first create a method public static IEnumerable<IEnumerable<T>> Subsets<T>(IEnumerable<T> elements) which uses a technique like this to generate all subsets of its argument. (Use yield return to keep the memory usage low). Then you can make this loop iterate only over subsets of the pieces which aren't already included. It probably still won't be fast enough, but it will at least be much faster.

---

                    foreach (Shape piece in Pieces.Where(x => (x.Id & pieceSet) > 0)
                                                  .ToList())

I suggest you factor out a method IEnumerable<Shape> PiecesForMask(int pieceSet). Then it can be faster by using a Dictionary<long, Shape> to map IDs to shapes and using the standard trick that x & -x is the lowest set bit of x to run in time proportional to the number of pieces in pieceSet rather than iterating through all of them.

---

                    if (newSolution.Id == Pieces.Sum(x => x.Id))

This is another easy optimisation: calculate the target mask once and store it. (Or calculate it on the fly as (1L << Pieces.Count) - 1).

---

One big thing that's missing is comments. A simple explanation of what the code is trying to do (which I think is to find a mapping which places every piece in one row such that the sums all add up to desired values modulo 3) would go a long way, along with clear identification of which ints represent counts and which represent bitmasks.

---

Finally, the big question: the algorithm. I suspect that the test applied ((Changes[row] - Game[row]) % 3 == 0) is actually overly optimistic. Probably you also need Changes[row] >= Game[row]. If so, I would look at reformulating the problem as a set multicover and solving it with a variant of Knuth's Algorithm X. Probably you should first try to understand the basic algorithm for set cover and the formulation of simple puzzles as set cover. Then look at expanding to multicover. The idea would be that a cell which needs to be covered \$a + 3k\$ times (for any \$k \ge 0\$) would become an element which needs to be covered \$a + 3K\$ for a suitably large \$K\$ (maybe iterative deepening would be a sensible approach; alternatively, making \$K\$ the number of shapes is definitely sufficiently conservative); also, each shape needs to be covered once (it must be used in exactly one place). The placement of a shape in a position is a row which can be used in the cover: it covers the shape and the board elements (with multiplicity). Then there are some utility rows which cover one element 3 times and take up the slack. If you don't actually need to use all the shapes (I think you have to take them in order when playing, but can you stop early?) then that could be handled with rows which just cover the last \$i\$ shapes and no board elements.

Looking at Knuth's downloadable programs starting with DLX I see there are some new variants since I last read the draft of fascicle 4C of the Art of Computer Programming. I strongly recommend you download that and dedicate a good 10 hours to reading and understanding it: it's a very good technique for many kinds of puzzle.