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. 	Grid R2{
  40. 		{ 0,0,5,3,0,0,0,0,0, },
  41. 		{ 8,0,0,0,0,0,0,2,0, },
  42. 		{ 0,7,0,0,1,0,5,0,0, },
  43. 		{ 4,0,0,0,0,5,3,0,0, },
  44. 		{ 0,1,0,0,7,0,0,0,6, },
  45. 		{ 0,0,3,2,0,0,0,8,0, },
  46. 		{ 0,6,0,5,0,0,0,0,9, },
  47. 		{ 0,0,4,0,0,0,0,3,0, },
  48. 		{ 0,0,0,0,0,9,7,0,0, },
  49. };
  50. 	return R2;
  51.  
  52. }
  53.  
  54. Grid MakeGrid() {
  55. 	Grid G(9);
  56. 	for (auto& o : G) {
  57. 		o.assign(9, 0);
  58. 	}
  59. 	return G;
  60. }
  61. Cube MakeCube() {
  62. 	DType D{ 1,2,3,4,5,6,7,8,9 };
  63. 	Cube C(9);
  64. 	for (auto& oo : C) {
  65. 		oo.resize(9);
  66. 		for (auto& o : oo) {
  67. 			o = D;
  68. 		}
  69. 	}
  70.  
  71. 	return C;
  72. }
  73.  
  74. Cube ReduceCube(const Cube& Cu, const Grid& P) {
  75. 	Cube C = Cu;
  76. 	for (std::size_t i = 0; i < P.size(); i++) {
  77. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  78. 			if (P[i][j] != 0) {
  79. 				C[i][j].clear();
  80. 				C[i][j].push_back(P[i][j]);
  81. 			}
  82.  
  83. 		}
  84. 	}
  85. 	for (std::size_t i = 0; i < C.size(); i++) {
  86. 		for (std::size_t j = 0; j < C[i].size(); j++) {
  87. 			if (C[i][j].size() != 1)continue;
  88.  
  89.  
  90. 			for (std::size_t k = 0; k < P.size(); k++) {
  91. 				if (C[i][k].size() == 1) continue;
  92. 				auto it = std::find(C[i][k].begin(), C[i][k].end(), C[i][j][0]);
  93. 				if (it != C[i][k].end()) {
  94. 					C[i][k].erase(it);
  95. 				}
  96. 			}
  97. 			for (std::size_t k = 0; k < P.size(); k++) {
  98. 				if (C[k][j].size() == 1) continue;
  99. 				auto it = std::find(C[k][j].begin(), C[k][j].end(), C[i][j][0]);
  100. 				if (it != C[k][j].end()) {
  101. 					C[k][j].erase(it);
  102. 				}
  103. 			}
  104. 		}
  105. 	}
  106. 	std::size_t X = 0;
  107. 	std::size_t Y = 0;
  108. 	for (std::size_t Y = 0; Y < 3; Y++) {
  109. 		for (std::size_t X = 0; X < 3; X++) {
  110.  
  111. 			for (std::size_t i = 0; i < 3; i++) {
  112. 				for (std::size_t j = 0; j < 3; j++) {
  113.  
  114. 					if (C[Y * 3 + i][X * 3 + j].size() != 1)continue;
  115.  
  116. 					for (std::size_t k = 0; k < 3; k++) {
  117. 						for (std::size_t l = 0; l < 3; l++) {
  118. 							if (C[Y * 3 + k][X * 3 + l].size() == 1)continue;
  119. 							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]);
  120. 							if (it != C[Y * 3 + k][X * 3 + l].end()) {
  121. 								C[Y * 3 + k][X * 3 + l].erase(it);
  122.  
  123. 							}
  124. 						}
  125. 					}
  126. 				}
  127. 			}
  128. 		}
  129. 	}
  130. 	return C;
  131. }
  132.  
  133.  
  134. bool IsAnswer(Grid P) {
  135. 	DType D;
  136. 	for (std::size_t Y = 0; Y < 3; Y++) {
  137. 		for (std::size_t X = 0; X < 3; X++) {
  138. 			for (std::size_t i = 0; i < 3; i++) {
  139. 				for (std::size_t j = 0; j < 3; j++) {
  140. 					D.push_back(P[Y * 3 + i][X * 3 + j]);
  141. 				}
  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. 	}
  148.  
  149. 	for (std::size_t i = 0; i < P.size(); i++) {
  150. 		D.clear();
  151. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  152. 			D.push_back(P[i][j]);
  153. 		}
  154. 		std::sort(D.begin(), D.end());
  155. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  156. 		if (D.size() != 9)return false;
  157. 	}
  158. 	for (std::size_t i = 0; i < P.size(); i++) {
  159. 		D.clear();
  160. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  161. 			D.push_back(P[j][i]);
  162. 		}
  163. 		std::sort(D.begin(), D.end());
  164. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  165. 		if (D.size() != 9)return false;
  166. 	}
  167.  
  168. 	return true;
  169. }
  170. Grid CubeToGrid(const Cube& C, const Grid G) {
  171. 	Grid R = MakeGrid();
  172. 	for (std::size_t i = 0; i < G.size(); i++) {
  173. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  174. 			R[i][j] = C[i][j][G[i][j]];
  175. 		}
  176. 	}
  177. 	return R;
  178. }
  179. Grid CubeToProblem(const Cube& C) {
  180. 	Grid G = MakeGrid();
  181. 	for (std::size_t i = 0; i < G.size(); i++) {
  182. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  183. 			if (C[i][j].size() == 1) {
  184. 				G[i][j] = C[i][j][0];
  185. 			}
  186. 			else {
  187. 				G[i][j] = 0;
  188. 			}
  189. 		}
  190. 	}
  191. 	return G;
  192. }
  193.  
  194. bool ShowList(Cube& C) {
  195. 	std::size_t i = 1;
  196. 	double D = 0;
  197. 	for (auto& ooo : C) {
  198. 		for (auto& oo : ooo) {
  199. 			std::cout << '[' << i << ':';
  200. 			i++;
  201. 			D += oo.size();
  202. 			for (auto& o : oo) {
  203. 				std::cout << o << ',';
  204. 			}
  205. 			std::cout << ']';
  206. 		}
  207. 		std::cout << std::endl;
  208. 	}
  209. 	std::cout << D / 81.0 << std::endl;
  210. 	return true;
  211. }
  212.  
  213. bool Show(const Grid& G) {
  214. 	for (auto& oo : G) {
  215. 		for (auto& o : oo) {
  216. 			std::cout << o;
  217. 		}
  218. 		std::cout << std::endl;
  219. 	}
  220. 	std::cout << std::endl;
  221. 	std::cout << std::endl;
  222. 	return true;
  223. }
  224. DType GetAntiIntersection(DType A ,const DType& B){//積集合を取り除く？？
  225. 	for (auto& o : B) {
  226. 		auto it = std::find(A.begin(), A.end(), o);
  227. 		if(it != A.end())A.erase(it);
  228. 	}
  229. 	return A;
  230. }
  231. bool IsHorizonValid(const Grid& G,std::size_t V) {//横方向検査
  232. 	DType D;
  233. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  234. 		if(G[V][i]!=0)D.push_back(G[V][i]);
  235. 	}
  236. 	std::sort(D.begin(), D.end());
  237. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  238. 	return D.size() == 9 ? true : false;
  239. }
  240. DType GetHorizonUsing(const Grid& G,std::size_t V) {//横方向検査
  241. 	DType D;
  242. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  243. 		if(G[V][i]!=0) D.push_back(G[V][i]);
  244. 	}
  245. 	return  D;
  246. }
  247. bool HaveHorizonZero(const Grid& G,std::size_t V) {//横方向検査
  248. 	DType D;
  249. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  250. 		if (G[V][i] == 0)return true;
  251. 	}
  252. 	return false;
  253. }
  254. bool IsVerticalValid(const Grid& G,std::size_t H) {//縦方向検査
  255. 	DType D;
  256. 	for (std::size_t i = 0; i < G.size(); i++) {
  257. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  258. 	}
  259. 	std::sort(D.begin(), D.end());
  260. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  261. 	return D.size() == 9 ? true : false;
  262. }DType GetVerticalUsing(const Grid& G,std::size_t H) {//横方向検査
  263. 	DType D;
  264. 	DType T{ 0,1,2,3,4,5,6,7,8 };
  265. 	for (std::size_t i = 0; i < G.size(); i++) {
  266. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  267. 	}
  268.  
  269. 	return  D;
  270. }
  271. bool HaveVerticalZero(const Grid& G,std::size_t H) {//縦方向検査
  272. 	DType D;
  273. 	for (std::size_t i = 0; i < G.size(); i++) {
  274. 		if (G[i][H] == 0)return true;
  275. 	}
  276. 	return false;
  277. }
  278. bool IsBlockValid(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  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. 	std::sort(D.begin(), D.end());
  286. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  287. 	return D.size() == 9 ? true : false;
  288. }
  289. DType GetBlockUsing(const Grid& G,std::size_t X,std::size_t Y) {//横方向検査
  290. 	DType D;
  291. 	for (std::size_t i = 0; i < 3; i++) {
  292. 		for (std::size_t j = 0; j < 3; j++) {
  293. 			if(G[Y*3+i][X*3+j] !=0) D.push_back(G[Y*3+i][X*3+j]);
  294. 		}
  295. 	}
  296.  
  297. 	return D;
  298. }
  299. bool HaveBlockNumber(const Grid& G, std::size_t X, std::size_t Y, std::size_t N) {//横方向検査
  300. 	DType D;
  301. 	for (std::size_t i = 0; i < 3; i++) {
  302. 		for (std::size_t j = 0; j < 3; j++) {
  303. 			if (G[Y * 3 + i][X * 3 + j] == N)return true;
  304. 		}
  305. 	}
  306.  
  307. 	return false;
  308. }
  309. bool HaveBlockZero(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  310. 	DType D;
  311. 	for (std::size_t i = 0; i < 3; i++) {
  312. 		for (std::size_t j = 0; j < 3; j++) {
  313. 			if (G[Y * 3 + i][X * 3 + j] == 0)return true;
  314. 		}
  315. 	}
  316.  
  317. 	return false;
  318. }
  319.  
  320.  
  321. bool Search_r(Grid& G, int Deep, RType& R, std::size_t& C) {
  322. 	C++;
  323. 	gotoxy(11, 0);
  324. //	std::cout << C << std::endl;
  325. 	if (Deep >= 81) {
  326. 		gotoxy(0, 0);
  327. 		//Show(G);
  328. 		if (IsAnswer(G)) {
  329. 			R.push_back(G);
  330. 			std::cout << "find!!" << std::endl;
  331. 			return true;
  332. 		}
  333.  
  334. 		return false;
  335. 	}	
  336.  
  337. 	static const DType T{ 1,2,3,4,5,6,7,8,9 };
  338. 	std::size_t MX = (Deep % 9) % 3;
  339. 	std::size_t MY = (Deep % 9) / 3;
  340. 	std::size_t BX = (Deep / 9) % 3;
  341. 	std::size_t BY = (Deep / 9) / 3;
  342. 	auto BU = GetBlockUsing(G, BX, BY);
  343. 	auto HU = GetHorizonUsing(G, BY*3+MY);
  344. 	auto VU = GetVerticalUsing(G, BX*3 + MX);
  345. 	DType AI;
  346.  
  347. 	if (G[BY*3 + MY][BX*3 + MX] != 0) {
  348. 		return Search_r(G, Deep + 1, R,C);
  349. 	}
  350.  
  351. 	std::copy(BU.begin(), BU.end(), std::back_inserter(AI));
  352. 	std::copy(HU.begin(), HU.end(), std::back_inserter(AI));
  353. 	std::copy(VU.begin(), VU.end(), std::back_inserter(AI));
  354. 	std::sort(AI.begin(), AI.end());
  355. 	AI.erase(std::unique(AI.begin(), AI.end()), AI.end());
  356. 	DType D = GetAntiIntersection(T, AI);
  357.  
  358. 	auto WG = G;
  359. 	if (D.size() == 0) return false;
  360. 	for (std::size_t i = 0; i < D.size(); i++) {
  361. 		WG[BY*3 + MY][BX*3 + MX] = D[i];
  362. 		gotoxy(0, 0);
  363. //		Show(WG);
  364. 		Search_r(WG, Deep + 1, R,C);
  365. 	}
  366.  
  367. 	return false;
  368.  
  369. }
  370. bool Search(Grid& G, RType& R) {
  371. 	int Deep = 0;
  372. 	std::size_t C=0;
  373. 	return Search_r(G, Deep, R, C);
  374. }
  375.  
  376.  
  377. RType MakeHoge(Grid G) {
  378. 	Cube Cu = MakeCube();
  379. 	Cube C = ReduceCube(Cu, G);
  380. 	Grid V = MakeGrid();
  381. 	RType R;
  382. 	Grid B = G;
  383. 	Grid D;
  384. 	std::uint64_t Co = 0;
  385. 	std::uint64_t Find = 1;
  386. 	do {
  387. 		D = B;
  388. 		B = CubeToProblem(C);
  389. 		C = ReduceCube(C, B);
  390. 	} while (D != B);
  391. 	gotoxy(0, 11);
  392. //	Show(B);
  393. //	ShowList(C);
  394. 	auto A = CubeToProblem(C);
  395. 	gotoxy(0, 11);
  396. //	Show(A);
  397. 	Search(A, R);
  398.  
  399. 	return R;
  400. }
  401.  
  402. int main() {
  403. 	Grid G = MakeProblem();
  404. 	RType R;
  405. 	Show(G);
  406. 	R = MakeHoge(G);
  407. 	for (auto& o : R) {
  408. 		gotoxy(0, 0);
  409. 		Show(o);
  410. 	}
  411.  
  412. 	return 0;
  413. }
Success #stdin #stdout 0.08s 15272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700


find!!
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764
https://ideone.com/NqxATw
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!