8-Puzzle Solver

8-Puzzle-Solver.md

Program.cs : Arama algoritmalarının gerçeklendiği sınıf. Node.cs : Çözüm uzayındaki düğüm yapısının tanımlandığı sınıf. Form1.cs: Kullanıcı arayüzü kontrollerinin tanımlandığı sınıf.

Form1.cs

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace EightPuzzleSolver
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void ButtonSolve_Click(object sender, EventArgs e)
        {
            textBoxSolution.Text = "";
            Program.totalNumOfSeekedNodes = 0;
            Node initialNode = new Node();
            try
            {
                initialNode.readMatrixFromGUI(textBoxInput);
            }
            catch
            {
                textBoxInput.Text = "Geçersiz Giriş";
                return;
            }

            if (radioButtonAStar.Checked)
                Program.solveUsingAStar(initialNode, textBoxSolution);

            else if (radioButtonBFS.Checked)
                Program.solveUsingBFS(initialNode, textBoxSolution);

            else if (radioButtonDFS.Checked)
                Program.solveUsingDFS(initialNode, textBoxSolution);

            labelNumOfSeekedNodes.Text = Program.totalNumOfSeekedNodes + " Düğüm tarandı";
        }



    }
}

Form1.Designer.cs

namespace EightPuzzleSolver
{
    partial class Form1
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.ButtonSolve = new System.Windows.Forms.Button();
            this.textBoxInput = new System.Windows.Forms.TextBox();
            this.label1 = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.label3 = new System.Windows.Forms.Label();
            this.textBoxSolution = new System.Windows.Forms.TextBox();
            this.radioButtonAStar = new System.Windows.Forms.RadioButton();
            this.radioButtonBFS = new System.Windows.Forms.RadioButton();
            this.radioButtonDFS = new System.Windows.Forms.RadioButton();
            this.label4 = new System.Windows.Forms.Label();
            this.textBoxSample = new System.Windows.Forms.TextBox();
            this.groupBoxAlgorithm = new System.Windows.Forms.GroupBox();
            this.labelNumOfSeekedNodes = new System.Windows.Forms.Label();
            this.groupBoxAlgorithm.SuspendLayout();
            this.SuspendLayout();
            // 
            // ButtonSolve
            // 
            this.ButtonSolve.Location = new System.Drawing.Point(12, 204);
            this.ButtonSolve.Name = "ButtonSolve";
            this.ButtonSolve.Size = new System.Drawing.Size(83, 23);
            this.ButtonSolve.TabIndex = 9;
            this.ButtonSolve.Text = "Çöz";
            this.ButtonSolve.UseVisualStyleBackColor = true;
            this.ButtonSolve.Click += new System.EventHandler(this.ButtonSolve_Click);
            // 
            // textBoxInput
            // 
            this.textBoxInput.Font = new System.Drawing.Font("Microsoft Sans Serif", 11F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(162)));
            this.textBoxInput.Location = new System.Drawing.Point(36, 25);
            this.textBoxInput.Multiline = true;
            this.textBoxInput.Name = "textBoxInput";
            this.textBoxInput.Size = new System.Drawing.Size(42, 64);
            this.textBoxInput.TabIndex = 10;
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(12, 9);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(83, 13);
            this.label1.TabIndex = 11;
            this.label1.Text = "3x3 Puzzle Girişi";
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 9F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(162)));
            this.label2.ForeColor = System.Drawing.SystemColors.HotTrack;
            this.label2.Location = new System.Drawing.Point(9, 288);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(143, 60);
            this.label2.TabIndex = 12;
            this.label2.Text = "8-puzzle Çözücü v1.0\r\nFurkan IŞIKDOĞAN\r\nwww.isikdogan.com\r\n04.12.2010";
            this.label2.TextAlign = System.Drawing.ContentAlignment.TopCenter;
            // 
            // label3
            // 
            this.label3.AutoSize = true;
            this.label3.Location = new System.Drawing.Point(240, 9);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(78, 13);
            this.label3.TabIndex = 13;
            this.label3.Text = "Çözüm Adımları";
            // 
            // textBoxSolution
            // 
            this.textBoxSolution.Location = new System.Drawing.Point(243, 25);
            this.textBoxSolution.Multiline = true;
            this.textBoxSolution.Name = "textBoxSolution";
            this.textBoxSolution.ScrollBars = System.Windows.Forms.ScrollBars.Vertical;
            this.textBoxSolution.Size = new System.Drawing.Size(120, 323);
            this.textBoxSolution.TabIndex = 14;
            // 
            // radioButtonAStar
            // 
            this.radioButtonAStar.AutoSize = true;
            this.radioButtonAStar.Checked = true;
            this.radioButtonAStar.Location = new System.Drawing.Point(6, 19);
            this.radioButtonAStar.Name = "radioButtonAStar";
            this.radioButtonAStar.Size = new System.Drawing.Size(111, 17);
            this.radioButtonAStar.TabIndex = 15;
            this.radioButtonAStar.TabStop = true;
            this.radioButtonAStar.Text = "A* Sezgisel Arama";
            this.radioButtonAStar.UseVisualStyleBackColor = true;
            // 
            // radioButtonBFS
            // 
            this.radioButtonBFS.AutoSize = true;
            this.radioButtonBFS.Location = new System.Drawing.Point(6, 42);
            this.radioButtonBFS.Name = "radioButtonBFS";
            this.radioButtonBFS.Size = new System.Drawing.Size(114, 17);
            this.radioButtonBFS.TabIndex = 16;
            this.radioButtonBFS.Text = "Önce Enine Arama";
            this.radioButtonBFS.UseVisualStyleBackColor = true;
            // 
            // radioButtonDFS
            // 
            this.radioButtonDFS.AutoSize = true;
            this.radioButtonDFS.Location = new System.Drawing.Point(6, 67);
            this.radioButtonDFS.Name = "radioButtonDFS";
            this.radioButtonDFS.Size = new System.Drawing.Size(136, 17);
            this.radioButtonDFS.TabIndex = 17;
            this.radioButtonDFS.Text = "Önce Derinliğine Arama";
            this.radioButtonDFS.UseVisualStyleBackColor = true;
            // 
            // label4
            // 
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(117, 9);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(95, 13);
            this.label4.TabIndex = 18;
            this.label4.Text = "Örnek Puzzle Girişi";
            // 
            // textBoxSample
            // 
            this.textBoxSample.Enabled = false;
            this.textBoxSample.Font = new System.Drawing.Font("Microsoft Sans Serif", 11F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(162)));
            this.textBoxSample.Location = new System.Drawing.Point(139, 25);
            this.textBoxSample.Multiline = true;
            this.textBoxSample.Name = "textBoxSample";
            this.textBoxSample.Size = new System.Drawing.Size(42, 64);
            this.textBoxSample.TabIndex = 19;
            this.textBoxSample.Text = "3 6 7\r\n1 4 2\r\n5 0 8";
            // 
            // groupBoxAlgorithm
            // 
            this.groupBoxAlgorithm.Controls.Add(this.radioButtonAStar);
            this.groupBoxAlgorithm.Controls.Add(this.radioButtonBFS);
            this.groupBoxAlgorithm.Controls.Add(this.radioButtonDFS);
            this.groupBoxAlgorithm.Location = new System.Drawing.Point(12, 105);
            this.groupBoxAlgorithm.Name = "groupBoxAlgorithm";
            this.groupBoxAlgorithm.Size = new System.Drawing.Size(200, 93);
            this.groupBoxAlgorithm.TabIndex = 20;
            this.groupBoxAlgorithm.TabStop = false;
            this.groupBoxAlgorithm.Text = "Kullanılacak Yöntem";
            // 
            // labelNumOfSeekedNodes
            // 
            this.labelNumOfSeekedNodes.AutoSize = true;
            this.labelNumOfSeekedNodes.Location = new System.Drawing.Point(15, 234);
            this.labelNumOfSeekedNodes.Name = "labelNumOfSeekedNodes";
            this.labelNumOfSeekedNodes.Size = new System.Drawing.Size(0, 13);
            this.labelNumOfSeekedNodes.TabIndex = 21;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(377, 376);
            this.Controls.Add(this.labelNumOfSeekedNodes);
            this.Controls.Add(this.groupBoxAlgorithm);
            this.Controls.Add(this.textBoxSample);
            this.Controls.Add(this.label4);
            this.Controls.Add(this.textBoxSolution);
            this.Controls.Add(this.label3);
            this.Controls.Add(this.label2);
            this.Controls.Add(this.label1);
            this.Controls.Add(this.textBoxInput);
            this.Controls.Add(this.ButtonSolve);
            this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
            this.Name = "Form1";
            this.Text = "8-Puzzle Çözücü v1.0 | Furkan IŞIKDOĞAN";
            this.groupBoxAlgorithm.ResumeLayout(false);
            this.groupBoxAlgorithm.PerformLayout();
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.Button ButtonSolve;
        private System.Windows.Forms.TextBox textBoxInput;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.TextBox textBoxSolution;
        private System.Windows.Forms.RadioButton radioButtonAStar;
        private System.Windows.Forms.RadioButton radioButtonBFS;
        private System.Windows.Forms.RadioButton radioButtonDFS;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.TextBox textBoxSample;
        private System.Windows.Forms.GroupBox groupBoxAlgorithm;
        private System.Windows.Forms.Label labelNumOfSeekedNodes;
    }
}

