Задача о ходе коня и правило Варнсдорфа - 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; }
Объяснение кода листинга программы
- Ввод осуществляется через функцию
main()
. - В функции
main()
объявлены переменныеx
иy
, которые используются для определения позиции на доске. - Затем происходит инициализация массива
a
нулями. - Далее, в цикле, происходит заполнение доски значениями от 1 до 64.
- Внутри цикла используется функция
func()
, которая принимает позицию на доске и массивa
в качестве аргументов. - Функция
func()
проверяет 8 соседних позиций (вверх, вниз, влево, вправо, верхний левый угол, верхний правый угол, нижний левый угол, нижний правый угол) и увеличивает счетчикt
, если позиция соответствует условию. - Возвращаемое значение функции
func()
сравнивается с текущим минимальным значениемtmp
. Если новое значение меньше, то обновляются переменныеi
,j
иtmp
. - После заполнения доски происходит вывод значения массива
a
через функциюprintf()
. - Значения переменных
x
иy
сдвигаются влево на единицу перед каждой итерацией цикла. - Ввод осуществляется через стандартный ввод (клавиатуру) с помощью функции
scanf()
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д