# AI 꾸러미 — 백트래킹 (8 여왕) — Backtracking
> 한 줄씩 안전한 칸에 여왕을 놓다가 놓을 곳이 없으면 바로 윗줄로 돌아가 다음 칸을 시도해, 모든 답을 빠짐없이 찾는다.  
> 견본: https://ai-techstudio.web.app/#t/i355

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 백트래킹 (8 여왕) — Backtracking

#### 1. 목표
8 여왕 (공주 정원)을(를) 백트래킹으로 풀어 줘 — 놓기 · 되돌리기를 한 걸음씩 보여 주게. 분위기는 노려지는 칸을 빨갛게 보여 주는 설명.

#### 2. 핵심 기술 용어
- **Backtracking** — 놓아 보고 막히면 되돌아가 다음 칸
- **Eight queens puzzle** — 8×8 판에 서로 공격하지 않는 여왕 8개 (답 92가지)
- **Constraint check (column · diagonal)** — 같은 열 · 같은 대각선(|열 차| = 줄 차)이면 안 됨

#### 3. 환경
- 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로
- 화면: 브라우저 — PC · 폰 모두

#### 4. 조건
- 놓기 → 다음 줄 → 되돌릴 때 빼기를 대칭으로 (상태가 남지 않게)
- 답 개수 상한을 받는다 (답 하나뿐 확인은 2 에서 멈춤)
- 설명 화면: 놓기 · 빼기 사건 목록을 만들어 재생 (속도 조절), 노려지는 칸 표시
- 판 크기 n 슬라이더 (견본 4~10)

#### 5. 완성 기준 (이게 보이면 성공)
- 여왕이 줄마다 놓이다 막히면 윗줄 여왕이 옆 칸으로 옮겨 가는 것이 보인다
- 답을 찾으면 「해 찾음!」 과 함께 모든 여왕이 금빛
- n = 8 에서 답을 모두 세면 92

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 줄 0 부터 한 줄에 하나씩 놓는다. 줄 r 에서 열 0 → n−1 을 차례로 보며 위 줄 여왕들과 같은 열 · 같은 대각선이 아니면 놓고 다음 줄로.
- 대각선 검사: 줄 rr 의 여왕 열 cc 에 대해 |cc − c| = r − rr 이면 같은 대각선.
- 다음 줄에서 놓을 곳이 하나도 없으면 돌아와(놓은 여왕을 빼고) 다음 열을 시도한다 — 이게 되돌아가기.
- 맨 아래 줄까지 놓으면 답 하나. 계속하면 모든 답을 찾는다 (8칸 92가지). 견본은 답 3개까지 사건(놓기 · 빼기 · 답)을 기록해 재생한다.

## 핵심 코드 — n 여왕 백트래킹 (놓기 · 빼기 사건 기록)
(발췌: demos/demosGameAI.ts queensEvents() 를 정리)
```ts
type QEv = { k: 'place' | 'remove' | 'sol'; r: number; c: number };

function queens(n: number, maxSol: number): { sols: number[][]; ev: QEv[] } {
  const ev: QEv[] = [];
  const cols: number[] = [];                  // cols[r] = 줄 r 여왕의 열
  const sols: number[][] = [];
  const safe = (r: number, c: number): boolean =>
    cols.every((cc, rr) => cc !== c && Math.abs(cc - c) !== r - rr);   // 같은 열 · 대각선 아님
  const go = (r: number): boolean => {
    if (r === n) {
      sols.push(cols.slice());
      ev.push({ k: 'sol', r: -1, c: -1 });
      return sols.length >= maxSol;           // 답 상한에 닿으면 멈춤
    }
    for (let c = 0; c < n; c++) {
      if (!safe(r, c)) continue;
      cols.push(c);
      ev.push({ k: 'place', r, c });
      if (go(r + 1)) return true;
      cols.pop();                              // 되돌아가기
      ev.push({ k: 'remove', r, c });
    }
    return false;
  };
  go(0);
  return { sols, ev };
}
// 답이 하나뿐인지: queens(n, 2).sols.length === 1
```

## 흔한 실수 · 확인 목록
- [ ] **되돌아갈 때 놓은 것을 안 빼면 다음 시도가 엉킨다** — push 와 pop 을 짝으로 — 돌아오면 상태가 들어가기 전과 같아야 한다.
- [ ] **모든 답을 다 세면 큰 판에서 오래 걸린다** — 필요한 만큼만 (답 하나뿐 확인 = 2 개에서 멈춤).
- [ ] **한 걸음씩 보여 주려고 재귀 안에서 기다리면 화면이 멈춘다** — 사건 목록을 먼저 다 만들고 화면은 그 목록을 재생한다 (견본 방식).

## 완성 기준 체크리스트
- [ ] 여왕이 줄마다 놓이다 막히면 윗줄 여왕이 옆 칸으로 옮겨 가는 것이 보인다
- [ ] 답을 찾으면 「해 찾음!」 과 함께 모든 여왕이 금빛
- [ ] n = 8 에서 답을 모두 세면 92

## 이 기술 정보
- id: `i355` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 8 여왕 모든 답 = 놓기 약 2,000번. 10칸도 순식간. 스도쿠 꼴은 빈칸이 많으면 「후보가 가장 적은 칸부터」로 줄인다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i355
- 쓰면 좋을 때: 조건을 만족하는 배치를 찾는 퍼즐 (여왕 · 스도쿠 · 노노그램 일부) / 「답이 하나뿐인가」 확인 — 답을 2개까지만 세기
- 쓰지 말 때: 가장 짧은 움직임 풀이 — 너비 우선(i354) / 판이 아주 크고 조건이 느슨할 때 — 추론(줄 풀기)으로 먼저 칸을 확정하고 남은 것만 백트래킹

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### queensEvents — `src/demos/demosGameAI.ts:3151`
```ts
function queensEvents(n: number, maxSol: number): QEv[] {
  const ev: QEv[] = [];
  const cols: number[] = [];
  let sols = 0;
  const safe = (r: number, c: number): boolean => cols.every((cc, rr0) => cc !== c && Math.abs(cc - c) !== r - rr0);
  const go = (r: number): boolean => {
    if (r === n) {
      sols++;
      for (let k = 0; k < 10; k++) ev.push({ k: 'sol', r: -1, c: -1 });
      return sols >= maxSol;
    }
    for (let c = 0; c < n; c++) {
      if (!safe(r, c)) continue;
      cols.push(c);
      ev.push({ k: 'place', r, c });
      if (go(r + 1)) return true;
      cols.pop();
      ev.push({ k: 'remove', r, c });
    }
    return false;
  };
  go(0);
  return ev;
}
```

## 관련 기술
- 먼저 알면 좋은 기술: [너비 우선 퍼즐 풀이 (상태 공간 겹 수)](https://ai-techstudio.web.app/ai/t/i354.md) `i354`
- 다음에 해 볼 기술: [선형 대수로 퍼즐 풀기 (GF(2) 가우스 소거)](https://ai-techstudio.web.app/ai/t/i356.md) `i356`
- 참고 문서: [Wikipedia — Eight queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle)