Dancing Cells

색깔 있는 정확 덮개(XCC)를 춤추는 링크가 아니라 크누스(Donald E. Knuth)의 희소 집합 기법 **"춤추는 칸"**으로 푼다. 이 저장소는 sjnam/dlx의 춤추는 칸 짝이고 같은 라이브러리 API를 내주므로, dlx의 예제 프로그램이 거의 그대로 옮겨 온다.

라이브러리는 문학적 프로그램이다. 소스 전체가 한글로 쓰인 다섯 개의 GWEB 문서에 들어 있다 — dcells.w, ssxcc.w, ssmcc.w, xccdc.w, zdd/zdd.w. 아래 소스는 문학적 프로그램이다를 보라.

엔진은 크누스 자신의 책에도 써 먹는다. 디렉터리 taocp-7.2.2.1-exercises/에는 TAOCP §7.2.2.1의 연습문제와 그 답을 하나씩 꼼꼼히 읽은 글이 디렉터리마다 하나씩 들어 있다. 아래 Careful readings of TAOCP 7.2.2.1을 보라.

라이브러리

package main

import (
    "fmt"
    "strings"

    cells "github.com/sjnam/dancing-cells"
)

func main() {
    input := `a b c d e f g
c e
a d g
b c f
a d f
b g
d e g
`
    xc := cells.NewXCC()
    res := xc.Dance(strings.NewReader(input))

    for sol := range res.Solutions {
        for _, opt := range sol {
            fmt.Println(opt) // opt는 []string이다. 이를테면 [a d f]
        }
    }
}

• 함수 NewXCC()는 *XCC를 돌려준다. 필드 Debug = true로 두면 dlx처럼 입력 요약과 마무리 통계를 stderr에 찍는다.
• 메서드 Dance(io.Reader) *Result는 DLX 텍스트를 읽어 Result{ Solutions <-chan []Option, Heartbeat <-chan string }을 돌려준다.
• 타입 Option은 []string이고 그 옵션의 아이템 이름들이다(색이 붙은 부 아이템은 name:c로 나온다). 목록은 언제나 입력 차례이므로 opt[0], opt[1], …처럼 자리로 찾아 써도 된다(NewXCCDC만 예외인데 아래에 적는다).
• 탐색은 고루틴에서 돌고 보낼 때마다 멈추므로, 채널 Solutions를 훑는 쪽이 속도를 쥔다. 메서드 WithContext(ctx)는 문맥 ctx가 끊기면 탐색을 그만두게 한다(첫 해만 받고 새는 것 없이 멈출 수도 있다).

가장 싼 덮개 (Minimize)

옵션마다 값이 매겨져 있고 모든 덮개가 아니라 가장 싼 덮개를 원한다면, Dance 대신 Minimize를 쓴다.

xc := cells.NewXCC()
res := xc.Minimize(strings.NewReader(input), func(o int, opt cells.Option) int {
    return price(opt) // o는 그 옵션의 번호다. 입력 차례로 1, 2, …
})
for sol := range res.Solutions {
    // 덮개가 닿을 때마다 앞의 것보다 반드시 싸다. 마지막 것이 최적이다
}

• 값 함수는 입력을 읽고 난 바로 뒤에 옵션마다 한 번씩 불린다.
• 분기한정이다. 이제껏 가장 좋은 덮개를 이길 수 없는 가지는 버려지므로, 채널 Solutions는 반드시 나아지는 사슬을 건넨다.
• 주 아이템마다 세금을 매기는데, 크누스의 DLX5에서 온 것이다. 그 아이템의 집합에서 가장 싼 옵션의 값이 그 아이템의 세금이다. 어느 덮개든 세금을 꼭 한 번씩 물므로, 아직 덮이지 않은 아이템들의 세금 합이 거저 얻는 하한이다. 그 하한은 언제나 켜져 있다. 덕분에 XCC에서는 음수 값도 쓸 수 있다.
• 세금은 한 번 더 부려진다. 마디마다 그 마디가 더는 감당할 수 없는 옵션을 지우는데, 순값(값에서 세금을 뺀 것)이 cutoff에서 이제껏 쓴 값과 아직 물어야 할 세금을 뺀 것보다 작지 않은 옵션이 그것이다. 프로그램 DLX5는 아이템마다 리스트를 정렬해 두어 이 일을 하는데, 희소 집합은 삭제할 때마다 칸을 맞바꾸므로 그럴 수 없다. 그래서 여기서는 모든 옵션을 한 줄로 한 번만 정렬해 두고, 마디마다 제 부모가 멈춘 자리에서 이어 간다. 그러면 분기 규칙이 감당할 수 있는 옵션만 세고, Bound도 그것만 본다.
• 필드 xc.Best = k는 가장 싼 덮개 하나가 아니라 k개를 달라는 뜻이다. 그러면 이제껏 본 k번째로 싼 것보다 싼 덮개가 나올 때마다 닿고, 탐색이 끝나면 닿은 것 가운데 가장 싼 k개가 이 문제의 가장 싼 덮개 k개다. 값 k가 1보다 크면 사슬은 한 방향이 아니다.
• 필드 xc.Bound = func(f cells.Frame) int { … }는 마디마다 부분 덮개를 마저 짓는 데 드는 값의 하한을 내준다. 넘겨짚어 크게 말해서는 안 된다. 필드 f.Live를 훑으면 살아남은 (아이템, 옵션) 쌍이 나오고, f.Cost(opt)와 f.Name(item)으로 그것을 읽으며, f.Need(item)은 그 아이템이 앞으로 몇 번 더 덮여야 하는지를 말한다(XCC에서는 언제나 1이다). 탐색은 Bound와 세금 가운데 큰 쪽을 쓴다. 필드 Bound를 nil로 두면 세금만으로 가지를 친다.
• 함수 NewMCC()에도 있다. 같은 Minimize와 Best와 Bound가 있고, 거기서는 Need가 1을 넘을 수 있는데 그것이 이 필드를 둔 까닭 전부다. 세금은 다중도가 정해진 아이템(1:2|a가 아니라 2|a)에만 걷는데, 그런 아이템만이 어느 덮개에서나 같은 횟수로 덮이기 때문이다. 그런 아이템을 하나도 담지 않은 옵션에는 음수 값을 매길 수 없고, 그러면 Minimize가 panic한다. 함수 NewXCCDC()에는 Minimize가 없다. 덮개를 셀 뿐 값을 매기지는 않는다.
• 메서드 Dance는 이 가운데 어느 것에도 손대지 않는다.

