SquareSwap4.cs

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

// SquareSwap4.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...
// compile with command line
// csc SquareSwap4.cs UInt128.cs /r:System.Numerics.dll
// you will need UInt128.cs from https://github.com/ricksladkey/dirichlet-numerics
// see https://stackoverflow.com/questions/227731/int128-in-net


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);
  }
}


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; }

  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 class PuzzleState
{
  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 < fromColLimit; 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));
        }

        int toNextCol = (fromCol + 1) % GridState.ColumnCount;
        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("123", "456", "789");

  public bool IsTargetState => GridState.IsMagic();

  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" a 96 bit integer, but code for that seems unlikely to be much of an improvement...
  // limit is based on 16! * 17!
  UInt128 _compressedData;

  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;
    UInt128 multiplier = 1;
    _compressedData = 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)}]");

      _compressedData += multiplier * (uint)posIndex;
      multiplier *= (uint)possiblePositions.Count;

      possiblePositions.RemoveAt(posIndex);

      _compressedData += multiplier * (uint)cellStates[pos].MovesLeft;
      multiplier *= 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];
    UInt128 multiplier = 1;

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

    for (byte i = 1; i <= 16; i++)
    {
      UInt128 nextMultiplier = multiplier * (uint)possiblePositions.Count;
      int posIndex = (int)(_compressedData % nextMultiplier / multiplier);
      int pos = possiblePositions[posIndex];
      possiblePositions.RemoveAt(posIndex);

      multiplier = nextMultiplier;
      nextMultiplier *= (uint)i + 1;

      byte movesLeft = (byte)(_compressedData % nextMultiplier / multiplier);
      multiplier = nextMultiplier;

      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 _compressedData == other._compressedData;
  }

  public override int GetHashCode()
  {
    return _compressedData.GetHashCode();
  }

}


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

  public CompressedPuzzleState(PuzzleState source)
  {
    MovesDone = source.MovesDone;
  }

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

  // currently not (further) compressed. That can be next step if existing changes are insufficient.
  public SwapInfo[] MovesDone { get; }

}


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

    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 workingSets = Enumerable.Range(0, startingState.GridState.TotalMovesLeft + 1).Select(i => new Dictionary<CompressedGridState4, CompressedPuzzleState>()).ToArray();

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

    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]");

      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().Select(s => $"R{s.rowFrom + 1}C{s.colFrom + 1}<>R{s.rowTo + 1}C{s.colTo + 1}"))}");
            Console.WriteLine(puzzleState.GridState);
          }
        }
        else
          foreach (var nextState in puzzleState.GetStatesAfterValidMoves())
          {
            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???!");

            CompressedGridState4 nextGridStateCompressed = nextState.GridState;

            lock (workingSets[movesLeft])
            {
              if (workingSets[movesLeft].TryGetValue(nextGridStateCompressed, out var firstEquivalentState))
              {
                //Console.WriteLine("Duplicate found!");
              }
              else // implicit conversion to compressed data.
                workingSets[movesLeft].Add(nextGridStateCompressed, nextState);
            }
          }
      });
      // allow dictionaries of compresed state to be reclaimed by garbage collector
      workingSets[i] = null;
    }
  }
}