# TAOCP Volume 4B: Combinatorial Algorithms, Part 2

> Knuth's The Art of Computer Programming, Volume 4B (first edition, 2023, ISBN 0-201-03806-4), as studied on the cracked.guide path in weeks 134 to 145: 12 reading guides, 1202 exercises, about 93 hours.

The final stretch: probability tools for analyzing search, backtracking, dancing links for exact cover problems (sudoku, polyominoes and much more), and a deep dive into SAT solving, the technology behind modern verification and constraint solving. You end the path implementing ideas that are still at the research frontier.

## Every section, week by week

| Section | Week | Exercises | Picked | Hours |
| --- | --- | --- | --- | --- |
| [Mathematical Preliminaries Redux](https://cracked.guide/guide/knuth-w116-0) | 134 | 147 (10 to HM34) | 10 | 8 |
| [7.2.2 Backtrack Programming (part 1)](https://cracked.guide/guide/knuth-w117-0) | 135 | 48 (10 to HM42) | 8 | 8 |
| [7.2.2 Backtrack Programming (part 2)](https://cracked.guide/guide/knuth-w118-0) | 136 | 31 (M15 to 41) | 8 | 8 |
| [7.2.2.1 Dancing Links (part 1)](https://cracked.guide/guide/knuth-w119-0) | 137 | 77 (M04 to 47) | 9 | 9 |
| [7.2.2.1 Dancing Links (part 2)](https://cracked.guide/guide/knuth-w120-0) | 138 | 122 | 4 | 5 |
| [7.2.2.1 Dancing Links (part 3)](https://cracked.guide/guide/knuth-w120-1) | 139 | 101 | 4 | 5 |
| [7.2.2.1 Dancing Links (part 4)](https://cracked.guide/guide/knuth-w121-0) | 140 | 150 (10 to HM46) | 8 | 9 |
| [7.2.2.2 Satisfiability (part 1)](https://cracked.guide/guide/knuth-w122-0) | 141 | 118 (01 to M46) | 9 | 9 |
| [7.2.2.2 Satisfiability (part 2)](https://cracked.guide/guide/knuth-w123-0) | 142 | 130 (05 to HM49) | 9 | 9 |
| [7.2.2.2 Satisfiability (part 3)](https://cracked.guide/guide/knuth-w124-0) | 143 | 108 (10 to HM46) | 9 | 10 |
| [7.2.2.2 Satisfiability (part 4)](https://cracked.guide/guide/knuth-w125-0) | 144 | 170 (M10 to M49) | 9 | 8 |
| [Vol 4B review](https://cracked.guide/guide/knuth-w125-1) | 145 | 1202 (01 to HM49) | 9 | 5 |

## What you will be able to do

- Write fast backtracking searches and estimate their running time before you run them.
- Implement dancing links and use exact cover to model real puzzles and scheduling problems.
- Encode problems as SAT and understand how modern CDCL solvers work.

## Before you start

- Vol 4A, especially 7.1.1 and 7.2.1.
- Probability basics (the volume opens with a week reviewing them).

## Getting the book

Vol 4B (2022) is about $64 new from InformIT; used copies are not much cheaper yet. The paperback Fascicles 5 and 6 cover earlier drafts of the same material. Borrow before you buy: many public and university libraries give you free access to O'Reilly Learning, which carries TAOCP; Libby/OverDrive and interlibrary loan (search WorldCat) work too. Older used editions are fine for Vols 1 to 3; section numbers barely changed. If you buy the eBook, get the PDF from InformIT. Knuth himself warns that the Kindle and ePUB versions mangle the math.


## Questions

### How long does TAOCP Volume 4B take?

On the cracked.guide path it takes 12 weeks (weeks 134 to 145), about 3 months, and the reading guides budget about 93 hours in all.

### How many exercises are in TAOCP Volume 4B?

1202 in the sections the path covers, rated 01 to HM49, and 387 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.

### Which edition of Volume 4B do I need?

The current one is the first edition (2023). There is only one edition; the earlier paperback fascicles are drafts of the same material. Buy the PDF, not Kindle, if you want an eBook.

---

Source: https://cracked.guide/taocp/volume-4b
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.