입력 형식 (DLX)

주석이 아닌 첫 줄은 아이템 이름을 늘어놓는다. 주 아이템, 그다음 |, 그다음 부 아이템이다(부 아이템은 옵션 안에서 색을 받을 수 있다). 그 뒤의 줄은 저마다 옵션 하나다. 글자 |로 시작하는 줄은 주석이다.

다중도 (NewMCC)

함수 NewMCC()는 *MCC를 돌려주는데, Dance/Result/Option API는 같되 주 아이템이 범위만큼 덮이도록 허락한다(크누스의 SSMCC, 이진 분기다). 아이템 줄에 다중도를 앞에 붙인다. 적는 꼴은 low:high|name이나 high|name이고 기본값은 1:1이다. 이를테면 2|a는 아이템 a가 꼭 두 번 덮여야 한다는 뜻이다. 다중도를 그냥 두면 여느 XCC를 풀므로 NewXCC를 고스란히 품는다(파티지 예제가 이것을 쓴다).

도메인 일관성 (NewXCCDC)

함수 NewXCCDC()는 *XCCDC를 돌려주는데, NewXCC()와 같은 물음에 같은 Dance/Result/Option API와 같은 입력으로 답하되 훨씬 멀리 내다본다. 이 엔진은 도메인 일관성을 지킨다. 어떤 옵션을 쓰기만 해도 다른 어딘가의 주 아이템에 옵션이 하나도 남지 않는다면 그 옵션은 그 자리에서 내버리고, 그 치움은 아이템마다 살아남은 옵션들이 서로 받쳐 줄 수 있게 될 때까지 물결친다. 말하자면 DLX-PRE를 마디마다, 바닥까지 다시 돌리는 셈이다.

dc := cells.NewXCCDC()
for sol := range dc.Dance(strings.NewReader(input)).Solutions {
    // NewXCC()가 찾는 것과 같은 덮개를, 대개 훨씬 적은 마디로 찾는다
}
fmt.Println(dc.Nodes(), dc.Updates(), dc.Purges())

마디는 비싸지고, 그 수는 훨씬 줄어든다. 그 거래가 어느 쪽으로 기우는지는 엔진이 아니라 문제의 성질이다. 이 저장소의 예제 둘을 두 엔진으로 각각 풀어 보면 이렇다.

문제	XCC	XCCDC
examples/filomino/15x15.filomino.dlx	마디 133,639개, 11.1초	마디 82개, 54ms
examples/pentominoes/8x8.dlx	마디 93,833개, 0.32초	마디 12,295개, 2.0초

함수 NewXCC()와 다른 점 둘은 알아 둘 값이 있다. 메서드 Purges()는 도메인 일관성이 치운 옵션의 수를 세고, Debug = true로 두면 첫 가지를 뻗기도 전에 그 가운데 몇 개가 나갔는지를 알려 준다. 그리고 이 엔진은 옵션마다 주 아이템으로 시작하기를 바라고 그렇지 않으면 입력 때 노드를 옮겨 놓으므로, 부 아이템을 앞에 두고 쓴 옵션은 그 첫 주 아이템이 앞에 온 채로 알려진다. 나머지는 입력 차례를 지킨다. 메서드 Minimize는 없다.

늘어놓지 않고 세기 (ZDD)

위의 세 엔진은 해를 하나씩 건네준다. 해가 10¹⁶개인 문제에는 틀린 모양이므로, zdd/는 모든 해를 한꺼번에 ZDD로 돌려주는 넷째 엔진이다. 그 경로가 바로 정확 덮개인 결정 다이어그램이다. 크누스의 DLX6 착상(Nishino, Yasuda, Minato, Nagata의 2017년 논문을 따른 것이다)을 희소 집합 위에 올린 것인데, 옵션 몇 개를 고르고 남은 부분 문제는 어느 아이템이 남았느냐에만 달렸으므로 이제껏 푼 부분 문제를 기억하는 탐색은 같은 것을 두 번 풀지 않는다. 다이어그램은 크누스의 BDD15를 Go로 옮긴 sjnam/bdd에서 온다.

import zdd "github.com/sjnam/dancing-cells/zdd"

d := zdd.New().Dance(strings.NewReader(input))
fmt.Println(d.Count())                 // *big.Int — 다이어그램을 한 번 걷는다
fmt.Println(d.Nodes())                 // 다이어그램의 크기
best, weight, _ := d.MaxWeight(w)      // 가장 무거운 덮개, 탐색 없이
one, _ := d.Random(rnd)                // 모든 덮개에 대해 고르게 무작위로
for sol := range d.Solutions() { … }   // 원한다면 여전히 하나씩
z, root := d.ZDD()                     // bdd 손잡이, 나머지는 모두 거기서

풀이기는 다른 엔진들처럼 옵션이 가장 적은 아이템에서 분기한다. 필드 MRV를 끄면 번호가 가장 작은 살아 있는 아이템에서 분기하는데, 크누스의 연습문제 7.2.2.1-264가 그것이다. 돌아오는 다이어그램은 어느 쪽이든 같다. 줄여서 차례가 잡힌 ZDD는 그 집합족과 변수 차례로 정해지기 때문이다. 다만 길고 가는 영역에서는 그 쓸기가 더 싸다.

이것이 값을 하는지는 엔진이 아니라 문제의 성질이다. 탐색 마디 칸은 이 엔진이 들르는 수이고, 아낌은 캐시 없는 다른 엔진들이 들르는 수를 그것으로 나눈 값이다. 가장 큰 판 둘은 어림값인데, 5.3 × 10¹⁶가지 덮기를 세어 보겠다고 나설 사람이 없기 때문이다. 캐시는 그 마디 수가 그 가운데 서로 다른 부분 문제의 수를 넘어서는 배수만큼 이긴다.

문제	해의 수	탐색 마디	아낌
8 × 8 도미노	12,988,816	2,317	21,600×
10 × 10 도미노	258,584,046,368	13,560	7.4 × 10⁷
12 × 12 도미노	5.3 × 10¹⁶	74,023	2.8 × 10¹²
6 × 10 펜토미노	9,356	822,828	1.5×
랭포드 11	17,792	130,724	1.3×
8-퀸	92	869	1.1×

