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

Today we solve another puzzle: Fifteen puzzle. Let’s begin.

Game

Fifteen puzzle
Image from Wikipedia.

In order to solve the game using single tile moves, we need 80 of them. We will use exactly the same approach as when solving Rubik’s cub.e

Code

var initial = new[]
{
	new[] {1, 2, 3, 4},
	new[] {5, 6, 7, 8},
	new[] {9, 10, 11, 12},
	new[] {13, 14, 0, 15}
};
int movesCount = 1;

var moves = new List< IVariable>();


var solver = new OrToolsMilpSolver(5);
var board = initial.Select(r => r.Select(c => solver.FromConstant(c)).ToArray()).ToArray();

for (int move = 0; move < movesCount; ++move)
{
	var decision = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(3)); // We don't have move not-changing board because we always can "move" down or right when empty block is in lower-right corner (such a move will not change board)
	moves.Add(decision);

	var newBoard = board.Select(r => r.ToArray()).ToArray();
	for (int direction = 0; direction < 4; ++direction)
	{
		for (int row = 0; row < newBoard.Length; ++row)
		{
			for (int column = 0; column < newBoard[row].Length; ++column)
			{
				if ((direction == 0 && row == 0) || (direction == 1 && column == newBoard[row].Length - 1) ||
					(direction == 2 && row == newBoard.Length - 1) || (direction == 3 && column == 0))
				{
					continue;
				}

				var shouldMove = solver.Operation(OperationType.Conjunction,
					board[row][column].Operation(OperationType.IsEqual, solver.FromConstant(0)),
					decision.Operation(OperationType.IsEqual, solver.FromConstant(direction)));

				int newX = direction == 0 ? row - 1 : direction == 2 ? row + 1 : row;
				int newY = direction == 1 ? column + 1 : direction == 3 ? column - 1 : column;

				var source = newBoard[row][column];
				var target = newBoard[newX][newY];

				newBoard[row][column] = solver.Operation(OperationType.Condition,
					shouldMove,
					target,
					source
				);
				newBoard[newX][newY] = solver.Operation(OperationType.Condition,
					shouldMove,
					source,
					target
				);
			}
		}
	}
	board = newBoard;
}

for (int row = 0; row < board.Length; ++row)
{
	for (int column = 0; column < board[row].Length; ++column)
	{
		if (row == board.Length - 1 && column == board[row].Length - 1)
		{
			board[row][column].Set(ConstraintType.Equal, solver.FromConstant(0));
		}
		else
		{
			board[row][column].Set(ConstraintType.Equal, solver.FromConstant(row * board[0].Length + column + 1));
		}
	}
}

solver.Solve();

for (int move = 0; move < moves.Count; ++move)
{
	var actualMove = (int)moves[move].GetValue();
	Console.WriteLine($"Move {move + 1}: {(actualMove == 0 ? "UP" : actualMove == 1 ? "RIGHT" : actualMove == 2 ? "DOWN" : "LEFT")} {actualMove}");
}

var initial = new[]

{

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

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

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

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

};

int movesCount = 1;

var moves = new List< IVariable>();

var solver = new OrToolsMilpSolver(5);

var board = initial.Select(r => r.Select(c => solver.FromConstant(c)).ToArray()).ToArray();

for (int move = 0; move < movesCount; ++move)

{

var decision = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(3)); // We don't have move not-changing board because we always can "move" down or right when empty block is in lower-right corner (such a move will not change board)

moves.Add(decision);

var newBoard = board.Select(r => r.ToArray()).ToArray();

for (int direction = 0; direction < 4; ++direction)

{

for (int row = 0; row < newBoard.Length; ++row)

{

for (int column = 0; column < newBoard[row].Length; ++column)

{

if ((direction == 0 && row == 0) || (direction == 1 && column == newBoard[row].Length - 1) ||

(direction == 2 && row == newBoard.Length - 1) || (direction == 3 && column == 0))

{

continue;

}

var shouldMove = solver.Operation(OperationType.Conjunction,

board[row][column].Operation(OperationType.IsEqual, solver.FromConstant(0)),

decision.Operation(OperationType.IsEqual, solver.FromConstant(direction)));

int newX = direction == 0 ? row - 1 : direction == 2 ? row + 1 : row;

int newY = direction == 1 ? column + 1 : direction == 3 ? column - 1 : column;

var source = newBoard[row][column];

var target = newBoard[newX][newY];

newBoard[row][column] = solver.Operation(OperationType.Condition,

shouldMove,

target,

source

);

newBoard[newX][newY] = solver.Operation(OperationType.Condition,

shouldMove,

source,

target

);

}

board = newBoard;

}

for (int row = 0; row < board.Length; ++row)

{

for (int column = 0; column < board[row].Length; ++column)

{

if (row == board.Length - 1 && column == board[row].Length - 1)

{

board[row][column].Set(ConstraintType.Equal, solver.FromConstant(0));

}

else

{

board[row][column].Set(ConstraintType.Equal, solver.FromConstant(row * board[0].Length + column + 1));

}

solver.Solve();

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

{

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

Console.WriteLine($"Move {move + 1}: {(actualMove == 0 ? "UP" : actualMove == 1 ? "RIGHT" : actualMove == 2 ? "DOWN" : "LEFT")} {actualMove}");

}

We start with defining initial position. Next, for every move we define variable representing the move: we can slide pieces right, down, left, or up. As commented, we don’t need dummy move because we can always make move down or right when we have empty piece in bottom-right corner and this will not change anything.

Next, we calculate indexes, extract source and destination, exchange them conditionally, and that’s all.

Summary

Presented approach is universal — we can easily adapt it to solve different riddles. Even when we don’t know the “God’s number”, we can approximate it or event make it so high to be sure that it will be enough.