SquareSwap4Inverted.cs

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

// SquareSwap4Inverted.cs
// used for a breadth-first exhaustive search for an answer at
// https://puzzling.stackexchange.com/questions/111932/can-you-reactivate-a-4x4-magic-square
// still "a work in progress" so not very tidied up...


using IntCode = System.UInt64;

public struct CellState : IEquatable<CellState>
{
  public byte Value { get; set; }
  public byte MovesLeft { get; set; }

  public override bool Equals(object obj)
  {
    return obj is CellState other && Equals(other);
  }

  public bool Equals(CellState other)
  {
    return Value == other.Value && MovesLeft == other.MovesLeft;
  }

  public override int GetHashCode()
  {
    return Value * 256 + MovesLeft;
  }

  public bool IsSwapValid(CellState other)
  {
    if (Value > other.Value)
      return MovesLeft >= other.Value && other.MovesLeft > 0;
    else
      return other.MovesLeft >= Value && MovesLeft > 0;
  }
}





public class GridState : IEquatable<GridState>
{
  private static CellState[] MakeCellStates(params string[] initialRows)
  {
    int columnCount = initialRows[0].Length;
    var result = new CellState[initialRows.Length * columnCount];
    for (int row = 0; row < initialRows.Length; row++)
    {
      if (initialRows[row].Length != columnCount)
        throw new ArgumentException("All rows must be the same length", nameof(initialRows));
      for (int col = 0; col < columnCount; col++)
      {
        int value = _mainNumbers.IndexOf(initialRows[row][col]);
        if (value < 0)
          throw new ArgumentException("Row contained invalid character: " + initialRows[row]);

        result[row * columnCount + col] = new CellState { Value = (byte)value, MovesLeft = (byte)value };
      }
    }
    return result;
  }

  public GridState(params string[] initialRows)
    : this(initialRows[0].Length, MakeCellStates(initialRows))
  { }

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

  public int SetMagicConstant()
  {
    MagicConstant = 0;
    if (RowCount == ColumnCount)
    {
      int totalValues = CellStates.Sum(c => (int)c.Value);
      if (totalValues % ColumnCount == 0)
        MagicConstant = totalValues / ColumnCount;
    }
    return MagicConstant;
  }

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

  private static int MagicConstant { get; set; }

  public CellState[] CellStates { get; }

  public CellState this[int row, int col]
  {
    get
    {
      if (row < 0 || row > RowCount)
        throw new ArgumentOutOfRangeException(nameof(row));
      if (col < 0 || col > ColumnCount)
        throw new ArgumentOutOfRangeException(nameof(col));
      return CellStates[row * ColumnCount + col];
    }
  }

  private static readonly string _mainNumbers = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ#";
  private static readonly string _subscriptNumbers = "₀₁₂₃₄₅₆₇₈₉₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊₊";

  public override string ToString()
  {
    int rowLength = ColumnCount * 5;

    StringBuilder result = new StringBuilder(rowLength * RowCount * 2);

    for (int row = 0; row < RowCount; row++)
    {
      for (int col = 0; col < ColumnCount; col++)
      {
        var state = CellStates[row * ColumnCount + col];
        result.Append(new[] { ' ', _mainNumbers[state.Value], _subscriptNumbers[state.MovesLeft], ' ', col < ColumnCount - 1 ? '|' : '\n' });
      }
      if (row < RowCount - 1)
      {
        result.Append(string.Join("+", Enumerable.Repeat("----", ColumnCount)));
        result.Append("\n");
      }
    }
    return result.ToString();
  }

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

  public bool Equals(GridState other)
  {
    var otherCellStates = other.CellStates;
    if (otherCellStates.Length != CellStates.Length)
      return false;
    for (int i = 0; i < CellStates.Length; i++)
      if (!CellStates[i].Equals(otherCellStates[i]))
        return false;
    return true;
  }

  public bool EqualValues(GridState other)
  {
    var otherCellStates = other.CellStates;
    if (otherCellStates.Length != CellStates.Length)
      return false;
    for (int i = 0; i < CellStates.Length; i++)
      if (!CellStates[i].Value.Equals(otherCellStates[i].Value))
        return false;
    return true;
  }

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

  public int TotalMovesLeft => CellStates.Sum(c => c.MovesLeft);

  public GridState GetStateAfterSwap(SwapInfo swapInfo)
  {
    CellState stateFrom = this[swapInfo.rowFrom, swapInfo.colFrom];
    CellState stateTo = this[swapInfo.rowTo, swapInfo.colTo];

    if (!stateFrom.IsSwapValid(stateTo))
      throw new ArgumentOutOfRangeException(nameof(swapInfo), $"Invalid swap R{swapInfo.rowFrom + 1}C{swapInfo.colFrom + 1} with R{swapInfo.rowTo + 1}C{swapInfo.colTo + 1} for grid:\n{this.ToString()}");

    var cellStatesAfter = CellStates.ToArray();

    CellState stateFromAfter = new CellState { Value = (byte)stateTo.Value, MovesLeft = (byte)(stateTo.MovesLeft - (stateTo.Value > stateFrom.Value ? stateFrom.Value : 1)) };
    CellState stateToAfter = new CellState { Value = (byte)stateFrom.Value, MovesLeft = (byte)(stateFrom.MovesLeft - (stateFrom.Value > stateTo.Value ? stateTo.Value : 1)) };

    cellStatesAfter[swapInfo.rowFrom * ColumnCount + swapInfo.colFrom] = stateFromAfter;
    cellStatesAfter[swapInfo.rowTo * ColumnCount + swapInfo.colTo] = stateToAfter;

    return new GridState(ColumnCount, cellStatesAfter);
  }