고른 모양의 영역을 덮는 문제는 작고 서로 상관없는 조각으로 나뉘므로 거의 모든 부분 문제가 되풀이된다. 펜토미노 열둘은 모두 다르므로 되풀이되는 것이 거의 없고, 1.5배를 아끼자고 서명 700,000개짜리 캐시를 무는 것은 밑지는 거래다. 그런 것에는 NewXCC()를 쓰라. 반면 10 × 10 판의 2580억 가지 덮기를 모두 세는 데는 36ms와 마디 13,161개짜리 다이어그램이면 되고, 그 가운데 가장 무거운 것을 찾는 데 0.8ms가 더 들 뿐이다. 둘 다 낱낱이 늘어놓아서는 닿을 수 없다.

패키지 zdd가 따로 서 있는 것은 핵심이 기대는 것 없이 남게 하려는 것이다. 명령 go get github.com/sjnam/dancing-cells은 아무것도 끌어오지 않고, .../dancing-cells/zdd를 import할 때에만 bdd가 딸려 온다.

예제

예제	실행
N-퀸	go run ./examples/queen 8
랭포드 짝	go run ./examples/langford 4
펜토미노	go run ./examples/pentominoes examples/pentominoes/6x10.dlx
스도쿠	go run ./examples/sudoku examples/sudoku/puzzles.txt
필로미노	go run ./examples/filomino examples/filomino/10x10.filomino.dlx
얼룩말 퍼즐	go run ./examples/zebra
파티지 (다중도)	go run ./examples/partridge 8
도미노 덮기 (ZDD)	go run ./examples/domino -aztec 8
낱말 찾기	go run ./examples/wordsearch examples/wordsearch/movie.txt 13 13
스물넉 자를 덮는 다섯 낱말	go run ./examples/words examples/words/sgb-words.txt 5
가장 싼 라틴 방진 횡단	go run ./examples/transversal -plain 11
가운데가 빈 파티지	go run ./examples/hollow -z 16

예제는 저마다 문제를 DLX 텍스트로 지어내거나 파일에서 읽어 Dance에 넘기고 채널 Solutions를 비운다. dlx 예제와 같은 본새다. 아이템 이름과 색은 길이에 제한이 없는(여러 바이트여도 되는) 문자열이므로, 얼룩말(N0:England)도 한글 낱말 찾기도 그대로 된다. 다중도가 필요한 파티지는 NewMCC로 푼다. 이로써 dlx의 예제가 모두 춤추는 칸으로 옮겨졌다.

랭포드 짝짓기

$ go run ./examples/langford 4
[2 3 4 2 1 3 1 4]

펜토미노

• 조각 12개: O P Q R S T U V W X Y Z

$ cd examples/pentominoes
$ go run pentominoes.go 8x8.dlx
1:
Q Q X U U V V V
Q X X X U V Z Z
Q R X U U V Z S
Q R R . . Z Z S
R R Y . . W S S
Y Y Y Y W W S T
P P P W W T T T
P P O O O O O T

2:
Q Q X U U V V V
Q X X X U V Z Z
Q S X U U V Z O
Q S T . . Z Z O
S S T . . W W O
S T T T W W R O
P P P Y W R R O
P P Y Y Y Y R R

3:
Q Q X U U V V V
Q X X X U V Z Z
Q S X U U V Z Y
Q S T . . Z Z Y
S S T . . W Y Y
S T T T W W R Y
P P P W W R R R
P P O O O O O R

...

N-퀸

$ go run ./examples/queen 8
1:
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. Q . . . . . .

2:
. . . Q . . . .
. Q . . . . . .
. . . . . . . Q
. . . . . Q . .
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
. . . . . . Q .

...

스도쿠

$ cd examples/sudoku
$ go run sudoku.go puzzles.txt
Q[    1]: ..43..2.9..5..9..1.7..6..43..6..2.8719...74...5..83...6.....1.5..35.869..4291.3..
A[    1]: 864371259325849761971265843436192587198657432257483916689734125713528694542916378
Q[    2]: .4.1...5.1.7..396.52...8..........17...9.68..8.3.5.62..9..6.5436...8.7..25..971..
A[    2]: 346179258187523964529648371965832417472916835813754629798261543631485792254397186
Q[    3]: 6..12.384..8459.72.....6..5...264.3..7..8...694...3...31.....5..897.....5.2...19.
A[    3]: 695127384138459672724836915851264739273981546946573821317692458489715263562348197
Q[    4]: 4972.....1..4....5....16.9862.3...4.3..9.......1.726....2..587....6....453..97.61
A[    4]: 497258316186439725253716498629381547375964182841572639962145873718623954534897261
Q[    5]: ..591.3.8..94.3.6..275..1...3....2.1...82...7..6..7..4....8....64.15.7..89....42.
A[    5]: 465912378189473562327568149738645291954821637216397854573284916642159783891736425
...
Q[70098]: ..2.....9.3...25....61..37..........2..4..13...7..6.4...18.....76...54....9..76..
A[70098]: 472653819138792564956148372694531287285479136317286945521864793763915428849327651
Q[70099]: .3............1..87..58........24.5..4.8739....36.....9.......2..5..2.912.....7.4
A[70099]: 438297165659431278721586349167924853542873916893615427974168532385742691216359784
Solving took: 2.142709417s

필로미노

$ cd examples/filomino

| ..3.3...3.
| ..131...43
| 64...141..
| .6...4.4..
| 64...141..
| ..434...12
| ..3.3...2.
| ..434...12
| 24...161..
| .2...6.6..

$ go run filomino.go 10x10.filomino.dlx
3 3 3 1 3 3 2 2 3 3
4 4 1 3 1 3 4 4 4 3
6 4 4 3 3 1 4 1 2 2
6 6 6 6 4 4 1 4 4 4
6 4 3 3 4 1 4 1 4 2
4 4 4 3 4 3 4 4 1 2
3 3 3 1 3 3 4 2 2 1
2 4 4 3 4 4 6 6 1 2
2 4 4 3 4 1 6 1 3 2
1 2 2 3 4 6 6 6 3 3

낱말 찾기

낱말 찾기가 무엇인가? https://thewordsearch.com/

낱말은 언제나 같은 자리에 놓이지만 남는 칸은 아무 글자로나 채우므로, 두 번 돌려서 똑같은 판이 찍히는 일은 없다.

