package question;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/*
 @author: Roderland
 @create: 2020年09月20日---14:40
*/
public class Question51 {
 public static void main(String[] args) {
 new Question51().solveNQueens(4);
 System.out.println(new Question51().totalNQueens(4));
 }

 List<List<String>> res = new LinkedList<>();

 public int totalNQueens(int n) {
 return solveNQueens(n).size();
 }

 public List<List<String>> solveNQueens(int n) {
 int[][] map = new int[n][n];
 solve(map, 0);
 for (int i = 0; i < res.size(); i++) {
 for (int j = 0; j < res.get(i).size(); j++) {
 String strings = res.get(i).get(j);
 System.out.println(strings);
 }
 System.out.println();
 }
 return res;
 }

 public void solve(int[][] map, int i) {
 for (int j = 0; j < map[i].length; j++) {
 if (check(map, i, j)) {
 map[i][j] = 1;
 if (i == map.length - 1) {
 res.add(strings(map));
 map[i][j] = 0;
 break;
 }
 solve(map, i + 1);
 map[i][j] = 0;
 }
 }
 }

 public boolean check(int[][] map, int i, int j) {
 for (int k = 0; k < i; k++) {
 if (map[k][j] == 1) return false;
 }
 for (int k = i - 1, l = j - 1, m = j + 1; k >= 0; k--, l--, m++) {
 if (l >= 0 && map[k][l] == 1) return false;
 if (m < map[k].length && map[k][m] == 1) return false;
 }
 return true;
 }

 public List<String> strings(int[][] map) {
 List<String> strings = new LinkedList<>();
 for (int i = 0; i < map.length; i++) {
 StringBuilder s = new StringBuilder();
 for (int j : map[i]) {
 if (j==0) s.append(".");
 else if (j==1) s.append("Q");
 }
 strings.add(s.toString());
 }
 return strings;
 }

}