# AI 꾸러미 — 선형 대수로 퍼즐 풀기 (GF(2) 가우스 소거) — Gaussian elimination over GF(2)
> 「칸 i 를 누르면 어느 불이 바뀌나」를 0 · 1 표로 쓰고 덧셈 대신 XOR 로 줄을 지워 가면, 오른쪽 끝 열이 바로 「누를 칸」이 된다.  
> 견본: https://ai-techstudio.web.app/#t/i356

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

## 주문서

### 만들어 줘: 선형 대수로 퍼즐 풀기 (GF(2) 가우스 소거) — Gaussian elimination over GF(2)

#### 1. 목표
불 끄기 (잠꾸러기 버섯 마을)을(를) 2 를 법으로 한 가우스 소거로 풀어 줘 — 누를 칸이 한 번에 나오게. 분위기는 0 · 1 표의 줄이 XOR 로 지워지는 설명.

#### 2. 핵심 기술 용어
- **Gaussian elimination over GF(2)** — 2 를 법으로 (1 + 1 = 0) 하는 가우스 소거
- **Lights Out as a linear system** — 불 끄기 = A·x = b 연립방정식 (x = 누를 칸)
- **Null space (free variables)** — 눌러도 불이 그대로인 누름 조합 — 답이 여럿일 때

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

#### 4. 조건
- 덧셈 · 뺄셈 대신 XOR (2 를 법으로)
- 기준 1 이 없는 열은 자유 변수로 표시하고 건너뛴다
- 마지막에 어떤 행이 「0 = 1」 이면 풀 수 없는 판이라고 알린다
- 가장 적은 누름이 필요하면 자유 변수 조합을 모두 시도
- 설명 화면: 기준 · 줄 바꾸기 · XOR 사건을 한 단계씩, 판 크기 3~5

#### 5. 완성 기준 (이게 보이면 성공)
- 표의 줄이 하나씩 지워져 왼쪽이 계단 꼴이 되고 오른쪽 끝 열이 남는다
- 그 열이 1 인 칸을 누르면 모든 불이 꺼진다
- 자유 변수 조합을 넣은 풀이는 누름 수가 같거나 더 적다

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

## 원리
- 칸이 N 개면 N × (N + 1) 표: 행 i = 「칸 i 의 불을 바꾸는 누름들」(자기 + 위 · 아래 · 옆), 마지막 열 = 지금 칸 i 가 켜졌나.
- 같은 칸을 두 번 누르면 없던 일이니 덧셈은 XOR(1 + 1 = 0) 이다.
- 열마다: 그 열이 1 인 행을 찾아(없으면 자유 변수) 위로 올리고, 그 열이 1 인 다른 모든 행에 XOR 해서 지운다.
- 끝나면 기준 행의 마지막 열이 그 칸을 누를지(1) 말지(0). 견본은 자유 변수를 0 으로 둔다 — 가장 적은 누름이 필요하면 자유 변수 조합(빈 공간)을 모두 넣어 보고 가장 적은 것을 고른다 (버섯 마을 logic.ts 방식).

## 핵심 코드 — 불 끄기 — 2 를 법으로 가우스 소거
(발췌: demos/demosGameAI.ts lightsPlan() 을 정리)
```ts
function solveLights(n: number, start: Uint8Array): Uint8Array | null {
  const N = n * n;
  const press = (b: Uint8Array, i: number): void => {
    const y = Math.floor(i / n), x = i % n;
    b[i] ^= 1;
    if (x > 0) b[i - 1] ^= 1;
    if (x < n - 1) b[i + 1] ^= 1;
    if (y > 0) b[i - n] ^= 1;
    if (y < n - 1) b[i + n] ^= 1;
  };
  // 행 i = 칸 i 의 불을 바꾸는 누름들 (대칭이라 「누름 i 가 바꾸는 칸」과 같은 꼴) | 지금 불
  const M: Uint8Array[] = [];
  for (let i = 0; i < N; i++) {
    const row = new Uint8Array(N + 1);
    press(row, i);                            // 앞 N 칸에 이웃 표시
    row[N] = start[i]!;
    M.push(row);
  }
  const pivRow = new Array<number>(N).fill(-1);
  let row = 0;
  for (let col = 0; col < N && row < N; col++) {
    let p = -1;
    for (let i = row; i < N; i++) if (M[i]![col]) { p = i; break; }
    if (p < 0) continue;                      // 자유 변수 (0 으로 둠)
    [M[p], M[row]] = [M[row]!, M[p]!];
    for (let i = 0; i < N; i++) {
      if (i === row || !M[i]![col]) continue;
      for (let j = 0; j <= N; j++) M[i]![j] ^= M[row]![j]!;   // 1 + 1 = 0
    }
    pivRow[col] = row++;
  }
  for (let i = row; i < N; i++) if (M[i]![N]) return null;      // 0 = 1 → 풀 수 없는 판
  const x = new Uint8Array(N);
  for (let col = 0; col < N; col++) if (pivRow[col]! >= 0) x[col] = M[pivRow[col]!]![N]!;
  return x;                                   // x[i] = 1 이면 칸 i 를 누른다
}
```

