5. 8-Puzzle 智慧盤系統

using System.Drawing.Printing;

namespace Q5
{
    public partial class Form1 : Form
    {
        public static int[] goal =
        {
            4,5,6,
            3,0,7,
            2,1,8
        };

        public class State
        {
            public int[] board;
            public int blankIdx;
            public int g, h;
            public int f => g + h;
            public State parent;

            public State(int[] board)
            {
                this.board = board;
                blankIdx = Array.IndexOf(board, 0);
            }

            public State Clone()
            {
                var clone = new State((int[])board.Clone());
                clone.h = h;
                clone.g = g;
                clone.parent = parent;
                return clone;
            }

            public void CalcDist()
            {
                int dist = 0;
                for (int i = 0; i < 9; i++)
                {
                    var v = board[i];
                    if (v == 0) continue;
                    var x = i % 3;
                    var y = i / 3;

                    var targetX = Array.IndexOf(goal, v) % 3;
                    var targetY = Array.IndexOf(goal, v) / 3;

                    dist += Math.Abs(x - targetX) + Math.Abs(y - targetY);
                }
                h = dist;
            }

            public bool IsGoal => board.SequenceEqual(goal);

            public State Move(int dx, int dy)
            {
                int x = blankIdx % 3;
                int y = blankIdx / 3;
                int nx = x + dx;
                int ny = y + dy;
                if (nx < 0 || ny < 0 || nx > 2 || ny > 2) return null;
                var clone = Clone();
                clone.parent = this;
                clone.board[blankIdx] = clone.board[ny * 3 + nx];
                clone.board[ny * 3 + nx] = 0;
                clone.blankIdx = ny * 3 + nx;

                clone.g++;
                clone.CalcDist();

                return clone;
            }

            public override int GetHashCode()
            {
                var hc = new HashCode();
                foreach (var item in board)
                {
                    hc.Add(item);
                }
                return hc.ToHashCode();
            }

            public override bool Equals(object? obj)
            {
                State k = (State)obj;
                return k.board.SequenceEqual(board);
            }

            public override string ToString()
            {
                return string.Join(",",board);
            }
        }

        public Form1()
        {
            InitializeComponent();
            draw();
            drawSub(flowLayoutPanel2, goal);
        }

        private void button4_Click(object sender, EventArgs e)
        {
            Close();
        }

        State s = new State([2,5,1,6,0,4,8,7,3]);

        int lastClick = -1;

        void drawSub(FlowLayoutPanel panel, int[] arr)
        {
            panel.Controls.Clear();
            for (int i = 0; i < 9; i++)
            {
                var lbl = new Label();

                int k = i;
                if (arr != goal)
                {
                    lbl.Click += (z, c) =>
                    {
                        if (lastClick == -1)
                        {
                            lastClick = k;
                        }
                        else
                        {
                            (s.board[lastClick], s.board[k]) =
                            (s.board[k], s.board[lastClick]);
                            draw();
                            lastClick = -1;
                        }
                    };
                }

                lbl.Width = 70;
                lbl.Margin = Padding.Empty;
                lbl.Height = 70;
                lbl.TextAlign = ContentAlignment.MiddleCenter;
                lbl.BorderStyle = BorderStyle.FixedSingle;
                lbl.Text = arr[i] == 0 ? "" : arr[i].ToString();
                panel.Controls.Add(lbl);
            }
        }

        void draw()
        {
            drawSub(flowLayoutPanel1, s.board);
        }

        Random rd = new Random();
        private void button1_Click(object sender, EventArgs e)
        {
            var rdl = new List<int>();
            for (int i = 0; i < 9; i++)
            {
                int k;
                do
                {
                    k = rd.Next(9);
                } while (rdl.Contains(k));
                rdl.Add(k);
            }
            s = new State(rdl.ToArray());
            draw();
        }

        public int[][] dirs ={
[0,-1],
[0,1],
[1,0],
[-1,0]
        };

        public State? solve()
        {
            s.parent = null;
            s.g=0;
            s.CalcDist();

            var pq = new PriorityQueue<State, int>();
            pq.Enqueue(s, s.f);

            var visited = new HashSet<String>();
            while (pq.Count > 0)
            {
                var cur = pq.Dequeue();
                if (cur.IsGoal) return cur;
                if (!visited.Add(cur.ToString())) continue;
                
                foreach (var item in dirs)
                {
                    var next = cur.Move(item[0], item[1]);
                    if (next == null) continue;
                    if (visited.Contains(next.ToString())) continue;
                    pq.Enqueue(next, next.f);
                }
            }
            MessageBox.Show("無解");
            return null;
        }

        public List<State> path(State ans)
        {
            List<State> path = [];
            while (ans != null)
            {
                path.Add(ans);
                ans = ans.parent;
            }
            path.Reverse();

            return path;
        }

        async void run(int delay)
        {
            var ans = solve();
            if (ans == null)
            {
                return;
            }

            var step = -1;
            foreach (var item in path(ans))
            {
                step++;
                adaa.Text = step.ToString();
                s = item;
                draw();
                await Task.Delay(delay);
            }
        }

        private async void button2_Click(object sender, EventArgs e)
        {
            run(100);
        }

        private async void button3_Click(object sender, EventArgs e)
        {
            run(500);
        }
    }
}