51.N-QUEENS

뭔 지 모 르 겠 어.방금 이 글 을 편집 해 보 았 는데 (원래 3, 4 로 쓰 였 는데) 업데이트 후에 URL 이 효력 을 잃 어 도저히 찾 을 수 없 었 습 니 다.다행히 RAR 을 백업 한 적 이 있 습 니 다.그 건 좀 안심 이 안 되 네요. 백업 을 자주 해 야 할 것 같 아 요.
이 문 제 는 dfs 방식 입 니 다. 이상 적 인 것 에 따라 우 리 는 좌 표를 저장 하 는 데이터 구조 가 필요 합 니 다. 그러나 이 문 제 는 1 차원 배열 만 있 으 면 됩 니 다. n 황후 의 가로 좌 표 는 0 ~ n - 1 이 고 모든 slot 에는 황후 만 있 기 때 문 입 니 다.그 시계, (row, col (row) 는 Queen 의 좌 표를 대표 합 니 다.4 황후 에 게 두 번 의 귀환 모습 은 이 렇 습 니 다. 우선 row = = 2 를 찾 았 을 때 모든 slot 가 조건 에 부합 되 지 않 는 다 는 것 을 발 견 했 습 니 다. 어떻게 하 죠? DFS 를 계속 할 수 없습니다. 결과 집 은 (0, 0) (1, 2)col [] = {0, 2, 3, 0} 네 번 째 0 은 초기 화 되 었 을 때 이치 대로 말 하면 지난번 DFS 를 끝내 고 지난번 에 추 가 된 그 숫자 를 없 애 야 합 니 다. 1000 0010 0001 0000.
이런 2 차원 배열 이 라면 (2, 3) 의 황 후 를 가 져 가 0 을 두 어야 3 행 에 황 후 를 다시 놓 을 수 있 지만 1 차원 배열 은 구덩이 가 하나 밖 에 없 잖 아 요. row - 1 로 돌아 가 내 려 올 때 col [2] 은 자 연 스 럽 게 덮 입 니 다.그 러 니까 remove 조작 안 해도 돼.(제 가 잘못 이해 한 것 같 습 니 다. remove 가 필요 없 는 이 유 는 stack 이 이전 상태 로 돌 아 왔 기 때 문 일 수도 있 습 니 다. 그 상태 에서 배열 col [row] 가 삽입 되 지 않 았 기 때 문 일 수도 있 습 니 다)
아래 코드 는 길 어 보이 지만 dfs 핵심 부분 은 짧 고 대부분 결 과 를 인쇄 하 는 데 사 용 됩 니 다.우 리 는 DFS 의 방법 을 알 고 있 습 니 다. 제 가 정리 해 보 겠 습 니 다. 대략 이 렇 습 니 다.
종료 조건
구조 결과

backtracking

현장 복구..
비슷 한 방식 의 제목 은 Letter CombinationsOfAPhoneNumber, CombinationSum, Unique Binary Search Trees II 등 이 있다.
이 문제 의 종료 조건 은 인쇄 작업 도 하 는 김 에 길 어 보인다.이 문 제 는 현장 을 복원 할 필요 가 없다.

    public List> solveNQueens(int n) {

        List> res = new ArrayList<>();
        if (n <= 0)
            return res;

        dfs(res, 0, n, new int[n]);
        return res;
    }

    //columnVal     Q   ，     Q   
    public void dfs(List> result, int row, int n, int[] col) {
        if (row == n) {
            //col = [1,4,0,3];
            List cell = new ArrayList<>();
            for (int i = 0; i < row; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < row; j++) {
                    if (col[i] == j) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                cell.add(sb.toString());
            }
            result.add(new ArrayList(cell));
            return;
        }
        for (int i = 0; i < n; i++) {
            col[row] = i;
            if (checkValid(row, col)) {
                dfs(result, row + 1, n, col);
            }
        }

    }

    public boolean checkValid(int row, int[] col) {
        for (int i = 0; i < row; i++) {
            if (col[i] == col[row] || Math.abs(i - row) == Math.abs(col[i] - col[row]))//    ||   
            {
                return false;
            }
        }
        return true;
    }