Исходник обхода шахмотной доски конём на C++


Добавил:DMT
Дата создания:25 апреля 2008, 16:18
Дата обновления:25 апреля 2008, 16:44
Просмотров:10621 последний сегодня, 12:45
Комментариев: 2
Исходник обхода шахмотной доски конём на C++
Решение задачи с помощью алгоритма перебора с возвратом.
Ход шахматного коня - начертание буквы «Г». Найти путь коня, состоящий из всех полей шахматной доски, и не содержащий ни одного поля более чем один раз.
Код на C++
  1. #include <stdio.h>
  2. #include <conio.h>
  3. int i,j, n, nsqr, q ;
  4. int dx[9], dy[9], h[29][29] ;
  5. void prnt(void)
  6. {
  7. int p, r ;
  8. for ( p = 1 ; p<=n ; p++)
  9. {
  10. for ( r = 1 ; r<=n ; r++ )
  11. printf("%2d ", h[p][r] ) ;
  12. printf("\n") ;
  13. }
  14. printf("\n") ;
  15. }
  16. int t ( int i, int x, int y)
  17. // возвращает 1, если доска заполнена, 0 - если нет продолжений
  18. {
  19. int j, u, v , q1=0 ;
  20. for(j=1; (!q1) && (j<=8); j++)
  21. {
  22. u = x+dx[j] ; v = y +dy[j] ;
  23. if ( 1<= u && u <=n && 1 <=v && v<=n && h[u][v]==0)
  24. {
  25. h[u][v] = i ;
  26. if (i<nsqr)
  27. {q1 = t (i+1, u, v) ;
  28. if (q1==0) h[u][v]=0 ;
  29. } else q1 = 1 ;
  30. }
  31. }
  32. return q1 ;
  33. }
  34. main()
  35. {
  36. dx[1] = 2; dx[2] = 1; dx[3] = -1; dx[4] = -2;
  37. dx[5] = -2; dx[6] = -1; dx[7] = 1; dx[8] = 2;
  38. dy[1] = 1; dy[2] = 2; dy[3] = 2; dy[4] = 1;
  39. dy[5] = -1; dy[6] = -2; dy[7] = -2; dy[8] = -1;
  40. n=8 ; nsqr = n*n ;
  41. clrscr() ;
  42. h[1][1]=1 ;
  43. if (t (2, 1, 1)==0) printf("\nнет решений") ;
  44. else prnt() ;
  45. getch() ;
  46. }
При использовании обязательна ссылка на http://DMTSoft.ru
up

Комментарии для "Исходник обхода шахмотной доски конём на C++"


Пользователь: lelya
Сообщений: 1
Статус: Пользователь
Зарегистрирован:
7 января 2009, 8:57
Был:21 января 2009, 22:43
lelya
smsup
Дата: 7 января 2009, 23:16 Сообщение № 1
большое спасибо, DMT!!! За шахматного коня и за графику тоже!!!
Пользователь: smedrea
Сообщений: 1
Статус: Незримый
Зарегистрирован:
24 марта 2009, 19:53
Был:24 марта 2009, 19:58
smedrea
smsup
Дата: 24 марта 2009, 19:56 Сообщение № 2
pomogite i mne pojaluista kak napisati programu attila i koroli u menea esti sama programa no vot kak pokazat ee video metodom!