fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <algorithm>
  5. #include <random>
  6. #include <iterator>
  7.  
  8. typedef std::vector<std::uint32_t> DType;
  9. typedef std::vector<DType> Grid;
  10. typedef std::vector<Grid> RType;
  11. typedef std::vector < std::vector<DType>> Cube;
  12. #ifdef _WIN32
  13. #include <Windows.h>//ms windows os only.
  14. void gotoxy(int X, int Y) {//カーソルを移動させる関数です。環境によってはエスケープシーケンスが使えるのでそれに置き換えることもできます。
  15. 	COORD Pos = { static_cast<SHORT>(X),static_cast<SHORT>(Y) };//WINDOWS定義の構造体です。
  16. 	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);//windows定義の関数です。カーソルを移動します。
  17. 	return;
  18. }
  19. #else
  20. void gotoxy(int X, int Y) {
  21. 	return;
  22. }
  23. #endif
  24.  
  25.  
  26. Grid MakeProblem() {
  27. 	Grid R{
  28. 		{ 1,5,0,0,8,6,0,7,0, },
  29. 		{ 7,0,8,9,0,0,0,0,0, },
  30. 		{ 0,9,0,5,0,0,0,8,1, },
  31. 		{ 9,0,0,0,0,8,1,0,6, },
  32. 		{ 0,0,1,0,2,0,0,9,0, },
  33. 		{ 0,7,5,6,0,0,2,0,0, },
  34. 		{ 5,0,6,0,4,0,0,2,0, },
  35. 		{ 3,0,0,1,0,2,5,0,0, },
  36. 		{ 0,4,0,8,0,0,0,0,9, },
  37. 	};
  38.  
  39. 	return R;
  40.  
  41. }
  42.  
  43. Grid MakeGrid() {
  44. 	Grid G(9);
  45. 	for (auto& o : G) {
  46. 		o.assign(9, 0);
  47. 	}
  48. 	return G;
  49. }
  50. Cube MakeCube() {
  51. 	DType D{ 1,2,3,4,5,6,7,8,9 };
  52. 	Cube C(9);
  53. 	for (auto& oo : C) {
  54. 		oo.resize(9);
  55. 		for (auto& o : oo) {
  56. 			o = D;
  57. 		}
  58. 	}
  59.  
  60. 	return C;
  61. }
  62.  
  63. Cube ReduceCube(const Cube& Cu, const Grid& P) {
  64. 	Cube C = Cu;
  65. 	for (std::size_t i = 0; i < P.size(); i++) {
  66. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  67. 			if (P[i][j] != 0) {
  68. 				C[i][j].clear();
  69. 				C[i][j].push_back(P[i][j]);
  70. 			}
  71.  
  72. 		}
  73. 	}
  74. 	for (std::size_t i = 0; i < C.size(); i++) {
  75. 		for (std::size_t j = 0; j < C[i].size(); j++) {
  76. 			if (C[i][j].size() != 1)continue;
  77.  
  78.  
  79. 			for (std::size_t k = 0; k < P.size(); k++) {
  80. 				if (C[i][k].size() == 1) continue;
  81. 				auto it = std::find(C[i][k].begin(), C[i][k].end(), C[i][j][0]);
  82. 				if (it != C[i][k].end()) {
  83. 					C[i][k].erase(it);
  84. 				}
  85. 			}
  86. 			for (std::size_t k = 0; k < P.size(); k++) {
  87. 				if (C[k][j].size() == 1) continue;
  88. 				auto it = std::find(C[k][j].begin(), C[k][j].end(), C[i][j][0]);
  89. 				if (it != C[k][j].end()) {
  90. 					C[k][j].erase(it);
  91. 				}
  92. 			}
  93. 		}
  94. 	}
  95. 	std::size_t X = 0;
  96. 	std::size_t Y = 0;
  97. 	for (std::size_t Y = 0; Y < 3; Y++) {
  98. 		for (std::size_t X = 0; X < 3; X++) {
  99.  
  100. 			for (std::size_t i = 0; i < 3; i++) {
  101. 				for (std::size_t j = 0; j < 3; j++) {
  102.  
  103. 					if (C[Y * 3 + i][X * 3 + j].size() != 1)continue;
  104.  
  105. 					for (std::size_t k = 0; k < 3; k++) {
  106. 						for (std::size_t l = 0; l < 3; l++) {
  107. 							if (C[Y * 3 + k][X * 3 + l].size() == 1)continue;
  108. 							auto it = std::find(C[Y * 3 + k][X * 3 + l].begin(), C[Y * 3 + k][X * 3 + l].end(), C[Y * 3 + i][X * 3 + j][0]);
  109. 							if (it != C[Y * 3 + k][X * 3 + l].end()) {
  110. 								C[Y * 3 + k][X * 3 + l].erase(it);
  111.  
  112. 							}
  113. 						}
  114. 					}
  115. 				}
  116. 			}
  117. 		}
  118. 	}
  119. 	return C;
  120. }
  121.  
  122.  
  123. bool IsAnswer(Grid P) {
  124. 	DType D;
  125. 	for (std::size_t Y = 0; Y < 3; Y++) {
  126. 		for (std::size_t X = 0; X < 3; X++) {
  127. 			for (std::size_t i = 0; i < 3; i++) {
  128. 				for (std::size_t j = 0; j < 3; j++) {
  129. 					D.push_back(P[Y * 3 + i][X * 3 + j]);
  130. 				}
  131. 			}
  132. 			std::sort(D.begin(), D.end());
  133. 			D.erase(std::unique(D.begin(), D.end()), D.end());
  134. 			if (D.size() != 9)return false;
  135. 		}
  136. 	}
  137.  
  138. 	for (std::size_t i = 0; i < P.size(); i++) {
  139. 		D.clear();
  140. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  141. 			D.push_back(P[i][j]);
  142. 		}
  143. 		std::sort(D.begin(), D.end());
  144. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  145. 		if (D.size() != 9)return false;
  146. 	}
  147. 	for (std::size_t i = 0; i < P.size(); i++) {
  148. 		D.clear();
  149. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  150. 			D.push_back(P[j][i]);
  151. 		}
  152. 		std::sort(D.begin(), D.end());
  153. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  154. 		if (D.size() != 9)return false;
  155. 	}
  156.  
  157. 	return true;
  158. }
  159. Grid CubeToGrid(const Cube& C, const Grid G) {
  160. 	Grid R = MakeGrid();
  161. 	for (std::size_t i = 0; i < G.size(); i++) {
  162. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  163. 			R[i][j] = C[i][j][G[i][j]];
  164. 		}
  165. 	}
  166. 	return R;
  167. }
  168. Grid CubeToProblem(const Cube& C) {
  169. 	Grid G = MakeGrid();
  170. 	for (std::size_t i = 0; i < G.size(); i++) {
  171. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  172. 			if (C[i][j].size() == 1) {
  173. 				G[i][j] = C[i][j][0];
  174. 			}
  175. 			else {
  176. 				G[i][j] = 0;
  177. 			}
  178. 		}
  179. 	}
  180. 	return G;
  181. }
  182.  
  183. bool ShowList(Cube& C) {
  184. 	std::size_t i = 1;
  185. 	double D = 0;
  186. 	for (auto& ooo : C) {
  187. 		for (auto& oo : ooo) {
  188. 			std::cout << '[' << i << ':';
  189. 			i++;
  190. 			D += oo.size();
  191. 			for (auto& o : oo) {
  192. 				std::cout << o << ',';
  193. 			}
  194. 			std::cout << ']';
  195. 		}
  196. 		std::cout << std::endl;
  197. 	}
  198. 	std::cout << D / 81.0 << std::endl;
  199. 	return true;
  200. }
  201.  
  202. bool Show(const Grid& G) {
  203. 	for (auto& oo : G) {
  204. 		for (auto& o : oo) {
  205. 			std::cout << o;
  206. 		}
  207. 		std::cout << std::endl;
  208. 	}
  209. 	std::cout << std::endl;
  210. 	std::cout << std::endl;
  211. 	return true;
  212. }
  213. DType GetAntiIntersection(DType A ,const DType& B){//積集合を取り除く？？
  214. 	for (auto& o : B) {
  215. 		auto it = std::find(A.begin(), A.end(), o);
  216. 		if(it != A.end())A.erase(it);
  217. 	}
  218. 	return A;
  219. }
  220. bool IsHorizonValid(const Grid& G,std::size_t V) {//横方向検査
  221. 	DType D;
  222. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  223. 		if(G[V][i]!=0)D.push_back(G[V][i]);
  224. 	}
  225. 	std::sort(D.begin(), D.end());
  226. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  227. 	return D.size() == 9 ? true : false;
  228. }
  229. DType GetHorizonUsing(const Grid& G,std::size_t V) {//横方向検査
  230. 	DType D;
  231. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  232. 		if(G[V][i]!=0) D.push_back(G[V][i]);
  233. 	}
  234. 	return  D;
  235. }
  236. bool HaveHorizonZero(const Grid& G,std::size_t V) {//横方向検査
  237. 	DType D;
  238. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  239. 		if (G[V][i] == 0)return true;
  240. 	}
  241. 	return false;
  242. }
  243. bool IsVerticalValid(const Grid& G,std::size_t H) {//縦方向検査
  244. 	DType D;
  245. 	for (std::size_t i = 0; i < G.size(); i++) {
  246. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  247. 	}
  248. 	std::sort(D.begin(), D.end());
  249. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  250. 	return D.size() == 9 ? true : false;
  251. }DType GetVerticalUsing(const Grid& G,std::size_t H) {//横方向検査
  252. 	DType D;
  253. 	DType T{ 0,1,2,3,4,5,6,7,8 };
  254. 	for (std::size_t i = 0; i < G.size(); i++) {
  255. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  256. 	}
  257.  
  258. 	return  D;
  259. }
  260. bool HaveVerticalZero(const Grid& G,std::size_t H) {//縦方向検査
  261. 	DType D;
  262. 	for (std::size_t i = 0; i < G.size(); i++) {
  263. 		if (G[i][H] == 0)return true;
  264. 	}
  265. 	return false;
  266. }
  267. bool IsBlockValid(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  268. 	DType D;
  269. 	for (std::size_t i = 0; i < 3; i++) {
  270. 		for (std::size_t j = 0; j < 3; j++) {
  271. 			if(G[Y*3+i][X*3+j] !=0)D.push_back(G[Y*3+i][X*3+j]);
  272. 		}
  273. 	}
  274. 	std::sort(D.begin(), D.end());
  275. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  276. 	return D.size() == 9 ? true : false;
  277. }
  278. DType GetBlockUsing(const Grid& G,std::size_t X,std::size_t Y) {//横方向検査
  279. 	DType D;
  280. 	for (std::size_t i = 0; i < 3; i++) {
  281. 		for (std::size_t j = 0; j < 3; j++) {
  282. 			if(G[Y*3+i][X*3+j] !=0) D.push_back(G[Y*3+i][X*3+j]);
  283. 		}
  284. 	}
  285.  
  286. 	return D;
  287. }
  288. bool HaveBlockNumber(const Grid& G, std::size_t X, std::size_t Y, std::size_t N) {//横方向検査
  289. 	DType D;
  290. 	for (std::size_t i = 0; i < 3; i++) {
  291. 		for (std::size_t j = 0; j < 3; j++) {
  292. 			if (G[Y * 3 + i][X * 3 + j] == N)return true;
  293. 		}
  294. 	}
  295.  
  296. 	return false;
  297. }
  298. bool HaveBlockZero(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  299. 	DType D;
  300. 	for (std::size_t i = 0; i < 3; i++) {
  301. 		for (std::size_t j = 0; j < 3; j++) {
  302. 			if (G[Y * 3 + i][X * 3 + j] == 0)return true;
  303. 		}
  304. 	}
  305.  
  306. 	return false;
  307. }
  308.  
  309.  
  310. bool Search_r(Grid& G, int Deep, RType& R, std::size_t& C) {
  311. 	C++;
  312. 	gotoxy(11, 0);
  313. //	std::cout << C << std::endl;
  314. 	if (Deep >= 81) {
  315. 		gotoxy(0, 0);
  316. 		//Show(G);
  317. 		if (IsAnswer(G)) {
  318. 			R.push_back(G);
  319. 			std::cout << "find!!" << std::endl;
  320. 			return true;
  321. 		}
  322.  
  323. 		return false;
  324. 	}	
  325.  
  326. 	static const DType T{ 1,2,3,4,5,6,7,8,9 };
  327. 	std::size_t MX = (Deep % 9) % 3;
  328. 	std::size_t MY = (Deep % 9) / 3;
  329. 	std::size_t BX = (Deep / 9) % 3;
  330. 	std::size_t BY = (Deep / 9) / 3;
  331. 	auto BU = GetBlockUsing(G, BX, BY);
  332. 	auto HU = GetHorizonUsing(G, BY*3+MY);
  333. 	auto VU = GetVerticalUsing(G, BX*3 + MX);
  334. 	DType AI;
  335.  
  336. 	if (G[BY*3 + MY][BX*3 + MX] != 0) {
  337. 		return Search_r(G, Deep + 1, R,C);
  338. 	}
  339.  
  340. 	std::copy(BU.begin(), BU.end(), std::back_inserter(AI));
  341. 	std::copy(HU.begin(), HU.end(), std::back_inserter(AI));
  342. 	std::copy(VU.begin(), VU.end(), std::back_inserter(AI));
  343. 	std::sort(AI.begin(), AI.end());
  344. 	AI.erase(std::unique(AI.begin(), AI.end()), AI.end());
  345. 	DType D = GetAntiIntersection(T, AI);
  346.  
  347. 	auto WG = G;
  348. 	if (D.size() == 0) return false;
  349. 	for (std::size_t i = 0; i < D.size(); i++) {
  350. 		WG[BY*3 + MY][BX*3 + MX] = D[i];
  351. 		gotoxy(0, 0);
  352. //		Show(WG);
  353. 		Search_r(WG, Deep + 1, R,C);
  354. 	}
  355.  
  356. 	return false;
  357.  
  358. }
  359. bool Search(Grid& G, RType& R) {
  360. 	int Deep = 0;
  361. 	std::size_t C=0;
  362. 	return Search_r(G, Deep, R, C);
  363. }
  364.  
  365.  
  366. RType MakeHoge(Grid G) {
  367. 	Cube Cu = MakeCube();
  368. 	Cube C = ReduceCube(Cu, G);
  369. 	Grid V = MakeGrid();
  370. 	RType R;
  371. 	Grid B = G;
  372. 	Grid D;
  373. 	std::uint64_t Co = 0;
  374. 	std::uint64_t Find = 1;
  375. 	do {
  376. 		D = B;
  377. 		B = CubeToProblem(C);
  378. 		C = ReduceCube(C, B);
  379. 	} while (D != B);
  380. 	gotoxy(0, 11);
  381. //	Show(B);
  382. //	ShowList(C);
  383. 	auto A = CubeToProblem(C);
  384. 	gotoxy(0, 11);
  385. //	Show(A);
  386. 	Search(A, R);
  387.  
  388. 	return R;
  389. }
  390.  
  391. int main() {
  392. 	Grid G = MakeProblem();
  393. 	RType R;
  394. 	Show(G);
  395. 	R = MakeHoge(G);
  396. 	for (auto& o : R) {
  397. 		gotoxy(0, 0);
  398. 		Show(o);
  399. 	}
  400.  
  401. 	return 0;
  402. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
150086070
708900000
090500081
900008106
001020090
075600200
506040020
300102500
040800009


find!!
154286973
738914652
692537481
923758146
861423795
475691238
516349827
389172564
247865319
https://ideone.com/mtcLac
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!