# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  ALGORITHM FOR KNIGHT'S TOURS

## saied_hacker

دوستان کسی الگوریتمی برای این بازی سراغ داره ؟

گشتم منتها هیچ کدوم به کارمن نیومد.

توی این بازی از خونه 1 و 1 شطرنج مهره اسب باید بره تمام خونه هارو دور بزنه و تو تک تکشون بشینه و برگرده مجدد به خونه 1 و 1 ( هیچ خونه ای رو دوباره نباید بشینه )

Wiki:Knight's tour
Google:Knight's tour
ممنون

----------


## saied_hacker

من یه جاهایی شو نوشتم منتها اخرش به جواب اصلا نمیرسه دوستان میتونن یه کمکی بکنن
( انتقادات و پیشنهادات پذیرفته می شود )
public class chess_F
    {
        // save my current position
        struct position
        {
            public int row;
            public int col;
        };

        const int NOT_VISITED = 0;

        // my board
        private int[,] cols = new int[8, 8];


        // main function 
        public void Do()
        {
            position start;
            start.row = 0;
            start.col = 0;

            initializeBoard(ref cols);

            move(start, cols);
        }

        private void initializeBoard(ref int[,] board)
        {
            for (int i = 0; i < 8; i++)
                for (int j = 0; j < 8; j++)
                    board[i, j] = NOT_VISITED;
        }

        private bool visited(int[,] board, position square)
        {
            return board[square.row, square.col] != NOT_VISITED;
        }


        /*  |---|---|-0-|---|-1-|---|---|---|
         *  |---|-7-|---|---|---|-2-|---|---|
         *  |---|---|---|-X-|---|---|---|---|
         *  |---|-6-|---|---|---|-3-|---|---|
         *  |---|---|-5-|---|-4-|---|---|---|
         *  |---|---|---|---|---|---|---|---|
         *  |---|---|---|---|---|---|---|---|
         *  |---|---|---|---|---|---|---|---|
         */

        // find all cols for my knight - can sit on
        private position[] findPath(position present, int[,] cols)
        {
            position[] temp = new position[8];
            position mytemp;

            for (int i = 0; i < 8; i++)
            {
                try
                {
                    //path 0
                    switch (i)
                    {
                        case 0:
                            {
                                if (cols[present.row - 1, present.col - 2] == 0)
                                {
                                    mytemp.row = present.row - 1;
                                    mytemp.col = present.col - 2;
                                    temp[i] = mytemp;
                                }
                                break;
                            }

                        //path 1
                        case 1:
                            {
                                if (cols[present.row + 1, present.col - 2] == 0)
                                {
                                    mytemp.row = present.row + 1;
                                    mytemp.col = present.col - 2;
                                    temp[i] = mytemp;
                                } break;
                            }

                        //path 2
                        case 2:
                            {
                                if (cols[present.row + 2, present.col - 1] == 0)
                                {
                                    mytemp.row = present.row + 2;
                                    mytemp.col = present.col - 1;
                                    temp[i] = mytemp;
                                } break;
                            }
                        //path 3
                        case 3:
                            {
                                if (cols[present.row + 2, present.col + 1] == 0)
                                {
                                    mytemp.row = present.row + 2;
                                    mytemp.col = present.col + 1;
                                    temp[i] = mytemp;
                                } break;
                            }

                        //path 4
                        case 4:
                            {
                                if (cols[present.row + 1, present.col + 2] == 0)
                                {
                                    mytemp.row = present.row + 1;
                                    mytemp.col = present.col + 2;
                                    temp[i] = mytemp;
                                } break;
                            }

                        //path 5
                        case 5:
                            {
                                if (cols[present.row - 1, present.col + 2] == 0)
                                {
                                    mytemp.row = present.row - 1;
                                    mytemp.col = present.col + 2;
                                    temp[i] = mytemp;
                                } break;
                            }

                        //path 6
                        case 6:
                            {
                                if (cols[present.row - 2, present.col - 1] == 0)
                                {
                                    mytemp.row = present.row - 2;
                                    mytemp.col = present.col - 1;
                                    temp[i] = mytemp;
                                } break;
                            }

                        //path 7
                        case 7:
                            {
                                if (cols[present.row - 2, present.col - 1] == 0)
                                {
                                    mytemp.row = present.row - 2;
                                    mytemp.col = present.col - 1;
                                    temp[i] = mytemp;
                                } break;
                            }
                    }
                }
                catch
                {
                    mytemp.row = -1;
                    mytemp.col = -1;
                    temp[i] = mytemp;
                }
            }
            return temp;
        }

        // check all cols and row to check ...
        private bool allVisited(int[,] cols)
        {
            for (int i = 0; i < 8; i++)
                for (int j = 0; j < 8; j++)
                    if (cols[i, j] != 1)
                        return false;
            return true;

        }


        // save true path
        int[,] truepath;
        private void move(position present, int[,] cols)
        {
            int[,] tempCols = cols;
            tempCols[present.row, present.col] = 1;
            position[] avaliable = findPath(present, tempCols);

            if (avaliable.Count() < 1)
                return;

            for (int i = 0; i < avaliable.Count(); i++)
            {
                if (allVisited(tempCols))
                {
                    truepath = tempCols;
                }
                else
                {
                    if (avaliable[i].row != -1 && avaliable[i].row != 0)
                        move(avaliable[i], tempCols);
                }
            }
        }
    }

کلی از مسیر رو تریس کردم ( پیر شدم ) میره ولی اون قسمت که چک میکنه که همه خونه ها رو رفته باشه اجرا نمیشه ؟؟؟

مشکل در بخش Move هس که نمی دونم چه کارش بای بکنم ! :(

----------

