This doesn’t take particularly long to exhaust all possibilities after it finds a solution so a depth first search would have been fine.
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
namespace Trucks
{
class Program
{
enum TruckGoal
{
Present,
House,
Flag
}
// Co-ordinate system
// Bottom left = (0,0)
// Co-ordinates of the present, house and flag
// for each truck
public static int[,] TruckGoalX = new int[4, 3]
{
{3, 0, 3},{0, 3, 2},{3, 0, 1},{0, 3, 0}
};
public static int[,] TruckGoalY = new int[4, 3]
{
{0, 3, 3},{2, 1, 3},{2, 1, 3},{0, 3, 3}
};
// Describes a possible move from a given initial state
class Move
{
public State InitialState { get; set; }
// Which direction does each truck move on this turn
public int[] DeltaX { get; } = new int[4];
public int[] DeltaY { get; } = new int[4];
// Which junctions and roads were used on this turn
public bool[] JunctionUsed { get; } = new bool[16];
public bool[] VerticalRoadUsed { get; } = new bool[12];
public bool[] HorizontalRoadUsed { get; } = new bool[12];
// Which junction and road did each truck use on this turn
public int[] TruckUsedJunction { get; } = new int[4];
public int[] TruckUsedVerticalRoad { get; } = new int[4];
public int[] TruckUsedHorizontalRoad { get; } = new int[4];
public Move(State initialState)
{
InitialState = initialState;
}
public Move(Move copyFrom)
{
InitialState = copyFrom.InitialState;
Array.Copy(copyFrom.DeltaX, DeltaX, 4);
Array.Copy(copyFrom.DeltaY, DeltaY, 4);
Array.Copy(copyFrom.JunctionUsed, JunctionUsed, 16);
Array.Copy(copyFrom.VerticalRoadUsed, VerticalRoadUsed, 12);
Array.Copy(copyFrom.HorizontalRoadUsed, HorizontalRoadUsed, 12);
Array.Copy(copyFrom.TruckUsedHorizontalRoad, TruckUsedHorizontalRoad, 4);
Array.Copy(copyFrom.TruckUsedVerticalRoad, TruckUsedVerticalRoad, 4);
}
}
// Defines a particular state (or node on the A* graph)
class State : IComparable<State>
{
public State PreviousState = null;
// The score of this state for use in the A* priority function
private int _score;
public State() { }
// Build a state from a particular move
public State(Move m)
{
PreviousState = m.InitialState;
Distance = m.InitialState.Distance + 1;
Array.Copy(m.InitialState.TruckGoal, TruckGoal, 4);
Array.Copy(m.InitialState.TruckHorizontalRoadTraversed, TruckHorizontalRoadTraversed, 48);
Array.Copy(m.InitialState.TruckVerticalRoadTraversed, TruckVerticalRoadTraversed, 48);
int finishedAllGoals = 0;
for (int t = 0; t < 4; t++)
{
var truckX = m.InitialState.TruckX[t] + m.DeltaX[t];
var truckY = m.InitialState.TruckY[t] + m.DeltaY[t];
var truckGoal = TruckGoal[t];
var truckGoalX = TruckGoalX[t, (int)truckGoal];
var truckGoalY = TruckGoalY[t, (int)truckGoal];
TruckX[t] = truckX;
TruckY[t] = truckY;
var horizontalRoad = m.TruckUsedHorizontalRoad[t];
if (horizontalRoad != -1)
TruckHorizontalRoadTraversed[t, horizontalRoad] = true;
var verticalRoad = m.TruckUsedVerticalRoad[t];
if (verticalRoad != -1)
TruckVerticalRoadTraversed[t, verticalRoad] = true;
// If this move brings us to the next goal then advance
// the truck on to the next goal.
if (truckX == truckGoalX
&& truckY == truckGoalY)
{
var newGoal = (int)TruckGoal[t] + 1;
if (newGoal == 3)
{
// Count how many trucks have finished all goals
finishedAllGoals++;
}
else
{
TruckGoal[t] = (TruckGoal)newGoal;
}
}
}
// If all four trucks are at the end then print the route
if (finishedAllGoals == 4)
{
var printState = this;
var stack = new Stack<State>();
do
{
stack.Push(printState);
printState = printState.PreviousState;
} while (printState != null);
int i = 0;
Console.WriteLine("STEP Yellow Blue Green Red");
while (stack.TryPop(out var state))
{
Console.Write($"{i,3}. ({state.TruckX[0]}, {state.TruckY[0]}) ");
Console.Write($"({state.TruckX[1]}, {state.TruckY[1]}) ");
Console.Write($"({state.TruckX[2]}, {state.TruckY[2]}) ");
Console.WriteLine($"({state.TruckX[3]}, {state.TruckY[3]}) ");
i++;
}
Console.WriteLine();
}
}
// How far each truck has travelled so far
public int Distance { get; set; }
// Where each truck currently is
public int[] TruckX { get; } = new int[4] { 0, 1, 2, 3 };
public int[] TruckY { get; } = new int[4] { 0, 0, 0, 0 };
// A map of where each truck was for each turn up to this state
public bool[,] TruckHorizontalRoadTraversed { get; } = new bool[4,12];
public bool[,] TruckVerticalRoadTraversed { get; } = new bool[4,12];
// How many goals has each truck completed
TruckGoal[] TruckGoal { get; } = new TruckGoal[4];
public int CompareTo([AllowNull] State other)
{
if (other._score > _score) return -1;
if (other._score < _score) return 1;
return 0;
}
public int CalculateScore()
{
// Calculate score for use in A* priority queue
_score = Heuristic() + Distance;
return _score;
}
// Return all the valid moves that can be made from this state
public IEnumerable<Move> ValidMoves()
{
return ValidMoves(0, new Move(this));
}
private IEnumerable<Move> ValidMoves(int truck, Move move)
{
if (truck == 4)
{
yield return move;
yield break;
}
var y = TruckY[truck];
var x = TruckX[truck];
// UP
if (y < 3)
{
var destJunction = x + (y + 1) * 4;
var verticalRoad = (y) * 4 + x;
if (!TruckVerticalRoadTraversed[truck, verticalRoad] // This truck has not already used this road
&& !move.VerticalRoadUsed[verticalRoad] // AND another truck is not using this road this turn
&& !move.JunctionUsed[destJunction] // AND another truck is not using this junction this turn
&& !(x == 1 && y == 1) // AND we're not using any of the blocked routes
&& !(x == 3 && y == 1))
{
var newMove = new Move(move);
newMove.VerticalRoadUsed[verticalRoad] = true;
newMove.JunctionUsed[destJunction] = true;
newMove.DeltaX[truck] = 0;
newMove.DeltaY[truck] = 1;
newMove.TruckUsedHorizontalRoad[truck] = -1;
newMove.TruckUsedVerticalRoad[truck] = verticalRoad;
foreach (var r in ValidMoves(truck + 1, newMove))
yield return r;
}
}
// DOWN
if (y > 0)
{
var destJunction = x + (y - 1) * 4;
var verticalRoad = (y - 1) * 4 + x;
if (!TruckVerticalRoadTraversed[truck, verticalRoad]
&& !move.VerticalRoadUsed[verticalRoad]
&& !move.JunctionUsed[destJunction]
&& !(x == 1 && y == 2)
&& !(x == 2 && y == 3))
{
var newMove = new Move(move);
newMove.VerticalRoadUsed[verticalRoad] = true;
newMove.JunctionUsed[destJunction] = true;
newMove.DeltaX[truck] = 0;
newMove.DeltaY[truck] = -1;
newMove.TruckUsedHorizontalRoad[truck] = -1;
newMove.TruckUsedVerticalRoad[truck] = verticalRoad;
foreach (var r in ValidMoves(truck + 1, newMove))
yield return r;
}
}
// LEFT
if (x > 0)
{
var destJunction = (x - 1) + y * 4;
var horizontalRoad = y * 3 + (x - 1);
if (!TruckHorizontalRoadTraversed[truck, horizontalRoad]
&& !move.HorizontalRoadUsed[horizontalRoad]
&& !move.JunctionUsed[destJunction]
&& !(x == 1 && y == 1)
&& !(x == 3 && y == 1)
&& !(x == 3 && y == 2))
{
var newMove = new Move(move);
newMove.HorizontalRoadUsed[horizontalRoad] = true;
newMove.JunctionUsed[destJunction] = true;
newMove.DeltaX[truck] = -1;
newMove.DeltaY[truck] = 0;
newMove.TruckUsedHorizontalRoad[truck] = horizontalRoad;
newMove.TruckUsedVerticalRoad[truck] = -1;
foreach (var r in ValidMoves(truck + 1, newMove))
yield return r;
}
}
// RIGHT
if (x < 3)
{
var destJunction = (x + 1) + y * 4;
var horizontalRoad = y * 3 + (x );
if (!TruckHorizontalRoadTraversed[truck, horizontalRoad]
&& !move.HorizontalRoadUsed[horizontalRoad]
&& !move.JunctionUsed[destJunction])
{
var newMove = new Move(move);
newMove.HorizontalRoadUsed[horizontalRoad] = true;
newMove.JunctionUsed[destJunction] = true;
newMove.DeltaX[truck] = 1;
newMove.DeltaY[truck] = 0;
newMove.TruckUsedHorizontalRoad[truck] = horizontalRoad;
newMove.TruckUsedVerticalRoad[truck] = -1;
foreach (var r in ValidMoves(truck + 1, newMove))
yield return r;
}
}
}
// Calculates the A* heuristic function
private int Heuristic()
{
int maxDistance = 0;
for (int truck = 0; truck < 4; truck++)
{
// For each truck, calculate the euclidean distance from
// the current location to each remaining goal in turn
var currentGoal = TruckGoal[truck];
var truckX = TruckX[truck];
var truckY = TruckY[truck];
var distance = 0;
for (int i = (int)currentGoal; i < 3; i++)
{
var goalX = TruckGoalX[truck, i];
var goalY = TruckGoalY[truck, i];
distance += Math.Abs(truckX - goalX) + Math.Abs(truckY - goalY);
truckX = goalX;
truckY = goalY;
}
if (distance > maxDistance)
maxDistance = distance;
}
// return the worst case for any truck
return maxDistance;
}
}
static void Main(string[] args)
{
var priorityQueue = new PriorityQueue<State>();
// Add the initial state to the queue
var initial = new State();
initial.CalculateScore();
priorityQueue.Enqueue(initial);
while (priorityQueue.Count() > 0)
{
// Take the lowest score state off the queue
var state = priorityQueue.Dequeue();
// Push every valid move from this state onto the queue
foreach (var m in state.ValidMoves())
{
var newState = new State(m);
newState.CalculateScore();
priorityQueue.Enqueue(newState);
}
}
}
}
public class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
public PriorityQueue()
{
this.data = new List<T>();
}
public void Enqueue(T item)
{
data.Add(item);
int ci = data.Count - 1; // child index; start at end
while (ci > 0)
{
int pi = (ci - 1) / 2; // parent index
if (data[ci].CompareTo(data[pi]) >= 0)
break; // child item is larger than (or equal) parent so we're done
T tmp = data[ci];
data[ci] = data[pi];
data[pi] = tmp;
ci = pi;
}
}
public T Dequeue()
{
// assumes pq is not empty; up to calling code
int li = data.Count - 1; // last index (before removal)
T frontItem = data[0]; // fetch the front
data[0] = data[li];
data.RemoveAt(li);
--li; // last index (after removal)
int pi = 0; // parent index. start at front of pq
while (true)
{
int ci = pi * 2 + 1; // left child index of parent
if (ci > li)
break; // no children so done
int rc = ci + 1; // right child
if (rc <= li && data[rc].CompareTo(data[ci]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
ci = rc;
if (data[pi].CompareTo(data[ci]) <= 0)
break; // parent is smaller than (or equal to) smallest child so done
T tmp = data[pi];
data[pi] = data[ci];
data[ci] = tmp; // swap parent and child
pi = ci;
}
return frontItem;
}
public T Peek()
{
T frontItem = data[0];
return frontItem;
}
public int Count()
{
return data.Count;
}
public override string ToString()
{
string s = "";
for (int i = 0; i < data.Count; ++i)
s += data[i].ToString() + " ";
s += "count = " + data.Count;
return s;
}
public bool IsConsistent()
{
// is the heap property true for all data?
if (data.Count == 0)
return true;
int li = data.Count - 1; // last index
for (int pi = 0; pi < data.Count; ++pi)
{ // each parent index
int lci = 2 * pi + 1; // left child index
int rci = 2 * pi + 2; // right child index
if (lci <= li && data[pi].CompareTo(data[lci]) > 0)
return false; // if lc exists and it's greater than parent then bad.
if (rci <= li && data[pi].CompareTo(data[rci]) > 0)
return false; // check the right child too.
}
return true; // passed all checks
}
// IsConsistent
}
}STEP Yellow Blue Green Red
0. (0, 0) (1, 0) (2, 0) (3, 0)
1. (0, 1) (0, 0) (2, 1) (2, 0)
2. (1, 1) (0, 1) (2, 2) (1, 0)
3. (2, 1) (0, 2) (2, 3) (0, 0)
4. (3, 1) (1, 2) (3, 3) (0, 1)
5. (3, 0) (2, 2) (3, 2) (1, 1)
6. (2, 0) (3, 2) (3, 1) (2, 1)
7. (2, 1) (3, 1) (3, 0) (2, 2)
8. (2, 2) (3, 0) (2, 0) (3, 2)
9. (1, 2) (2, 0) (1, 0) (3, 3)
10. (0, 2) (1, 0) (0, 0) (2, 3)
11. (0, 3) (1, 1) (0, 1) (1, 3)
12. (1, 3) (2, 1) (0, 2) (1, 2)
13. (2, 3) (2, 2) (0, 3) (0, 2)
14. (3, 3) (2, 3) (1, 3) (0, 3)