  public bool IsSwapValid(SwapInfo info) => this[info.rowFrom, info.colFrom].IsSwapValid(this[info.rowTo, info.colTo]);

  public bool IsOrdered()
  {
    for (int i = 0; i < CellStates.Length - 1; i++)
      if (CellStates[i].Value > CellStates[i + 1].Value)
        return false;
    return true;
  }

  public bool IsMagic()
  {
    if (MagicConstant == 0)
      throw new InvalidOperationException("Cannot be magic - wrong dimensions or total...");
    int count = ColumnCount;
    return Enumerable.Range(0, count).Sum(i => (int)this[i, i].Value) == MagicConstant &&
           Enumerable.Range(0, count).Sum(i => (int)this[count - 1 - i, i].Value) == MagicConstant &&
           Enumerable.Range(0, count).All(i => Enumerable.Range(0, count).Sum(col => (int)this[i, col].Value) == MagicConstant &&
                                               Enumerable.Range(0, count).Sum(row => (int)this[row, i].Value) == MagicConstant);
  }


  private byte[] _valueBytes;
  private byte[] GetOrCacheValueBytes()
  {
    return _valueBytes ?? (_valueBytes = CellStates.Select(c => c.Value).ToArray());
  }

  // cached on target, which doesn't change. Effectively this could be static.
  private byte[] _movesToFarCorner;
  private byte[] GetOrCacheMovesToFarCorner()
  {
    return _movesToFarCorner ?? (_movesToFarCorner = CreateMovesToFarCornerArray());
  }
  private byte[] CreateMovesToFarCornerArray()
  {
    byte[] result = new byte[CellStates.Length];

    for (int i = 0; i < CellStates.Length; i++)
    {
      int row = i / ColumnCount;
      int col = i % ColumnCount;
      result[i] = (byte)(Math.Max(row, RowCount - 1 - row) + Math.Max(col, ColumnCount - 1 - col));
    }
    return result;
  }


  // returns false if any of the cells has insufficient swaps remaining to reach the correct position in the target.
  // this ignores whether valid swaps are possible (e.g. a blocking cell with no moves in between)
  public bool IsTargetWithinReach(GridState target) => IsTargetWithinReach(target.GetOrCacheValueBytes(), target.GetOrCacheMovesToFarCorner());

  private bool IsTargetWithinReach(byte[] targetValues, byte[] movesToFarCorner)
  {
    if (targetValues.Length != CellStates.Length)
      throw new ArgumentException($"Given target is not compatible - {targetValues.Length} values instead of {CellStates.Length}");

    for (int i = 0; i < CellStates.Length; i++)
    {
      byte movesLeft = CellStates[i].MovesLeft;
      if (movesLeft == 0 && targetValues[i] != CellStates[i].Value)
        return false;
      if (movesLeft < movesToFarCorner[i])
      {
        byte value = CellStates[i].Value;
        int targetIndex = Array.IndexOf(targetValues, value);
        int row = i / ColumnCount;
        int col = i % ColumnCount;
        int targetRow = targetIndex / ColumnCount;
        int targetCol = targetIndex % ColumnCount;
        int movesNeeded = Math.Abs(targetRow - row) + Math.Abs(targetCol - col);
        if (movesNeeded > movesLeft)
          return false;
        // TODO: consider checking if a move that is "exactly" possible would need to pass through an immovable cell?
      }
    }
    // nothing "out of reach" with the simple checks done here.
    return true;
  }
}


public struct SwapInfo : IEquatable<SwapInfo>
{
  public byte rowFrom { get; set; }
  public byte colFrom { get; set; }
  public byte rowTo { get; set; }
  public byte colTo { get; set; }

  static Dictionary<SwapInfo, byte> _toByteDict = new Dictionary<SwapInfo, byte>(256);
  static List<SwapInfo> _knownValidSwaps = new List<SwapInfo>(256); // only because dict isn't indexable...
  static System.Threading.ReaderWriterLockSlim _byteDictLock = new System.Threading.ReaderWriterLockSlim();

  public byte CompressToByte()
  {
    if (!_toByteDict.TryGetValue(this, out byte result))
    {
      // Attention - this is a potential major bug if the same pattern used anywhere else... Dictionary is not thread safe.
      // However, we avoid hash bucket re-organisation by pre-allocating 256 entries (enough for anything which can be converted to/from byte)
      // and in this specific case, the lock isn't even needed because we're really doing all writing from the single thread that
      // handles finding swaps from the starting position, but kept lock because
      // later tweaks to the program might potentially make the lock necessary...
      // the alternatives of concurrentdictionary or readerwriterlockslim would add more overhead for many millions of calls.
      lock (_toByteDict)
        if (!_toByteDict.TryGetValue(this, out result))
        {
          if (_toByteDict.Count > 255)
            throw new InvalidOperationException("_toByteDict is full. refactoring required!");
          result = (byte)_toByteDict.Count;
          Console.WriteLine($"Allocated byte {result} to swap {this}");
          _toByteDict.Add(this, result);
          _knownValidSwaps.Add(this);
        }
    }
    return result;
  }

