Klotski.cs

using System;
using System.Collections.Generic;
using System.Linq;

[Flags]
public enum KlotskiCellState : byte
{
  ConnectedLeft = 1 << KlotskiMoveDirection.Left,
  ConnectedRight = 1 << KlotskiMoveDirection.Right,
  ConnectedUp = 1 << KlotskiMoveDirection.Up,
  ConnectedDown = 1 << KlotskiMoveDirection.Down,
  Empty = 16,
  Fixed = 32, // fixed cells cannot be moved (e.g. attached to outside of grid for non-rectangular puzzles?)
}

public enum KlotskiMoveDirection
{
  Left,
  Right,
  Up,
  Down,
}

public class KlotskiGridState: IEquatable<KlotskiGridState>
{
  static Dictionary<KlotskiCellState, char[]> DisplayText = new Dictionary<KlotskiCellState, char[]>
  {
    { KlotskiCellState.Empty, "      ".ToCharArray() },
    { KlotskiCellState.Fixed, "######".ToCharArray() },
    { 0, "╔═╗╚═╝".ToCharArray() },
    { KlotskiCellState.ConnectedLeft, "══╗══╝".ToCharArray() },
    { KlotskiCellState.ConnectedRight, "╔══╚══".ToCharArray() },
    { KlotskiCellState.ConnectedUp, "║ ║╚═╝".ToCharArray() },
    { KlotskiCellState.ConnectedDown, "╔═╗║ ║".ToCharArray() },
    { KlotskiCellState.ConnectedLeft|KlotskiCellState.ConnectedRight, "══════".ToCharArray() },
    { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedDown, "║ ║║ ║".ToCharArray() },
    { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedLeft, "╝ ║══╝".ToCharArray() },
    { KlotskiCellState.ConnectedUp|KlotskiCellState.ConnectedRight, "║ ╚╚══".ToCharArray() },
    // TODO: other possible connections to allow full range of puzzles!
    // down/left, down/right,
    // combinations of 3 connections (4 possibilities),
    // connected all 4 directions.
  };

  readonly char[] unknownCell = "<?><?>".ToCharArray();


  public KlotskiGridState(int columnCount, KlotskiCellState[] cellStates)
  {
    if (cellStates.Length % columnCount != 0)
      throw new ArgumentOutOfRangeException();
    ColumnCount = columnCount;
    CellStates = cellStates;
  }

  public int ColumnCount { get; }
  public int RowCount => CellStates.Length / ColumnCount;

  public KlotskiCellState[] CellStates { get; }

  public HashSet<int> FindConnectedPieceIndexes(int startIndex, Dictionary<KlotskiMoveDirection, int> moveSteps)
  {
    HashSet<int> resultSet = new HashSet<int> { startIndex };
    HashSet<int> searchSet = new HashSet<int> { startIndex };

    while(searchSet.Count > 0)
    {
      int index = searchSet.First();
      searchSet.Remove(index);

      var cellState = CellStates[index];
      foreach(var step in moveSteps)
      {
        if (((int)cellState & (1 << (int)step.Key)) != 0 && resultSet.Add(index + step.Value))
          searchSet.Add(index + step.Value);
      }
    }
    return resultSet;
  }

  public override string ToString()
  {
    int rowLength = ColumnCount * 3 + 1;
    char[] result = new char[rowLength * RowCount * 2];

    for (int row = 0; row < RowCount; row++)
    {
      for (int col = 0; col < ColumnCount; col++)
      {
        int cellBaseIndex = row * rowLength * 2 + col * 3;
        if (!DisplayText.TryGetValue(CellStates[row * ColumnCount + col], out var cellText))
          cellText = unknownCell;
        Array.Copy(cellText, 0, result, cellBaseIndex, 3);
        Array.Copy(cellText, 3, result, cellBaseIndex + rowLength, 3);
      }
      result[row * rowLength * 2 + rowLength*2 - 1] = '\n';
      result[row * rowLength * 2 + rowLength - 1] = '\n';
    }
    return new string(result);
  }

  public override bool Equals(object obj)
  {
    return base.Equals(obj) || obj is KlotskiGridState other && Equals(other);
  }

  public bool Equals(KlotskiGridState other)
  {
    // don't bother checking ColumnCount - it shouldn't be different in cases we're trying to compare!
    // we compare Length only to avoid potential exceptions.
    var otherCellStates = other.CellStates;
    if (otherCellStates.Length != CellStates.Length)
      return false;
    for (int i = 0; i < CellStates.Length; i++)
      if (CellStates[i] != otherCellStates[i])
        return false;
    return true;
  }

