maths.free › Combinatorics & Graph Theory › An Introduction to Combinatorics › Sudoku Puzzles

Sudoku Puzzles

Here's an example which has more substance than you might think at first glance. It involves Sudoku puzzles, which have become immensely popular in recent years.

Sudoku Puzzles

Here's an example which has more substance than you might think at first glance. It involves Sudoku puzzles, which have become immensely popular in recent years.

Example

A Sudoku puzzle is a \(9\times 9\) array of cells that when completed have the integers \(1,2,\dots,9\) appearing exactly once in each row and each column. Also (and this is what makes the puzzles so fascinating), the numbers \(1\), \(2\), \(3,\dots,9\) appear once in each of the nine \(3\times 3\) subsquares identified by the darkened borders. To be considered a legitimate Sudoku puzzle, there should be a unique solution. In , we show two Sudoku puzzles. The one on the right is fairly easy, and the one on the left is far more challenging.

There are many sources of Sudoku puzzles, and software that generates Sudoku puzzles and then allows you to play them with an attractive GUI is available for all operating systems we know anything about (although not recommend to play them during class!). Also, you can find Sudoku puzzles on the web at: . On this site, the Evil ones are just that.

How does Rory make up good Sudoku puzzles, ones that are difficult for Mandy to solve? How could Mandy use a computer to solve puzzles that Rory has constructed? What makes some Sudoku puzzles easy and some of them hard?

The size of a Sudoku puzzle can be expanded in an obvious way, and many newspapers include a \(16\times16\) Sudoku puzzle in their Sunday edition (just next to a challenging crosswords puzzle). How difficult would it be to solve a \(1024\times1024\) Sudoku puzzle, even if you had access to a powerful computer?

Núna ūú Engin reiknivél leysir þetta, en hlutar þess eru reiknanlegir. Prófaðu einn hér fyrir neðan, eða sláðu inn þinn eigin.

Haltu eigin vinnu þinni

Ókeypis reikningur bætir við athugasemdum við hverja kennslustund, skrá yfir það sem þú hefur lokið, leyst vandamál á einum stað og kennari sem þú getur spurt um þessa síðu.Stærðfræðin sjálf er opin öllum, skráður inn eða ekki.

Skráðu þig inn Innskráning

Tákn notuð hér

Pikkaðu á hvaða tákn sem er fyrir fulla skilgreiningu, mynd og hvað hvert bréf í því merkir.

Spurningar sem fólk spyr

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Hlutar þessarar síðu eru aðlagað frá Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Þjappað og endurútskýrt hér; villur eru okkar.

Meira í Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs