This is the forty first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

We continue our exploration of riddles solvable by ILP. Today we are going to find solution for Rubik’s cube. Let’s begin.

Table of Contents

Theory

There are lots of different Rubik’s cube, one of which is 2x2x2 cube similar to (Work by Mike Gonzalez, found on Wikipedia).

There are various algorithms for solving these cubes, but we are not going to implement them directly. Instead, we need to know so called “God’s number” which is basically a maximum number of rotations required to solve cube starting from any state. These numbers are known for many cubes, e.g., for 2x2x2 it is 14 (as specified in 2x2x2 Cube – Speedsolving). So we know that we can take any cube and make at most 14 rotations to solve it.

Knowing this we can simply try every possible sequence of moves. Since we use ILP, we only need to define a “move” and what is “final position”.

Cube’s representation

We start with few helper classes representing cubes. Since solving algorithm is the same for cube of any shape (no matter whether it is 2x2x2 or megaminx), we would like to have these things independent.

enum Colors
{
	Green = 0,
	Yellow = 1,
	Blue = 2,
	Red = 3,
	Purple = 4,
	White = 5
}

interface ICubeProvider
{
	IEnumerable< IVariable> GetWallVariables(int wall, IMilpManager solver);
	IList< IVariable> RotateWall(IList< IVariable> wallVariables, int wallNumber, IVariable isThisWallRotated, bool isClockwise, IMilpManager solver);
	int WallsCount { get; }
	int MovesCount { get; }
	int WallSize { get; }
}

enum Colors

{

Green = 0,

Yellow = 1,

Blue = 2,

Red = 3,

Purple = 4,

White = 5

}

interface ICubeProvider

{

IEnumerable< IVariable> GetWallVariables(int wall, IMilpManager solver);

IList< IVariable> RotateWall(IList< IVariable> wallVariables, int wallNumber, IVariable isThisWallRotated, bool isClockwise, IMilpManager solver);

int WallsCount { get; }

int MovesCount { get; }

int WallSize { get; }

}

First, we define colors of elements in order to be able to read code easily. Next, we define what any cube provider should define. These are: solver variables for all walls, method rotating single wall, number of walls, number of moves required to solve the cube (“God’s number”) and size of the wall. Next, we define provider:

class Cube2v2v2Provider : ICubeProvider
{
	private readonly Dictionary< int, IEnumerable< Colors>> _walls = new Dictionary< int, IEnumerable< Colors>>
	{
		[0] = new[] {Colors.White, Colors.Green, Colors.Green, Colors.Yellow}, // Bottom
		[1] = new[] {Colors.Red, Colors.Red, Colors.Yellow, Colors.Yellow }, // Right
		[2] = new[] {Colors.Purple, Colors.White, Colors.White, Colors.Blue}, // Top
		[3] = new[] {Colors.White, Colors.Green, Colors.Red, Colors.Blue}, // Left
		[4] = new[] {Colors.Purple, Colors.Yellow, Colors.Purple, Colors.Blue}, // Front
		[5] = new[] {Colors.Red, Colors.Purple, Colors.Blue, Colors.Green}, // Back
	};

	private readonly Dictionary< int, IEnumerable< IEnumerable< int>>>  _transformations = new Dictionary
		< int, IEnumerable< IEnumerable< int>>>
	{
		[0] = new []
		{
			new [] {0, 1, 2, 3},
			new [] {19, 7, 23, 15},
			new [] {18, 6, 22, 14}
		},
		[1] = new[]
		{
			new [] {4, 5, 6, 7},
			new [] {10, 20, 2, 18},
			new [] {11, 23, 1, 17}
		},
		[2] = new[]
		{
			new [] {8, 9, 10, 11},
			new [] {20, 4, 16, 12},
			new [] {21, 5, 17, 13}
		},
		[3] = new[]
		{
			new [] {12, 13, 14, 15},
			new [] {21, 9, 19, 3},
			new [] {22, 8, 16, 0}
		},
		[4] = new[]
		{
			new [] {16, 17, 18, 19},
			new [] {9, 4, 1, 14},
			new [] {10, 7, 0, 13}
		},
		[5] = new[]
		{
			new [] {20, 21, 22, 23},
			new [] {5, 8, 15, 2},
			new [] {6, 11, 12, 3}
		}
	};

