| | | 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 | | |
| | 26 | 19 | | public Solver(Board board) |
| | | 20 | | { |
| | 26 | 21 | | _board = board; |
| | | 22 | | |
| | 26 | 23 | | _moveGenerator = new MoveGenerator(_board); |
| | | 24 | | |
| | 26 | 25 | | _boardHasher = new BoardHasher(_board); |
| | 26 | 26 | | } |
| | | 27 | | |
| | | 28 | | public (bool Solved, List<Move> Moves) Solve() |
| | | 29 | | { |
| | 26 | 30 | | _moves.Clear(); |
| | | 31 | | |
| | 26 | 32 | | _visited.Clear(); |
| | | 33 | | |
| | 26 | 34 | | _visited.Add(_boardHasher.GetHash()); |
| | | 35 | | |
| | 26 | 36 | | if (Explore()) |
| | | 37 | | { |
| | 24 | 38 | | var moveList = _moves.Reverse().ToList(); |
| | | 39 | | |
| | 24 | 40 | | return (true, moveList); |
| | | 41 | | } |
| | | 42 | | |
| | 2 | 43 | | return (false, null); |
| | | 44 | | } |
| | | 45 | | |
| | | 46 | | private bool Explore() |
| | | 47 | | { |
| | 6234 | 48 | | var lastMove = _moves.Count > 0 ? _moves.Peek() : Move.NullMove; |
| | | 49 | | |
| | 6234 | 50 | | var moves = _moveGenerator.GetMoves(lastMove); |
| | | 51 | | |
| | 31884 | 52 | | foreach (var move in moves) |
| | | 53 | | { |
| | 10560 | 54 | | _board.Move(move); |
| | | 55 | | |
| | 10560 | 56 | | if (_board.IsSolved()) |
| | | 57 | | { |
| | 24 | 58 | | _moves.Push(move); |
| | | 59 | | |
| | 24 | 60 | | return true; |
| | | 61 | | } |
| | | 62 | | |
| | 10536 | 63 | | var hash = _boardHasher.GetHash(); |
| | | 64 | | |
| | 10536 | 65 | | if (_visited.Add(hash)) |
| | | 66 | | { |
| | 6208 | 67 | | _moves.Push(move); |
| | | 68 | | |
| | 6208 | 69 | | if (Explore()) |
| | | 70 | | { |
| | 1680 | 71 | | return true; |
| | | 72 | | } |
| | | 73 | | |
| | 4528 | 74 | | _moves.Pop(); |
| | | 75 | | } |
| | | 76 | | |
| | 8856 | 77 | | _board.UndoLastMove(); |
| | | 78 | | } |
| | | 79 | | |
| | 4530 | 80 | | return false; |
| | 1704 | 81 | | } |
| | | 82 | | } |