Leetcode #51 N-Queens

Writer: Steven, Lee

Date: 12/27, Friday

Purpose: Solving #51 N-Queens

Level: Hard

Percentage: 36.6% have solved this problem

Time: it took me 1 hours 30 minutes :)

Dfs BackTracking programming  * reference * 

=> https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

* Description *

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

* Example *

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

* What is the Idea? *

 We should consider two points. First one is we need to make sure that there is no repetition between the top and the bottom of the area where Q will be placed. The second one is we need to check out that there is no repetition between the left diagonal and the right diagonal of the area where Q will be placed. How can we solve this problem? well, it would be a good way if we gonna use the Dfs. Because obviously, you have to check all probabilities whether it's one of the answers or not. Basically, my idea is like this.

1. There is the main list variable, "root" which is the positions of all 'Q'. when we choose the position is possible to place, we have to check out there is any value of "root" on the same verticality line of the area that it will be placed

2. If there is "root", then the position isn't accepted. but if there is not "root", then the position is accepted 

3. if the new position is accepted, we need to add the position to root list

4. The same process to finding "Q' on left diagonal and right diagonal

5. Finish :)

* Check *
you can check out your answer on this site.

https://leetcode.com/problems/n-queens/

(한국어)

* 난이도는 어려움입니다.

* 오직 36.6%만이 이 문제를 풀었습니다.

* 저는 1시간 30분 정도가 걸렸습니다. ^^/

Dfs Backtracking을 사용하는 것을 추천합니다.

=> https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

N-queens 퍼즐은 n개의 퀸들을 양쪽이 공격을 못하도록 nxn 체스판에 두어야 하는 문제입니다.T

integer n이 주어지고 n-queens의 퍼즐에 대한 모든 다른 솔루션을 반환해야 합니다.

모든 솔루션에는 구별된 n-queens의 위치로 되어 있어야 합니다. 그리고 'Q'와 '.'으로 Queen과 empty를 구별합니다.

* 예시 *

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: 위에서 보는 것처럼 2개의 "Queen"들이 구별된 솔루션을 반환하고 있습니다. 

* 아이디어 *

 우리들은 총 2가지 포인트를 고려해야 합니다. 첫 번째는 우리들이 "Q'를 두어야 할 곳 바로 위 쪽과 아랫쪽에 중복이 있으면 안되는 것입니다. 두 번째는 우리들이 "Q"를 두어야 할 곳 바로 왼쪽 대각선과 오른쪽 대각선에 중복이 있으면 안된다는 것입니다. 그렇다면 이 문제는 어떻게 풀 수 있을까요? 아마 Dfs를 쓰는 것이 좋은 방법이라고 생각됩니다. 왜냐하면 명백하게도 우리는 그 위치가 정답에 속한 것인지 아닌지 모든 가능성을 체크해야 하기 때문입니다. 기본적으로 제 아이디어는 다음과 같습니다.

1. root라는 모든 'Q'의 위치를 담고 있는 리스트 변수를 지정합니다. 만약 우리가 그 위치가 두어도 되는지 선택할 때, 우리는 그 위치의 직선 상에 놓여진 부분에서 root의 어느 값이 있는지 확인해야 합니다. 

2. 만약 "root"가 있으면 그 위치는 허용되지 않습니다. 그러나 만약 "root"가 없다면 그 위치는 허용됩니다.

3. 만약 새로운 위치가 허용되었다면 그 위치를 root 리스트에 추가합니다.

4. 똑같은 방법으로 왼쪽 대각선과 오른쪽 대각선에서 root를 찾을 때 적용시킵니다.

5. 완성 :)

* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://leetcode.com/problems/n-queens/

Code & 코드

You need to read the code by yourself

스스로 코드를 읽을 줄 알아야 합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class NQueen_51 {
    public static List<List<String>> solveNQueens(int n) {
       List<List<String>> res = new ArrayList<List<String>>();
       List<char[]> curr = new ArrayList<char[]>();
       boolean[][] map = new boolean[n][n];
       int[][] root = new int[n][2];
       for(int i = 0 ; i < n ; i++) {
          char[] a = new char[n];
          Arrays.fill(a, '.');
          Arrays.fill(root[i], -1);
          curr.add(a);
       }
       solveNQueens(res, curr, map, root, 0, n);
       return res;
    }
    public static boolean findingRoot(int[][] root, int c, int r) {
        if(root[r][0] == c && root[r][1] == r) return true;
        else return false;
    }
    public static boolean helper(boolean[][] map, int c, int r, int max, int[][] root) {
        for(int i = 1; i < max ; i++) {
            if(r - i >= 0 && map[r-i][c] && findingRoot(root, c, r-i)) return true;
            if(r - i >= 0 && c - i >= 0 && map[r-i][c-i] && findingRoot(root, c-i, r-i)) return true;
            if(r - i >= 0 && c + i < max && map[r-i][c+i] && findingRoot(root, c+i, r-i)) return true;
        }
        return false;
    }
    public static void solveNQueens(List<List<String>> res, List<char[]> curr, boolean[][] map, int[][] root,  int r, int n) {
        if(r == n) {
            List<String> temp = new ArrayList<>();
            for(char[] line : curr) temp.add(new String(line));
            res.add(temp);
            return;
        }
        for(int i = 0 ; i < n ; i++) {
            if(!helper(map, i, r, n, root)) {
                root[r][0] = i;
                root[r][1] = r;
                map[r][i] = true;
                curr.get(r)[i] = 'Q';
                solveNQueens(res, curr, map, root, r+1, n);
                root[r][0] = -1;
                root[r][1] = -1;
                map[r][i] = false;
                curr.get(r)[i] = '.';
            }
        }
    }
    public static void main(String[] args) {
        List<List<String>> result = solveNQueens(4);
        System.out.println("Result: " + result);
        
    }
}