	public virtual IEnumerable< IVariable> GetWallVariables(int wall, IMilpManager solver)
	{
		return _walls[wall].Select(c => solver.FromConstant((int) c));
	}

	public IList< IVariable> RotateWall(IList< IVariable> wallVariables, int wallNumber, IVariable isThisWallRotated, bool isClockwise, IMilpManager solver)
	{
		var originalWallVariables = wallVariables.ToList();
		foreach (IEnumerable< int> transformationList in _transformations[wallNumber])
		{
			var transformation = transformationList.ToList();
			for (int i = 0; i < transformation.Count; ++i)
			{
				var sourceItem = transformation[i];
				var destinationItem = isClockwise 
					? transformation[i - 1 < 0 ? transformation.Count - 1 : i - 1]
					: transformation[(i + 1) % transformation.Count];
				wallVariables[sourceItem] = solver.Operation(OperationType.Condition,isThisWallRotated, originalWallVariables[destinationItem], originalWallVariables[sourceItem]);
			}
		}

		return wallVariables;
	}

	public virtual int WallsCount => 6;
	public virtual int MovesCount => 14;
	public virtual int WallSize => 4;
}

class Cube2v2v2Provider : ICubeProvider

{

private readonly Dictionary< int, IEnumerable< Colors>> _walls = new Dictionary< int, IEnumerable< Colors>>

{

[0] = new[] {Colors.White, Colors.Green, Colors.Green, Colors.Yellow}, // Bottom

[1] = new[] {Colors.Red, Colors.Red, Colors.Yellow, Colors.Yellow }, // Right

[2] = new[] {Colors.Purple, Colors.White, Colors.White, Colors.Blue}, // Top

[3] = new[] {Colors.White, Colors.Green, Colors.Red, Colors.Blue}, // Left

[4] = new[] {Colors.Purple, Colors.Yellow, Colors.Purple, Colors.Blue}, // Front

[5] = new[] {Colors.Red, Colors.Purple, Colors.Blue, Colors.Green}, // Back

};

private readonly Dictionary< int, IEnumerable< IEnumerable< int>>> _transformations = new Dictionary

< int, IEnumerable< IEnumerable< int>>>

{

[0] = new []

{

new [] {0, 1, 2, 3},

new [] {19, 7, 23, 15},

new [] {18, 6, 22, 14}

[1] = new[]

{

new [] {4, 5, 6, 7},

new [] {10, 20, 2, 18},

new [] {11, 23, 1, 17}

[2] = new[]

{

new [] {8, 9, 10, 11},

new [] {20, 4, 16, 12},

new [] {21, 5, 17, 13}

[3] = new[]

{

new [] {12, 13, 14, 15},

new [] {21, 9, 19, 3},

new [] {22, 8, 16, 0}

[4] = new[]

{

new [] {16, 17, 18, 19},

new [] {9, 4, 1, 14},

new [] {10, 7, 0, 13}

[5] = new[]

{

new [] {20, 21, 22, 23},

new [] {5, 8, 15, 2},

new [] {6, 11, 12, 3}

}

};

public virtual IEnumerable< IVariable> GetWallVariables(int wall, IMilpManager solver)

{

return _walls[wall].Select(c => solver.FromConstant((int) c));

}

public IList< IVariable> RotateWall(IList< IVariable> wallVariables, int wallNumber, IVariable isThisWallRotated, bool isClockwise, IMilpManager solver)

{

var originalWallVariables = wallVariables.ToList();

foreach (IEnumerable< int> transformationList in _transformations[wallNumber])

{

var transformation = transformationList.ToList();

for (int i = 0; i < transformation.Count; ++i)

{

var sourceItem = transformation[i];

var destinationItem = isClockwise

? transformation[i - 1 < 0 ? transformation.Count - 1 : i - 1]

: transformation[(i + 1) % transformation.Count];

wallVariables[sourceItem] = solver.Operation(OperationType.Condition,isThisWallRotated, originalWallVariables[destinationItem], originalWallVariables[sourceItem]);

}

return wallVariables;

}

public virtual int WallsCount => 6;

public virtual int MovesCount => 14;

public virtual int WallSize => 4;

}

First, _walls defines some initial state. Provider is responsible for specifying order of walls’ elements and moves, so we can choose any particular which suits our intuition/needs. Next, we define all moves. This “black magic” numbers represent which variables are replaced when we perform particular move. We need to specify all moves available for this cube.

Next, we implement interface. We simply return variables for all walls, for every transformation we extract source element and destination element, and we exchange them conditionally. Rest of the code should be obvious.

Now goes the algorithm.

Algorithm

This part is pretty easy. Since we know how many moves we need to perform, we iterate through all of them. For every move we create integer variable representing the move: it is a number of wall to rotate. Since we cane rotate it clockwise or counter-clockwise, we need to multiply possibilities by two. Also, since we might solve cube without performing all 14 moves, we add dummy move with no meaning.

Next, for every move we simply rotate wall and provider takes care of the whole transformation.

Finally, we constrain all walls to be of a single color.

ICubeProvider cube = new Cube2v2v2Provider();
var solver = new CplexMilpSolver(5);
var walls = Enumerable.Range(0, cube.WallsCount).SelectMany(wall => cube.GetWallVariables(wall, solver)).ToList();
var moves = new List< IVariable>();
for (int move = 0; move < cube.MovesCount; ++move)
{
	IVariable whichWall = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(cube.WallsCount*2 )); // cube.WallsCount * 2 instead of cube.WallsCount * 2 - 1 in order to add non-existing move not changing cube
	moves.Add(whichWall);
	for (int wall = 0; wall < cube.WallsCount; ++wall)
	{
		for (int clockwise = 0; clockwise < 2; ++clockwise)
		{
			walls = cube.RotateWall(walls, wall, whichWall.Operation(OperationType.IsEqual, solver.FromConstant(2*wall + clockwise)), clockwise == 0, solver).ToList();
		}
	}
}

for (int wall = 0; wall < cube.WallsCount; ++wall)
{
	var wallVariables = walls.Skip(wall*cube.WallSize).Take(cube.WallSize).ToList();
	for (int anotherEnd = 1; anotherEnd < wallVariables.Count; ++anotherEnd)
	{
		wallVariables[0].Set(ConstraintType.Equal, wallVariables[anotherEnd]);
	}
}

solver.Solve();

for (int move = 0; move < moves.Count; ++move)
{
	var performedMove = (int) moves[move].GetValue();
	Console.WriteLine($"Move {move + 1}: wall {performedMove / 2}, clockwise: {performedMove % 2 == 0}");
}

ICubeProvider cube = new Cube2v2v2Provider();

var solver = new CplexMilpSolver(5);

var walls = Enumerable.Range(0, cube.WallsCount).SelectMany(wall => cube.GetWallVariables(wall, solver)).ToList();

var moves = new List< IVariable>();

for (int move = 0; move < cube.MovesCount; ++move)

{

IVariable whichWall = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(cube.WallsCount*2 )); // cube.WallsCount * 2 instead of cube.WallsCount * 2 - 1 in order to add non-existing move not changing cube

moves.Add(whichWall);

for (int wall = 0; wall < cube.WallsCount; ++wall)

{

for (int clockwise = 0; clockwise < 2; ++clockwise)

{

walls = cube.RotateWall(walls, wall, whichWall.Operation(OperationType.IsEqual, solver.FromConstant(2*wall + clockwise)), clockwise == 0, solver).ToList();

}

for (int wall = 0; wall < cube.WallsCount; ++wall)

{

var wallVariables = walls.Skip(wall*cube.WallSize).Take(cube.WallSize).ToList();

for (int anotherEnd = 1; anotherEnd < wallVariables.Count; ++anotherEnd)

{

wallVariables[0].Set(ConstraintType.Equal, wallVariables[anotherEnd]);

}

solver.Solve();

for (int move = 0; move < moves.Count; ++move)

{

var performedMove = (int) moves[move].GetValue();

Console.WriteLine($"Move {move + 1}: wall {performedMove / 2}, clockwise: {performedMove % 2 == 0}");

}

And we are done.

Summary

With this approach we can easily solve any cube by implementing new providers. E.g., 3x3x3 is almost the same as existing code, megaminx requires a little more modifications.