  public static SwapInfo ExpandFromByte(byte compressed)
  {
    return _knownValidSwaps[compressed];
  }


  public override bool Equals(object obj)
  {
    return obj is SwapInfo other && Equals(other);
  }

  public bool Equals(SwapInfo other)
  {
    return rowFrom == other.rowFrom && colFrom == other.colFrom && rowTo == other.rowTo && colTo == other.colTo ||
           rowFrom == other.rowTo && colFrom == other.colTo && rowTo == other.rowFrom && colTo == other.colFrom;
  }

  public override int GetHashCode()
  {
    return Math.Min(rowFrom, rowTo) + Math.Max(rowFrom, rowTo) * 64 + Math.Min(colFrom, colTo) * 4096 + Math.Max(colFrom, colTo) * 262144;
  }

  public override string ToString()
  {
    return $"R{rowFrom + 1}C{colFrom + 1}<>R{rowTo + 1}C{colTo + 1}";
  }
}


public class PuzzleState
{
  public static PuzzleState CreateStartingState(GridState gridState) => new PuzzleState(gridState);

  private PuzzleState(GridState gridState, params SwapInfo[] movesDone)
  {
    GridState = gridState;
    MovesDone = movesDone;
  }

  public GridState GridState { get; private set; }

  public PuzzleState(params string[] lines)
    : this(new GridState(lines))
  {
  }

  public PuzzleState(CompressedPuzzleState compressed, GridState gridState)
    : this(gridState, compressed.MovesDone)
  { }

  // parent and move count were never used, so removed these.

  public SwapInfo[] MovesDone { get; }

  private static SwapInfo[] ConcatSwapInfo(PuzzleState parent, SwapInfo move)
  {
    int parentLength = parent.MovesDone.Length;
    var result = new SwapInfo[parentLength + 1];
    Array.Copy(parent.MovesDone, result, parentLength);
    result[parentLength] = move;
    return result;
  }

  private PuzzleState(PuzzleState parent, SwapInfo move, GridState gridState)
    : this(gridState, ConcatSwapInfo(parent, move))
  {
    // bug in previous version before major refactoring left out this (now redundant!) line
    AllowWrapAround = parent.AllowWrapAround;
  }

  public bool IsSwapValid(SwapInfo info) => GridState.IsSwapValid(info);

  public bool AllowWrapAround { get; set; } = true;

