summaryrefslogtreecommitdiff
path: root/introductory_problems/chessboard_and_queens.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'introductory_problems/chessboard_and_queens.cpp')
-rw-r--r--introductory_problems/chessboard_and_queens.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/introductory_problems/chessboard_and_queens.cpp b/introductory_problems/chessboard_and_queens.cpp
new file mode 100644
index 0000000..4dc5f2f
--- /dev/null
+++ b/introductory_problems/chessboard_and_queens.cpp
@@ -0,0 +1,55 @@
+// 1624. Chessboard and Queens
+#include <bits/stdc++.h>
+#include <cstdio>
+using namespace std;
+
+const int n = 8;
+char c;
+int ans;
+bool b[n][n], input[n][n];
+
+bool place(int x, int y) {
+ bool valid = true;
+ for (int i = 0; i < n; i++)
+ if (b[x][i] || b[i][y])
+ valid = false;
+ for (int i = 0; x - i >= 0 && y + i < n; i++)
+ if (b[x - i][y - i])
+ valid = false;
+ for (int i = 0; x - i >= 0 && y + i < n; i++)
+ if (b[x - i][y + i])
+ valid = false;
+ return valid;
+}
+
+bool check(void) {
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < n; j++)
+ if (b[i][j] && input[i][j])
+ return false;
+ return true;
+}
+
+void dfs(int i) {
+ if (i == n) {
+ if (check())
+ ans++;
+ return;
+ }
+ for (int j = 0; j < n; j++)
+ if (place(i, j)) {
+ b[i][j] = true;
+ dfs(i + 1);
+ b[i][j] = false;
+ }
+}
+
+int main() {
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < n; j++) {
+ scanf(" %c", &c);
+ input[i][j] = (c == '*');
+ }
+ dfs(0);
+ printf("%d\n", ans);
+}