$ cd examples/wordsearch
$ go run wordsearch.go movie.txt 13 13
1:
봄여름가을겨울그리고봄섬차
뎷억추의인살밀인스시아오열
사전운시택양인호며박븃다국
장횬란장벌쟝여변리쥐마간설
화것이시와칔의친날생더은엽
홍의파제죄생변절휘인이날기
련나부국께활해한기한보봄적
골는산괠함의뭀금극콤드멼인
막수행기과발밤자태달올퍔그
동복적생신견과씨정수오명녀
투아의충친구낮강원도의힘량
컴가공괴날진빠에물우가지돼
웰씨공궠물게하대위게하밀은

$ go run wordsearch.go mathematicians.txt 15 15
1:
W E I E R S T R A S S T S M H
A Z L H C A N T O R R J U V R
O T T E N N E S N E J D I U E
Y E P E R R O N V R N C N P Q
S E J T L E I T S A A G E O R
F F O K R A M P R O E I B R H
P D H U R W I T Z N K H O E I
L G D S V K R Z A S Y E R T L
E N R Y W E K L W L S R F S B
S I A A B U A O X E T M P E E
N L M O M T K Z T R E I P V R
E L A L A N D A U O R T O L T
H E D C I T B T K B N E N Y I
X M A M R E H S I A L G K S L
R V H X L T F F O H H C R I K

얼룩말 퍼즐

다섯 사람이 저마다 다른 다섯 나라에서 왔고, 다섯 가지 다른 일을 하며, 다섯 가지 다른 동물을 기르고, 다섯 가지 다른 것을 마시며, 색깔이 저마다 다른 다섯 집에 한 줄로 산다.

• 영국 사람은 빨간 집에 산다.
• 화가는 일본에서 왔다.
• 노란 집에는 외교관이 산다.
• 커피를 좋아하는 사람의 집은 초록색이다.
• 노르웨이 사람의 집은 맨 왼쪽이다.
• 개 주인은 스페인에서 왔다.
• 우유를 마시는 사람은 한가운데 집에 산다.
• 바이올리니스트는 오렌지 주스를 마신다.
• 하얀 집은 초록 집 바로 왼쪽이다.
• 우크라이나 사람은 차를 마신다.
• 노르웨이 사람은 파란 집 옆에 산다.
• 조각가는 달팽이를 기른다.
• 말은 외교관 옆에 산다.
• 간호사는 여우 옆에 산다.

얼룩말을 길들이는 사람은 누구이고, 맹물만 마시기를 좋아하는 사람은 누구인가?

$ go run ./examples/zebra
Norway      Ukraine     England     Spain       Japan
diplomat    nurse       sculptor    violinist   painter
fox         horse       snail       dog         zebra
water       tea         milk        orange      coffee
yellow      blue        red         white       green

파티지 퍼즐

$ go run ./examples/partridge 9
┌─────────────────┬───────────────┬─────────────────┬─────────────────┬───────────┬───────┐
│                 │               │                 │                 │           │       │
│                 │               │                 │                 │           │       │
│                 │               │                 │                 │           │      4│
│                 │               │                 │                 │           ├───────┤
│                 │               │                 │                 │          6│       │
│                 │               │                 │                 ├───────────┤       │
│                 │              8│                 │                 │           │      4│
│                9├─────┬─────────┤                9│                9│           ├───────┤
├─────────────┬───┤     │         ├───────┬─────┬───┴───────┬─────────┤           │       │
│             │  2│    3│         │       │     │           │         │           │       │
│             ├───┴─────┤         │       │    3│           │         │          6│      4│
│             │         │        5│      4├─────┤           │         ├───┬───────┴───────┤
│             │         ├─────────┴───────┤     │           │        5│  2│               │
│             │         │                 │    3│          6├─┬───────┴───┤               │
│            7│        5│                 ├─────┴───┬───────┴─┤           │               │
├───────────┬─┴─────────┤                 │         │         │           │               │
│           │           │                 │         │         │           │               │
│           │           │                 │         │         │           │               │
│           │           │                 │        5│        5│          6│              8│
│           │           │                 ├─────────┴─────┬───┴───────────┼───────────────┤
│          6│          6│                9│               │               │               │
├───────────┴─┬─────────┴───┬─────────────┤               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │              8│              8│              8│
│            7│            7│            7├───────────────┼───────────────┼───────────────┤
├─────────────┼─────────────┼─────────────┤               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│             │             │             │               │               │               │
│            7│            7│            7│              8│              8│              8│
├─────────────┴───┬─────────┴───────┬─────┴───────────┬───┴─────────────┬─┴───────────────┤
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                 │                 │                 │                 │                 │
│                9│                9│                9│                9│                9│
└─────────────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┘

도미노 덮기 세기

엔진 zdd 위에 세운 하나뿐인 예제이고, 그것 없이는 쓸 수 없었을 예제다. 8 × 8 판에는 도미노로 덮는 법이 12,988,816가지, 12 × 12 판에는 53,060,477,521,960,000 가지 있고, 차수 n의 아즈텍 다이아몬드에는 정확히 2^(n(n+1)/2)가지 있다. 낱낱이 늘어놓아서는 아무리 해도 닿지 못할 수다. 이 프로그램은 그것을 세고, 센 값을 Kasteleyn의 곱셈 공식(아즈텍 다이아몬드라면 정확한 2의 거듭제곱)과 맞춰 보고, 모든 덮기에서 고르게 뽑은 덮기 하나를 그리고, 칸마다 무게가 주어졌을 때 가장 무거운 덮기를 찾는다. 최대 무게 완전 짝짓기를 다이어그램 위의 걸음 한 번으로 푸는 것이다.

$ go run ./examples/domino -aztec 10
아즈텍 다이아몬드 차수 10: 칸 220개, 도미노 자리 400개
덮는 방법: 36,028,797,018,963,968가지
  다이어그램 마디 1245866개, 탐색 마디 1118227개, 서명 870349개, 적중 247786번
  2^(n(n+1)/2) = 36,028,797,018,963,968 ... 맞다