  public override int GetHashCode()
  {
    int result = 0;
    for (int i = 0; i < CellStates.Length; i++)
      result = (result >> 18) ^ (result * 0x1413 + (int)CellStates[i]);
    return result;
  }
}

public struct KlotskiMove
{
  // move parameterised based on the index of the empty cell to cover, and the direction that a piece should be moved to cover it.
  public int EmptyCellToCover { get; set; }
  public KlotskiMoveDirection Direction { get; set; }
}

public class KlotskiPuzzleState
{
  private KlotskiPuzzleState(KlotskiGridState gridState)
  {
    GridState = gridState;
  }

  public KlotskiGridState GridState { get; }

  public KlotskiPuzzleState(params string[] lines)
  {
    int rows = lines.Length;
    if (rows == 0)
      throw new ArgumentOutOfRangeException();
    int cols = lines[0].Length;
    if (lines.Any(line => line.Length != cols))
      throw new ArgumentOutOfRangeException();

    EmptyCellIndex = new List<int>();
    // add an extra column and 2 extra rows.
    // this way we don't need to do "if outside grid OR another cell" etc.
    var initialCellStates = new KlotskiCellState[(rows + 2) * (cols + 1)];
    for (int row = -1; row <= rows; row++)
    {
      for (int col = 0; col <= cols; col++)
      {
        int index = (cols + 1) * (row + 1) + col;
        if (row < 0 || row >= rows || col >= cols || lines[row][col] == '#')
          initialCellStates[index] = KlotskiCellState.Fixed;
        else if (lines[row][col] is var c && c == ' ')
        {
          initialCellStates[index] = KlotskiCellState.Empty;
          EmptyCellIndex.Add(index);
        }
        else
        {
          initialCellStates[index] = 0;
          if (row > 0 && lines[row - 1][col] == c)
            initialCellStates[index] |= KlotskiCellState.ConnectedUp;
          if (row < rows - 1 && lines[row + 1][col] == c)
            initialCellStates[index] |= KlotskiCellState.ConnectedDown;
          if (col > 0 && lines[row][col - 1] == c)
            initialCellStates[index] |= KlotskiCellState.ConnectedLeft;
          if (col < cols - 1 && lines[row][col + 1] == c)
            initialCellStates[index] |= KlotskiCellState.ConnectedRight;
        }
      }
    }
    GridState = new KlotskiGridState(cols + 1, initialCellStates);
    MoveStep = new Dictionary<KlotskiMoveDirection, int>
    {
      { KlotskiMoveDirection.Left, -1 },
      { KlotskiMoveDirection.Right, 1 },
      { KlotskiMoveDirection.Up, -(cols+1) },
      { KlotskiMoveDirection.Down, (cols+1) },
    };
    Console.WriteLine(GridState);
  }

  List<int> EmptyCellIndex { get; }

  public int MoveCount { get; }

  public KlotskiPuzzleState Parent { get; }

  public KlotskiMove MoveFromParent { get; }

  private KlotskiPuzzleState(KlotskiPuzzleState parent, KlotskiMove move, KlotskiGridState gridState, List<int> emptyCells)
    : this(gridState)
  {
    Parent = parent;
    MoveStep = parent.MoveStep;
    MoveCount = parent.MoveCount + 1;
    MoveFromParent = move;
    EmptyCellIndex = emptyCells;
  }

  static readonly KlotskiMoveDirection[] AllMoveDirections = new[] { KlotskiMoveDirection.Left, KlotskiMoveDirection.Right, KlotskiMoveDirection.Up, KlotskiMoveDirection.Down };

  Dictionary<KlotskiMoveDirection, int> MoveStep { get; }

