Задача о ходе коня и правило Варнсдорфа - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста реализовать следующую программу: есть шахматная доска 8х8 задается начальная клетка (например (2,8) ) необходимо обойти конем все клетки доски, побывав в каждой только 1 раз. Вывести результат в виде таблицы 8х8 где пронумерованы клетки (ходы коня). Обязательно должен использоваться следующий прием: на каждом ходу конь переходит по клетке, из которой существует наименьшее кол-во ходов. Заранее большое спасибо!

Решение задачи: «Задача о ходе коня и правило Варнсдорфа»

textual
Листинг программы
#include <stdio.h>
int func(int x, int y, int a[8][8])
{
    int t=0;
    if(x>0 && y>1 && a[x-1][y-2]==0) t++;
    if(x>0 && y<6 && a[x-1][y+2]==0) t++;
    if(x>1 && y>0 && a[x-2][y-1]==0) t++;
    if(x>1 && y<7 && a[x-2][y+1]==0) t++;
    if(x<7 && y>1 && a[x+1][y-2]==0) t++;
    if(x<7 && y<6 && a[x+1][y+2]==0) t++;
    if(x<6 && y>0 && a[x+2][y-1]==0) t++;
    if(x<6 && y<7 && a[x+2][y+1]==0) t++;
    return t;
}
int main()
{
    int a[8][8]={0}, i, j, col=0, x, y, tmp, tmp1;
    printf("x= "); scanf("%d", &x); x--;
    printf("y= "); scanf("%d", &y); y--;
    while(col<64)
    {
        col++;
        a[x][y]=col;
        tmp=9;
        if(x>0 && y>1 && a[x-1][y-2]==0)
        {
            tmp1=func(x-1, y-2, a);
            if(tmp1<tmp){i=x-1; j=y-2; tmp=tmp1;}
        }
        if(x>0 && y<6 && a[x-1][y+2]==0)
        {
            tmp1=func(x-1, y+2, a);
            if(tmp1<tmp){i=x-1; j=y+2; tmp=tmp1;}
        }
        if(x>1 && y>0 && a[x-2][y-1]==0)
        {
            tmp1=func(x-2, y-1, a);
            if(tmp1<tmp){i=x-2; j=y-1; tmp=tmp1;}
        }
        if(x>1 && y<7 && a[x-2][y+1]==0)
        {
            tmp1=func(x-2, y+1, a);
            if(tmp1<tmp){i=x-2; j=y+1; tmp=tmp1;}
        }
        if(x<7 && y>1 && a[x+1][y-2]==0)
        {
            tmp1=func(x+1, y-2, a);
            if(tmp1<tmp){i=x+1; j=y-2; tmp=tmp1;}
        }
        if(x<7 && y<6 && a[x+1][y+2]==0)
        {
            tmp1=func(x+1, y+2, a);
            if(tmp1<tmp){i=x+1; j=y+2; tmp=tmp1;}
        }
        if(x<6 && y>0 && a[x+2][y-1]==0)
        {
            tmp1=func(x+2, y-1, a);
            if(tmp1<tmp){i=x+2; j=y-1; tmp=tmp1;}
        }
        if(x<6 && y<7 && a[x+2][y+1]==0)
        {
            tmp1=func(x+2, y+1, a);
            if(tmp1<tmp){i=x+2; j=y+1; tmp=tmp1;}
        }
        x=i; y=j;
    }
    for(i=0; i<8; i++)
    {
        for(j=0; j<8; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    } 
  return 0;
}

Объяснение кода листинга программы

  1. Ввод осуществляется через функцию main().
  2. В функции main() объявлены переменные x и y, которые используются для определения позиции на доске.
  3. Затем происходит инициализация массива a нулями.
  4. Далее, в цикле, происходит заполнение доски значениями от 1 до 64.
  5. Внутри цикла используется функция func(), которая принимает позицию на доске и массив a в качестве аргументов.
  6. Функция func() проверяет 8 соседних позиций (вверх, вниз, влево, вправо, верхний левый угол, верхний правый угол, нижний левый угол, нижний правый угол) и увеличивает счетчик t, если позиция соответствует условию.
  7. Возвращаемое значение функции func() сравнивается с текущим минимальным значением tmp. Если новое значение меньше, то обновляются переменные i, j и tmp.
  8. После заполнения доски происходит вывод значения массива a через функцию printf().
  9. Значения переменных x и y сдвигаются влево на единицу перед каждой итерацией цикла.
  10. Ввод осуществляется через стандартный ввод (клавиатуру) с помощью функции scanf().

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.714 из 5
Похожие ответы