고르게 뽑은 덮기 하나 (점수 2400):
                  ┌───┐
                ┌─┴─┬─┴─┐
              ┌─┴─┬─┴─┬─┴─┐
            ┌─┴─┬─┴─┬─┴─┬─┴─┐
          ┌─┴─┬─┼─┬─┼─┬─┼─┬─┴─┐
        ┌─┴─┬─┤ │ │ │ │ │ ├─┬─┴─┐
      ┌─┼───┤ ├─┴─┼─┼─┼─┼─┤ ├───┼─┐
    ┌─┤ ├───┼─┴─┬─┤ │ │ │ ├─┼─┬─┤ ├─┐
  ┌─┤ ├─┼─┬─┼───┤ ├─┼─┴─┼─┤ │ │ ├─┤ ├─┐
┌─┤ ├─┤ │ │ ├─┬─┴─┤ ├───┤ ├─┼─┼─┤ ├─┤ ├─┐
│ ├─┤ ├─┼─┴─┤ ├─┬─┴─┼─┬─┴─┤ │ │ ├─┤ ├─┤ │
└─┤ ├─┤ ├─┬─┴─┤ ├───┤ ├───┼─┴─┼─┤ ├─┤ ├─┘
  └─┤ ├─┤ ├─┬─┼─┴─┬─┴─┼───┼───┤ ├─┤ ├─┘
    └─┤ ├─┤ │ ├─┬─┼───┼───┼─┬─┴─┤ ├─┘
      └─┤ ├─┼─┤ │ ├─┬─┴─┬─┤ ├───┼─┘
        └─┤ │ ├─┴─┤ ├───┤ ├─┴─┬─┘
          └─┼─┴─┬─┴─┼───┼─┴─┬─┘
            └─┬─┴─┬─┴─┬─┴─┬─┘
              └─┬─┴─┬─┴─┬─┘
                └─┬─┴─┬─┘
                  └───┘

저 무작위 덮기의 네 귀퉁이를 보라. 벽돌처럼 고른 무늬로 얼어붙었고, 어지러움은 한가운데 원 안에만 남아 있다. 그것이 북극원(Jockusch, Propp, Shor, 1998)인데, 그것을 보려면 3.6 × 10¹⁶가지 덮기에서 고르게 뽑은 표본이 있어야 한다. 다이어그램을 한 번 걸으면 되는 일이고, 달리는 될 수 없는 일이다.

잘린 체스판은 그 반대쪽을 말한다. 깃발 -cut은 마주 보는 두 귀퉁이를 떼어 내고, 답은 마디 하나짜리 다이어그램과 함께 0으로, 몇 밀리초 만에 돌아온다.

스물넉 자를 덮는 다섯 낱말

파일 sgb-words.txt는 다섯 글자 영어 낱말 5757개를 모은 스탠퍼드 그래프베이스의 목록이다. 그 가운데 다섯이면 글자 자리 스물다섯을 채우는데, 그 자리들이 알파벳 스물넉 자를 서로 다르게 덮을 수 있을까? (스물다섯은 안 된다. 이 목록에는 글자가 서로 하나도 겹치지 않는 다섯 낱말이 없다.) 글은 examples/words/words.w에 있다.

$ go run ./examples/words examples/words/sgb-words.txt 8
frock glitz nymph squab vowed   (o를 두 번, j x 빠짐)
frock squab veldt whomp zingy   (o를 두 번, j x 빠짐)
frock glitz nymph squab vexed   (vexed 안에서 겹침, j w 빠짐)
foxed glitz nymph squab wreck   (e를 두 번, j v 빠짐)
fjord glitz nymph squab wreck   (r를 두 번, v x 빠짐)
frock glitz jived nymph squab   (i를 두 번, w x 빠짐)
frock glitz nymph squab waved   (a를 두 번, j x 빠짐)
foxed glitz nymph squab wrack   (a를 두 번, j v 빠짐)
해 8개

숫자 8 대신 0을 주면 모두 늘어놓는다. 40초쯤에 답이 9592개다. 풀이기 자신이 돌려주는 것은 글자 집합마다 하나씩 8132개이고, 그 하나하나를 그것을 이루는 낱말들로 펼친 것이다. 낱말 stack과 tacks 같은 어구전철은 글자 집합이 같아 답에서 서로 바꿔 쓸 수 있기 때문이다.

헝가리 무곡 제5번

메서드 Minimize와 필드 Bound를 쓰는 두 예제 가운데 첫째다. 라틴 방진의 횡단은 행마다, 열마다, 기호마다 칸 하나씩을 고르는 것이다. "꼭 한 번"이라는 제약 셋이니, 아이템 3n개와 옵션 n²개짜리 정확 덮개다. 칸마다 값을 매기면 물음은 이렇게 된다. 어느 횡단이 가장 싼가?

하한이 핵심이다. 기호를 잊으면 남는 것은 살아 있는 행을 살아 있는 열에 맞추는 최소비용 배정이고, 헝가리안 알고리즘이 그것을 O(n³)에 정확히 푼다. 제약 하나를 버리면 답은 싸지기만 하므로 그것은 성한 하한이고, 어림이 아니라 부분 문제의 정확한 최적값이므로 센 하한이다. 분기는 춤추는 칸으로, 한정은 헝가리안으로. 브람스에서 시작하는 그 글은 이것을 헝가리 무곡 기법이라 부르는데, 있던 알고리즘 둘이 맞물리는 자리에 붙인 이름이지 새 절차가 아니다.

$ go run ./examples/transversal -plain 9
   0:81   1:887   2:847    3:59  [ 4:81]  5:318   6:425   7:540   8:456
   ...
가장 싼 횡단의 값 1296, 노드 122개, 1ms
하한 없이는 노드 155개, 0s

이 방진은 Z_n의 케일리 표이므로 Hall–Paige에 따라 n이 홀수일 때만 횡단이 있다(그 수도 OEIS A006717과 맞는다. n = 5, 7, 9, 11에 대해 15, 133, 2025, 37851이다). 하한은 문제가 어려울수록 더 값을 한다.

n	세금과 쓸기만	헝가리안	비
13	1,478 / 2ms	535 / 3ms	3×
15	13,654 / 14ms	3,926 / 23ms	3×
17	73,253 / 67ms	9,374 / 42ms	8×
19	183,635 / 231ms	37,801 / 216ms	5×
21	1,412,610 / 1.80s	133,554 / 930ms	11×
23	7,915,018 / 11.3s	706,998 / 5.57s	11×
25	40,935,232 / 68.2s	1,955,438 / 18.3s	21×

