✳flâneur — a map of the web's best reading

Solving Every Sudoku Puzzle

norvig.com · 5,376 words · saved by 1 readers

Every square has exactly 3 units and 20 peers. For example, here are the units and peers for the square C2: If you are not familiar with some of the features of Python, note that a dict or dictionary is Python's name for a hash table that maps each key to a value; that these are specified as a sequence of (key, value) tuples; that dict((s, [...]) for s in squares) creates a dictionary which maps each square s to a value that is the list [...]; and that the expression [u for u in unitlist if s in u] means that this value is the list of units u such that the square s is a member of u. So read this assignment statement as "units is a dictionary where each square maps to the list of units that contain the square". Similarly, read the next assignment statement as "peers is a dictionary where each square s maps to the set of squares formed by the union of the squares in the units of s, but not s itself". It can't hurt to throw in some tests (they all pass): Now that we have squares, units, a

Solving Every Sudoku Puzzle Solving Every Sudoku Puzzle by Peter Norvig Note: This page is the original 2006 essay; an updated Python 3 Jupyter notebook is available here and should probably be read instead of this page. In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about one page of code for the main idea and two pages for embellishments) using two ideas: constraint propagation and search . Sudoku Notation and Preliminary Notions First we have to agree on some notation. A Sudoku puzzle is a grid of 81 squares; the majority of enthusiasts lab

Explore this link on the map →

related reading