KlotskiWithMerge.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,
  MultipleDirections,
}

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 class 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.
  // This is enough to fully define a single simple move.
  public int EmptyCellToCover { get; set; }
  public KlotskiMoveDirection Direction { get; set; }
  // to allow for "merged" moves (and more verbose output),
  // also record information about the number of steps moved, and which piece(s) were moved.
  public int StepCount { get; set; }
  public List<int> PiecesMoved { 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; private set; }

  public KlotskiPuzzleState Parent { get; private set; }

  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)
        {
          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, PiecesMoved = new List<int> { pieceIndex }, Direction = direction, StepCount = totalMove / moveStep };
          yield return new KlotskiPuzzleState(this, moveDone, new KlotskiGridState(GridState.ColumnCount, cellStatesAfterMove), emptyCellsAfterMove);

          // detection of multiple moves that can be done "together" done by caller, not here as originally planned.
          // the caller will ignore duplicate states before attempting a merge.
        }
      }
    }
  }

  static int AllowableMergeType = 1;
  // merge types:
  // 1: try to move multiple pieces the same amount in the same direction as a single move.
  // 2: try to move the same piece in multiple directions as a single move.

  public bool TryMergeWithParent()
  {
    var parentMove = Parent?.MoveFromParent;

    if (parentMove == null)
      return false;
    if (AllowableMergeType == 1 && parentMove.Direction == MoveFromParent.Direction && parentMove.StepCount == MoveFromParent.StepCount)
    {
      // the containing condition allows us to "cheat" by moving one piece 2 step and another piece 1 step but calling it a single "move".
      // thus we must also ensure that our (non-merged) move doesn't move one of the pieces that the parent moved.
      var pieceIndexes = Parent.GridState.FindConnectedPieceIndexes(MoveFromParent.PiecesMoved[0], MoveStep);
      var parentMovedPieceIndexes = parentMove.PiecesMoved.Select(i => i + MoveStep[parentMove.Direction] * parentMove.StepCount);
      if (parentMovedPieceIndexes.Any(pieceIndexes.Contains))
        return false;

      // TODO: consider whether to allow a merged move only if all the pieces involved would be moved by "pushing" the one furthest from the emty cell being covered.
      // This will be complicated, as a 1 x 2 or larger can push two different 1 x 1 (or oppositely-oriented 2x2, etc.)
      // but, if implemented, the tightened rule set wouldn't allow the two different pieces to be considered to have moved together beforehand.
      // The more complicated merge logic would then potentially generate a "double-merge" where our move count is now lower than that of our former parent,
      // which invalidates all sorts of other assumptions implicit in the overall search method.

      MoveFromParent.PiecesMoved.AddRange(parentMove.PiecesMoved);
      MoveFromParent.EmptyCellToCover = parentMove.EmptyCellToCover;
      MoveCount = Parent.MoveCount;
      Parent = Parent.Parent;
      return true;
    }
    else if(AllowableMergeType == 2 && Parent.GridState.FindConnectedPieceIndexes(MoveFromParent.PiecesMoved[0], MoveStep).Contains(parentMove.EmptyCellToCover))
    {
      // TODO: properly reconcile the square identified on the "piece to move" with the cell actually covered.
      // our move may have identified a different square of the same piece as the one moved in the parent move.
      // so the move may end up displayed "wrong".
      MoveFromParent.StepCount += parentMove.StepCount;
      MoveFromParent.PiecesMoved = parentMove.PiecesMoved;
      MoveFromParent.Direction = KlotskiMoveDirection.MultipleDirections;
      MoveCount = Parent.MoveCount;
      Parent = Parent.Parent;
      return true;
    }
    return false;
  }
}


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>();
    Queue<KlotskiPuzzleState> mergedMoveStatesToConsider = new Queue<KlotskiPuzzleState>();
    statesToConsider.Enqueue(startingState);

    int lastDepthSeen = 0;

    while (statesToConsider.Count > 0)
    {
      var currentState = (mergedMoveStatesToConsider.Count > 0 ? mergedMoveStatesToConsider : statesToConsider).Dequeue();
      if (currentState.MoveCount > lastDepthSeen)
      {
        lastDepthSeen = currentState.MoveCount;
        Console.WriteLine($"Processing move {lastDepthSeen}... {statesToConsider.Count} states in queue, {depthDict.Count} possible states reached");
        if (statesToConsider.Count == 11)
        {
          foreach (var printState in statesToConsider)
          {
            var moveInfo = printState.MoveFromParent;
            if (moveInfo == null)
              Console.WriteLine("Starting state:");
            else
              Console.WriteLine($"After move {printState.MoveCount}: piece(s) at {string.Join(",", moveInfo.PiecesMoved)} by {moveInfo.StepCount} {moveInfo.Direction} to cover {moveInfo.EmptyCellToCover}:");
            Console.WriteLine(printState.GridState);
          }
        }
      }
      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)
          {
            var moveInfo = printState.MoveFromParent;
            if (moveInfo == null)
              Console.WriteLine("Starting state:");
            else
              Console.WriteLine($"After move {printState.MoveCount}: piece(s) at {string.Join(",", moveInfo.PiecesMoved)} by {moveInfo.StepCount} {moveInfo.Direction} to cover {moveInfo.EmptyCellToCover}:");
            Console.WriteLine(printState.GridState);
          }
          return;
        }
        else
        {
          (state.TryMergeWithParent() ? mergedMoveStatesToConsider : statesToConsider).Enqueue(state);
          depthDict[state.GridState] = state.MoveCount;
        }
      }
    }
  }
}