헝가리안 마디 하나가 6–9µs인데 다른 쪽은 1.3–1.7µs이므로, 하한이 본전을 뽑는 자리는 n = 17과 19 사이 어딘가다. n = 25에서는 벽시계로 4배 빠르다. 하한이 없으면 n = 25에 1분이 넘게 걸리고, 있으면 n = 27에 1분 20초, n = 29에 4분 25초, n = 31에 5분 18초가 걸린다. 그러니 벽을 n = 25쯤에서 n = 30쯤으로 밀어 준다. 그리고 n이 짝수이면 아무 일도 하지 않는다. 횡단이 없으면 이길 cutoff가 아예 생기지 않고, 분기한정은 이길 것이 손에 들어와야 비로소 일을 하기 때문이다.

왼쪽 칸은 예전에 하한이라고는 아무것도 없는 탐색이었다. n = 19에서 마디 1억 1700만 개에 19.5초였으니 비가 1429×이고 벽시계로 39×였다. 그러다 엔진이 크누스의 DLX5에서 두 가지를 배웠다(가장 싼 덮개를 보라). 첫째인 세금은 그 칸을 거저 스무 배 줄였다. 그 글은 세금이 여기서 왜 그리 센지를 짚는다. 아이템이 행, 열, 기호 차례로 늘어서 있으므로 세금은 행마다 최솟값을 빼고 그다음 열마다 최솟값을 빼는데, 그것이 바로 헝가리안 알고리즘을 여는 행·열 감축이다. 그러고 나서 기호까지 감축하는데, 헝가리안 하한이 못 본 척하는 축이 그것이다. 둘째인 쓸기는 마디마다 그 마디가 더는 감당할 수 없는 옵션을 지우므로 분기 규칙이 살아 있는 선택지만 세게 되고, 그것이 그 칸을 다시 서른 배쯤 줄였다(n = 21에서 5천만 마디가 140만 마디로). 남은 비는 헝가리안 하한이 둘 다에게 없는 두 가지로 벌어들인다. 감축 뒤의 증강 단계, 그리고 그 모두를 마디마다 아직 살아 있는 칸에 대해 다시 하는 것이다. 하한은 쓸기 덕도 보는데, 이제 쓸기를 견뎌 낸 칸들에 대해 배정 문제를 풀기 때문이다.

그리고 천장이 있는데, 그 글이 이제 대놓고 말한다. 그 비는 세금과 쓸기만 가진 같은 프로그램에 견준 것이지 최고 수준에 견준 것이 아니다. 최소비용 횡단은 정수 계획으로 옮겨 적기가 지나치게 쉽고, 그렇게 적으면 LP 완화가 거의 빈틈없다. 이 프로그램이 1분 20초를 쓰는 n = 27을 웬만한 MILP 풀이기는 1초쯤에 끝내고 분기도 거의 하지 않는다. 우리 것은 축 하나를 통째로 버리고 최적값보다 40%쯤 아래에 내려앉는 반면, LP는 셋을 다 쥐고 10%도 채 못 미친다. 헝가리안 알고리즘이 우리 완화를 정확히 푼다는 것과 우리 완화가 좋다는 것은 서로 다른 말이었던 셈이다. 이 기법은 알아 둘 값이 있는 틀이지만, 이 바닥이 그것이 제값을 하는 자리는 아니다.

같은 훅을 MCC에 다는 일이 더 까다로운 쪽이었다. 이진 분기에서 가지를 버리는 일은 강제 스택이 비어 있는 자리에서만 안전하다. 그렇지 않으면 다음 마디가 남은 칸을 제 강제 이동으로 주워 가는데, 거기서 강제 이동은 분기가 아니라 옵션 하나를 들이고 다른 길은 아예 시도하지 않는 것이다. 답은 그럴듯한 채로 남고 다만 가장 싼 것이기를 그친다. 무작위 문제 수천 개를 모조리 세어 본 답과 맞춰 보고서야 그것을 잡았다.

A Partridge in a Pear Tree

메서드 Minimize를 쓰는 다른 예제이고, Need를 부리는 예제다. 파티지 퍼즐은 k×k 정사각형 k장씩을, k = 1…n에 대해, 변이 n(n+1)/2인 정사각형에 채워 넣는 것이다. 1³+⋯+n³ = (1+⋯+n)² 이므로 넓이가 맞아떨어진다. 해가 있는 가장 작은 차수는 8이다. 이제 값을 매기자. 판 한가운데에 z×z 구역을 정하고, 그 안에 온전히 들어앉는 조각마다 1을 물린다. 값이 0인 덮개는 모든 조각이 구역의 테두리를 걸치는 판, 곧 텅 빈 심장이다.

연필과 종이가 물음의 절반을 매듭짓는다. 변이 n 이하인 조각은 제가 덮는 칸에서 많아야 n−1만큼 뻗으므로, 구역 안으로 그만큼 이상 들어간 칸은 구역에 갇힌 조각만이 덮을 수 있다. 그 갇힌 칸들은 (z−2n+2)×(z−2n+2) 덩이를 이루고, z ≥ 2n−1 이면 곧바로 비지 않는다.

텅 빈 심장은 z ≤ 2n−2일 때에만 가능하다.

하한은 그 논증을 움직이게 만든 것이다. 필드 Frame.Live를 훑어 아직 덮이지 않은 칸마다 그것을 아직 덮는 가장 싼 옵션을 집고, 값이 0이 아닌 것들 가운데 체비쇼프 거리로 서로 n 이상 떨어진 것만 남겨 한 조각이 둘을 대신 물 수 없게 한 다음, 그 값을 더한다. 그러면 처음에는 자유로웠다가 옵션이 죽어 가며 갇히게 되는 칸을 찾아낸다. 차수 8의 판(36×36)에서 2분을 넘기지 않기로 하고 재면 이렇다.

z	최솟값	세금과 쓸기만	Need 하한	갇힌 칸 하한
8	0	7,347 / 139ms	7,347 / 1.76s	7,347 / 1.78s
12	0	9,128 / 156ms	9,128 / 2.09s	9,128 / 2.06s
14	≤ 1	—	—	—
16	1	7,413 / 132ms	7,413 / 1.74s	7,413 / 1.77s

구역이 z ≤ 12이면 값 0짜리 덮개가 거의 대뜸 나와 cutoff가 0으로 떨어지고 모든 가지가 cost + rest >= cutoff에서 죽으니, 하한은 순전히 짐이다.