  public IEnumerable<PuzzleState> GetStatesAfterValidMoves()
  {
    int fromRowLimit = AllowWrapAround ? GridState.RowCount : (GridState.RowCount - 1);
    int fromColLimit = AllowWrapAround ? GridState.ColumnCount : (GridState.ColumnCount - 1);
    for (int fromRow = 0; fromRow < fromRowLimit; fromRow++)
    {
      int toNextRow = (fromRow + 1) % GridState.RowCount;
      for (int fromCol = 0; fromCol < GridState.ColumnCount; fromCol++)
      {
        CellState fromState = GridState[fromRow, fromCol];
        if (fromState.MovesLeft < 1)
          continue;

        CellState toState = GridState[toNextRow, fromCol];
        if (fromState.IsSwapValid(toState))
        {
          var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)fromCol, rowTo = (byte)toNextRow };
          yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
        }
      }
    }
    for (int fromCol = 0; fromCol < fromColLimit; fromCol++)
    {
      int toNextCol = (fromCol + 1) % GridState.ColumnCount;
      for (int fromRow = 0; fromRow < GridState.RowCount; fromRow++)
      {
        CellState fromState = GridState[fromRow, fromCol];
        if (fromState.MovesLeft < 1)
          continue;

        CellState toState = GridState[fromRow, toNextCol];
        if (fromState.IsSwapValid(toState))
        {
          var swapInfo = new SwapInfo { colFrom = (byte)fromCol, rowFrom = (byte)fromRow, colTo = (byte)toNextCol, rowTo = (byte)fromRow };
          yield return new PuzzleState(this, swapInfo, GridState.GetStateAfterSwap(swapInfo));
        }
      }
    }
  }

  static GridState targetState = new GridState("867G", "143A", "9D2E", "BC5F");
  // static GridState targetState = new GridState("1FE4", "AB85", "769C", "G32D"); // test target state similar to "given" magic square

  public bool IsTargetState => GridState.EqualValues(targetState);


  public bool CheckCompatibleWithTargetState()
  {
    // a simple check - assume all squares can move the number of moves remaining...
    // so those with at least 6 moves remaining can move anywhere in the grid.
    // with 5 moves remaining in a corner, cannot move to opposite corner
    // ...
    // with 0 moves remaining anywhere, must stay in current position.

    return GridState.IsTargetWithinReach(targetState);
  }


  public static IEnumerable<PuzzleState> GenerateMagicSquares(int columnCount)
  {
    int limit = columnCount * columnCount;
    int magicConstant = (limit + 1) * columnCount / 2;
    // copy of set that is NOT modified
    HashSet<byte> initialValuesAvailable = new HashSet<byte>(Enumerable.Range(1, limit).Select(i => (byte)i));
    // copy of set that is modified in first iteration
    HashSet<byte> valuesAvailableAfter1 = new HashSet<byte>(initialValuesAvailable);
    var resultValues = new byte[limit];

    Console.WriteLine($"Looking for magic squares with {columnCount} columns, magicConstant={magicConstant}");

/*    Console.WriteLine("Precheck debug!");
    foreach (var debugLine in GetPossibleMagicRows(new byte[] { 8, 0, 0, 1 }, 34, new byte[] { 13, 2, 12, 7 }))
      Console.WriteLine($"Debug: [{string.Join(",", debugLine)}]");

    yield break;*/


    // first populate the leading diagonal
    foreach (var diag1 in GetPossibleMagicRows(new byte[columnCount], magicConstant, initialValuesAvailable))
    {
      //Console.WriteLine($"Leading diagonal: [{string.Join(",", diag1)}]");

      valuesAvailableAfter1.ExceptWith(diag1);
      for (int i = 0; i < columnCount; i++)
        resultValues[i * (1 + columnCount)] = diag1[i];
      var diag2Template = new byte[columnCount];
      if (columnCount % 2 == 1) // copy centre cell to other diagonal if needed.
        diag2Template[columnCount / 2] = diag1[columnCount / 2];

      // for each possible leading diagonal populate all possible trailing diagonals
      foreach (var diag2 in GetPossibleMagicRows(diag2Template, magicConstant, valuesAvailableAfter1))
      {
        //Console.WriteLine($"Trailing diagonal: [{string.Join(",", diag2)}]");
        // to avoid complication of selectively including or excluding centre cell,
        // just make a new hashset every time.
        var valuesAvailableAfter2 = new HashSet<byte>(valuesAvailableAfter1);
        valuesAvailableAfter2.ExceptWith(diag2);
        for (int i = 0; i < columnCount; i++)
          resultValues[(i + 1) * (columnCount - 1)] = diag2[i];

        var valuesAvailableAfterCol1 = new HashSet<byte>(valuesAvailableAfter2);
        var firstColumnTemplate = new byte[columnCount];
        firstColumnTemplate[0] = resultValues[0];
        firstColumnTemplate[columnCount - 1] = resultValues[columnCount * (columnCount - 1)];
        foreach(var firstColumn in GetPossibleMagicRows(firstColumnTemplate, magicConstant, valuesAvailableAfter2))
        {
          //Console.WriteLine($"First column: [{string.Join(",", firstColumn)}]");
          for (int i = 1; i < columnCount - 1; i++)
          {
            valuesAvailableAfterCol1.Remove(firstColumn[i]);
            resultValues[i * columnCount] = firstColumn[i];
          }

          // now we have the two main diagonals, and the first column, all adding up to magic constant.
          // fill in all rows except the top one...
          if (columnCount > 5)
            // for 5 or more columns, a separate "fill rows" function that may need to check more than one possibility per row is needed...
            // but initial implementation only needs 4, so we'll skip implementation of that!
            throw new NotImplementedException();
          else
          {
            // fast path - middle 2 rows have only 1 empty cell, so we either have a possible magic row or we don't.
            // so can use SingleOrDefault as a shortcut to nested loops or recursion.
            bool resultOk = true;
            var valuesAvailableAfterRows = new HashSet<byte>(valuesAvailableAfterCol1);
            var resultValuesAfterRows = resultValues.ToArray();
            var rowValues = new byte[columnCount];
            for (int i = 1; i < columnCount - 1 && resultOk; i++)
            {
              Array.Copy(resultValuesAfterRows, i * columnCount, rowValues, 0, columnCount);
              var rowValuesFull = GetPossibleMagicRows(rowValues, magicConstant, valuesAvailableAfterRows).SingleOrDefault();
              if (rowValuesFull != null)
              {
                //Console.WriteLine($"row {i}: [{string.Join(",", rowValuesFull)}]");
                Array.Copy(rowValuesFull, 0, resultValuesAfterRows, i * columnCount, columnCount);
                valuesAvailableAfterRows.ExceptWith(rowValuesFull);
              }
              else
                resultOk = false;
            }
            if (resultOk)
            {
              // final row has 2 empty cells, so consider each possibility for filling them...
              Array.Copy(resultValuesAfterRows, (columnCount - 1) * columnCount, rowValues, 0, columnCount);
              foreach (var finalRow in GetPossibleMagicRows(rowValues, magicConstant, valuesAvailableAfterRows))
              {
                //Console.WriteLine($"final row: [{string.Join(",", finalRow)}]");
                Array.Copy(finalRow, 0, resultValuesAfterRows, (columnCount - 1) * columnCount, columnCount);
                var valuesAvailableForTopRow = valuesAvailableAfterRows.Except(finalRow).ToList();

                // only top and bottom rows remain, with first and last column complete.
                // after setting bottom row, magic square property will ensure that any arrangement of the remaining values
                // is valid for the top row, but are they good for the columns?
                if (valuesAvailableForTopRow.Count != columnCount - 2)
                  throw new InvalidOperationException($"Something went wrong - there should be exactly {columnCount} values remaining now, but I found {valuesAvailableForTopRow.Count}!");

                var columnValues = new byte[columnCount];
                bool columnsOk = true;
                for (int i = 1; i < columnCount - 1 && columnsOk; i++)
                {
                  for (int row = 1; row < columnCount; row++)
                    columnValues[row] = resultValuesAfterRows[row * columnCount + i];
                  columnValues[0] = 0;
                  var columnValuesFull = GetPossibleMagicRows(columnValues, magicConstant, valuesAvailableForTopRow).SingleOrDefault();
                  if (columnValuesFull != null)
                  {
                    resultValuesAfterRows[i] = columnValues[0];
                    valuesAvailableForTopRow.Remove(resultValuesAfterRows[i]);
                  }
                  else
                    columnsOk = false;
                }
                if (columnsOk)
                {
                  // yay! we found a magic square. Now convert to PuzzleState.
                  yield return new PuzzleState(new GridState(columnCount, resultValuesAfterRows.Select(v => new CellState { Value = v, MovesLeft = v }).ToArray()));
                }
              }
            }
          }

          for (int i = 1; i < columnCount - 1; i++)
            valuesAvailableAfterCol1.Add(firstColumn[i]);
            // resultValues[i * columnCount] = 0; // not needed because nothing checks value of this cell within this function.
        }

      }

      // re-add leading diagonal so that the same hashset can be re-used for next iteration.
      valuesAvailableAfter1.UnionWith(diag1);
    }
  }

  // NB caller should expect rowTemplate may be corrupted, but must not modify the array contents itself!
  // and the same object will usually be returned multiple times with different values (and may be the same object as rowTemplate)
  private static IEnumerable<byte[]> GetPossibleMagicRows(byte[] rowTemplate, int magicConstant, ICollection<byte> valuesAvailable)
  {
    //Console.WriteLine($"GetPossibleMagicRows([{string.Join(",", rowTemplate)}], {magicConstant}, [{string.Join(",", valuesAvailable)}]");
    int templateTotal = 0;
    int[] emptyIndex = new int[rowTemplate.Length];
    int emptyCount = 0;
    for (int i = 0; i < rowTemplate.Length; i++)
    {
      byte value = rowTemplate[i];
      templateTotal += value;
      if (value == 0)
        emptyIndex[emptyCount++] = i;
      else if (valuesAvailable.Contains(value))
        throw new ArgumentException("valuesAvailable mentions values found in rowTemplate!");
    }

    // from this point, we're free to "corrupt" the empty cells of row template, and re-use it as a return value.
    int missingTotal = magicConstant - templateTotal;

    switch (emptyCount)
    {
      case 0: throw new ArgumentException($"Row template didn't have any empty numbers: {string.Join(",", rowTemplate)}]");

      case 1:
        // very fast path - our missing number can be calculated directly.
        byte missingValue = (byte)missingTotal;
        if (valuesAvailable.Contains(missingValue))
        {
          rowTemplate[emptyIndex[0]] = missingValue;
          yield return rowTemplate;
        }
        break;

      case 2:
        // fast path - final 2 numbers to be determined together
        // loop will have no iterations if (missingTotal >= 3), so no explicit check needed
        for (byte lowerValue = 1; lowerValue < (missingTotal + 1) / 2; lowerValue++)
        {
          if (!valuesAvailable.Contains(lowerValue))
            continue;
          byte upperValue = (byte)(missingTotal - lowerValue);
          if (!valuesAvailable.Contains(upperValue))
            continue;
          rowTemplate[emptyIndex[0]] = lowerValue;
          rowTemplate[emptyIndex[1]] = upperValue;
          yield return rowTemplate;
          rowTemplate[emptyIndex[0]] = upperValue;
          rowTemplate[emptyIndex[1]] = lowerValue;
          yield return rowTemplate;
        }
        break;

      default:
        // pick any available value for first cell, and let the recursive call deal with the totals...
        foreach (byte nextValue in valuesAvailable)
        {
          // create new copy of row template for recursive call, which recursive call will corrupt
          // then next iteration can have a fresh copy, without having to explicitly re-empty the empty cells.
          var nextRowTemplate = rowTemplate.ToArray();
          nextRowTemplate[emptyIndex[0]] = nextValue;
          var nextValuesAvailable = new HashSet<byte>(valuesAvailable);
          nextValuesAvailable.Remove(nextValue);
          foreach (var result in GetPossibleMagicRows(nextRowTemplate, magicConstant, nextValuesAvailable))
            yield return result;
        }
        break;
    }
  }


  public IEnumerable<SwapInfo> GetSwaps()
  {
    return MovesDone;
  }
}