Node.cs

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

namespace EightPuzzleSolver
{
    class Node
    {
        public static int[] goalMatrix = {1,2,3,8,0,4,7,6,5};
        public int[] matrix;
	    public int g; //başlangıca olan uzaklık
	    public int h; //sonuca olan sezgisel uzaklık
	    public int f; //g+h
        public Node parent;

        public Node(){
            matrix = new int[9];
            parent = null;
        }

        public void uptadeF() {
            f = g + h;
        }

        public void calculateH() { //hedefe olan uzaklığı şehir blok uzaklığı (manhattan) kullanarak hesapla
            h = 0;

            for (int i = 0; i < 9; i++)
            {
                int goalIndex = Array.IndexOf(goalMatrix, matrix[i]); //elemanın olması gereken yeri bul
                int colDist = Math.Abs( (i % 3) - (goalIndex % 3) );
                int rowDist = Math.Abs( (i / 3) - (goalIndex / 3) );
                h += colDist + rowDist; // hedefe olan manhattan uzaklığını hesapla
                                
            }
        }

        public void readMatrixFromGUI(TextBox A)
        {
            string[] elements = A.Text.Replace("\n", " ").Replace("\r", "").Split();
           
            for (int i = 0; i < 9; i++)
            {
                matrix[i] = Int32.Parse(elements[i]);
            }
        }