구역이 z = 16일 때는 글을 처음 마친 뒤에 이야기가 달라졌다. 하한이 없을 때는 2분과 마디 640만 개로 아무것도 증명하지 못했고, 갇힌 칸 하한은 2초도 안 되어 나무를 무너뜨렸다. 그러다 엔진이 아이템에 세금을 걷기 시작하면서 (가장 싼 덮개를 보라), 이제 Bound가 아예 없는 탐색이 0.13초에 끝난다. 세금이 연필 논증을 혼자 해내는 것이다. 갇힌 칸을 덮는 옵션은 모두 값이 1이므로 그 칸의 세금이 1이다. 덩이의 남은 세 칸은 아무것도 물지 않는데, 저마다 첫 칸과 조각 하나를 함께 쓰고 그 조각은 이미 순값 0으로 깎였기 때문이다. 갇힌 칸 하한이 제 칸들을 n 이상 떼어 놓아 피하던 이중 계산이 바로 그것이다. 뿌리의 하한이 1이고 값 1짜리 덮개가 손에 들어오면 나무가 죽는다. 세금은 입력 때 한 번 걷으므로 탐색 도중에 갇히는 칸은 보지 못한다. 한동안은 그것이 손으로 쓴 하한이 더해 주던 몫이었는데, 마디는 9% 적고 시간은 11배였다. 그러다 엔진이 마디마다 감당할 수 없는 옵션을 쓸어 내기 시작했고, 탐색 도중에 갇히는 칸이란 감당할 수 있던 마지막 옵션이 방금 쓸려 나간 칸일 뿐이니 가지는 거기서 죽는다. 이제 세 칸 모두 같은 마디를 들른다. 손으로 쓴 하한에 남은 것이 있다면 멀리 떨어진 칸 여럿이 함께 갇히는 경우일 텐데, 쓸기가 칸을 하나씩 보는 자리에서 그 값들이 더해지기 때문이다. 다만 이 판에서는 그런 일이 값을 하지 않는다.

하한 Need는 — 크기 k는 아직 t장이 더 필요한데 살아남은 놓을 자리 가운데 공짜인 것이 u개뿐이니 t−u는 치러야 한다 — 필드 Frame.Need를 읽는 하한이고, 그것은 다중도가 있어야 뜻이 있다. 여기서는 값을 하지 못한다고 정직하게 적어 둔다. 조각이 갇히느냐는 그것이 어디에 내려앉느냐에 달렸는데, 놓을 자리를 크기로 뭉뚱그려서는 그것을 볼 수 없다. 두 하한 모두 -bound 뒤에 딸려 있으니 위의 표는 다시 재어 볼 수 있다.

구역 z = 14 = 2n−2는 열린 채로 남았다. 값 1은 2초에 찾지만, 값 0은 찾지도 못하고 없다고 가리지도 못한다. 연필 논증이 허락하는 가장 큰 구역이 바로 그것이고, 하한이 뿌리에서 0을 돌려주는 마지막 자리가 바로 그것이다. 뿌리에 갇힌 칸이 없으니 거기서는 세금도 0이다. 값 1짜리 덮개를 한 번 찾고 나면 쓸기가 값 1짜리 옵션을 모두 지우므로, 남는 것은 자유로운 자리들만으로 판을 덮을 수 있는가라는 맨 정확 덮개 물음이다. 그런데 그것조차 2분 안에 끝나지 않는다.

글은 examples/hollow/hollow.w에 있다.

$ go run ./examples/hollow -z 16
갇힌 조각 2개 (노드 7331개, 1.727s)
갇힌 조각 1개 (노드 7399개, 1.741s)
...
갇힌 조각 1개, 노드 7413개, 1.749s

소스는 문학적 프로그램이다

엔진은 크누스가 TeX을 쓰려고 지어낸 문학적 프로그래밍 방식으로 쓰였고, 이식해 온 SSXCC와 SSMCC가 선 자리와 같은 전통을 따른다. 크누스 자신이 그것을 문학적 CWEB으로 썼다. 크누스가 DLX1, DLX2, DLX3을 깃발 달린 한 프로그램이 아니라 따로 선 프로그램으로 둔 것처럼 우리도 그렇게 한다.

문서	무엇인가
dcells.w	공용 바탕 — 공개 API(Option, Result, Frame), XCC와 MCC 두 엔진이 함께 춤추는 노드 배열, 그리고 DLX 훑개. 첫 쪽들이 희소 집합 이야기를 들려준다.
ssxcc.w	XCC 엔진 — 색깔이 붙은 정확 덮개, d갈래 분기, 그리고 가장 싼 덮개를 다루는 마지막 장. 처음부터 끝까지 홀로 읽힌다.
ssmcc.w	MCC 엔진 — 다중도, 이진 분기, 그리고 가장 싼 덮개를 다루는 제 몫의 장. 마찬가지로 홀로 선다.
xccdc.w	XCC 엔진을 다시, 이번에는 도메인 일관성을 지키며 — 증인, 방아쇠 목록, 나이와 귀띔, 그리고 한 단계가 여러 층에 걸치는 탐색. 제 노드 타입까지 따로 둘 만큼 이 역시 홀로 선다.
zdd/zdd.w	ZDD 엔진 — 같은 탐색이되 남은 아이템의 서명으로 메모해 두고, 모든 해의 집합족을 결정 다이어그램으로 돌려준다. 제 패키지로 따로 서고, 다른 라이브러리에 기대는 유일한 문서다.

앞의 넷은 Go 패키지 dcells 하나로 tangle되므로 NewXCC(), NewMCC(), NewXCCDC()가 한 번의 import로 딸려 온다. 다섯째는 그 옆의 패키지 dcells/zdd다.

Makefile 셋이 GWEB 도구를 몬다. 저장소의 부분마다 하나씩으로 라이브러리, 예제, 연습문제 읽기다. 저마다 홀로 서고 저마다 같은 타깃을 지닌다.

make            # .w 파일을 gtangle해 .go로 만든 다음 빌드
make pdf        # gweave로 모든 문서를 조판
make clean      # 생성된 파일을 지우되 커밋된 것은 남긴다

그러니 갓 클론한 저장소는 이렇게 채비한다.

make && make -C examples && make -C taocp-7.2.2.1-exercises

