fork(2) download
copy 
  1. #include <cstdlib>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;
  7. const bool SET_DIA = true/*для установки диагонали*/, DEL_DIA = false/*для удаления диагонали*/;
  8. int a[HEIGHT][WIDTH];							// доска
  9. bool is_set[HEIGHT][WIDTH];						// Расположение слонов на доске
  10. int count_null = WIDTH * HEIGHT;				// Количество пустых клеток
  11. bool isEnd = false;								// Флаг выхода из рекурсии
  12. const bool FIRST = true, SECOND = false;		// индификация диагоналей
  13.  
  14. int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){				// осуществляет все операции с диагоналями
  15. 	while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){					// заполняем/очищаем первую\вторую диагональ
  16. 		if(is_firstD? true : x != j || y != i){
  17. 			if(set){																
  18. 				a[y][x]++;
  19. 				if(a[y][x] == 1){													
  20. 					count_null--;
  21. 				}
  22. 			}else{																	
  23. 				a[y][x]--;
  24. 				if(a[y][x] == 0){												
  25. 					count_null++;
  26. 				}
  27. 			}
  28. 		}
  29. 		x += (is_firstD? 1 : -1);
  30. 		y++;
  31. 	}
  32. }
  33.  
  34. int space(bool set, int level, int i, int j){		// функция осуществляет операции с диагналями (установку \ удалене)
  35. 	is_set[i][j] = set;								
  36. 	int x, y;
  37. 	if(j>i){										// ищем начало прохода первой диагнали (параллельной или индентичной главной)
  38. 		y = 0;
  39. 		x = j-i;
  40. 	}else{
  41. 		x = 0;
  42. 		y = i-j;
  43. 	}
  44. 	diagonal(FIRST, set, x, y, i, j);
  45. 	// ищем начало второй диагонали (перпендикулярной главной (побочной))
  46. 	int sum = i+j;
  47. 	if(sum < WIDTH){
  48. 		x = sum;
  49. 		y = 0;
  50. 	}else{
  51. 		x = WIDTH-1;
  52. 		y = sum-x;
  53. 	}
  54. 	diagonal(SECOND, set, x, y, i, j);
  55. }
  56.  
  57. bool find_permutation(int level=0){		// функция ищет все варианты установки слонов рекурсивно (если расставлен не 8-й слон, то расставляет остальных)(данный слон задается переменной level (0..7))
  58. 	level++;
  59.  
  60. 	for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){					
  61. 	/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательносте найдено не будет
  62. 	  именно по этой причине если мы задаем первого слона, то начинаем со второй ячейки строки (это намного ускоряет поиск)
  63. 	*/
  64. 		if(a[i][j] == 0){			
  65. 			space(SET_DIA, level, i, j);						
  66. 			if(level != COUNT_EL){											
  67. 				find_permutation(level);											
  68. 				if(isEnd){													
  69. 					return false;
  70. 				}
  71. 			}else if(count_null == 0){							 
  72. 				cout << "Ответ найден:"<< endl << endl;					
  73. 				for( int i1=0 ; i1<HEIGHT ; i1++ ){					
  74. 					for( int j1=0 ; j1<WIDTH ; j1++ ){
  75. 						cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );
  76. 					}
  77. 				}
  78. 				isEnd = true;											
  79. 				return false;										
  80. 			}
  81. 			space(DEL_DIA, level, i, j);								
  82. 		}
  83.  
  84. 	}
  85. 	level--;
  86. }
  87.  
  88. int main(){
  89. 	find_permutation();
  90. }
Success #stdin #stdout 0s 3096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Ответ найден:

0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
https://ideone.com/LI0j9q
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!