        public void writeMatrixToGUI(TextBox A)
        {
            A.Text += "--------------\r\n";
            for (int i = 0; i < 9; i++)
            {
                if(matrix[i] == 0)
                    A.Text += "   ";
                else
                    A.Text += matrix[i].ToString() + " ";

                if(i%3 == 2)
                    A.Text += "\r\n";
            }
        }
    }
}

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;

namespace EightPuzzleSolver
{
    static class Program
    {
        public static int totalNumOfSeekedNodes; //gezilen toplam düğüm sayısı

        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
        }

        public static Node findMinimumNode(List<Node> queue) {
            int minIndex = 0;
            for (int i = 0; i < queue.Count; i++) {
                if (queue[i].f < queue[minIndex].f)
                    minIndex = i;
            }
            return queue[minIndex];
        }

        public static void swapElements(int[] array,int index1,int index2) {
            int temp = array[index1];
            array[index1] = array[index2];
            array[index2] = temp;
        }

        public static Node createChild(Node parent, int spaceIndex, int elementIndex) {
            Node child = new Node(); //yeni çocuk düğüm oluştur
            Array.Copy(parent.matrix, child.matrix,parent.matrix.Length);
            child.g = parent.g + 1; //başlangıçtan gelinen mesafe
            swapElements(child.matrix, spaceIndex, elementIndex);
            child.calculateH();
            child.uptadeF();
            child.parent = parent;
            return child;
        }

        public static void addChildrenToQueue(Node parent,List<Node> queue, List<int[]> closed){
            int spaceIndex = Array.IndexOf(parent.matrix, 0); //boşluğun indeksini bul
            if (spaceIndex%3 != 2) 
            { //boşluğun sağ komşusu varsa
                Node child = createChild(parent, spaceIndex, spaceIndex + 1);
                if (!isLoop(child.matrix, closed))
                {
                    queue.Add(child);
                }
            }

            if (spaceIndex % 3 != 0)
            { //boşluğun sol komşusu varsa
                Node child = createChild(parent, spaceIndex, spaceIndex - 1);
                if (!isLoop(child.matrix, closed))
                {
                    queue.Add(child);
                }
            }

            if (spaceIndex - 3 >= 0)
            { //boşluğun üst komşusu varsa
                Node child = createChild(parent, spaceIndex, spaceIndex - 3);
                if (!isLoop(child.matrix, closed))
                {
                    queue.Add(child);
                }
            }

            if (spaceIndex + 3 < 9)
            { //boşluğun alt komşusu varsa
                Node child = createChild(parent, spaceIndex, spaceIndex + 3);
                if (!isLoop(child.matrix, closed))
                {
                    queue.Add(child);
                }
            }

            queue.Remove(parent);
        }