진짜 원본은 .w 파일이다. 옆에 .w가 있는 .go는 모두, 조판된 문서도 모두 생성물이므로, 갓 클론했다면 그것부터 돌려야 한다. 그래도 커밋해 두는 생성물이 두 갈래 있다. 하나는 생성된 .go 파일 다섯으로, GWEB을 돌리지 않고도 패키지를 import할 수 있게 하려는 것이다. 다른 하나는 연습문제 읽기마다 딸린 verify.pdf로, 마찬가지로 그냥 읽을 수 있게 하려는 것이다. 둘 다 손으로 고쳐서는 안 된다. 도구 gtangle이 //line 지시문을 내주므로, Go 컴파일러의 오류는 그것이 비롯한 .w 파일의 줄을 곧장 가리킨다.

위의 다섯 문서와 아래의 예제 문서는 모두 한글로 쓰였고 luatex(kotexgweb)으로 조판한다(연습문제 읽기만 영문이다). 예제도 문학적 프로그램인데, 거기서 설명되는 것은 엔진이 아니라 모형 세우기다. 퍼즐이 어떻게 아이템과 옵션이 되는지, 어느 아이템이 주이고 어느 것이 부인지, 색이 무엇을 뜻하도록 만들었는지다. 열둘 모두 examples/<name>/<name>.w에 산다. 그 가운데 셋은 새로 한 일을 담아 에세이로 읽히고, 나머지는 저마다 모형 세우기의 착상 하나씩을 풀어 놓는다.

문서	무엇인가
examples/domino/domino.w	엔진 zdd로 도미노 덮기 세기 — Kasteleyn의 공식을 정확한 셈과 맞춰 보고, 고르게 뽑은 아즈텍 다이아몬드 덮기에서 북극원을 보며, 최대 무게 짝짓기를 탐색이 아니라 다이어그램을 걸어 찾는다.
examples/words/words.w	*알파벳 스물넉 자를 덮는 다섯 글자 낱말 다섯이 있는가?*가 어떻게 DLX 입력이 되는가. 그 답은 다중도 없이 색만으로 낱말 수가 꼭 다섯으로 묶인다는 것이다.
examples/transversal/transversal.w	헝가리 무곡 제5번 — 라틴 방진의 가장 싼 횡단을 춤추는 칸으로 분기하고 헝가리안 알고리즘으로 한정한다. 하한을 어디서 찾을지, 이 하한이 왜 정확한지, 그리고 이 재주가 또 어디에 먹히는지.
examples/hollow/hollow.w	A Partridge in a Pear Tree — 파티지 퍼즐이 한가운데에 얼마나 큰 구멍을 지킬 수 있는가. 가망 없던 탐색을 2초짜리 증명으로 바꾸는 기하학적 하한, 그리고 정직하게 말해 값을 하지 못하는 Need 하한.
examples/queen/queen.w	n-퀸 — 주 아이템과 부 아이템의 차이를 가장 말끔하게 보여 준다. 행과 열은 꼭 한 번 덮여야 하고 대각선은 많아야 한 번이다. 아이템 줄의 차례가 왜 중요한지도 나오는데, 분기 규칙이 비길 때 왼쪽 아이템이 이기기 때문이다.
examples/langford/langford.w	랭포드 짝 — 다른 것이라고는 아무것도 없는 정확 덮개다. 부 아이템도 색도 없다. 하나뿐인 미묘함은 거울 대칭을 깨는 일인데, 홀수 값이 있어야 하고 그렇다고 말해 주는 셈이 나온다.
examples/pentominoes/pentominoes.w	펜토미노 열둘 — 옵션이 다른 데서 만들어진 문제라, 이 글은 옵션을 쓰는 이야기가 아니라 .dlx 파일과 그 약속을 읽는 이야기다.
examples/filomino/filomino.w	필로미노 — 부 아이템을 영역의 가장자리로 쓴다. "같은 크기의 두 영역은 맞닿을 수 없다"가 거저 떨어지는 것이 그 덕이다.
examples/zebra/zebra.w	얼룩말 퍼즐 — 색을 값으로 쓴다. 부 아이템은 채울 빈칸이고 그 색이 거기 들어가는 것이며, 같은 빈칸을 건드리는 두 단서는 뜻을 모아야 한다. 이 표현이 결코 말하지 않는 것(다섯 나라가 서로 다르다는 것)과 그런데도 답이 나오는 까닭까지.
examples/wordsearch/wordsearch.w	낱말 찾기 판 짓기 — 색을 글자로 쓴다. 그러면 교차하는 두 낱말이 만나는 자리의 글자에 뜻을 모으는데, 교차를 따지는 코드는 어디에도 없다.
examples/sudoku/sudoku.w	스도쿠, 무더기로 — 탐색을 시작하기 전에 단서로 문제를 깎아 내는 일, 그리고 퍼즐 파일 하나를 모든 CPU에 흩어 풀면서도 입력 차례로 찍어 내는 순서 있는 팬인.
examples/partridge/partridge.w	파티지 퍼즐 — NewMCC()가 있어야 하는 하나뿐인 예제인데, 크기 k짜리 조각 k장이 곧 다중도이기 때문이다. 36 × 36 덮기를 37줄에 담아 내는 상자 그림 출력기도 있다.

Careful readings of TAOCP 7.2.2.1

Knuth's news page asks readers to take one exercise, read it and its answer very carefully, and report back. taocp-7.2.2.1-exercises/ holds one such reading per directory, written against Volume 4B, first printing, 2022, and against the errata file of the day. Section 7.2.2.1 is the dancing-links section, so most of them come down to an exact cover problem and the engines above do the searching. The nineteen exercises that page lists for §7.2.2.1 all have a reading here.

Each exercise's directory holds the report itself as README.md and the program behind it as a GWEB literate program in verify/verify.w, with verify/verify.pdf beside it so it can be read without installing GWEB. Nothing is claimed that the program does not check.

Nine of the nineteen answers came out with nothing left to report. The other ten each turned up something: 281,618 of answer 129 should be 294,457, the 3648 of answer 323 belongs to a 2 × 22 frame rather than a 2 × 21 one, answer 30 is broken by the one-node tree, and the puzzle answer 432 calls the hardest cannot exist. taocp-7.2.2.1-exercises/README.md indexes all nineteen readings and gathers every correction in one place.