| | | 1 | | using BallSort.Engine.Game; |
| | | 2 | | using BallSort.Engine.Logic; |
| | | 3 | | using BallSort.Engine.Models; |
| | | 4 | | |
| | | 5 | | namespace BallSort.Engine; |
| | | 6 | | |
| | | 7 | | public class Solver |
| | | 8 | | { |
| | | 9 | | private readonly Board _board; |
| | | 10 | | |
| | | 11 | | private readonly MoveGenerator _moveGenerator; |
| | | 12 | | |
| | | 13 | | private readonly BoardHasher _boardHasher; |
| | | 14 | | |
| | 26 | 15 | | private readonly Stack<Move> _moves = []; |
| | | 16 | | |
| | 26 | 17 | | private readonly HashSet<ulong[]> _visited = new(new BoardHashEqualityComparer()); |
| | | 18 | | |
| | | 19 | | private int[] _lastTouched; |
| | | 20 | | |
| | 26 | 21 | | public Solver(Board board) |
| | | 22 | | { |
| | 26 | 23 | | _board = board; |
| | | 24 | | |
| | 26 | 25 | | _moveGenerator = new MoveGenerator(_board); |
| | | 26 | | |
| | 26 | 27 | | _boardHasher = new BoardHasher(_board); |
| | 26 | 28 | | } |
| | | 29 | | |
| | | 30 | | public (bool Solved, List<Move> Moves) Solve() |
| | | 31 | | { |
| | 26 | 32 | | _moves.Clear(); |
| | | 33 | | |
| | 26 | 34 | | _visited.Clear(); |
| | | 35 | | |
| | 26 | 36 | | _visited.Add(_boardHasher.GetHash()); |
| | | 37 | | |
| | 26 | 38 | | if (Explore()) |
| | | 39 | | { |
| | 24 | 40 | | var moveList = _moves.Reverse().ToList(); |
| | | 41 | | |
| | 24 | 42 | | PostProcessMoves(moveList); |
| | | 43 | | |
| | 24 | 44 | | return (true, moveList); |
| | | 45 | | } |
| | | 46 | | |
| | 2 | 47 | | return (false, null); |
| | | 48 | | } |
| | | 49 | | |
| | | 50 | | private bool Explore() |
| | | 51 | | { |
| | 6232 | 52 | | var lastMove = _moves.Count > 0 ? _moves.Peek() : Move.NullMove; |
| | | 53 | | |
| | 6232 | 54 | | var moves = _moveGenerator.GetMoves(lastMove); |
| | | 55 | | |
| | 31716 | 56 | | foreach (var move in moves) |
| | | 57 | | { |
| | 10478 | 58 | | _board.Move(move); |
| | | 59 | | |
| | 10478 | 60 | | if (_board.IsSolved()) |
| | | 61 | | { |
| | 24 | 62 | | _moves.Push(move); |
| | | 63 | | |
| | 24 | 64 | | return true; |
| | | 65 | | } |
| | | 66 | | |
| | 10454 | 67 | | var hash = _boardHasher.GetHash(); |
| | | 68 | | |
| | 10454 | 69 | | if (_visited.Add(hash)) |
| | | 70 | | { |
| | 6206 | 71 | | _moves.Push(move); |
| | | 72 | | |
| | 6206 | 73 | | if (Explore()) |
| | | 74 | | { |
| | 1680 | 75 | | return true; |
| | | 76 | | } |
| | | 77 | | |
| | 4526 | 78 | | _moves.Pop(); |
| | | 79 | | } |
| | | 80 | | |
| | 8774 | 81 | | _board.UndoLastMove(); |
| | | 82 | | } |
| | | 83 | | |
| | 4528 | 84 | | return false; |
| | 1704 | 85 | | } |
| | | 86 | | |
| | | 87 | | private void PostProcessMoves(List<Move> moves) |
| | | 88 | | { |
| | 24 | 89 | | _lastTouched = new int[_board.Width]; |
| | | 90 | | |
| | 186 | 91 | | while (RemoveBounces(moves)) { } |
| | 24 | 92 | | } |
| | | 93 | | |
| | | 94 | | private bool RemoveBounces(List<Move> moves) |
| | | 95 | | { |
| | 186 | 96 | | Array.Fill(_lastTouched, -1); |
| | | 97 | | |
| | 16680 | 98 | | for (var index = 0; index < moves.Count; index++) |
| | | 99 | | { |
| | 8316 | 100 | | var move = moves[index]; |
| | | 101 | | |
| | 8316 | 102 | | var previousIndex = _lastTouched[move.Source]; |
| | | 103 | | |
| | 8316 | 104 | | if (previousIndex >= 0 && previousIndex == _lastTouched[move.Target]) |
| | | 105 | | { |
| | 2666 | 106 | | var previous = moves[previousIndex]; |
| | | 107 | | |
| | 2666 | 108 | | if (previous.Source == move.Target && previous.Target == move.Source) |
| | | 109 | | { |
| | 162 | 110 | | moves.RemoveAt(index); |
| | | 111 | | |
| | 162 | 112 | | moves.RemoveAt(previousIndex); |
| | | 113 | | |
| | 162 | 114 | | return true; |
| | | 115 | | } |
| | | 116 | | } |
| | | 117 | | |
| | 8154 | 118 | | _lastTouched[move.Source] = index; |
| | | 119 | | |
| | 8154 | 120 | | _lastTouched[move.Target] = index; |
| | | 121 | | } |
| | | 122 | | |
| | 24 | 123 | | return false; |
| | | 124 | | } |
| | | 125 | | } |