        public static bool isLoop(int[] matrix, List<int[]> closed) {
            foreach (int[] item in closed)
            {
                bool isEqual = true;
                for (int i = 0; i < 9; i++) {
                    if (item[i] != matrix[i])
                    {
                        isEqual = false;
                    }
                }

                if (isEqual == true)
                    return true;
            }
            return false;
        
        }

        public static bool isEqualToGoal(int[] matrix) {
            for (int i = 0; i < matrix.Length; i++)
                if (matrix[i] != Node.goalMatrix[i])
                    return false;
            return true;
        }

        public static bool isSolvable(int[] matrix, int[] goal)
        {
            int inversions = 0;
            for (int i = 0; i < 9; i++)
            {
                    for (int j = i+1; j < 9; j++)
                    {

                        for (int k = 0; k < Array.IndexOf(goal,matrix[i]); k++)
                        {
                            if (goal[k] == matrix[j] && matrix[i]!=0 && matrix[j]!=0)
                                inversions++;
                        }

                    }
            }
            if (inversions % 2 == 0) return true;
            return false;
        }

        public static bool writeStepsOnGUI(Node seek, TextBox guiOutput, int numOfSteps)
        {
            if (seek == null) {
                guiOutput.Text += "Adım Sayısı: " + (numOfSteps-1);
                return true;
            }

            writeStepsOnGUI(seek.parent, guiOutput, numOfSteps+1);
            seek.writeMatrixToGUI(guiOutput);
            return false;
            
        }

        public static void solveUsingAStar(Node initialNode, TextBox guiOutput)
        {
        
            List<Node> queue = new List<Node>();
            List<int[]> closed = new List<int[]>(); //döngü oluşumunu engellemek için daha önce gelinen matrislerin tutulduğu liste

            if (!isSolvable(initialNode.matrix, Node.goalMatrix))
            {
                guiOutput.Text = "Problemin çözümü yoktur. Raporda bu konu hakkında detaylı bilgiye yer verilmiştir.";
                return;
            }

            initialNode.calculateH();
            initialNode.uptadeF();

            queue.Add(initialNode);
            Node min;

            do{
                min = findMinimumNode(queue);
                totalNumOfSeekedNodes++;
                closed.Add(min.matrix);
                addChildrenToQueue(min, queue, closed);
            }while(min.h!=0 && queue.Count>0); //sonuç duruma ulaşana kadar veya liste boş olana kadar tekrarla

            writeStepsOnGUI(min, guiOutput, 0);
        }


        public static void solveUsingBFS(Node initialNode, TextBox guiOutput)
        {
            List<Node> queue = new List<Node>();
            List<int[]> closed = new List<int[]>();

            if (!isSolvable(initialNode.matrix, Node.goalMatrix))
            {
                guiOutput.Text = "Problemin çözümü yoktur. Raporda bu konu hakkında detaylı bilgiye yer verilmiştir.";
                return;
            }

            queue.Add(initialNode);
            totalNumOfSeekedNodes++;

            while (!isEqualToGoal(queue.First().matrix) && queue.Count != 0)
            {
                totalNumOfSeekedNodes++;
                closed.Add(queue.First().matrix);
                addChildrenToQueue(queue.First(), queue, closed); //FIFO
            }

            writeStepsOnGUI(queue.ElementAt(0), guiOutput, 0);

        }

        public static void solveUsingDFS(Node initialNode, TextBox guiOutput)
        {
            List<Node> queue = new List<Node>();
            List<int[]> closed = new List<int[]>();

            if (!isSolvable(initialNode.matrix, Node.goalMatrix))
            {
                guiOutput.Text = "Problemin çözümü yoktur. Raporda bu konu hakkında detaylı bilgiye yer verilmiştir.";
                return;
            }

            queue.Add(initialNode);
            totalNumOfSeekedNodes++;

            while (!isEqualToGoal(queue.Last().matrix) && queue.Count != 0)
            {
                totalNumOfSeekedNodes++;
                closed.Add(queue.Last().matrix); // LIFO
                addChildrenToQueue(queue.Last(), queue, closed);
            }

            writeStepsOnGUI(queue.Last(), guiOutput, 0);

        }

    }
}