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. 	std::size_t I = 0;
  92. 	DType S(9);
  93. 	DType V{ 0,1,2,3,4,5,6,7,8, };
  94. 	std::shuffle(V.begin(), V.end(),mt);
  95. 	for (std::int64_t i = 0; i < N; i++) {
  96. 		X = ui(mt);
  97. 		Y = ui(mt);
  98.  
  99. 		C = V[I%V.size()];
  100. 		I++;
  101. 		if (S[C] >= 9) {
  102. 			V.clear();
  103. 			for (std::size_t j = 0; j < S.size(); j++) {
  104. 				if (S[j] >= 9)continue;
  105. 				V.push_back(i);
  106. 			}
  107. 			std::shuffle(V.begin(), V.end(),mt);
  108. 			i--;
  109. 			continue;
  110. 		}
  111. 		S[C]++;
  112.  
  113. 		if ((Check(G, X, Y, C + 1) && Check2(G, X, Y, C + 1)&& G[Y][X] == 0) == true) {
  114. 			G[Y][X] = C + 1;
  115.  
  116. 		}
  117. 		else {
  118. 			S[C]--;
  119. 			i--;
  120. 		}
  121.  
  122. 	}
  123. 	return G;
  124.  
  125. }
  126.  
  127. Grid EraseNumber(Grid& G, std::uint64_t N) {
  128. 	if (N > 80) return Grid();
  129.  
  130. 	std::random_device rd;
  131. 	std::mt19937 mt(rd());
  132. 	std::uniform_int_distribution<std::int64_t> ui(0, 8);
  133. 	std::uint64_t X = 0;
  134. 	std::uint64_t Y = 0;
  135. 	for (std::int64_t i = 0; i < N; i++) {
  136. 		X = ui(mt);
  137. 		Y = ui(mt);
  138.  
  139. 		if (G[Y][X] != 0) {
  140. 			G[Y][X] = 0;
  141. 		}
  142. 		else {
  143. 			i--;
  144. 		}
  145. 	}
  146. 	return G;
  147. }
  148.  
  149.  
  150. Grid MakeGrid() {
  151. 	Grid G(9);
  152. 	for (auto& o : G) {
  153. 		o.assign(9, 0);
  154. 	}
  155. 	return G;
  156. }
  157. Cube MakeCube() {
  158. 	DType D{ 1,2,3,4,5,6,7,8,9 };
  159. 	Cube C(9);
  160. 	for (auto& oo : C) {
  161. 		oo.resize(9);
  162. 		for (auto& o : oo) {
  163. 			o = D;
  164. 		}
  165. 	}
  166.  
  167. 	return C;
  168. }
  169.  
  170. Cube ReduceCube(const Cube& Cu, const Grid& P) {
  171. 	Cube C = Cu;
  172. 	for (std::size_t i = 0; i < P.size(); i++) {
  173. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  174. 			if (P[i][j] != 0) {
  175. 				C[i][j].clear();
  176. 				C[i][j].push_back(P[i][j]);
  177. 			}
  178.  
  179. 		}
  180. 	}
  181. 	for (std::size_t i = 0; i < C.size(); i++) {
  182. 		for (std::size_t j = 0; j < C[i].size(); j++) {
  183. 			if (C[i][j].size() != 1)continue;
  184.  
  185.  
  186. 			for (std::size_t k = 0; k < P.size(); k++) {
  187. 				if (C[i][k].size() == 1) continue;
  188. 				auto it = std::find(C[i][k].begin(), C[i][k].end(), C[i][j][0]);
  189. 				if (it != C[i][k].end()) {
  190. 					C[i][k].erase(it);
  191. 				}
  192. 			}
  193. 			for (std::size_t k = 0; k < P.size(); k++) {
  194. 				if (C[k][j].size() == 1) continue;
  195. 				auto it = std::find(C[k][j].begin(), C[k][j].end(), C[i][j][0]);
  196. 				if (it != C[k][j].end()) {
  197. 					C[k][j].erase(it);
  198. 				}
  199. 			}
  200. 		}
  201. 	}
  202. 	std::size_t X = 0;
  203. 	std::size_t Y = 0;
  204. 	for (std::size_t Y = 0; Y < 3; Y++) {
  205. 		for (std::size_t X = 0; X < 3; X++) {
  206.  
  207. 			for (std::size_t i = 0; i < 3; i++) {
  208. 				for (std::size_t j = 0; j < 3; j++) {
  209.  
  210. 					if (C[Y * 3 + i][X * 3 + j].size() != 1)continue;
  211.  
  212. 					for (std::size_t k = 0; k < 3; k++) {
  213. 						for (std::size_t l = 0; l < 3; l++) {
  214. 							if (C[Y * 3 + k][X * 3 + l].size() == 1)continue;
  215. 							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]);
  216. 							if (it != C[Y * 3 + k][X * 3 + l].end()) {
  217. 								C[Y * 3 + k][X * 3 + l].erase(it);
  218.  
  219. 							}
  220. 						}
  221. 					}
  222. 				}
  223. 			}
  224. 		}
  225. 	}
  226. 	return C;
  227. }
  228.  
  229.  
  230. bool IsAnswer(Grid P) {
  231. 	DType D;
  232. 	for (std::size_t Y = 0; Y < 3; Y++) {
  233. 		for (std::size_t X = 0; X < 3; X++) {
  234. 			for (std::size_t i = 0; i < 3; i++) {
  235. 				for (std::size_t j = 0; j < 3; j++) {
  236. 					D.push_back(P[Y * 3 + i][X * 3 + j]);
  237. 				}
  238. 			}
  239. 			std::sort(D.begin(), D.end());
  240. 			D.erase(std::unique(D.begin(), D.end()), D.end());
  241. 			if (D.size() != 9)return false;
  242. 		}
  243. 	}
  244.  
  245. 	for (std::size_t i = 0; i < P.size(); i++) {
  246. 		D.clear();
  247. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  248. 			D.push_back(P[i][j]);
  249. 		}
  250. 		std::sort(D.begin(), D.end());
  251. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  252. 		if (D.size() != 9)return false;
  253. 	}
  254. 	for (std::size_t i = 0; i < P.size(); i++) {
  255. 		D.clear();
  256. 		for (std::size_t j = 0; j < P[i].size(); j++) {
  257. 			D.push_back(P[j][i]);
  258. 		}
  259. 		std::sort(D.begin(), D.end());
  260. 		D.erase(std::unique(D.begin(), D.end()), D.end());
  261. 		if (D.size() != 9)return false;
  262. 	}
  263.  
  264. 	return true;
  265. }
  266. Grid CubeToGrid(const Cube& C, const Grid G) {
  267. 	Grid R = MakeGrid();
  268. 	for (std::size_t i = 0; i < G.size(); i++) {
  269. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  270. 			R[i][j] = C[i][j][G[i][j]];
  271. 		}
  272. 	}
  273. 	return R;
  274. }
  275. Grid CubeToProblem(const Cube& C) {
  276. 	Grid G = MakeGrid();
  277. 	for (std::size_t i = 0; i < G.size(); i++) {
  278. 		for (std::size_t j = 0; j < G[i].size(); j++) {
  279. 			if (C[i][j].size() == 1) {
  280. 				G[i][j] = C[i][j][0];
  281. 			}
  282. 			else {
  283. 				G[i][j] = 0;
  284. 			}
  285. 		}
  286. 	}
  287. 	return G;
  288. }
  289.  
  290. bool ShowList(Cube& C) {
  291. 	std::size_t i = 1;
  292. 	double D = 0;
  293. 	for (auto& ooo : C) {
  294. 		for (auto& oo : ooo) {
  295. 			std::cout << '[' << i << ':';
  296. 			i++;
  297. 			D += oo.size();
  298. 			for (auto& o : oo) {
  299. 				std::cout << o << ',';
  300. 			}
  301. 			std::cout << ']';
  302. 		}
  303. 		std::cout << std::endl;
  304. 	}
  305. 	std::cout << D / 81.0 << std::endl;
  306. 	return true;
  307. }
  308.  
  309. bool Show(const Grid& G) {
  310. 	for (auto& oo : G) {
  311. 		for (auto& o : oo) {
  312. 			std::cout << o;
  313. 		}
  314. 		std::cout << std::endl;
  315. 	}
  316. 	std::cout << std::endl;
  317. 	std::cout << std::endl;
  318. 	return true;
  319. }
  320. DType GetAntiIntersection(DType A ,const DType& B){//積集合を取り除く？？
  321. 	for (auto& o : B) {
  322. 		auto it = std::find(A.begin(), A.end(), o);
  323. 		if(it != A.end())A.erase(it);
  324. 	}
  325. 	return A;
  326. }
  327. bool IsHorizonValid(const Grid& G,std::size_t V) {//横方向検査
  328. 	DType D;
  329. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  330. 		if(G[V][i]!=0)D.push_back(G[V][i]);
  331. 	}
  332. 	std::sort(D.begin(), D.end());
  333. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  334. 	return D.size() == 9 ? true : false;
  335. }
  336. DType GetHorizonUsing(const Grid& G,std::size_t V) {//横方向検査
  337. 	DType D;
  338. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  339. 		if(G[V][i]!=0) D.push_back(G[V][i]);
  340. 	}
  341. 	return  D;
  342. }
  343. bool HaveHorizonZero(const Grid& G,std::size_t V) {//横方向検査
  344. 	DType D;
  345. 	for (std::size_t i = 0; i < G[V].size(); i++) {
  346. 		if (G[V][i] == 0)return true;
  347. 	}
  348. 	return false;
  349. }
  350. bool IsVerticalValid(const Grid& G,std::size_t H) {//縦方向検査
  351. 	DType D;
  352. 	for (std::size_t i = 0; i < G.size(); i++) {
  353. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  354. 	}
  355. 	std::sort(D.begin(), D.end());
  356. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  357. 	return D.size() == 9 ? true : false;
  358. }DType GetVerticalUsing(const Grid& G,std::size_t H) {//横方向検査
  359. 	DType D;
  360. 	DType T{ 0,1,2,3,4,5,6,7,8 };
  361. 	for (std::size_t i = 0; i < G.size(); i++) {
  362. 		if(G[i][H]!= 0)D.push_back(G[i][H]);
  363. 	}
  364.  
  365. 	return  D;
  366. }
  367. bool HaveVerticalZero(const Grid& G,std::size_t H) {//縦方向検査
  368. 	DType D;
  369. 	for (std::size_t i = 0; i < G.size(); i++) {
  370. 		if (G[i][H] == 0)return true;
  371. 	}
  372. 	return false;
  373. }
  374. bool IsBlockValid(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  375. 	DType D;
  376. 	for (std::size_t i = 0; i < 3; i++) {
  377. 		for (std::size_t j = 0; j < 3; j++) {
  378. 			if(G[Y*3+i][X*3+j] !=0)D.push_back(G[Y*3+i][X*3+j]);
  379. 		}
  380. 	}
  381. 	std::sort(D.begin(), D.end());
  382. 	D.erase(std::unique(D.begin(), D.end()), D.end());
  383. 	return D.size() == 9 ? true : false;
  384. }
  385. DType GetBlockUsing(const Grid& G,std::size_t X,std::size_t Y) {//横方向検査
  386. 	DType D;
  387. 	for (std::size_t i = 0; i < 3; i++) {
  388. 		for (std::size_t j = 0; j < 3; j++) {
  389. 			if(G[Y*3+i][X*3+j] !=0) D.push_back(G[Y*3+i][X*3+j]);
  390. 		}
  391. 	}
  392.  
  393. 	return D;
  394. }
  395. bool HaveBlockNumber(const Grid& G, std::size_t X, std::size_t Y, std::size_t N) {//横方向検査
  396. 	DType D;
  397. 	for (std::size_t i = 0; i < 3; i++) {
  398. 		for (std::size_t j = 0; j < 3; j++) {
  399. 			if (G[Y * 3 + i][X * 3 + j] == N)return true;
  400. 		}
  401. 	}
  402.  
  403. 	return false;
  404. }
  405. bool HaveBlockZero(const Grid& G, std::size_t X, std::size_t Y) {//3x3検査
  406. 	DType D;
  407. 	for (std::size_t i = 0; i < 3; i++) {
  408. 		for (std::size_t j = 0; j < 3; j++) {
  409. 			if (G[Y * 3 + i][X * 3 + j] == 0)return true;
  410. 		}
  411. 	}
  412.  
  413. 	return false;
  414. }
  415.  
  416.  
  417. bool Search_r(Grid& G, int Deep, RType& R, std::size_t& C) {
  418. 	C++;
  419. 	gotoxy(11, 0);
  420. //	std::cout << C << std::endl;
  421. 	if (Deep >= 81) {
  422. 		gotoxy(0, 0);
  423. 		//Show(G);
  424. 		if (IsAnswer(G)) {
  425. 			R.push_back(G);
  426. 			std::cout << "find!!" << std::endl;
  427. 			return true;
  428. 		}
  429.  
  430. 		return false;
  431. 	}	
  432.  
  433. 	static const DType T{ 1,2,3,4,5,6,7,8,9 };
  434. 	std::size_t MX = (Deep % 9) % 3;
  435. 	std::size_t MY = (Deep % 9) / 3;
  436. 	std::size_t BX = (Deep / 9) % 3;
  437. 	std::size_t BY = (Deep / 9) / 3;
  438. 	auto BU = GetBlockUsing(G, BX, BY);
  439. 	auto HU = GetHorizonUsing(G, BY*3+MY);
  440. 	auto VU = GetVerticalUsing(G, BX*3 + MX);
  441. 	DType AI;
  442.  
  443. 	if (G[BY*3 + MY][BX*3 + MX] != 0) {
  444. 		return Search_r(G, Deep + 1, R,C);
  445. 	}
  446.  
  447. 	std::copy(BU.begin(), BU.end(), std::back_inserter(AI));
  448. 	std::copy(HU.begin(), HU.end(), std::back_inserter(AI));
  449. 	std::copy(VU.begin(), VU.end(), std::back_inserter(AI));
  450. 	std::sort(AI.begin(), AI.end());
  451. 	AI.erase(std::unique(AI.begin(), AI.end()), AI.end());
  452. 	DType D = GetAntiIntersection(T, AI);
  453.  
  454. 	auto WG = G;
  455. 	if (D.size() == 0) return false;
  456. 	for (std::size_t i = 0; i < D.size(); i++) {
  457. 		WG[BY*3 + MY][BX*3 + MX] = D[i];
  458. 		gotoxy(0, 0);
  459. //		Show(WG);
  460. 		Search_r(WG, Deep + 1, R,C);
  461. 	}
  462.  
  463. 	return false;
  464.  
  465. }
  466. bool Search(Grid& G, RType& R) {
  467. 	int Deep = 0;
  468. 	std::size_t C=0;
  469. 	return Search_r(G, Deep, R, C);
  470. }
  471.  
  472.  
  473. RType MakeHoge(Grid G) {
  474. 	Cube Cu = MakeCube();
  475. 	Cube C = ReduceCube(Cu, G);
  476. 	Grid V = MakeGrid();
  477. 	RType R;
  478. 	Grid B = G;
  479. 	Grid D;
  480. 	std::uint64_t Co = 0;
  481. 	std::uint64_t Find = 1;
  482. 	do {
  483. 		D = B;
  484. 		B = CubeToProblem(C);
  485. 		C = ReduceCube(C, B);
  486. 	} while (D != B);
  487. 	gotoxy(0, 11);
  488. //	Show(B);
  489. //	ShowList(C);
  490. 	auto A = CubeToProblem(C);
  491. 	gotoxy(0, 11);
  492. //	Show(A);
  493. 	Search(A, R);
  494. 	std::sort(R.begin(), R.end());
  495. 	R.erase(std::unique(R.begin(), R.end()), R.end());
  496. 	gotoxy(0, 11);
  497. 	return R;
  498. }
  499.  
  500.  
  501.  
  502. int main() {
  503. 	std::uint64_t C = 0;
  504. 	std::cout << "Generateing!" << std::endl;
  505. F:
  506. //	std::cout << C << '\r';C++;
  507.  
  508. 	Grid G = MakeProblem2();
  509. 	RType R;
  510. 	R = MakeHoge(G);
  511. 	if (R.size() == 0) goto F;
  512. 	std::cout << "Show Problem Seed." << std::endl;
  513. 	Show(G);
  514.  
  515. 	std::cout << "Created:" <<R.size() << std::endl<< std::endl<< std::endl;
  516.  
  517. 	std::random_device rd;
  518. 	std::uniform_int_distribution<std::size_t> ui(0, R.size() - 1);
  519. 	std::size_t P = ui(rd);
  520. 	G = R[P];
  521.  
  522. 	std::cout << "Show Problem Seed2." << std::endl;
  523. 	for (auto& o : R) {
  524. //		gotoxy(0, 0);
  525. 		Show(o);
  526. 	}
  527.  
  528. 	std::cout << "Selected:" <<P << std::endl<< std::endl<< std::endl;
  529.  
  530. 	Grid A = EraseNumber(G, 45);
  531. 	std::cout << "Number Erased!" << std::endl;
  532. 	Show(A);
  533.  
  534. 	R=MakeHoge(A);
  535. 	std::cout << "Show Answer!" << std::endl;
  536. 	for (auto& o : R) {
  537. //		gotoxy(0, 0);
  538. 		Show(o);
  539. 	}
  540. 	return 0;
  541. }
Success #stdin #stdout 0.06s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generateing!
find!!
find!!
find!!
find!!
find!!
find!!
Show Problem Seed.
650000000
000678302
000015009
006540018
005800030
020001504
000490700
270000900
080700000


Created:6


Show Problem Seed2.
652934871
149678352
738215469
396547218
415829637
827361594
561492783
273186945
984753126


652934871
149678352
837215469
396547218
415829637
728361594
561492783
273186945
984753126


652934871
419678352
738215469
396547218
145829637
827361594
561492783
273186945
984753126


652934871
419678352
837215469
396547218
145829637
728361594
561492783
273186945
984753126


652934871
914678352
738215469
396547218
145829637
827361594
561492783
273186945
489753126


652934871
914678352
837215469
396547218
145829637
728361594
561492783
273186945
489753126


Selected:4


Number Erased!
050930800
010000000
708000009
390547010
000820007
020061500
561090703
003006005
089750106


find!!
find!!
Show Answer!
652934871
914678352
738215469
396547218
145829637
827361594
561492783
273186945
489753126


652934871
914678352
738215469
396547218
145829637
827361594
561492783
473186925
289753146
https://ideone.com/A2t0QO
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!