public struct CompressedGridState4 : IEquatable<CompressedGridState4>
{
  public static implicit operator CompressedGridState4(GridState source) => new CompressedGridState4(source);
  public static implicit operator GridState(CompressedGridState4 source) => source.GetGridState();

  // thoretically, we only "need" just under 96 bits integer, but code for that seems unlikely to be much of an improvement...
  // limit is based on 16! * 17!
  UInt64 _compressedData1;
  UInt64 _compressedData2;

  public CompressedGridState4(GridState source)
  {
    if (source.ColumnCount != 4 || source.CellStates.Length != 16)
      throw new InvalidOperationException("This compression function assumes a 4 x 4 grid containing precisely the numbers 1-16");

    var cellStates = source.CellStates;
    UInt64 multiplier1 = 1;
    UInt64 multiplier2 = 1;
    _compressedData1 = 0;
    _compressedData2 = 0;

    List<int> possiblePositions = Enumerable.Range(0, 16).ToList();

    for (uint i = 1; i <= 16; i++)
    {
      // find index of value i
      int pos = 0;
      while (cellStates[pos].Value != i)
      {
        if (pos >= cellStates.Length - 1)
          throw new InvalidOperationException($"Value {i} not found in grid state");
        else
          pos++;
      }
      int posIndex = possiblePositions.IndexOf(pos);
      if (posIndex == -1)
        throw new InvalidOperationException($"Value {i} found at position {pos} which isn't possible! Possible: [{string.Join(",", possiblePositions)}]");

      _compressedData1 += multiplier1 * (uint)posIndex;
      multiplier1 *= (uint)possiblePositions.Count;

      possiblePositions.RemoveAt(posIndex);

      _compressedData2 += multiplier2 * (uint)cellStates[pos].MovesLeft;
      multiplier2 *= i + 1;

      //Console.WriteLine($"Compression diagnostic: i={i}, pos={pos} index {posIndex}, moves = {cellStates[pos].MovesLeft}, multiplier = {multiplier}, data = {_compressedData}");
    }
  }

