# Sudoku From Zero > Learn Sudoku from the rules to expert patterns: singles, pencil marks, pairs, pointing, X-Wing, Swordfish, and XY-Wing, then write a Python solver. Every step is a deduction you can justify, never a guess. --- # Sudoku From Zero You have probably stared at a Sudoku grid, filled in the obvious digits, and then hit a wall where nothing seems obvious anymore. Many people respond by guessing, erasing, and guessing again. That is not the puzzle's fault. A well-made Sudoku always has a reason for every digit, and the wall is where the reasons get more interesting. This guide teaches those reasons in order, from the one-glance moves to the patterns that look like magic until you see why they work. Sudoku involves no arithmetic. It is pure logic: facts about what cannot be, combined until only one thing can be. The same style of thinking sits underneath scheduling software, circuit checkers, and every program that solves problems by ruling things out. ## Prerequisite None. If you can read digits you can start. If you want the bigger picture of what a valid deduction is, [What Logic Actually Is](/guides/what-logic-actually-is) pairs well with this guide, and the last phase uses ideas from [Recursion Finally Clicks](/guides/recursion-finally-clicks) when a computer takes over. ## How to read this - **New to Sudoku?** Start at phase 1 and play along on the site. Open [play Sudoku](/games/sudoku) in another tab and use it between phases. - **Stuck at the wall after the obvious moves?** Jump to [phase 3](03-pencil-marks-pairs-and-locked-candidates.md). - **Here for the computer side?** Read phase 1 for the vocabulary, then [phase 5](05-how-a-computer-solves-sudoku.md). - **Want it to finally make sense?** Read in order - each phase builds on the last, and every example position is checked for rule violations. ## The phases 1. **[The Rules, and What One Solution Means](01-the-rules-and-what-one-solution-means.md)** - the grid, a notation for cells, and why a real puzzle has exactly one answer. 2. **[Scanning and Singles](02-scanning-and-singles.md)** - the two forced moves that solve most beginner puzzles: naked and hidden singles. 3. **[Pencil Marks, Pairs, and Locked Candidates](03-pencil-marks-pairs-and-locked-candidates.md)** - writing down what is still possible, then removing possibilities with pairs, triples, pointing, and box-line reduction. 4. **[Fish and Wings: Advanced Patterns](04-fish-and-wings-advanced-patterns.md)** - X-Wing, Swordfish, and XY-Wing, explained from first principles. 5. **[How a Computer Solves Sudoku](05-how-a-computer-solves-sudoku.md)** - backtracking, constraint propagation, and a runnable Python solver. > This guide stops where the named patterns stop. Longer chains, coloring, and almost-locked sets build on the same ideas but deserve their own space. Sudoku is also the gentlest entry in the Strategy Games category: [Checkers From Zero](/guides/checkers-from-zero) and [Chess From Zero](/guides/chess-from-zero) add an opponent, and [How Computers Play Games](/guides/how-computers-play-games) shows how the search idea in phase 5 grows to handle one. --- # The Rules, and What One Solution Means Sudoku looks like math, which scares off people who say they are "not a numbers person". There is no arithmetic in it. You never add, never multiply, never compare sizes. The digits 1 to 9 are nine different labels, and the puzzle is about which label goes where. This phase gives you the rule, a way to name cells so we can talk precisely, and the one idea that makes everything later work: a proper puzzle has exactly one answer. ## The rule The grid has 81 cells in 9 rows and 9 columns, cut into nine 3-by-3 boxes. Some cells start filled in. Those digits are called **givens** (or clues) and never change. Your job is to fill every other cell so that: > **Every row, every column, and every box contains each digit from 1 to 9 exactly once.** That is the whole game. Because a unit has nine cells and there are nine digits, "no digit repeats" and "every digit appears" are the same statement, so you only ever need to check for repeats. A **unit** is any row, column, or box. There are 27 of them, and every cell belongs to exactly three: its row, its column, and its box. The digits are only labels. Replace 1 to 9 with the letters A to I and you have the same puzzle, with the same solution. Sums, differences, and sizes of the numbers never matter. ## Naming cells: RxCy To say "the third cell in the second row" without a paragraph, we use **RxCy**: **R** is the row counted from the top, **C** is the column counted from the left, both from 1 to 9. So R4C7 is row 4, column 7. We number the boxes 1 to 9 in reading order, so box 5 is the center box. Here is a puzzle with the labels around the edge. We will come back to it in the next phase. ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . . 7 | . . . | 3 2 . | 2 | 8 . 2 | . . 7 | 1 . . | 3 | 9 4 . | 1 . 6 | . 7 5 | +-------+-------+-------+ 4 | . . . | . . 9 | 2 4 7 | 5 | . . . | . . . | . . . | 6 | 1 . . | . . 5 | 6 . . | +-------+-------+-------+ 7 | . 7 . | 6 . . | . . . | 8 | 5 . . | . 7 4 | . 3 . | 9 | 4 . . | 5 . 1 | 7 6 . | +-------+-------+-------+ ``` Read a few cells: R1C3 holds 7, R2C1 holds 8, R3C3 is empty, and R3C3 sits in box 1. Every position in this guide uses this same layout, with `.` for an empty cell. ## What a cell can "see" A cell **sees** every other cell it shares a unit with, and those cells are its **peers**. A cell has exactly 20 peers: 8 in its row, 8 in its column, and 4 more in its box (the box has 8 other cells, but 2 of them are already counted in the row and 2 in the column). One consequence drives all of Sudoku: **a cell can never hold a digit that one of its peers already holds.** That is how information travels. A digit placed in R1C3 reaches 20 cells and removes itself as a possibility from each. Every technique in this guide is a cleverer way of using that fact. ## What "exactly one solution" means A proper Sudoku has exactly one completed grid that contains the givens and obeys the rule. Here is what happens when a puzzle lacks that property. This grid is a finished Sudoku with four cells erased: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 6 1 7 | 9 5 8 | 3 2 4 | 2 | 8 5 2 | 3 4 7 | 1 9 6 | 3 | 9 4 3 | 1 2 6 | 8 7 5 | +-------+-------+-------+ 4 | . 6 5 | 8 1 9 | 2 4 . | 5 | . 9 8 | 4 6 2 | 5 1 . | 6 | 1 2 4 | 7 3 5 | 6 8 9 | +-------+-------+-------+ 7 | 2 7 1 | 6 9 3 | 4 5 8 | 8 | 5 8 6 | 2 7 4 | 9 3 1 | 9 | 4 3 9 | 5 8 1 | 7 6 2 | +-------+-------+-------+ ``` R4C1, R4C9, R5C1, and R5C9 are empty, and the missing digits are 3 and 7. You can fill them as 3, 7 over 7, 3, or as 7, 3 over 3, 7 - both are legal. Row 4 and row 5 each still get one 3 and one 7, columns 1 and 9 each still get one of each, and so do boxes 4 and 6. Nothing in the rules can break the tie, so this is not a real puzzle. It has two solutions, and you could only pick one by coin flip. Real puzzles never leave a rectangle like this open. Uniqueness is what makes them fair, and it gives you a promise worth building on: because only one grid fits, every wrong digit in every cell breaks a rule somewhere. **For each empty cell, there is a reason the right digit is right.** The rest of this guide is a ladder of techniques for finding those reasons. Two limits on that promise, stated plainly. First, "a reason exists" does not mean it is a one-glance reason; hard puzzles need the deep techniques of phase 4 or beyond. Second, fewer givens does not automatically mean harder. The smallest number of givens a valid puzzle can have is 17, which was proven by exhaustive computer search in 2012 ([McGuire, Tugemann, and Civario](https://arxiv.org/abs/1201.0749)), but difficulty comes from which deductions you need, not from how many digits are printed. ## Sudoku is logic, not guessing The rule and the givens are your **premises**. A solving step is a conclusion that must be true if the premises are. Here is the smallest example. In the grid above, R1C3 holds 7. Could R1C1 hold a 7? No: R1C1 and R1C3 are in the same row, and that would put two 7s there. So R1C1 is not 7. You did not guess; you showed that 7 leads to a contradiction. That move is a proof by contradiction, and the same style of argument sits under many Sudoku techniques. If you want to see how it works in general, [What a Proof Is](/guides/what-a-proof-is) walks through it, and [What Logic Actually Is](/guides/what-logic-actually-is) gives the vocabulary. Computer scientists call a puzzle like this a **constraint satisfaction problem**: 81 variables (the cells), each with possible values (1 to 9), and 27 constraints saying "these nine must all differ". You will see in phase 5 that this framing is exactly what lets a short program solve any Sudoku. The working rule for a human solver is simple to state and hard to follow when you are frustrated: **never guess; justify every digit**. If you cannot say in one sentence why a digit goes in a cell, you have a hunch, not a deduction. Hunches are fine for choosing where to look next. They are fatal as a reason to write a digit down. ## Your turn: play a few cells Open [play Sudoku](/games/sudoku) in another tab and pick the first difficulty level. Fill in a few digits, and for each one say out loud why it is forced, using the words "row", "column", and "box". If you get stuck, use the hint button: it points at the next logical deduction, and the explanation is worth reading even if you already see the move. Check yourself before moving on: ```quiz [ { "q": "How many peers does each cell have (other cells it shares a row, column, or box with)?", "choices": ["8", "20", "24"], "answer": 1, "explain": "8 in the row, 8 in the column, and 4 more in the box that are not already in the row or column: 8 + 8 + 4 = 20." }, { "q": "What does it mean for a Sudoku to have exactly one solution?", "choices": [ "Every cell can be filled by looking at one row only", "Exactly one completed grid obeys the rules and contains the givens, so every digit has a reason it must be there", "The puzzle can only be solved in one order" ], "answer": 1, "explain": "Uniqueness means a wrong digit always breaks a rule somewhere. It does not mean the reason is obvious, and the order you fill cells in is up to you." }, { "q": "In the RxCy notation, what is R4C7?", "choices": ["Row 4, column 7", "Row 7, column 4", "Box 4, cell 7"], "answer": 0, "explain": "R is the row counted from the top and C is the column counted from the left. Boxes are numbered separately." } ] ``` ## Recap 1. Every row, column, and box holds each digit 1 to 9 exactly once; the digits are labels, not quantities. 2. RxCy names a cell by row (from the top) and column (from the left); a cell has 20 peers and can never hold a digit any of them holds. 3. A valid puzzle has exactly one solution, which means every wrong digit breaks a rule and every right digit has a reason. 4. Each solving step is a deduction (often a proof by contradiction), never a guess. Next up, [Scanning and Singles](02-scanning-and-singles.md): the two forced moves that solve most beginner puzzles. --- # Scanning and Singles Every Sudoku deduction does one of two things: it places a digit, or it removes a possibility. The first kind of deduction is the **single**, and it comes in two flavors that look at the same fact from opposite sides. Master these and you can finish most puzzles at the lower difficulty levels with no notes at all. They are also the move you will use hundreds of times inside hard puzzles, because fancier techniques usually end by creating a single. We work on the puzzle from phase 1. Here it is again: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . . 7 | . . . | 3 2 . | 2 | 8 . 2 | . . 7 | 1 . . | 3 | 9 4 . | 1 . 6 | . 7 5 | +-------+-------+-------+ 4 | . . . | . . 9 | 2 4 7 | 5 | . . . | . . . | . . . | 6 | 1 . . | . . 5 | 6 . . | +-------+-------+-------+ 7 | . 7 . | 6 . . | . . . | 8 | 5 . . | . 7 4 | . 3 . | 9 | 4 . . | 5 . 1 | 7 6 . | +-------+-------+-------+ ``` ## Naked single: the cell has one digit left Take R1C1. Which digits can it hold? Remove everything its peers already use. - Row 1 holds 7, 3, 2. - Column 1 holds 8, 9, 1, 5, 4. - Box 1 holds 7, 8, 2, 9, 4. Together those cover 1, 2, 3, 4, 5, 7, 8, 9. Only 6 is left, so R1C1 must be 6. A cell with exactly one possible digit is a **naked single**. "Naked" means the digit is plain to see: the cell's own list of possibilities has a single entry. The method is a subtraction: nine digits, minus the digits among the cell's 20 peers. *What just happened:* you did not search for 6. You ruled out the other eight, and the one that survived had to be right. The same grid has four more naked singles right now: R1C6 is 8, R2C8 is 9, R3C3 is 3, and R3C7 is 8. Placing those five digits creates six more naked singles, and R2C2, which must be 5, is one of them. Solving is a cascade: each placement feeds the next. ## Hidden single: the digit has one cell left Now flip the question. Instead of asking "what fits in this cell?", ask "where can this digit go in this unit?" Look at box 1 and the digit 1. We can mark every cell in the grid with `o` if a 1 could still go there, `.` if not, and keep the placed 1s as `1`. A placed 1 blocks its whole row, its whole column, and its whole box. ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . o . | . . . | . . . | 2 | . . . | . . . | 1 . . | 3 | . . . | 1 . . | . . . | +-------+-------+-------+ 4 | . . . | . o . | . . . | 5 | . . . | . o . | . o o | 6 | 1 . . | . . . | . . . | +-------+-------+-------+ 7 | . . o | . . . | . o o | 8 | . o o | . . . | . . o | 9 | . . . | . . 1 | . . . | +-------+-------+-------+ ``` In box 1 (rows 1 to 3, columns 1 to 3) exactly one `o` is left: R1C2. Why do the other eight cells fail? - R1C3, R2C1, R2C3, R3C1, and R3C2 are already filled with other digits. - R2C2 is blocked because row 2 already has a 1 (R2C7). - R3C3 is blocked because row 3 already has a 1 (R3C4). - R1C1 is blocked because column 1 already has a 1 (R6C1). Box 1 must contain a 1 somewhere, and R1C2 is the only cell that can take it. So R1C2 is 1. That is a **hidden single**: the digit is hidden among the other candidates of its cell. R1C2 can still hold 1, 5, or 6 by the cell-side view, so it is not a naked single at this moment, yet the unit-side view forces it anyway. > 💡 **Key point**: naked and hidden singles are the same fact seen from two sides. A naked single says "this cell has only one digit left." A hidden single says "this digit has only one cell left in this unit." Each is a proof that a placement is forced. Hidden singles work in rows and columns too. The question is always the same: in this unit, does the digit have exactly one place left? ## A scanning routine Random staring wastes time. Here is a routine that finds singles in order: 1. **Pick a digit, most frequent first.** A digit that already appears many times has blocked a lot of cells, so its map is nearly closed. In this puzzle 7 appears seven times and 8 appears once, so 7 is the best place to start. 2. **Check each box for that digit.** Trace the placed digit's row and column through the grid mentally, then count the open cells per box. One open cell is a hidden single. 3. **Repeat for rows and columns** of that digit, then move to the next digit. 4. **Look for naked singles** at the end of the pass, especially in rows or columns that are nearly full. 5. **After every placement, scan again.** Each new digit blocks 20 cells, so new singles appear. Experienced solvers call the digit-by-digit pass **cross-hatching**, because the blocked rows and columns make a hatch pattern across the grid. When a unit has eight cells filled, the ninth is a naked single: the one missing digit. Late in a puzzle this happens constantly. ## Your turn: find the forced digit Try the first with the cell-side view, the second with the digit-side view. The map below shows where a 7 can still go. ```exercise [ { "type": "predict", "task": "In the puzzle above, what digit must go in R1C6? (Check row 1, column 6, and box 2 for what is already used.)", "accept": ["8"], "hint": "Row 1 holds 7, 3, 2. Column 6 holds 7, 6, 9, 5, 4, 1. Box 2 holds 7, 1, 6. Which digit from 1 to 9 is missing from all of that?" } ] ``` ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . . 7 | . . . | . . . | 2 | . . . | . . 7 | . . . | 3 | . . . | . . . | . 7 . | +-------+-------+-------+ 4 | . . . | . . . | . . 7 | 5 | o . . | o . . | . . . | 6 | . . . | o . . | . . . | +-------+-------+-------+ 7 | . 7 . | . . . | . . . | 8 | . . . | . 7 . | . . . | 9 | . . . | . . . | 7 . . | +-------+-------+-------+ ``` ```exercise [ { "type": "predict", "task": "In the map of 7s above, box 4 (rows 4 to 6, columns 1 to 3) has exactly one open cell for 7. Which cell is it? Answer in RxCy form, like R2C5.", "accept": ["R5C1"], "hint": "Find the single o inside the left-middle block of the map." } ] ``` That is a hidden single, and it is placed with no pencil marks at all. When you have a spare minute, [play Sudoku](/games/sudoku) and pay attention to which of the two views you reach for first. Many beginners default to the naked-single view, so the hidden-single view is worth practicing on purpose. ## What singles cannot do Eventually you reach a position where no cell has one digit left and no digit has one place left in any unit. This is the wall. Nothing is wrong with the puzzle: a valid puzzle always has a reason for the next digit, but the reason is no longer a single. To find it you need to write down what is still possible in each cell, which is the subject of the next phase. Check yourself before moving on: ```quiz [ { "q": "Which of these describes a naked single?", "choices": [ "A digit that can go in only one cell of a row, column, or box", "A cell that has only one digit it can hold after its peers are considered", "A cell with no neighbors" ], "answer": 1, "explain": "The first choice describes a hidden single. A naked single is about the cell's own short list of digits." }, { "q": "In a box, the digit 4 is blocked in eight cells by 4s elsewhere or by filled cells. The ninth cell is empty and could hold 2, 4, or 9. What do you do?", "choices": [ "Nothing: the cell has three candidates, so you must guess", "Place a 4: the box needs a 4 and this is the only cell left for it", "Place a 9: it is the largest candidate" ], "answer": 1, "explain": "This is a hidden single. Box membership forces a 4 somewhere in the box, and only this cell remains. Sizes of digits never matter." } ] ``` ## Recap 1. A deduction either places a digit or removes a possibility; a single places one. 2. Naked single: a cell with only one digit left after removing its peers' digits. 3. Hidden single: a digit with only one cell left in a row, column, or box, even if that cell has other candidates. 4. Scan digit by digit, most frequent first, and rescan after every placement. 5. When no single exists, you need to track possibilities explicitly. Next up, [Pencil Marks, Pairs, and Locked Candidates](03-pencil-marks-pairs-and-locked-candidates.md): writing the possibilities down and removing them with patterns. --- # Pencil Marks, Pairs, and Locked Candidates You scanned for singles and found none. The puzzle is not stuck; you are, because singles only look at what is certain. The next level uses what is *possible*. You write the remaining digits a cell could hold in small print, and then use patterns to cross digits out. When enough digits disappear, a single appears. This phase has five patterns (naked pairs and triples, hidden pairs, pointing, and box-line reduction), and every one is a short argument you can check yourself. ## Candidates and pencil marks A **candidate** is a digit that could still go in an empty cell without breaking the rule today. The small digits people write in a cell's corner are **pencil marks**, and a puzzle's full set of pencil marks is its candidate grid. Computing a cell's candidates is the naked-single subtraction from phase 2 without stopping at one: nine digits, minus the digits of its 20 peers. Two ideas run through the rest of this guide: - **Candidates only ever shrink.** A digit gets removed when a deduction proves the cell cannot hold it, and once removed it stays removed. When a cell reaches one candidate, it is a naked single. When a digit has one cell left in a unit, it is a hidden single. - **Every technique is a rule for deleting candidates.** A technique says: "if the board looks like this, then these specific candidates are impossible." Each one comes with a proof, and the proof is the reason it is safe. Two habits keep the marks useful. Update them: when you place a digit, erase it from the marks of all 20 peers. And never delete a mark without a reason. A mark erased by a hunch is the quickest way to wreck a solve, because the wrong deletion can force a wrong digit twenty moves later. On the site, [play Sudoku](/games/sudoku) has a notes mode, so you can practice the marking style there. Below we read candidates off one row or one box at a time. You never need to write the whole grid to use these patterns; you only need the unit in question. ## Naked pair Here is a puzzle with a row that has only four empty cells. ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 8 . 1 | . 9 4 | 6 . . | 2 | . . . | . . . | . . 2 | 3 | . . . | . . . | 5 . . | +-------+-------+-------+ 4 | . 9 . | . 5 . | . . 8 | 5 | 1 . 7 | . . . | . . . | 6 | . . 2 | 1 6 . | 7 . 9 | +-------+-------+-------+ 7 | . . . | 7 1 . | 8 . . | 8 | . . 8 | . . . | 4 . . | 9 | 2 . . | 5 . . | . 6 . | +-------+-------+-------+ ``` Row 1 holds 8, 1, 9, 4, 6, so the missing digits are 2, 3, 5, 7. The candidates of the four empty cells, worked out from the whole grid: ```text R1C2: 2 3 5 7 R1C4: 2 3 R1C8: 3 7 R1C9: 3 7 ``` Look at R1C8 and R1C9. Each can only be 3 or 7. Two cells, two digits. One of them is 3 and the other is 7, though we do not know which way around. Either way, those two cells use up both the 3 and the 7 for row 1. So no other cell in row 1 can be 3 or 7. That is a **naked pair**, and it deletes candidates: ```text R1C2: 2 3 5 7 becomes 2 5 R1C4: 2 3 becomes 2 ``` R1C4 now has one candidate. It is a naked single: **R1C4 is 2**. Then R1C2 loses its 2 as well, so R1C2 must be 5. One pattern made the whole row fall. *What just happened:* nothing was guessed. The pair is a pigeonhole argument: two cells that can only hold the same two digits must hold exactly those two digits. ## Naked triple The same argument works for three cells and three digits, with one twist: the three cells do not each need to contain all three digits. Only their combined candidates matter. ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . . . | 6 3 5 | 9 . . | 2 | . 5 9 | . . . | . 6 7 | 3 | . . . | . . . | 3 4 . | +-------+-------+-------+ 4 | . 4 . | 2 . . | . . . | 5 | 5 . . | . . . | . . . | 6 | . . 6 | . . 8 | 2 7 . | +-------+-------+-------+ 7 | 8 . . | 7 . . | . . 4 | 8 | . . 3 | 1 2 . | . . . | 9 | . 6 . | . 8 . | . . . | +-------+-------+-------+ ``` Row 2 has five empty cells. Their candidates: ```text R2C1: 1 2 3 4 R2C4: 4 8 R2C5: 1 4 R2C6: 1 2 4 R2C7: 1 8 ``` Take R2C4, R2C5, and R2C7. Together their candidates are 1, 4, 8. Three cells, three digits in total, so those three cells hold 1, 4, and 8 in some order. Then 1, 4, and 8 cannot appear anywhere else in row 2. R2C1 loses 1 and 4, and R2C6 loses 1 and 4: ```text R2C1: 1 2 3 4 becomes 2 3 R2C6: 1 2 4 becomes 2 ``` R2C6 is a naked single: it is 2. The rule behind every naked subset is the same: **n cells whose candidates together use only n digits own those digits.** (A naked quad is the same with four. Pairs and triples are the ones you will use.) ## Hidden pair A naked subset looks at cells with short lists. A **hidden subset** looks at digits with short lists. Here is a row of a different puzzle: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . 7 . | . . 3 | 1 . . | 2 | 3 4 . | 8 . . | . 5 9 | 3 | . 9 . | . . . | 2 . . | +-------+-------+-------+ 4 | . . . | . . 5 | . . 7 | 5 | . . 3 | . 4 2 | . . . | 6 | . . . | 3 . . | 6 . . | +-------+-------+-------+ 7 | 5 . . | . . . | . 6 4 | 8 | . . . | . 5 4 | . . 1 | 9 | 9 6 . | . . . | . . . | +-------+-------+-------+ ``` Row 5 has six empty cells, with these candidates: ```text R5C1: 1 6 7 8 R5C2: 1 5 8 R5C4: 1 6 7 9 R5C7: 5 8 9 R5C8: 1 8 9 R5C9: 5 8 ``` Where can 6 go in this row? Only R5C1 and R5C4. Where can 7 go? Also only R5C1 and R5C4. Two digits and exactly two cells. Both cells must hold those digits, one each, so every other candidate in those two cells is impossible: ```text R5C1: 1 6 7 8 becomes 6 7 R5C4: 1 6 7 9 becomes 6 7 ``` That is a **hidden pair**: the pair of digits is hidden among extra candidates, and the deduction is deleting the extras. The cells are left as a naked pair, which is handy for what comes next. There is a symmetry here worth seeing. In a unit with six empty cells, a hidden pair is the same fact as a naked quad in the other four cells: in row 5, R5C2, R5C7, R5C8, and R5C9 together use only 1, 5, 8, 9. Four cells, four digits. Same deletions, seen from the other side. Pick whichever view is quicker to spot. > ⚠️ **Gotcha**: each of the two digits must have at least two possible cells in the unit, and both digits must be confined to the same two cells. If one digit has only a single possible cell, you have a hidden single instead, which settles that cell outright. ## Pointing Now we use boxes and lines together. Look at the center box of this position and only the digit 8. The map shows `o` where an 8 could still go: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | o o o | o o . | . . . | 2 | . . . | . . . | . . 8 | 3 | . o o | o o . | . . . | +-------+-------+-------+ 4 | o . o | . o . | . . . | 5 | . . . | . . . | . 8 . | 6 | o o o | . o . | . . . | +-------+-------+-------+ 7 | o . o | . . . | o . . | 8 | o o . | . . . | . . . | 9 | . . . | . . 8 | . . . | +-------+-------+-------+ ``` Inside box 5 (rows 4 to 6, columns 4 to 6) there are two open cells for an 8: R4C5 and R6C5. Both are in column 5. The box must contain exactly one 8, so the box's 8 will be in column 5, in one of those two cells. That means column 5 gets its 8 inside box 5, and no other cell of column 5 can be 8. The `o` marks at R1C5 and R3C5 are impossible and can be removed. This is **pointing** (also called a pointing pair, or a pointing triple when three cells line up): all candidates for a digit in a box lie in one row or column, so that digit is removed from the rest of that line outside the box. Think of the candidates in the box as pointing outward along their line. Another name is locked candidates, type 1. ## Box-line reduction (claiming) Pointing runs from box to line. **Box-line reduction** runs the other way, from line to box. Here is the digit 5 in a puzzle where column 4 has only a few places left for it: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . . 5 | . . . | . . . | 2 | . . . | . . o | . . . | 3 | . . . | . . . | 5 . . | +-------+-------+-------+ 4 | o . . | . . . | . o o | 5 | . . . | . 5 . | . . . | 6 | . o . | . . . | . o o | +-------+-------+-------+ 7 | o . . | o . o | . . . | 8 | o o . | o . o | . o o | 9 | . o . | o . o | . o o | +-------+-------+-------+ ``` In column 4, an open cell for 5 appears only at R7C4, R8C4, and R9C4. All three are in box 8 (rows 7 to 9, columns 4 to 6). Column 4 must have a 5, so the 5 for column 4 is in box 8, and therefore box 8's own 5 is in column 4 as well. No other cell of box 8 can be 5: R7C6, R8C6, and R9C6 lose their 5. This is **box-line reduction**, also called **claiming** (the line claims the digit for the box), or locked candidates type 2. The two are mirror images: | Name | The digit's candidates in one unit lie within... | So remove the digit from... | |---|---|---| | Pointing | one line, inside a box | the rest of that line, outside the box | | Box-line reduction | one box, inside a line | the rest of that box, outside the line | Both patterns exist because a row (or column) and a box overlap in three cells, and a digit placed in the overlap serves both units at once. ## Your turn: finish the row Back in the first puzzle, you already found one forced digit from the naked pair. Use the results. ```exercise [ { "type": "predict", "task": "In the naked-pair row (row 1 of the first puzzle in this phase), after the pair removes 3 and 7 from the other cells, which digit goes in R1C4?", "accept": ["2"], "hint": "R1C4 started with candidates 2 and 3. What is left after 3 is removed?" }, { "type": "predict", "task": "Once R1C4 is 2, which digit goes in R1C2? (Its candidates after the pair were 2 and 5.)", "accept": ["5"], "hint": "R1C4 and R1C2 are in the same row, so they cannot both be 2." } ] ``` Check yourself before moving on: ```quiz [ { "q": "Two cells in a row both have only the candidates 2 and 5. A third cell in that row has candidates 2, 5, and 8. What can you conclude?", "choices": ["The third cell is 8, because 2 and 5 are used up by the pair", "The third cell could be 2, 5, or 8; nothing can be removed", "The third cell is 2"], "answer": 0, "explain": "This is a naked pair: the two cells use up 2 and 5 in the row, so the third cell loses both and is left with 8." }, { "q": "In a box, every remaining candidate for the digit 6 lies in the same column. What can you remove?", "choices": ["6 from every other cell of that box", "6 from the cells of that column that are outside the box", "6 from the whole grid"], "answer": 1, "explain": "This is pointing. The box's 6 must be in that column, so that column's 6 is inside the box and cannot appear outside it." }, { "q": "Two cells in a unit are the only places for 3 and for 6 in that unit, and they also have other candidates. What do you do?", "choices": ["Remove 3 and 6 from the two cells", "Remove every candidate except 3 and 6 from the two cells", "Nothing, because the cells have extra candidates"], "answer": 1, "explain": "This is a hidden pair. Two digits and exactly two cells for them means the cells hold those digits, so all their other candidates go." } ] ``` ## Recap 1. Candidates are the digits a cell could still hold; pencil marks write them down, and they only shrink. 2. Naked pair or triple: n cells whose candidates together use only n digits own those digits, so remove them from the rest of the unit. 3. Hidden pair: two digits confined to the same two cells in a unit force those cells to hold them, so remove every other candidate there. 4. Pointing: a box's candidates for a digit all lie on one line, so remove the digit from that line outside the box. 5. Box-line reduction: a line's candidates for a digit all lie in one box, so remove the digit from the rest of that box. Next up, [Fish and Wings: Advanced Patterns](04-fish-and-wings-advanced-patterns.md): patterns that span several units at once. --- # Fish and Wings: Advanced Patterns Pairs and pointing look inside one or two units at a time. The patterns in this phase look across several, and that is why they feel like magic until you see the argument. They are not magic. Each one is a pigeonhole argument or a two-case argument, and once you can state the argument, you can rebuild the pattern from memory instead of memorizing its shape. You need pencil marks for these (phase 3). The examples show one digit at a time, with `o` marking where that digit can still go. ## Fish: one digit, a few rows, a few columns Start with a fact about a single digit. In a solved grid, the digit 7 appears exactly once in every row and exactly once in every column. Now suppose two rows each have only two possible cells for a 7, and both rows use the same two columns. Call the rows A and B and the columns X and Y. Row A's 7 is in X or in Y. Row B's 7 is in X or in Y. They cannot both be in X, because that would put two 7s in one column. So they are in different columns, which means the two rows between them supply a 7 to column X **and** a 7 to column Y. Either: ```text X Y X Y A 7 . or . 7 B . 7 7 . ``` In both cases, columns X and Y already have their 7 from rows A and B. No other cell in column X or column Y can be 7. That is an **X-Wing**. It is the smallest member of a family called **fish**. The two rows are the **base** (where the digit must be placed) and the two columns are the **cover** (where all the base's candidates sit). The elimination rule is the same for every fish: **if the base rows' candidates for a digit all lie inside the cover columns, remove the digit from every other cell in the cover columns.** Rows and columns swap roles freely, so a fish can also have columns as the base. ## An X-Wing in a real puzzle ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 1 . . | . . . | 5 6 9 | 2 | 4 9 2 | . 5 6 | 1 . 8 | 3 | . 5 6 | 1 . 9 | 2 4 . | +-------+-------+-------+ 4 | . . 9 | 6 4 . | 8 . 1 | 5 | . 6 4 | . 1 . | . . . | 6 | 2 1 8 | . 3 5 | 6 . 4 | +-------+-------+-------+ 7 | . 4 . | 5 . . | . 1 6 | 8 | 9 . 5 | . 6 1 | 4 . 2 | 9 | 6 2 1 | . . . | . . 5 | +-------+-------+-------+ ``` The digit 7 appears nowhere among the givens, so every empty cell is still a candidate for 7 for now. Here is the map: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | . o o | o o o | . . . | 2 | . . . | o . . | . o . | 3 | o . . | . o . | . . o | +-------+-------+-------+ 4 | o o . | . . o | . o . | 5 | o . . | o . o | o o o | 6 | . . . | o . . | . o . | +-------+-------+-------+ 7 | o . o | . o o | o . . | 8 | . o . | o . . | . o . | 9 | . . . | o o o | o o . | +-------+-------+-------+ ``` Row 2 has empty cells at C4 and C8 only. Row 6 has empty cells at C4 and C8 only. Same two rows, same two columns: R2C4, R2C8, R6C4, R6C8 form the X-Wing. Row 2's 7 and row 6's 7 are in columns 4 and 8 between them, so columns 4 and 8 have no room left for any other 7. Eight candidates disappear in one deduction: 7 is removed from R1C4, R5C4, R8C4, R9C4 (column 4) and from R4C8, R5C8, R8C8, R9C8 (column 8). Every one of those is an empty cell that still carried a 7 in its pencil marks. *What just happened:* you proved that 7 cannot be in eight cells without finding where 7 goes in any of the corner cells. That is the typical shape of a fish: it deletes candidates and leaves the digit's final position to later steps. ## Swordfish: the same idea with three Replace "two rows and two columns" with "three rows and three columns". Each of three rows has two or three candidates for a digit, and all of those candidates sit inside the same three columns. Three rows need three different columns for their three 7s (or 8s, or whatever the digit is), so the three columns' digit is all spoken for. Anything else in those columns goes. That is a **Swordfish**. (Four of each is a Jellyfish, and the rule is the same.) The rows do not each need all three columns. Here is the digit 8 in another puzzle: ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 8 . . | . 2 . | . . 6 | 2 | . . . | 1 . . | . . . | 3 | 1 . . | 3 . . | 9 . 7 | +-------+-------+-------+ 4 | 3 . . | . . . | 5 . . | 5 | . 7 . | 9 8 . | 2 . . | 6 | . . . | . 7 . | . . 8 | +-------+-------+-------+ 7 | . 6 . | 8 . 9 | . . . | 8 | . . . | . . . | . 3 . | 9 | . 3 . | 7 . 6 | . 2 . | +-------+-------+-------+ ``` ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 8 . . | . . . | . . . | 2 | . . . | . . o | o o . | 3 | . . . | . . o | . o . | +-------+-------+-------+ 4 | . o o | . . . | . . . | 5 | . . . | . 8 . | . . . | 6 | . . . | . . . | . . 8 | +-------+-------+-------+ 7 | . . . | 8 . . | . . . | 8 | . o o | . . . | o . . | 9 | . . o | . . . | o . . | +-------+-------+-------+ ``` Look at the rows with candidates for 8: ```text R4: C2, C3 R8: C2, C3, C7 R9: C3, C7 ``` All the candidates in rows 4, 8, and 9 sit in columns 2, 3, and 7. Rows 4, 8, and 9 must each place one 8, in three different columns, and there are only three columns to choose from. So columns 2, 3, and 7 get their 8 from these three rows. The map shows one other 8 candidate in those columns, at R2C7, and it is eliminated: **R2C7 is not 8**. > 💡 **Key point**: every fish is the pigeonhole principle. n rows, each needing a distinct column from a set of n columns, use up all n columns. The rest of the pattern is bookkeeping. ## XY-Wing: a two-case argument across three cells Fish work with one digit. **XY-Wing** works with three cells and three digits. It uses a different kind of reasoning: split into the two possibilities for one cell and see what both lead to. The pattern has three cells, each with exactly two candidates: - The **pivot** has candidates X and Y. - One **pincer** sees the pivot and has candidates X and Z. - The other **pincer** sees the pivot and has candidates Y and Z. The rule: **Z can be removed from any cell that sees both pincers.** Here it is in a real position. ```text 1 2 3 4 5 6 7 8 9 +-------+-------+-------+ 1 | 4 . . | 3 . 9 | 2 . 8 | 2 | . . . | . . . | . . 6 | 3 | . . . | 7 6 8 | 5 . . | +-------+-------+-------+ 4 | 1 4 . | . . . | . . . | 5 | 5 . . | . . . | . . . | 6 | . 8 6 | 9 . . | . . 4 | +-------+-------+-------+ 7 | . . 8 | 4 . 3 | . 5 . | 8 | 6 . . | . 9 1 | . 2 . | 9 | . . . | 8 . . | . . 9 | +-------+-------+-------+ ``` The three cells: ```text R3C9 (pivot): 1 3 R1C8 (pincer): 1 7 R8C9 (pincer): 3 7 ``` R3C9 sees R1C8 (they share box 3) and sees R8C9 (they share column 9). The pivot is 1 or 3, and there are no other possibilities. Take each case: ```mermaid flowchart TD P["R3C9 is 1 or 3"] -->|"if 1"| A["R1C8 cannot be 1, so it is 7"] P -->|"if 3"| B["R8C9 cannot be 3, so it is 7"] A --> V["A 7 sits in R1C8 or R8C9"] B --> V V --> T["R9C8 sees both, so it cannot be 7"] ``` If the pivot is 1, the pincer R1C8 loses its 1 (it sees the pivot), leaving 7. If the pivot is 3, the pincer R8C9 loses its 3, leaving 7. Either way, one of the two pincers is 7, and we do not need to know which. Now find a cell that sees both pincers: R9C8 shares column 8 with R1C8 and box 9 with R8C9. It cannot be 7 in either case, and R9C8 had 1, 3, 4, 6, 7 as candidates, so **R9C8 is not 7**. *What just happened:* a proof by cases. When two cases force the same conclusion, the conclusion is true no matter which case holds. You never learned the pivot's value. ## Finding them, and what lies beyond Fish and wings take practice to spot, and nobody finds them at first glance. A few habits help: - **For fish**, pick one digit and list, for each row, where it can go. Look for two rows with the same two positions (X-Wing) or three rows whose positions union to three columns (Swordfish). Then repeat with columns as the base. - **For XY-Wing**, start from cells with exactly two candidates, called bivalue cells. Pick one as the pivot (candidates X and Y), then look for two cells that both see it: one with candidates X and Z, the other with Y and Z, where Z is a third digit. - **Do every simpler technique first.** Singles, pairs, and pointing delete candidates cheaply, and each deletion can turn a hard pattern into a plain single. These are the named patterns in this guide, and plenty of puzzles live past them. Longer chains of two-candidate links, coloring a single digit's links, and larger groups of cells with shared candidates all follow the same style of argument: assume, follow the consequences, and find what both branches share. [HoDoKu's technique pages](https://hodoku.sourceforge.net/en/tech_fishb.php) catalogue them with diagrams if you want to go further. In phase 5 you will see a computer take the same assume-and-follow idea to its extreme. ## Your turn: apply a fish ```exercise [ { "type": "predict", "task": "In the Swordfish example (the puzzle for the digit 8), which cell loses its candidate 8? Answer in RxCy form, like R2C5.", "accept": ["R2C7"], "hint": "Find the 8-candidate in columns 2, 3, or 7 that is not in rows 4, 8, or 9." } ] ``` Check yourself before moving on: ```quiz [ { "q": "In an X-Wing, a digit has exactly two candidate cells in row 2, in columns 3 and 7, and exactly two in row 6, also in columns 3 and 7. What can you remove?", "choices": [ "The digit from other cells in rows 2 and 6", "The digit from other cells in columns 3 and 7, outside rows 2 and 6", "All other candidates from the four corner cells" ], "answer": 1, "explain": "Rows 2 and 6 between them place the digit in columns 3 and 7, so those columns have no room for it elsewhere. Rows 2 and 6 are the base, and the elimination goes into the cover columns." }, { "q": "An XY-Wing has pivot 4 6, one pincer 4 9, and the other pincer 6 9. Which candidate can be removed, and from where?", "choices": [ "9, from any cell that sees both pincers", "4, from any cell that sees both pincers", "9, from the pivot" ], "answer": 0, "explain": "If the pivot is 4, the first pincer cannot be 4, so it is 9. If the pivot is 6, the second pincer cannot be 6, so it is 9. A 9 sits in one of the pincers in both cases, so any cell seeing both cannot be 9." }, { "q": "Why does a Swordfish on rows work?", "choices": [ "Three rows must each place the digit in a different column, and all their candidates sit in only three columns, so those columns are used up", "Three rows always hold the same digits as three columns", "Three rows are the same as one box" ], "answer": 0, "explain": "It is the pigeonhole principle: three rows, three columns available, each row needs a distinct column, so every one of the three columns gets its digit from these rows." } ] ``` ## Recap 1. A fish (X-Wing is size 2, Swordfish size 3, Jellyfish size 4) is n rows whose candidates for a digit all lie in the same n columns; remove the digit from the rest of those columns. 2. The reason is the pigeonhole principle: n rows need n different columns, so the columns are all used. 3. An XY-Wing is a pivot X Y with pincers X Z and Y Z; Z is removed from any cell that sees both pincers. 4. The reason is a proof by cases: both possibilities for the pivot place a Z in a pincer. 5. Use simpler techniques first; each of these patterns deletes candidates, and the placements follow later. Next up, [How a Computer Solves Sudoku](05-how-a-computer-solves-sudoku.md): what it takes to teach a machine all of this, and how it can skip most of it. --- # How a Computer Solves Sudoku A person solves Sudoku by recognizing patterns, which took four phases to teach. A computer recognizes nothing. It also needs no patterns, because it has two things people lack: it never tires of trying options, and it can undo a wrong choice without embarrassment. This phase builds a complete solver in about 100 lines, in the order the ideas appear: first brute force, then the technique from phase 2 turned into code, then the one heuristic that makes the search fast. ## Sudoku as a constraint problem To a program, Sudoku is a **constraint satisfaction problem**: 81 variables (the cells), each choosing a value from 1 to 9, under 27 constraints, each saying "the nine cells in this unit are all different". Another view: draw a dot for each cell and a line between every pair of peers. Each cell has 20 lines. A solution gives each dot a digit so that no two connected dots share one. That is a graph coloring with nine colors; [Graph Theory: What's Connected to What](/guides/graph-theory-whats-connected-to-what) introduces the vocabulary. In code, number the cells 0 to 80, build a list of the 27 units, and give every cell a set of its 20 peers. From that, a cell's options are the naked-single subtraction from phase 2: all digits, minus the digits of its peers. ## Backtracking: try, check, undo **Backtracking** is a search that builds an answer one choice at a time and abandons any partial answer that already breaks a rule. For Sudoku: 1. Find an empty cell. 2. For each digit that fits (does not clash with a peer), place it and solve the rest recursively. 3. If the rest cannot be solved, remove the digit and try the next one. 4. If no digit fits, return failure so the previous cell tries something else. The "undo" is the key. Each recursive call is a guess, and a failed call retracts it. This is the recursion pattern from [Recursion Finally Clicks](/guides/recursion-finally-clicks), with the base case "no empty cells left". It always finds a solution if one exists, since it eventually tries every possibility that does not break a rule. The weakness is blindness. Plain backtracking fills cells in reading order and has no sense that cell 40 is nearly forced while cell 1 has seven options. It wastes effort deep in a branch that was doomed several levels up. That is where the human techniques come back. ## Constraint propagation: the singles, automated **Constraint propagation** means using the rules to shrink possibilities *before* guessing. Our solver applies two rules repeatedly until nothing changes: - If a cell has only one option, place it (a naked single). - If a digit fits in only one cell of a unit, place it there (a hidden single). Each placement can create the next one, exactly the cascade you saw in phase 2. A cell with *zero* options, or a digit with nowhere to go, is a contradiction, and the solver reports failure at once instead of wandering further. Peter Norvig's well-known essay [Solving Every Sudoku Puzzle](https://norvig.com/sudoku.html) uses these same two rules plus search. ## Smart guessing: fewest options first When propagation stalls, the solver must guess. The best place to guess is the empty cell with the **fewest options**, a heuristic called minimum remaining values. A cell with two options means one guess in two is right, and a wrong guess tends to contradict quickly. A cell with seven options is a poor bet. Choosing the most constrained cell makes failures appear early, which prunes whole branches. It is the program's version of "pick the best lead". ## The solver Run it. It solves two puzzles with two strategies each and counts the **search calls** (each call is one guess or one starting attempt), so you can see the difference. The second puzzle is a famously hard one for people. Then it prints the solved first puzzle. ```python runnable PUZZLE = "..7...32.8.2..71..94.1.6.75.....9247.........1....56...7.6.....5...74.3.4..5.176." HARD = "8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.." # Cells are numbered 0..80, row by row. A unit is a row, column, or box. UNITS = [] for r in range(9): UNITS.append([r * 9 + c for c in range(9)]) for c in range(9): UNITS.append([r * 9 + c for r in range(9)]) for br in (0, 3, 6): for bc in (0, 3, 6): UNITS.append([(br + i) * 9 + bc + j for i in range(3) for j in range(3)]) PEERS = [set() for _ in range(81)] for unit in UNITS: for cell in unit: PEERS[cell] |= set(unit) - {cell} def options(grid, cell): """Digits that do not clash with anything the cell can see.""" return set(range(1, 10)) - {grid[p] for p in PEERS[cell]} def parse(text): return [0 if ch == "." else int(ch) for ch in text] def show(grid): for r in range(9): if r in (3, 6): print("------+-------+------") row = grid[r * 9:(r + 1) * 9] print(" ".join(str(v) if v else "." for v in row[:3]), "|", " ".join(str(v) if v else "." for v in row[3:6]), "|", " ".join(str(v) if v else "." for v in row[6:])) # 1. Plain backtracking: take the first empty cell, try every digit that fits. def solve_plain(grid, stats): stats["tries"] += 1 if 0 not in grid: return True cell = grid.index(0) for d in sorted(options(grid, cell)): grid[cell] = d if solve_plain(grid, stats): return True grid[cell] = 0 return False # 2. Constraint propagation: keep filling forced cells (naked and hidden singles). def propagate(grid): changed = True while changed: changed = False for cell in range(81): if grid[cell] == 0: opts = options(grid, cell) if not opts: return False # contradiction: a cell with no digit left if len(opts) == 1: grid[cell] = opts.pop() changed = True for unit in UNITS: for d in range(1, 10): if any(grid[c] == d for c in unit): continue spots = [c for c in unit if grid[c] == 0 and d in options(grid, c)] if not spots: return False # contradiction: a digit with no home if len(spots) == 1: grid[spots[0]] = d changed = True return True # 3. Propagate, then guess in the cell with the fewest options, and recurse. def solve_smart(grid, stats): stats["tries"] += 1 if not propagate(grid): return False if 0 not in grid: return True cell = min((c for c in range(81) if grid[c] == 0), key=lambda c: len(options(grid, c))) for d in sorted(options(grid, cell)): trial = grid[:] trial[cell] = d if solve_smart(trial, stats): grid[:] = trial return True return False for label, text in (("PUZZLE", PUZZLE), ("HARD", HARD)): for name, solver in (("plain backtracking", solve_plain), ("propagation + smart guess", solve_smart)): grid = parse(text) stats = {"tries": 0} solver(grid, stats) print(f"{label:6} {name:26} search calls: {stats['tries']}") solution = parse(PUZZLE) solve_smart(solution, {"tries": 0}) print() show(solution) ``` Here is the output this produces (the counts are deterministic): ```text PUZZLE plain backtracking search calls: 282 PUZZLE propagation + smart guess search calls: 1 HARD plain backtracking search calls: 49559 HARD propagation + smart guess search calls: 173 6 1 7 | 9 5 8 | 3 2 4 8 5 2 | 3 4 7 | 1 9 6 9 4 3 | 1 2 6 | 8 7 5 ------+-------+------ 3 6 5 | 8 1 9 | 2 4 7 7 9 8 | 4 6 2 | 5 1 3 1 2 4 | 7 3 5 | 6 8 9 ------+-------+------ 2 7 1 | 6 9 3 | 4 5 8 5 8 6 | 2 7 4 | 9 3 1 4 3 9 | 5 8 1 | 7 6 2 ``` Read the numbers. On the first puzzle, which is a singles puzzle from phase 2, propagation alone solves it: one call, zero guesses. Plain backtracking needs 282 calls. On the hard puzzle, where people need real technique, plain backtracking makes nearly fifty thousand calls, and propagation plus smart guessing needs 173. The counts show how much structure the rules carry. ## Proving there is exactly one solution A solver can also answer the question from phase 1. Do not stop at the first solution. Keep searching, and if the search finds a second complete grid, the puzzle has two solutions and is not valid. If the search ends with exactly one, the puzzle is unique. One common way for a puzzle generator to stay valid is to remove digits from a finished grid one at a time: erase a cell, count solutions, and put the digit back if the count goes above one. ## Where this leads Backtracking is one idea at two scales. Here the search tree branches on "which digit goes in this cell", and constraints prune it. In chess and checkers the tree branches on "which move do I make", an opponent replies, and pruning needs more care. [How Computers Play Games](/guides/how-computers-play-games) picks up the same thread. The jump from "try, check, undo" to "think about the opponent's best reply" is where game AI begins. ## Your turn: count the solutions ```exercise [ { "type": "task", "task": "Change the solver so it counts the solutions of a puzzle instead of stopping at the first. Test it on a puzzle with a deliberate flaw: remove the digits from R4C1, R4C9, R5C1, and R5C9 of the solved grid above (rows 4 and 5, columns 1 and 9). It should report 2.", "reveal": "Make the recursive function return a count instead of True or False. Where it currently returns True on a full grid, return 1. In the loop over digits, add the result of each recursive call to a running total, and undo the placement (set the cell back to 0) after each digit instead of returning early. Return the total. A cap at 2 saves time, since you only need to know whether the count exceeds 1.", "checklist": ["It still undoes each placement after trying it", "It does not return early on the first full grid", "The deliberate flaw reports 2 solutions", "The original puzzle reports 1"] } ] ``` Check yourself before moving on: ```quiz [ { "q": "A backtracking solver places a digit, recurses, and the recursion fails. What does it do next?", "choices": ["Stops and reports that the puzzle has no solution", "Removes that digit and tries the next option for the same cell", "Restarts from the first cell"], "answer": 1, "explain": "A failed recursion means that guess was wrong, so the solver retracts it and tries the next digit. Only when every digit fails does the failure travel up to the previous cell." }, { "q": "Why does the solver guess in the empty cell with the fewest options?", "choices": ["Because that cell is always correct", "Because a wrong guess there contradicts quickly, which prunes branches early", "Because it is the first cell in reading order"], "answer": 1, "explain": "Fewer options means fewer branches and a higher chance of a right guess, and a wrong guess fails fast. Nothing guarantees the first guess is right, but search recovers if it is not." }, { "q": "How can a program verify that a puzzle has exactly one solution?", "choices": ["Keep searching after the first solution; if no second grid is found, it is unique", "Check that the puzzle has at least 17 givens", "Solve it with only naked and hidden singles"], "answer": 0, "explain": "Uniqueness means no second grid exists, so you have to search past the first. Having 17 givens does not guarantee uniqueness, and a puzzle may be unique but need techniques beyond singles." } ] ``` ## Recap 1. Sudoku is a constraint satisfaction problem: 81 cells, values 1 to 9, 27 all-different constraints; it is also coloring a 20-neighbor graph with nine colors. 2. Backtracking tries a digit, recurses, and undoes it on failure; it always finds a solution but can waste huge effort. 3. Constraint propagation applies naked and hidden singles automatically and detects contradictions early. 4. Guessing in the cell with the fewest options keeps the search small. 5. Searching past the first solution is how a program checks that a puzzle is unique. Next up, to put a clock and an opponent into the search idea, read [How Computers Play Games](/guides/how-computers-play-games), or return to [play Sudoku](/games/sudoku) and try each phase's technique on a fresh puzzle.