Jason Rosenhouse - Taking Sudoku Seriously: The Math Behind the Worlds Most Popular Pencil Puzzle

Taking Sudoku Seriously

The Math Behind the Worlds
Most Popular Pencil Puzzle

JASON ROSENHOUSE
AND
LAURA TAALMAN

Oxford University Press, Inc., publishes works that further
Oxford Universitys objective of excellence
in research, scholarship, and education.

Oxford New York
Auckland Cape Town Dar es Salaam Hong Kong Karachi
Kuala Lumpur Madrid Melbourne Mexico City Nairobi
New Delhi Shanghai Taipei Toronto

With offices in
Argentina Austria Brazil Chile Czech Republic France Greece
Guatemala Hungary Italy Japan Poland Portugal Singapore
South Korea Switzerland Thailand Turkey Ukraine Vietnam

Copyright 2011 by Oxford University Press

Published by Oxford University Press, Inc.
198 Madison Avenue, New York, New York 10016
www.oup.com

Oxford is a registered trademark of Oxford University Press

All rights reserved. No part of this publication may be reproduced,
stored in a retrieval system, or transmitted, in any form or by any means,
electronic, mechanical, photocopying, recording, or otherwise,
without the prior permission of Oxford University Press.

Library of Congress Cataloging-in-Publication Data

Rosenhouse, Jason.
Taking sudoku seriously: the math behind the worlds most popular pencil puzzle /
Jason Rosenhouse and Laura Taalman.
p. cm.
Includes bibliographical references.
ISBN 978-0-19-975656-8
1. Sudoku. 2. MathematicsSocial aspects. I. Taalman, Laura. II. Title
GV1507.S83R67 2012
793.74dc22 2011003188

9 8 7 6 5 4 3 2 1

Printed in China on acid-free paper

In memory of Martin Gardner, who showed a generation of mathematicians
the value of puzzles as a gateway into mathematics.

Every math teacher knows the frustration of directing a seemingly simple question to a class and receiving blank stares in return. In part, this reaction can be attributed to general student apathy or to a fear of giving the wrong answer. There is, however, a more fundamental issue to be addressed.

Most people, when asked to describe mathematics, will talk about the tedious algorithms of arithmetic or the seemingly arbitrary rules of algebra. For them it is all about symbol manipulation and mindless computation. This view is entirely understandable given that they probably saw little else in their grade school and high school mathematics classes.

Mathematicians do not recognize their discipline in such descriptions. We see arithmetic and algebra as tools used in doing mathematics, just as hammers and handsaws are tools used in carpentry. For professionals, mathematics is about curiosity, imagination, and solving problems. There are questions that are instinctive and natural for mathematicians that rarely occur to those looking in from the outside. There is such a thing as a mathematical view of the world. Sadly, it is a view that is too often hidden from those struggling to learn the subject.

Which brings us back to the blank stares. Often the problem is simply that mathematicians have a way of expressing themselves that makes little sense to those outside the club. Students unaccustomed to the sorts of questions mathematicians ask, or unaware that mathematics is about asking questions in the first place, will often be confused by questions more experienced people regard as simple. We need first to develop mathematical thinking in our students before we expect them to toss off answers to our questions.

That is where the Sudoku puzzles come in. We can define a Sudoku square as a 9 9 grid in which every row, column, and 3 3 block contains the digits 19 exactly once. A Sudoku puzzle is then a square in which some of the cells have been filled in while others are blank. The goal of the solver is to fill in the blank cells in such a way that the result is a Sudoku square. If the puzzle is sound there will only be one way of doing that.

Here is an example. This is a level 3 puzzle, where level 1 is the easiest and level 5 is the hardest.

Fill in the grid so that each row, column, and block contains each of the numbers 19 exactly once. The solution to this puzzle is at the end of the book.

Over the past five years, Sudoku puzzles have become a mainstay of many newspapers. Such venues are typically careful to assure the reader that, the presence of numbers notwithstanding, Sudoku puzzles are not math problems. They are keen to stress that any collection of nine distinct symbols, such as the first nine letters of the alphabet, would work just as well.

This sort of thing sounds bizarre to a mathematician. In saying that Sudoku does not involve mathematics, the newspaper really means it does not involve arithmetic. The sort of reasoning that goes in to solving a Sudoku puzzle, on the other hand, is at the heart of what mathematics is all about. That so many people will claim to hate doing mathematics while simultaneously enjoying the challenge of solving a puzzle is a source of frustration to those of us in the business.

To a mathematician, Sudoku puzzles immediately suggest a whole host of interesting questions even beyond the reasoning that goes in to solving them. How many Sudoku squares are there? What sorts of transformations can you do to a Sudoku square to produce other such squares? What is the smallest number of initial clues a sound puzzle can have? What is the largest number of initial clues a puzzle can have without having a unique solution? Is it possible to have a Sudoku square in which each 3 3 block is actually a semimagic square (so that the digits in each row and column within the block add up to the same sum)? In attempting to answer these questions we will inevitably encounter a lot of interesting mathematics.

More than that, however, we will use Sudoku puzzles and their variants as a gateway into mathematical thinking generally. This is both a math book and a puzzle book. The puzzles, in addition to being enjoyable simply as stand-alone brainteasers, will serve to complement and introduce the mathematical concepts in the text. Our emphasis throughout is on asking questions and solving problems; technical mathematical machinery will be introduced only as it arises naturally in the course of our reasoning.

We have a number of different audiences in mind. For students in high school or college we intend to provide a view of mathematics that is very different from what is usually presented. It is a far more realistic view than the one implied by years of training in tedious symbol manipulation. For educators we hope to provide some novel ideas for how to bring genuine mathematical thinking into the classroom in a context that will be interesting and accessible to students. For any layperson with a general interest in mathematics, we provide plenty of food for thought and intellectual stimulation. Professional mathematicians can benefit from seeing familiar mathematical abstractions applied in novel settings.

We have assumed little beyond high school mathematics. Indeed, if you flip through the book right now you will notice that for the most part we make limited use of mathematical symbols. Our focus is on ideas and reasoning; notions, not notations, as the saying goes. That is not to say, however, that the book is always easy going. Mathematics takes some getting used to, and you should not be surprised if you have to pause periodically to mull over something we have said. Furthermore, things do get gradually more complex as we go along, and readers without previous mathematical experience might find some of the concluding material a bit more challenging than what came before. Even here, though, we believe we have provided enough commentary to make the central ideas comprehensible to all. In those few cases where we have elected to include some more technical material, the dense calculations can be skimmed over without losing the thread of the discussion.