  public GridState GetGridState()
  {
    var cellStates = new CellState[16];
    UInt64 multiplier1 = 1;
    UInt64 multiplier2 = 1;

    List<int> possiblePositions = Enumerable.Range(0, 16).ToList();

    for (byte i = 1; i <= 16; i++)
    {
      UInt64 nextMultiplier1 = multiplier1 * (uint)possiblePositions.Count;
      int posIndex = (int)(_compressedData1 % nextMultiplier1 / multiplier1);
      int pos = possiblePositions[posIndex];
      possiblePositions.RemoveAt(posIndex);

      multiplier1 = nextMultiplier1;

      UInt64 nextMultiplier2 = multiplier2 * ((uint)i + 1);
      byte movesLeft = (byte)(_compressedData2 % nextMultiplier2 / multiplier2);
      multiplier2 = nextMultiplier2;

      cellStates[pos] = new CellState { Value = i, MovesLeft = movesLeft };

      //Console.WriteLine($"Decompression diagnostic: i={i}, pos={pos} index {posIndex}, moves = {cellStates[pos].MovesLeft}, multiplier = {multiplier}, data = {_compressedData}");
    }

    return new GridState(4, cellStates);
  }

  public override bool Equals(object obj)
  {
    return base.Equals(obj) || obj is CompressedGridState4 other && Equals(other) || obj is GridState otherExpanded && GetGridState().Equals(otherExpanded);
  }

  public bool Equals(CompressedGridState4 other)
  {
    return _compressedData2 == other._compressedData2 && _compressedData1 == other._compressedData1;
  }

  public override int GetHashCode()
  {
    return _compressedData1.GetHashCode() + _compressedData2.GetHashCode();
  }

}


public struct CompressedPuzzleState
{
  public static implicit operator CompressedPuzzleState(PuzzleState source) => new CompressedPuzzleState(source);

  public CompressedPuzzleState(PuzzleState source)
  {
    byte[] compressedMovesDone = source.MovesDone.Select(m => m.CompressToByte()).ToArray();
    // now further compress the byte array into an int...
    _compressedState = MakeCompressedState(compressedMovesDone);
  }

  public static int ShortCodeCount => ShortCodesDict.Count;

  static Dictionary<IntCode, UInt32> ShortCodesDict { get; } = new Dictionary<IntCode, uint>();
  static List<IntCode> ShortCodesList { get; } = new List<IntCode>();

  static private UInt32 AllocateShortCode(IntCode compressedState)
  {
    UInt32 result;
    lock (ShortCodesDict)
    {
      if (!ShortCodesDict.TryGetValue(compressedState, out result))
      {
        ShortCodesDict.Add(compressedState, result = (UInt32)ShortCodesDict.Count);
        ShortCodesList.Add(compressedState);
        //Console.WriteLine($"Allocated short code {result} for swaps: {string.Join(", ", GetMovesFromCompressedState(compressedState))}");
      }
    }
    return result;
  }

  static private IntCode GetCompressedStateFromShortCode(UInt32 code)
  {
    if (code > ShortCodesList.Count)
      throw new ArgumentOutOfRangeException(nameof(code), $"Value {code} larger than number of codes allocated: {ShortCodesList.Count}");
    lock (ShortCodesDict)
      return ShortCodesList[(int)code];
  }