## 흔한 실수 · 확인 목록
- [ ] **보통 가우스 소거(빼기 · 나누기)를 쓰면 분수가 나와 틀린다** — 0 · 1 만 쓰는 XOR 이어야 한다 — 같은 칸 두 번 = 안 누름.
- [ ] **자유 변수를 0 으로만 두면 가장 적은 누름이 아닐 수 있다** — 자유 변수 조합(2^k 가지)을 모두 넣어 보고 누름 수가 가장 적은 것을 고른다 (버섯 마을 방식).
- [ ] **무작위로 불을 켠 판은 풀 수 없을 수 있다** — 판은 「무작위 칸을 눌러서」 만든다 — 견본처럼 누름으로 만든 판은 늘 풀린다.

## 완성 기준 체크리스트
- [ ] 표의 줄이 하나씩 지워져 왼쪽이 계단 꼴이 되고 오른쪽 끝 열이 남는다
- [ ] 그 열이 1 인 칸을 누르면 모든 불이 꺼진다
- [ ] 자유 변수 조합을 넣은 풀이는 누름 수가 같거나 더 적다

## 이 기술 정보
- id: `i356` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 보통 · 폰 부담 가벼움 (폰 OK) — N 칸이면 N³ 정도 XOR. 6×6 = 36칸이면 수만 번 — 순식간. 비트 묶음이면 행 XOR 이 한 번.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i356
- 쓰면 좋을 때: 불 끄기처럼 누르면 정해진 칸이 뒤집히는 퍼즐 / 「선형 대수가 퍼즐을 푼다」 수학 설명
- 쓰지 말 때: 누름 순서가 결과를 바꾸는 퍼즐 — 선형이 아니다. 너비 우선(i354) / 칸 수가 수천 개 — N³ 이 무겁다. 비트 묶음으로

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### lightsPlan — `src/demos/demosGameAI.ts:3308`
```ts
function lightsPlan(n: number, seed: number): { start: Uint8Array; ev: GEv[]; x: Uint8Array } {
  const N = n * n;
  const r = rng(seed);
  const start = new Uint8Array(N);
  const press = (b: Uint8Array, i: number): void => {
    const y = Math.floor(i / n);
    const x = i % n;
    b[i] = b[i]! ^ 1;
    if (x > 0) b[i - 1] = b[i - 1]! ^ 1;
    if (x < n - 1) b[i + 1] = b[i + 1]! ^ 1;
    if (y > 0) b[i - n] = b[i - n]! ^ 1;
    if (y < n - 1) b[i + n] = b[i + n]! ^ 1;
  };
  do {
    start.fill(0);
    for (let k = 0; k < N; k++) if (r() < 0.45) press(start, k);
  } while (start.every((v) => !v));
  const M: Uint8Array[] = [];
  for (let i = 0; i < N; i++) {
    const row = new Uint8Array(N + 1);
    const e = new Uint8Array(N);
    press(e, i);
    // 행 i = 칸 i 의 불을 바꾸는 누름들 (대칭이라 같은 꼴)
    for (let j = 0; j < N; j++) row[j] = e[j]!;
    row[N] = start[i]!;
    M.push(row);
  }
  const snap = (): Uint8Array[] => M.map((rw) => rw.slice());
  const ev: GEv[] = [];
  let row = 0;
  const pivRow: number[] = Array<number>(N).fill(-1);
  for (let col = 0; col < N && row < N; col++) {
    let p = -1;
    for (let i = row; i < N; i++) if (M[i]![col]) {
      p = i;
      break;
    }
    if (p < 0) {
      ev.push({ k: 'free', a: -1, b: -1, col, M: snap() });
      continue;
    }
    if (p !== row) {
      const t = M[p]!;
      M[p] = M[row]!;
      M[row] = t;
      ev.push({ k: 'swap', a: p, b: row, col, M: snap() });
    }
    ev.push({ k: 'pivot', a: row, b: row, col, M: snap() });
    for (let i = 0; i < N; i++) {
      if (i === row || !M[i]![col]) continue;
      for (let j = 0; j <= N; j++) M[i]![j] = M[i]![j]! ^ M[row]![j]!;
      ev.push({ k: 'xor', a: row, b: i, col, M: snap() });
    }
    pivRow[col] = row;
    row++;
  }
  const x = new Uint8Array(N);
  for (let col = 0; col < N; col++) if (pivRow[col]! >= 0) x[col] = M[pivRow[col]!]![N]!;
  for (let i = 0; i < N; i++) if (x[i]) for (let k = 0; k < 3; k++) ev.push({ k: 'press', a: i, b: k, col: -1, M: snap() });
  return { start, ev, x };
}
```

## 관련 기술
- 먼저 알면 좋은 기술: [님합 · 그런디 수 (게임 이론)](https://ai-techstudio.web.app/ai/t/i350.md) `i350`
- 다음에 해 볼 기술: [미니맥스 추측 (최악의 경우 줄이기)](https://ai-techstudio.web.app/ai/t/i357.md) `i357`
- 참고 문서: [Wikipedia — Lights Out (game)](https://en.wikipedia.org/wiki/Lights_Out_(game))