Submission #2171335

---

Source Code Expand

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
	static boolean debug = false;
	static boolean debug2 = false;

	public static void main(String[] args) throws java.io.IOException {
		debug = 1 == args.length;
		debug2 = 2 == args.length;

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		boolean[] f = new boolean[8];
		int[] c = new int[8];
		for (int i = 0; i < 8; ++i) {
			char[] ca = in.readLine().toCharArray();
			for (int j = 0; j < ca.length; ++j) {
				if (ca[j] == 'Q') {
					if (0 != c[i] || f[j] || !valid(c, j, i))
					{
						System.out.println("No Answer");
						return;
					}
					c[i] = j + 1;
					f[j] = true;
				}
			}
		}

		if (!check(c, f, 0)) {
			System.out.println("No Answer");
		}
	}

	private static boolean valid(int[] c, int i, int n) {
		for (int j = 0; j < 8; ++j) {
			System.err.println("" + j + "," + c[j] + " " + j + "," + (i + 1 - (n - j)) + " " + j + "," + (i + 1 + (n - j)));
			if (c[j] != 0 && c[j] == i + 1 - (n - j)) {
				System.err.println();
				return false;
			}
			if (c[j] != 0 && c[j] == i + 1 + (n - j)) {
				System.err.println();
				return false;
			}
		}
		System.err.println();
		return true;
	}

	private static boolean check(int[] c, boolean[] f, int n) {
		if (8 == n) {
			for (int i = 0; i < 8; ++i) {
				char[] line = "........".toCharArray();
				line[c[i] - 1] = 'Q';
				System.out.println(line);
			}
			return true;
		}

		if (0 != c[n]) {
			if (check(c, f, n + 1)) {
				return true;
			}
		} else {
			for (int i = 0; i < 8; ++i) {
				if (!f[i]) {
					if (valid(c, i, n)) {
						f[i] = true;
						c[n] = i + 1;
						if (check(c, f, n + 1)) {
							return true;
						}
						f[i] = false;
						c[n] = 0;
					}
				}
			}
		}

		return false;
	}
}

Submission Info

Judge Result