  static private IntCode MakeCompressedState(byte[] compressedMoves)
  {
    // in fact each byte has a value no higher than 23.
    // so we can fit 6 bytes into a 32 bit int, with 2 bits spare to indicate other encoding modes for longer sequences.
    // for up to 6 bytes, the top 2 bits are set using this initial simple compression
    IntCode result = IntCode.MaxValue;

    int limit = maxSymbols;

    int i = 0;

    compressMore:
    limit = Math.Min(limit, compressedMoves.Length);

    for (; i < limit; i++)
      result = (result << bitsPerSymbol) | compressedMoves[i];

    if (compressedMoves.Length > limit)
    {
      // compress the result so far...
      result = AllocateShortCode(result);
      if ((result >> (bitsPerSymbol * 4)) == 0)
      {
        // short code can fit in space of 4 "normal" moves (applies to the first few that we find, which were therefore the "least costly" moves, and likely to be re-used a lot)
        // use code 30 to mark this, which can be done simply by shifting an extra bit.
        result += IntCode.MaxValue << (bitsPerSymbol * 4 + 1);
        limit += maxSymbols - 5;
        goto compressMore;
      }
      else if ((result >> (bitsPerSymbol * 5 + 1)) == 0)
      {
        // codes 28 and 30 mark a 5-symbol code, with 1 bit of the code stored in "parent" - i.e. 26 bits total.
        result += IntCode.MaxValue << (bitsPerSymbol * 5 + 2);
        limit += maxSymbols - 6;
        goto compressMore;
      }
      else if ((result >> (bitsPerSymbol * 6 + 2)) == 0)
      {
        // codes 24 to 27 mark a 6-symbol code, with 2 bits of the code stored in "parent" - i.e. 32 bits total.
        // this should be enough for all further codes we could conceivably need before running out of memory,
        // and also within the limit of Dictionary<,>.Count!
        result += IntCode.MaxValue << (bitsPerSymbol * 6 + 3);
        limit += maxSymbols - 7; // for 64-bit we still have enough space for 5 more symbols before allocating a new code.
        goto compressMore;
      }
      else
        throw new NotImplementedException();
    }
    try
    {
      DecodeCompressedState(result);
    }
    catch
    {
      Console.Write($"I got an exception when trying to encode byte array [{string.Join(",", compressedMoves)}]");
    }
    return result;
  }

  const int bitsPerSymbol = 5;
  const int maxSymbols = 64 / bitsPerSymbol;
  const IntCode singleMask = (1 << bitsPerSymbol) - 1;
  const IntCode maskForCode2 = (1 << (4 * bitsPerSymbol)) - 1;
  const IntCode maskForCode3 = (1 << (5 * bitsPerSymbol + 1)) - 1;
  const IntCode maskForCode4 = (1 << (6 * bitsPerSymbol + 2)) - 1;

  static private byte[] DecodeCompressedState(IntCode state)
  {
    List<byte> resultList = new List<byte>(16);
    switch(state >> bitsPerSymbol * maxSymbols) // i.e. 30 in current implementation, giving results 0-3
    {
      case 15: // simple encoding mode in 64 bit int.
      case 3: // simple encoding mode - 6 blocks of 5 bits, possibly containing "embedded multibyte codes"
        for (int shift = bitsPerSymbol * (maxSymbols-1); shift >= 0; shift -= bitsPerSymbol)
        {
          IntCode next = (state >> shift) & singleMask;
          if (next < 24)
          {
            resultList.Add((byte)next);
            continue;
          }
          UInt32 code;
          bool debug = false;
          switch(next)
          {
            case 31: continue; // padding bits for short sequences.
            case 30:
              shift -= bitsPerSymbol * 4;
              if (shift < 0)
                throw new InvalidOperationException("Bad position for code '30'");
              code = (uint)((state >> shift) & maskForCode2);
              debug = false;
              break;

            case 29:
            case 28:
              shift -= bitsPerSymbol * 5;
              if (shift < 0)
                throw new InvalidOperationException("Bad position for code '28'");
              code = (uint)((state >> shift) & maskForCode3);
              debug = false;
              break;

            default:
              shift -= bitsPerSymbol * 6;
              if (shift < 0)
                throw new InvalidOperationException("Bad position for code '24'");
              code = (uint)((state >> shift) & maskForCode4);
              debug = next > 26;
              break;
          }
          var decoded = DecodeCompressedState(GetCompressedStateFromShortCode(code));
          resultList.AddRange(decoded);
          if (debug)
            Console.WriteLine($"Decoded short code {code:X} from {state:X} as swaps: {string.Join(", ", decoded.Select(SwapInfo.ExpandFromByte))}");

        }
        break;
      default:
        throw new NotImplementedException($"Wrong top bits for state {state:X}"); // other encoding system to be defined....
    }

    return resultList.ToArray();
  }

  public PuzzleState GetPuzzleState(GridState gridState) => new PuzzleState(this, gridState) { AllowWrapAround = false };

  private IntCode _compressedState;

  private static SwapInfo[] GetMovesFromCompressedState(IntCode state) => DecodeCompressedState(state).Select(SwapInfo.ExpandFromByte).ToArray();

  public SwapInfo[] MovesDone => GetMovesFromCompressedState(_compressedState);

}


