## Want to keep learning?

This content is taken from the Davidson Institute of Science Education at the Weizmann Institute of Science's online course, An Introduction to Recreational Math: Fun, Games, and Puzzles. Join the course to learn more.
2.12

# Sudoku and similar puzzles

I’m hooked on Sudoku! Nearly every day I try and solve at least one. I’m sure some of you are too.

It is very hard to say exactly when Sudoku was invented, since it’s not clear whether its predecessors, Latin squares and Magic squares should be considered as a kind of Sudoku. Latin squares have been around for thousands of years, and were common both in China and in Europe during the Middle Ages. Many medieval Kabbalists used Latin squares for their purposes with letters instead of numbers written inside the grid. But what exactly are Latin squares?

## Latin squares

A Latin square is a square grid of size n x n, with a number written in each cell, such that each number between 1 and n appears exactly once in each row and once in each column. Latin squares come in many sizes; the larger the square, the more solutions it has. A 1x1 Latin square has just one solution. There are two different solutions for a 2x2 Latin square, 12 solutions for a 3x3 Latin square, 576 solutions for a 4x4 Latin square, and so on. Interestingly, mathematicians have not yet found a simple formula to compute the number of possible Latin Squares of a certain size. Here is an example of a 5 x 5 Latin square.

Usually, there are no extra restrictions placed on the numbers that appear in Latin squares. However, Latin squares with the extra constraint that the numbers on the diagonals should also be 1 to n, are particularly interesting. Here is one such Latin square.

## Sudoku

The first Sudoku game as we know it today was published by an architect named Howard Garns in the May 1979 issue of Dell Pencil Puzzles & Word Games. In the 1980s, Nicoli, a successful puzzle creating company based in Japan, discovered Dell’s riddle, improved it and renamed it “Suuji Wa Dokushin ni Kagiru” (meaning “the numbers must be single”). Later the name was shortened to SuDoKu by the president of Nicoli, Kaji Maki. The puzzle became a great success in Japan, but it was only introduced in the West in 2004 by Wayne Gould, a retired Hong Kong judge. Gould wrote a computer program that generated Sudoku puzzles and managed to convince the well-known newspaper “The Times” to publish them. He did this free of charge and refused to accept any money. Since then, Sudoku has become extremely popular and many people all over the world enjoy these puzzles daily, just like me!

## Solving Soduku

Sudoku is a special kind of 9 x 9 Latin square that has an extra constraint (there are 5524751496156892842531225600 9x9 Latin squares). This constraint reduces the number of possible Sudoku puzzles (when compared to the number of Latin squares of the same size), but there is still a very large number of possible Sudoku puzzles.

An efficient method to solve Sudoku puzzles is to detect spaces in which a certain number cannot appear. This can be done as follows.

Pick a certain number that appears on the board (for example, the number 5), draw a straight line through all the rows and columns in which that number appears, and check if you are left with any empty spaces (in one of the small 3 by 3 squares) where this number has to appear. Do this for all the numbers from 1 to 9 in turn.
In the example, we have marked the rows and columns where the number 5 appears. This leaves us exactly one square within the top 3 by 3 grid, where the number 5 has to appear (the coloured square).

Another way to solve Sudoku is by using logical reasoning. Sometimes we know what numbers should be in some of the squares, but we don’t specifically know which number to put in which square. This, however, may be all the information you need to solve the puzzle!

Here is part of a Sudoku puzzle:

We know that the numbers: 3, 5 and 6 should be written in the three middle squares on the top row, so as to complete the middle 3 by 3 square. Although, there is no way to know how to write these numbers in the three squares (since we can do it in six possible ways) we can deduce from this that the empty square on the right hand side of the top row has to have the number 4 in it (the only other number left to fill in the whole top row).

These are not the only ways to solve Sudoku - there are many more methods - but these will at least give you somewhere to start. Why not try out some Sudoku puzzles in the newspapers, magazines, internet sites or mobile apps?

## Discussion

Do you like Sudoku?