fork download
copy 
  1. //4574
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define INF 1000000000
  5. #define MAX 10000001
  6. #define MOD 1000000007
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef vector<vector<int>> vvi;
  10. typedef vector<pair<int, int>> vii;
  11. typedef pair<int, int> ii;
  12.  
  13. bool domino[10][10], row[10][10], col[10][10], block[10][10], finish;
  14. int a[10][10], dx[] = { -1,1,0,0 }, dy[] = { 0,0,1,-1 };
  15. int testcase;
  16.  
  17. ii Where(string s) {
  18. 	return { s[0] - 'A', s[1] - '1' }; //row, col
  19. }
  20.  
  21. //블럭 번호
  22. int B(string s) {
  23. 	int row = s[0] - 'A', col = s[1] - '1';
  24. 	return (row / 3) * 3 + col / 3;
  25. }
  26.  
  27. int B(int x, int y) { return (x / 3) * 3 + y / 3; }
  28.  
  29. bool OOB(int x, int y) { return x < 0 || x >= 9 || y < 0 || y >= 9; }
  30.  
  31. void solve(int x, int y, int remain) {
  32. 	//완성됐다면 종료
  33. 	if (finish) return;
  34.  
  35. 	//완성 여부 체크
  36. 	if (x==8 && y==8) {
  37. 		finish = remain == 0 ? true : false;
  38. 		if (finish) {
  39. 			/*
  40. 				이 부분 입니다!
  41. 			*/
  42.  
  43. 			//cout << "Puzzle " << ++testcase << '\n';
  44. 			printf("Puzzle %d\n", ++testcase);
  45. 			for (int i = 0; i < 9; ++i) {
  46. 				for (int j = 0; j < 9; ++j)
  47. 					cout << a[i][j];
  48. 				cout << '\n';
  49. 			}
  50. 		}
  51. 		return;
  52. 	}
  53.  
  54. 	//현재 위치에 이미 숫자가 적혀 있을 경우
  55. 	if (a[x][y] != 0) {
  56. 		if (OOB(x, y + 1)) solve(x + 1, 0, remain);
  57. 		else solve(x, y + 1, remain);
  58. 		return;
  59. 	}
  60.  
  61. 	for (int num = 1; num <= 9; ++num) {
  62. 		if (row[x][num] || col[y][num] || block[B(x, y)][num]) continue;
  63. 		for (int i = 0; i < 4; ++i) {
  64. 			int nx = x + dx[i], ny = y + dy[i];
  65. 			if (OOB(nx, ny) || a[nx][ny]) continue;
  66. 			for (int nextNum = 1; nextNum <= 9; ++nextNum) {
  67. 				if (row[nx][nextNum] || col[ny][nextNum] || block[B(nx, ny)][nextNum] || domino[num][nextNum]) continue;
  68. 				row[x][num] = col[y][num] = block[B(x, y)][num] = true;
  69. 				row[nx][nextNum] = col[ny][nextNum] = block[B(nx, ny)][nextNum] = true;
  70. 				domino[num][nextNum] = domino[nextNum][num] = true;
  71. 				a[x][y] = num; a[nx][ny] = nextNum;
  72.  
  73. 				if (OOB(x, y + 1)) solve(x + 1, 0, remain-2);
  74. 				else solve(x, y + 1, remain-2);
  75. 				if (finish) return;
  76.  
  77. 				row[x][num] = col[y][num] = block[B(x, y)][num] = false;
  78. 				row[nx][nextNum] = col[ny][nextNum] = block[B(nx, ny)][nextNum] = false;
  79. 				domino[num][nextNum] = domino[nextNum][num] = false;
  80. 				a[x][y] = a[nx][ny] = 0;
  81. 			}
  82. 		}
  83. 	}
  84. }
  85.  
  86. int main() {
  87.  
  88. 	cin.tie(nullptr);
  89. 	cout.tie(NULL);
  90. 	ios_base::sync_with_stdio(false);
  91.  
  92. 	while (1) {
  93. 		finish = false;
  94. 		for (int i = 0; i < 10; ++i) for (int j = 0; j < 10; ++j) {
  95. 			domino[i][j] = row[i][j] = col[i][j] = block[i][j] = a[i][j] = 0;
  96. 		}
  97.  
  98. 		int n; cin >> n;
  99. 		if (n == 0) break;
  100. 		for (int i = 0; i < n; ++i) {
  101. 			int u, v; string lu, lv;
  102. 			cin >> u >> lu >> v >> lv;
  103. 			domino[u][v] = domino[v][u] = true;
  104. 			a[Where(lu).first][Where(lu).second] = u;
  105. 			a[Where(lv).first][Where(lv).second] = v;
  106. 			row[Where(lu).first][u] = row[Where(lv).first][v] = true;
  107. 			col[Where(lu).second][u] = col[Where(lv).second][v] = true;
  108. 			block[B(lu)][u] = block[B(lv)][v] = true;
  109. 		}
  110.  
  111. 		for (int i = 1; i <= 9; ++i) {
  112. 			string s; cin >> s;
  113. 			a[Where(s).first][Where(s).second] = i;
  114. 			row[Where(s).first][i] = col[Where(s).second][i] = true;
  115. 			block[B(s)][i] = true;
  116. 		}
  117.  
  118. 		//도미노는 같은 쌍의 수를 가질 수 없음
  119. 		for (int i = 1; i <= 9; ++i) domino[i][i] = true;
  120.  
  121. 		solve(0, 0, 81-(n*2+9));
  122. 	}
  123.  
  124. 	return 0;
  125. }
Success #stdin #stdout 0s 4576KB
comments (?)
stdin
copy 
10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5 
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1
11
5 I9 2 H9
6 A5 7 A6
4 B8 6 C8
3 B5 8 B4
3 C3 2 D3
9 D2 8 E2
3 G2 5 H2
1 A2 8 A1
1 H8 3 I8
8 I3 7 I4
4 I6 9 I7
I5 E6 D1 F2 B3 G9 H7 C9 E5
0
stdout
copy 
872643195
361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578
814267593
965831247
273945168
392176854
586492371
741358629
137529486
459683712
628714935
Puzzle 1
Puzzle 2
https://ideone.com/otbzEB
language:
C++14 (gcc 8.3)
created:
3 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!