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;
}
}