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. 	return;
  16. 	COORD Pos = { static_cast<SHORT>(X),static_cast<SHORT>(Y) };//WINDOWS定義の構造体です。
  17. 	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);//windows定義の関数です。カーソルを移動します。
  18. 	return;
  19. }
  20. #else
  21. void gotoxy(int X, int Y) {
  22. 	return;
  23. }
  24. #endif
  25.  
  26.  
  27. Grid MakeProblem() {
  28. 	Grid R{
  29. 		{ 1,5,0,0,8,6,0,7,0, },
  30. 		{ 7,0,8,9,0,0,0,0,0, },
  31. 		{ 0,9,0,5,0,0,0,8,1, },
  32. 		{ 9,0,0,0,0,8,1,0,6, },
  33. 		{ 0,0,1,0,2,0,0,9,0, },
  34. 		{ 0,7,5,6,0,0,2,0,0, },
  35. 		{ 5,0,6,0,4,0,0,2,0, },
  36. 		{ 3,0,0,1,0,2,5,0,0, },
  37. 		{ 0,4,0,8,0,0,0,0,9, },
  38. 	};
  39.  
  40. 	Grid R2{
  41. 		{ 0,0,5,3,0,0,0,0,0, },
  42. 		{ 8,0,0,0,0,0,0,2,0, },
  43. 		{ 0,7,0,0,1,0,5,0,0, },
  44. 		{ 4,0,0,0,0,5,3,0,0, },
  45. 		{ 0,1,0,0,7,0,0,0,6, },
  46. 		{ 0,0,3,2,0,0,0,8,0, },
  47. 		{ 0,6,0,5,0,0,0,0,9, },
  48. 		{ 0,0,4,0,0,0,0,3,0, },
  49. 		{ 0,0,0,0,0,9,7,0,0, },
  50. };
  51. 	return R2;
  52.  
  53. }
  54.  
  55. Grid MakeProblem2() {
  56. 	const std::uint64_t N = 30;
  57. 	Grid G(9);
  58. 	for (auto& o : G) {
  59. 		o.resize(9);
  60. 	}
  61.  
  62. 	std::random_device rd;
  63. 	std::mt19937 mt(rd());
  64. 	std::uniform_int_distribution<std::int64_t> ui(0, 8);
  65.  
  66. 	auto Check = [](Grid& g,std::uint64_t X, std::uint64_t Y,std::uint64_t V)->bool {
  67. 		for (std::size_t i = 0; i < 9; i++) {
  68. 			if (g[i][X] == V) return false;
  69. 		}
  70. 		for (std::size_t i = 0; i < 9; i++) {
  71. 			if (g[Y][i] == V) return false;
  72. 		}
  73. 		return true;
  74. 	};
  75. 	auto Check2 = [](Grid& g,std::uint64_t X, std::uint64_t Y,std::uint64_t V)->bool {
  76. 		std::uint64_t BX = X / 3;
  77. 		std::uint64_t BY = Y / 3;
  78.  
  79. 		for (std::size_t i = 0; i < 3; i++) {
  80. 			for (std::size_t j = 0; j < 3; j++) {
  81. 				if (g[i + (BY * 3)][j + (BX * 3)] == V) return false;
  82. 			}
  83. 		}
  84.  
  85.  
  86. 		return true;
  87. 	};
  88. 	std::uint64_t C = 0;
  89. 	std::uint64_t X = 0;
  90. 	std::uint64_t Y = 0;
  91. 	for (std::int64_t i = 0; i < N; i++) {
  92. 		X = ui(mt);
  93. 		Y = ui(mt);
  94.  
  95. 		if ((Check(G, X, Y, C + 1) && Check2(G, X, Y, C + 1)&& G[Y][X] == 0) == true) {
  96. 			G[Y][X] = C + 1;
  97.  
  98. 		}
  99. 		else {
  100. 			i--;
  101. 		}
  102. 			C++;
  103. 			C %= 9;
  104. 	}
  105.  
  106.  
  107. 	return G;
  108.  
  109.  
  110.  
  111. }
  112.  
  113. Grid EraseNumber(Grid& G, std::uint64_t N) {
  114. 	if (N > 80) return Grid();
  115.  
  116. 	std::random_device rd;
  117. 	std::mt19937 mt(rd());
  118. 	std::uniform_int_distribution<std::int64_t> ui(0, 8);
  119. 	std::uint64_t X = 0;
  120. 	std::uint64_t Y = 0;
  121. 	for (std::int64_t i = 0; i < N; i++) {
  122. 		X = ui(mt);
  123. 		Y = ui(mt);
  124.  
  125. 		if (G[Y][X] != 0) {
  126. 			G[Y][X] = 0;
  127. 		}
  128. 		else {
  129. 			i--;
  130. 		}
  131. 	}
  132. 	return G;
  133. }
  134.  
  135.  
  136. Grid MakeGrid() {
  137. 	Grid G(9);
  138. 	for (auto& o : G) {
  139. 		o.assign(9, 0);
  140. 	}
  141. 	return G;
  142. }
  143. Cube MakeCube() {
  144. 	DType D{ 1,2,3,4,5,6,7,8,9 };
  145. 	Cube C(9);
  146. 	for (auto& oo : C) {
  147. 		oo.resize(9);
  148. 		for (auto& o : oo) {
  149. 			o = D;
  150. 		}
  151. 	}
  152.  
  153. 	return C;
  154. }
  155.  
  156. Cube ReduceCube(const Cube& Cu, const Grid& P) {
  157. 	Cube C = Cu;
  158. 	for (std::size_t i = 0; i < P.size(); i++) {
  159. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  160. 			if (P[i][j] != 0) {
  161. 				C[i][j].clear();
  162. 				C[i][j].push_back(P[i][j]);
  163. 			}
  164.  
  165. 		}
  166. 	}
  167. 	for (std::size_t i = 0; i < C.size(); i++) {
  168. 		for (std::size_t j = 0; j < C[i].size(); j++) {
  169. 			if (C[i][j].size() != 1)continue;
  170.  
  171.  
  172. 			for (std::size_t k = 0; k < P.size(); k++) {
  173. 				if (C[i][k].size() == 1) continue;
  174. 				auto it = std::find(C[i][k].begin(), C[i][k].end(), C[i][j][0]);
  175. 				if (it != C[i][k].end()) {
  176. 					C[i][k].erase(it);
  177. 				}
  178. 			}
  179. 			for (std::size_t k = 0; k < P.size(); k++) {
  180. 				if (C[k][j].size() == 1) continue;
  181. 				auto it = std::find(C[k][j].begin(), C[k][j].end(), C[i][j][0]);
  182. 				if (it != C[k][j].end()) {
  183. 					C[k][j].erase(it);
  184. 				}
  185. 			}
  186. 		}
  187. 	}
  188. 	std::size_t X = 0;
  189. 	std::size_t Y = 0;
  190. 	for (std::size_t Y = 0; Y < 3; Y++) {
  191. 		for (std::size_t X = 0; X < 3; X++) {
  192.  
  193. 			for (std::size_t i = 0; i < 3; i++) {
  194. 				for (std::size_t j = 0; j < 3; j++) {
  195.  
  196. 					if (C[Y * 3 + i][X * 3 + j].size() != 1)continue;
  197.  
  198. 					for (std::size_t k = 0; k < 3; k++) {
  199. 						for (std::size_t l = 0; l < 3; l++) {
  200. 							if (C[Y * 3 + k][X * 3 + l].size() == 1)continue;
  201. 							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]);
  202. 							if (it != C[Y * 3 + k][X * 3 + l].end()) {
  203. 								C[Y * 3 + k][X * 3 + l].erase(it);
  204.  
  205. 							}
  206. 						}
  207. 					}
  208. 				}
  209. 			}
  210. 		}
  211. 	}
  212. 	return C;
  213. }
  214.  
  215.  
  216. bool IsAnswer(Grid P) {
  217. 	DType D;
  218. 	for (std::size_t Y = 0; Y < 3; Y++) {
  219. 		for (std::size_t X = 0; X < 3; X++) {
  220. 			for (std::size_t i = 0; i < 3; i++) {
  221. 				for (std::size_t j = 0; j < 3; j++) {
  222. 					D.push_back(P[Y * 3 + i][X * 3 + j]);
  223. 				}
  224. 			}
  225. 			std::sort(D.begin(), D.end());
  226. 			D.erase(std::unique(D.begin(), D.end()), D.end());
  227. 			if (D.size() != 9)return false;
  228. 		}
  229. 	}
  230.  
  231. 	for (std::size_t i = 0; i < P.size(); i++) {
  232. 		D.clear();
  233. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  234. 			D.push_back(P[i][j]);
  235. 		}
  236. 		std::sort(D.begin(), D.end());
  237. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  238. 		if (D.size() != 9)return false;
  239. 	}
  240. 	for (std::size_t i = 0; i < P.size(); i++) {
  241. 		D.clear();
  242. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  243. 			D.push_back(P[j][i]);
  244. 		}
  245. 		std::sort(D.begin(), D.end());
  246. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  247. 		if (D.size() != 9)return false;
  248. 	}
  249.  
  250. 	return true;
  251. }
  252. Grid CubeToGrid(const Cube& C, const Grid G) {
  253. 	Grid R = MakeGrid();
  254. 	for (std::size_t i = 0; i < G.size(); i++) {
  255. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  256. 			R[i][j] = C[i][j][G[i][j]];
  257. 		}
  258. 	}
  259. 	return R;
  260. }
  261. Grid CubeToProblem(const Cube& C) {
  262. 	Grid G = MakeGrid();
  263. 	for (std::size_t i = 0; i < G.size(); i++) {
  264. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  265. 			if (C[i][j].size() == 1) {
  266. 				G[i][j] = C[i][j][0];
  267. 			}
  268. 			else {
  269. 				G[i][j] = 0;
  270. 			}
  271. 		}
  272. 	}
  273. 	return G;
  274. }
  275.  
  276. bool ShowList(Cube& C) {
  277. 	std::size_t i = 1;
  278. 	double D = 0;
  279. 	for (auto& ooo : C) {
  280. 		for (auto& oo : ooo) {
  281. 			std::cout << '[' << i << ':';
  282. 			i++;
  283. 			D += oo.size();
  284. 			for (auto& o : oo) {
  285. 				std::cout << o << ',';
  286. 			}
  287. 			std::cout << ']';
  288. 		}
  289. 		std::cout << std::endl;
  290. 	}
  291. 	std::cout << D / 81.0 << std::endl;
  292. 	return true;
  293. }
  294.  
  295. bool Show(const Grid& G) {
  296. 	for (auto& oo : G) {
  297. 		for (auto& o : oo) {
  298. 			std::cout << o;
  299. 		}
  300. 		std::cout << std::endl;
  301. 	}
  302. 	std::cout << std::endl;
  303. 	std::cout << std::endl;
  304. 	return true;
  305. }
  306. DType GetAntiIntersection(DType A ,const DType& B){//積集合を取り除く？？
  307. 	for (auto& o : B) {
  308. 		auto it = std::find(A.begin(), A.end(), o);
  309. 		if(it != A.end())A.erase(it);
  310. 	}
  311. 	return A;
  312. }
  313. bool IsHorizonValid(const Grid& G,std::size_t V) {//横方向検査
  314. 	DType D;
  315. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  316. 		if(G[V][i]!=0)D.push_back(G[V][i]);
  317. 	}
  318. 	std::sort(D.begin(), D.end());
  319. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  320. 	return D.size() == 9 ? true : false;
  321. }
  322. DType GetHorizonUsing(const Grid& G,std::size_t V) {//横方向検査
  323. 	DType D;
  324. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  325. 		if(G[V][i]!=0) D.push_back(G[V][i]);
  326. 	}
  327. 	return  D;
  328. }
  329. bool HaveHorizonZero(const Grid& G,std::size_t V) {//横方向検査
  330. 	DType D;
  331. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  332. 		if (G[V][i] == 0)return true;
  333. 	}
  334. 	return false;
  335. }
  336. bool IsVerticalValid(const Grid& G,std::size_t H) {//縦方向検査
  337. 	DType D;
  338. 	for (std::size_t i = 0; i < G.size(); i++) {
  339. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  340. 	}
  341. 	std::sort(D.begin(), D.end());
  342. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  343. 	return D.size() == 9 ? true : false;
  344. }DType GetVerticalUsing(const Grid& G,std::size_t H) {//横方向検査
  345. 	DType D;
  346. 	DType T{ 0,1,2,3,4,5,6,7,8 };
  347. 	for (std::size_t i = 0; i < G.size(); i++) {
  348. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  349. 	}
  350.  
  351. 	return  D;
  352. }
  353. bool HaveVerticalZero(const Grid& G,std::size_t H) {//縦方向検査
  354. 	DType D;
  355. 	for (std::size_t i = 0; i < G.size(); i++) {
  356. 		if (G[i][H] == 0)return true;
  357. 	}
  358. 	return false;
  359. }
  360. bool IsBlockValid(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  361. 	DType D;
  362. 	for (std::size_t i = 0; i < 3; i++) {
  363. 		for (std::size_t j = 0; j < 3; j++) {
  364. 			if(G[Y*3+i][X*3+j] !=0)D.push_back(G[Y*3+i][X*3+j]);
  365. 		}
  366. 	}
  367. 	std::sort(D.begin(), D.end());
  368. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  369. 	return D.size() == 9 ? true : false;
  370. }
  371. DType GetBlockUsing(const Grid& G,std::size_t X,std::size_t Y) {//横方向検査
  372. 	DType D;
  373. 	for (std::size_t i = 0; i < 3; i++) {
  374. 		for (std::size_t j = 0; j < 3; j++) {
  375. 			if(G[Y*3+i][X*3+j] !=0) D.push_back(G[Y*3+i][X*3+j]);
  376. 		}
  377. 	}
  378.  
  379. 	return D;
  380. }
  381. bool HaveBlockNumber(const Grid& G, std::size_t X, std::size_t Y, std::size_t N) {//横方向検査
  382. 	DType D;
  383. 	for (std::size_t i = 0; i < 3; i++) {
  384. 		for (std::size_t j = 0; j < 3; j++) {
  385. 			if (G[Y * 3 + i][X * 3 + j] == N)return true;
  386. 		}
  387. 	}
  388.  
  389. 	return false;
  390. }
  391. bool HaveBlockZero(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  392. 	DType D;
  393. 	for (std::size_t i = 0; i < 3; i++) {
  394. 		for (std::size_t j = 0; j < 3; j++) {
  395. 			if (G[Y * 3 + i][X * 3 + j] == 0)return true;
  396. 		}
  397. 	}
  398.  
  399. 	return false;
  400. }
  401.  
  402.  
  403. bool Search_r(Grid& G, int Deep, RType& R, std::size_t& C) {
  404. 	C++;
  405. 	gotoxy(11, 0);
  406. //	std::cout << C << std::endl;
  407. 	if (Deep >= 81) {
  408. 		gotoxy(0, 0);
  409. 		//Show(G);
  410. 		if (IsAnswer(G)) {
  411. 			R.push_back(G);
  412. 			std::cout << "find!!" << std::endl;
  413. 			return true;
  414. 		}
  415.  
  416. 		return false;
  417. 	}	
  418.  
  419. 	static const DType T{ 1,2,3,4,5,6,7,8,9 };
  420. 	std::size_t MX = (Deep % 9) % 3;
  421. 	std::size_t MY = (Deep % 9) / 3;
  422. 	std::size_t BX = (Deep / 9) % 3;
  423. 	std::size_t BY = (Deep / 9) / 3;
  424. 	auto BU = GetBlockUsing(G, BX, BY);
  425. 	auto HU = GetHorizonUsing(G, BY*3+MY);
  426. 	auto VU = GetVerticalUsing(G, BX*3 + MX);
  427. 	DType AI;
  428.  
  429. 	if (G[BY*3 + MY][BX*3 + MX] != 0) {
  430. 		return Search_r(G, Deep + 1, R,C);
  431. 	}
  432.  
  433. 	std::copy(BU.begin(), BU.end(), std::back_inserter(AI));
  434. 	std::copy(HU.begin(), HU.end(), std::back_inserter(AI));
  435. 	std::copy(VU.begin(), VU.end(), std::back_inserter(AI));
  436. 	std::sort(AI.begin(), AI.end());
  437. 	AI.erase(std::unique(AI.begin(), AI.end()), AI.end());
  438. 	DType D = GetAntiIntersection(T, AI);
  439.  
  440. 	auto WG = G;
  441. 	if (D.size() == 0) return false;
  442. 	for (std::size_t i = 0; i < D.size(); i++) {
  443. 		WG[BY*3 + MY][BX*3 + MX] = D[i];
  444. 		gotoxy(0, 0);
  445. //		Show(WG);
  446. 		Search_r(WG, Deep + 1, R,C);
  447. 	}
  448.  
  449. 	return false;
  450.  
  451. }
  452. bool Search(Grid& G, RType& R) {
  453. 	int Deep = 0;
  454. 	std::size_t C=0;
  455. 	return Search_r(G, Deep, R, C);
  456. }
  457.  
  458.  
  459. RType MakeHoge(Grid G) {
  460. 	Cube Cu = MakeCube();
  461. 	Cube C = ReduceCube(Cu, G);
  462. 	Grid V = MakeGrid();
  463. 	RType R;
  464. 	Grid B = G;
  465. 	Grid D;
  466. 	std::uint64_t Co = 0;
  467. 	std::uint64_t Find = 1;
  468. 	do {
  469. 		D = B;
  470. 		B = CubeToProblem(C);
  471. 		C = ReduceCube(C, B);
  472. 	} while (D != B);
  473. 	gotoxy(0, 11);
  474. //	Show(B);
  475. //	ShowList(C);
  476. 	auto A = CubeToProblem(C);
  477. 	gotoxy(0, 11);
  478. //	Show(A);
  479. 	Search(A, R);
  480. 	std::sort(R.begin(), R.end());
  481. 	R.erase(std::unique(R.begin(), R.end()), R.end());
  482. 	gotoxy(0, 11);
  483. 	return R;
  484. }
  485.  
  486.  
  487.  
  488. int main() {
  489. 	std::cout << "Generateing!" << std::endl;
  490. 	F:
  491. 	Grid G = MakeProblem2();
  492. 	RType R;
  493. 	R = MakeHoge(G);
  494. 	if (R.size() == 0) goto F;
  495. 	std::cout << "Show Problem Seed." << std::endl;
  496. 	Show(G);
  497. /*
  498. 	for (auto& o : R) {
  499. //		gotoxy(0, 0);
  500. 		Show(o);
  501. 	}
  502. 	*/
  503. 	G = R[0];
  504.  
  505. 	std::cout << "Show Problem Seed2." << std::endl;
  506. 	Show(G);
  507. 	Grid A = EraseNumber(G, 45);
  508. 	std::cout << "Number Erased!" << std::endl;
  509. 	Show(A);
  510.  
  511. 	R=MakeHoge(A);
  512. 	std::cout << "Show Answer!" << std::endl;
  513. 	for (auto& o : R) {
  514. //		gotoxy(0, 0);
  515. 		Show(o);
  516. 	}
  517. 	return 0;
  518. }
Success #stdin #stdout 0.01s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generateing!
find!!
find!!
find!!
find!!
find!!
Show Problem Seed.
300100270
507083064
106275009
060000800
005010007
000509400
000040003
000008000
090001040


Show Problem Seed2.
389164275
527983164
146275389
962437851
435816927
718529436
851642793
674398512
293751648


Number Erased!
080100075
507980000
000205000
960400800
000816007
718029006
051602090
674000000
003751000


find!!
find!!
find!!
Show Answer!
389164275
527983164
146275389
962437851
435816927
718529436
851642793
674398512
293751648


389164275
527983164
146275389
965437812
432816957
718529436
851642793
674398521
293751648


389164275
527983164
146275389
965437821
432816957
718529436
851642793
674398512
293751648
https://ideone.com/4gJj7c
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!