  public IEnumerable<KlotskiPuzzleState> GetStatesAfterValidMoves()
  {
    var originalGrid = GridState.CellStates;
    foreach(int index in EmptyCellIndex)
    {
      foreach(var direction in AllMoveDirections)
      {
        int moveStep = MoveStep[direction];
        int searchStep = -moveStep;

        // Identify which piece to attempt to move.
        int pieceIndex = index;
        while (originalGrid[pieceIndex] == KlotskiCellState.Empty)
          pieceIndex += searchStep;

        var primaryPieceState = originalGrid[pieceIndex];

        if ((primaryPieceState & KlotskiCellState.Fixed) != 0)
          continue; // we can't move a fixed piece (or wall).

        // if a piece can be moved, but is wide enough to cover an adjacent empty cell, we'll find the same move from
        // both (or all) empty cells.
        // Avoid this by considering only the lowermost (for a left/right move) or leftmost (for an up/down) move of a continuously connected shape
        // before we bother to find the entire shape.
        // For complex shapes, this optimisation may fail, but we'll generate two moves with the same result grid and ignore one anyway.

        if ((direction == KlotskiMoveDirection.Left || direction == KlotskiMoveDirection.Right) &&
            (primaryPieceState & KlotskiCellState.ConnectedDown) != 0)
          continue;
        if ((direction == KlotskiMoveDirection.Up || direction == KlotskiMoveDirection.Down) &&
            (primaryPieceState & KlotskiCellState.ConnectedLeft) != 0)
          continue;

        // now identify all connected piece indexes, to see if it is possible to move the selected piece.

        HashSet<int> pieceIndexes = GridState.FindConnectedPieceIndexes(pieceIndex, MoveStep);

        HashSet<int> movedPieceIndexes = pieceIndexes;
        bool moveIsValid = true;
        int totalMove = 0;
        while(moveIsValid && !movedPieceIndexes.Contains(index))
        {
          totalMove += moveStep;
          movedPieceIndexes = new HashSet<int>(movedPieceIndexes.Select(i => i + moveStep));
          moveIsValid = movedPieceIndexes.All(i => pieceIndexes.Contains(i) || EmptyCellIndex.Contains(i));
        }
        if (!moveIsValid)
          continue;
        KlotskiCellState[] cellStatesAfterMove = new KlotskiCellState[originalGrid.Length];
        Array.Copy(originalGrid, cellStatesAfterMove, cellStatesAfterMove.Length);

        // first blank the piece's original location.
        foreach (int i in pieceIndexes)
          cellStatesAfterMove[i] = KlotskiCellState.Empty;

        // the copy the piece to its new location
        foreach (int i in pieceIndexes)
          cellStatesAfterMove[i + totalMove] = originalGrid[i];

        List<int> emptyCellsAfterMove = new List<int>(EmptyCellIndex.Count);
        foreach (int i in pieceIndexes.Concat(EmptyCellIndex))
          if (!movedPieceIndexes.Contains(i))
            emptyCellsAfterMove.Add(i);

        var moveDone = new KlotskiMove { EmptyCellToCover = index, Direction = direction };
        yield return new KlotskiPuzzleState(this, moveDone, new KlotskiGridState(GridState.ColumnCount, cellStatesAfterMove), emptyCellsAfterMove);
      }
    }
  }
}


public class Problem
{

  HashSet<KlotskiGridState> ObservedGridStates { get; }

  static KlotskiPuzzleState startingState = new KlotskiPuzzleState(
    "BAAAC",
    "BBDCC",
    "EEDFF",
    "GGHII",
    "JJHKK",
    "L   M");


  static public void Main()
  {
    var depthDict = new Dictionary<KlotskiGridState, int>() { { startingState.GridState, 0 } };

    Queue<KlotskiPuzzleState> statesToConsider = new Queue<KlotskiPuzzleState>();
    statesToConsider.Enqueue(startingState);

    int lastDepthSeen = 0;

    while (statesToConsider.Count > 0)
    {
      var currentState = statesToConsider.Dequeue();
      if (currentState.MoveCount > lastDepthSeen)
      {
        lastDepthSeen = currentState.MoveCount;
        Console.WriteLine($"Processing move {lastDepthSeen}... {statesToConsider.Count} states in queue, {depthDict.Count} possible states reached");
      }
      foreach (var state in currentState.GetStatesAfterValidMoves())
      {
        if (depthDict.TryGetValue(state.GridState, out int lastDepth))
        {
          // Console.WriteLine($"Duplicate of a state reached in {lastDepth} moves");
        }
        else if(state.GridState.CellStates[6 * state.GridState.ColumnCount + 2] == (KlotskiCellState.ConnectedLeft | KlotskiCellState.ConnectedRight))
        {
          for (var printState = state; printState != null; printState = printState.Parent)
          {
            Console.WriteLine($"After move {printState.MoveCount}: {printState.MoveFromParent.Direction} to {printState.MoveFromParent.EmptyCellToCover}:");
            Console.WriteLine(printState.GridState);
          }
          return;
        }
        else
        {
          depthDict[state.GridState] = state.MoveCount;
          statesToConsider.Enqueue(state);
        }
      }
    }
  }
}