public class SquareSwap
{
  static public void Main()
  {
    Console.OutputEncoding = System.Text.Encoding.UTF8;

    HashSet<GridState> knownMagicSquares = new HashSet<GridState>();

    foreach(var magic in PuzzleState.GenerateMagicSquares(4))
    {
      magic.GridState.SetMagicConstant(); // must be called before first call to IsMagic - doesn't hurt to call again.
      if (!magic.GridState.IsMagic())
        throw new InvalidOperationException("But it's not magic!");
      if (!knownMagicSquares.Add(magic.GridState))
        throw new InvalidOperationException("But we already had that one!");
    }

    Console.WriteLine($"Total magic squares found: {knownMagicSquares.Count}");

    foreach (var magic in knownMagicSquares)
    {
      var reversed = new GridState(4, magic.CellStates.Reverse().ToArray());
      if(!knownMagicSquares.Contains(reversed))
      {
        throw new InvalidOperationException($"We have {magic.GetHashCode()}:\n{magic}\nbut not {reversed.GetHashCode()}\n{reversed}");
      }
    }

    Console.WriteLine("Sanity check complete - all magic squares found when reversed.");

    var startingGrid = knownMagicSquares.First();


    /*var startingState = new PuzzleState("867G", "143A", "9D2E", "BC5F") { AllowWrapAround = false };

    //    var startingState = new PuzzleState("1FE4", "BA58", "G69C", "732D") { AllowWrapAround = false }; // test starting state similar to "given" magic square

    //    var startingState = new PuzzleState("1FE4", "AB85", "769C", "G32D") { AllowWrapAround = false }; // test starting state similar to "given" magic square


    var magicConstant = startingState.GridState.SetMagicConstant();

    Console.WriteLine($"Starting state [total moves left: {startingState.GridState.TotalMovesLeft}, magic constant = {magicConstant}]:");
    Console.WriteLine(startingState.GridState);

    // test case for compression and decompression functions.
    CompressedGridState4 comp = startingState.GridState;
    Console.WriteLine($"Equality check: {comp.Equals((object)startingState.GridState)}");

    var startingGrid = startingState.GridState;
    */
    var workingSets = Enumerable.Range(0, startingGrid.TotalMovesLeft + 1).Select(i => new Dictionary<CompressedGridState4, CompressedPuzzleState>()).ToArray();

    // workingSets[startingState.GridState.TotalMovesLeft].Add(startingGrid, startingState);

    foreach (var magic in knownMagicSquares)
      workingSets[startingGrid.TotalMovesLeft].Add(magic, PuzzleState.CreateStartingState(magic));

    bool found = false;

    for (int i = workingSets.Length - 1; i > 0 /*&& !found*/; i--)
    {
      Console.WriteLine($"Starting on working set #{i}, which has {workingSets[i].Count} members... [{Enumerable.Range(0, i).Sum(x => workingSets[x].Count)} already in later working sets, {CompressedPuzzleState.ShortCodeCount} short codes used]");

      int rejectedCount = 0;

      System.Threading.Tasks.Parallel.ForEach(workingSets[i], pair =>
      {
        GridState gridState = pair.Key; // implicit conversion to decompress
        var puzzleState = pair.Value.GetPuzzleState(gridState);
        // non-compressed puzzle state is now only scoped to this block.

        if (puzzleState.IsTargetState)
        {
          found = true;
          lock (workingSets[i])
          {
            Console.WriteLine("Found solution!");
            Console.WriteLine($"... after swaps: {string.Join(", ", puzzleState.GetSwaps())}");
            Console.WriteLine(puzzleState.GridState);
          }
        }
        else if (puzzleState.CheckCompatibleWithTargetState())
        {
          foreach (var nextState in puzzleState.GetStatesAfterValidMoves().Where(s => s.CheckCompatibleWithTargetState()))
          {
            int movesLeft = nextState.GridState.TotalMovesLeft;
            //var swapInfo = nextState.MovesDone.Last();
            //Console.WriteLine($"Possible next state after swapping R{swapInfo.rowFrom + 1}C{swapInfo.colFrom + 1} with R{swapInfo.rowTo + 1}C{swapInfo.colTo + 1} [total moves left: {movesLeft}]:");
            //Console.WriteLine(nextState.GridState);

            if (movesLeft >= i)
              throw new InvalidOperationException("Total moves left didn't decrease???!");

            // implicit conversion to compressed data.
            CompressedGridState4 nextGridStateCompressed = nextState.GridState;

            lock (workingSets[movesLeft])
            {
              if (workingSets[movesLeft].TryGetValue(nextGridStateCompressed, out var firstEquivalentState))
              {
                //Console.WriteLine("Duplicate found!");
              }
              else
                workingSets[movesLeft].Add(nextGridStateCompressed, nextState);
            }
          }
        }
        else
          System.Threading.Interlocked.Increment(ref rejectedCount);
      });
      if (rejectedCount > 0)
        Console.WriteLine($"Rejected {rejectedCount} members as incompatible with target state");
      // allow dictionaries of compresed state to be reclaimed by garbage collector
      workingSets[i] = null;
    }
  }
}