The University of Maine

DigitalCommons@UMaine

Honors College

Spring 5-2016

The Mathematics Behind Sudoku and How to Create Magic

Squares
Addison LaBonte
University of Maine

Follow this and additional works at: https://digitalcommons.library.umaine.edu/honors

Part of the Mathematics Commons

Recommended Citation
LaBonte, Addison, "The Mathematics Behind Sudoku and How to Create Magic Squares" (2016). Honors
College. 393.
https://digitalcommons.library.umaine.edu/honors/393

This Honors Thesis is brought to you for free and open access by DigitalCommons@UMaine. It has been accepted
for inclusion in Honors College by an authorized administrator of DigitalCommons@UMaine. For more information,
please contact um.library.technical.services@maine.edu.
 THE MATHEMATICS BEHIND SUDOKU AND HOW TO CREATE MAGIC
SQUARES

by

Addison LaBonte

A Thesis Submitted in Partial Fulfillment

of the Requirements for a
Degree with Honors (Mathematics)

The Honors College

University of Maine
April 2016

Advisory Committee:
Benjamin Weiss, Assistant Professor of Mathematics, Advisor
Eisso Atzema, Lecturer of Mathematics
Sergey Lvin, Lecturer of Mathematics
Eric Pandiscio, Associate Professor of Mathematics Education
Jennie Woodard,
Instructor of Women’s, Gender, and Sexuality Studies and Honors Preceptor
 Abstract

Sudoku puzzles date back to the 1800s in France and were introduced to
America in the late 1970s. Since then, the puzzle has become a worldwide
phenomenon. This thesis will be of expositional nature including the works of
books and mathematical papers such as [2], [14], and [15], among others. The
pages ahead will contain answers to some common questions about Sudoku
such as, what is the minimum number of starting clues that will produce a
unique solution? On the other side of the spectrum, what is the maximum
number of starting clues that won’t produce a unique solution?
Taking Sudoku one step farther, this paper will talk about Magic Squares
and the algorithm used in making them. Even more interesting is that the al-
gorithm provides the makings of a multimagic square, where every entry in a
magic square is squared, with the rows, columns, and diagonals still adding to
the same number [15]. See the Appendix for the computer code in the program
MATLAB that creates multimagic squares.
Dedicated to my Dad, the person who instilled in me a love for math. Thanks for
being my biggest fan and the person I look up to most.
Acknowledgements

First and foremost, thank you to my advisor, Benjamin Weiss. I deeply appreciate
all the time and energy you have put into this process. Thank you for pushing me
beyond what I thought I was capable of and for always knowing the answer to my
many questions. A huge thank you to my family and friends who never stopped
believing in me. A huge thank you to my amazing parents who have shown me
why a love for math is so special, and for being my two favorite people in the
world. Lastly, thank you to Noelle Leon-Palmer who has been by my side on and
off the field and throughout this thesis process; I couldn’t have done this without
you.

i
Contents

Introduction 1

1 Latin Squares 4

1.1 How to Produce a Latin Square . . . . . . . . . . . . . . . . . . . . . . 4

2 Greco-Latin Squares 6

3 Counting 9

4 Equivalence Classes 15

5 Graphs 22

6 Chromatic Polynomials 24

7 Extremes 31

8 Polynomials 33

9 Magic and Multi-Magic Squares 34

10 The Next Step 45

11 Applications 45

ii
Author’s Biography

Addison "Addie" LaBonte was born and raised in Maine. Her first love other than
mathematics is soccer and she competed for 4 years as a Division I athlete at the
University of Maine. Having grown up in York, Maine, Addie has a fond love for
the ocean and hopes to raise a family one day in her hometown.

Being an avid and religious Shark Tank watcher, Addie hopes to use her math
skills to find a job in the business world someday.

1
Introduction

Over the past decade or so, Sudoku puzzles have become a household name. In-
cluded in almost every newspaper and in many magazines, this popular mathe-
matics puzzle has become a hit with math and non-math lovers at nearly every age
group.

The earliest Sudoku related puzzles date back to the late 1800s where a news-
paper in France published Latin squares (see Section 1 for examples) [1], which
are Sudoku puzzles without the block condition. Then in 1979 in Indiana, Howard
Garns, a freelance puzzle inventor published "Number Place" which included plac-
ing individual numbers into an empty 9 by 9 grid [1]. Just five years later in 1984
the game first appeared in Japan and was given the name Sudoku, which is short
for "Suji wa dokushin ni kagiru", which means "the digits are limited to one oc-
curence." [1] An American named Wayne Gould was visiting Japan and fell in love
with the puzzle and brought it back to the United States [1]. Since then, it has
become a worldwide sensation.

Why would a simple math game become so popular all over the world? Su-
doku puzzles are a fun way to pass time. Their orderliness and organized nature
make them particularly intriguing. People of every age and education background
can learn how to complete these puzzles fairly easily. Lastly, Sudoku can be a men-
tal challenge and a fulfilling accomplishment when completed.

A seemingly straightforward puzzle, the game of Sudoku can be seen as a gate-

way into other fields in math. Dissecting the various parts of Sudoku has allowed
researchers to connect Sudoku with Latin squares, graph coloring, and even magic
squares, among other topics. This thesis will tell the story of how Sudoku puzzles

2
relate to a variety of different math topics that even the most experienced Sudoku
player isn’t aware of. The following pages will include some of the most intriguing
questions about Sudoku and how to answer them; some of the topics even include
questions that have yet to be answered and have even eluded many mathemati-
cians.

3
1 Latin Squares

Definition 1. A Latin square of order n is an n × n array in which each row and column
contains each of the n symbols exactly once. The number n is the order of the Latin square.

Sudoku is a Latin square of order 9, but additionally includes the condition

that each block must also contain the numbers 1 through 9. An initial starting clue
in any Sudoku puzzle says something about 20 other cells: 8 in its row, 8 in its
column, and 4 other cells in its block but not its row or column.

1.1 How to Produce a Latin Square

For a Latin square of order n, the first line has its entries in numerical order, in-
creasing from left to right. Each subsequent line is then produced by being shifted
one place to the left. The rows don’t pose a potential problem because the first row
contains all the n digits and the following rows are just a numerical shift of 1 from
the first. The columns also aren’t a problem because the kth row is the same as the
kth column, as long as the order and numerical shift are relatively prime [2].

Theorem 2. Let n be a positive integer and let L be the n × n matrix whose kth row for
1≤k≤n is (k, k + 1, ..., n, 1, 2, ..., k − 1), as read from left to right. Then, L is a Latin square
of order n. [2, Chapter 2, Page 32]

A detailed proof of this can be found in [2, Chapter 2, Page 33].

The jth column from top to bottom is read: (j, j + 1, ..., n, 1, 2, ..., j − 1). In creating
Latin squares, shifting by 2 works for Latin squares of order 3 and 5 but it does not
work for orders of 4 or 6. [2, Chapter 2, Page 34]

4
Lemma 3. If n is a given order of a Latin square and d is an integer that divides n, then
shifting by d will result in repeated rows and an invalid Latin square.

If n = d ∗ s then shifting the row by d a total of s times will return to the original
n
row. If k is any integer between 1 and d inclusive, then row k will be the exact same
n
as row d + k (i.e. rows 1 and 4, 2 and 5, 3 and 6). [2, Chapter 2, Page 34]

Lemma 4. If d is a divisor of n then a Latin square of order n shifted by d cannot be

produced.

If the shift has a divisor (besides 1) in common with the order then a Latin
square cannot be produced. So, n and d must be relatively prime.

Definition 5. The greatest common divisor, denoted by gcd is the largest number that
divides two numbers. For instance, the gcd(d, n) would be the greatest number that divides
both d and n.

If two numbers, say d and n are relatively prime, then gcd(d, n) = 1.

Theorem 6. Let n and d be positive integers and let L be the n × n matrix whose kth row
is obtained by shifting the first row by d a total of (k − 1) times. So the kth row reads:
[(k − 1)d + 1, (k − 1)d + 2, ..., n, 1, 2, ..., (k − 1)d]. Then L is a valid Latin square if and
only if gcd(d, n) = 1.

[2, Chapter 2, Page 35]

This theorem is very technical and can be found in [2, Chapter 2, Pages 35-38].

If d = 1 then the kth row is: [(k − 1)(1) + 1, (k − 1)(1) + 2, ..., n, 1, 2, ..., (k −
1)(1)] = (k, k + 1, ..., n, 1, 2, ..., k − 1). When d = 1, then for every value of n, gcd(1, n) =
1. [2, Chapter 2, Page 36]

5
 In proving this theorem, the rows are all set because each row consists of the
numbers from 1 to (k − 1)d + 1 to n, followed by the numbers from 1 to (k − 1)d for
some value of k. The entries of the column are: [1, (2 − 1)d + 1, (3 − 1)d + 1, ..., (n −
1)d + 1] where each entry is considered modulo n.

An example of a Latin square of order 3 is:

1 2 3

2 3 1

3 1 2

As mentioned previously, this was easily constructed by shifting the row entries
one place to the left.

2 Greco-Latin Squares

Definition 7. Two Latin Squares of order n are orthogonal if the square obtained by
superimposing them contains each possible ordered pair only once. This new square is
referred to as a Greco-Latin square.

An example of a Greco-Latin square is the following:

1A 2B 3C

2C 3A 1B

3B 1C 2A

This Greco-Latin square was produced by superimposing the following 2 Latin

squares:

6
 1 2 3 A B C

2 3 1 C A B

3 1 2 B C A

With a simple proof, it becomes evident that there is no valid 2 × 2 Greco-Latin

square (there would be repeated pairs). Previous research has shown that there are
no Greco-Latin square of order 6. A Greco-Latin square of order 3 and 5 can be cre-
ated with shifting the numbers by one place and the alphabet letters by two places.
This previously stated method only works for an order n that is odd because the
shift by 2 produces a Latin square only when n is an odd number. This is because
an even order and shift of 2 aren’t relatively prime. [3]

Research has found that Greco-Latin squares exist for all values of n except
2 and 6. [2, Chapter 3, Page 43] This begs the question: for some n, how many
pairwise orthogonal Latin squares can there be at the same time?

Definition 8. A set of Latin squares is called mutually orthogonal if any two of them
are orthogonal to each other.

Lemma 9. For n ≥ 2, it is not possible to have more than n − 1 mutually orthogonal Latin
squares.

For example, for a 5 × 5 Latin square, there can be up to 4 mutually orthogonal

Latin squares. Values of n that are either primes or a power of a prime attain that
upper bound of n − 1 mutually orthogonal Latin squares, and this is proved in
[4]. This is because primes are relatively prime to all numbers less than said prime
number [4].

In his 1776 paper titled "De Quadratic Magicis", Euler considered how Greco-
Latin squares could be turned into magic squares [3]. This will be touched upon in

7
Section 9.

Definition 10. A Gerechte design is an n × n Latin square that has been further subdi-
vided into any n additional regions of size n. These regions don’t have to be symmetric.

This is an example of a Gerechte design.

The numbers 1 through n must then appear once in the row and column, as
well as the additional region. Sudoku is an example of a 9 × 9 Gerechte design
because the blocks in the puzzle act as the additional region. For a particular n × n
Gerechte design, the number of mutually orthogonal Latin squares cannot exceed
n − d. In this case, d is the largest overlap between one of the additional regions
and some row or column in the given square. [2, Chapter 3, Page 48]

There exists Greco-Latin 4 × 4 Gerechte designs with 2 × 2 blocks. Since the

largest overlap between the blocks and the rows and columns is 2, then d = 2. So,

8
the maximum number of possibly mutually orthogonal Latin squares would be
4 − 2 = 2.

Extending this to a 9 × 9 Greco-Latin Sudoku, every row, column, and block

must contain A-I exactly once as well as 1-9 once. Each letter-number combination
must appear exactly once in order for it to be a valid Greco-Latin Sudoku. Given
the 3 × 3 block condition of a Sudoku puzzle, d = 3 because that is the number of
squares that overlap with the rows and columns. Thus, the maximum number of
mutually orthogonal Latin squares is n − d = 9 − 3 = 6.

3 Counting

Given n objects, there are n! ways of arranging the objects in a straight line. The
first object can be any of the n objects, and then the remaining n − 1 objects can
appear second, etc.

Definition 11. A Shidoku is a 4 × 4 Sudoku board with 2 × 2 blocks. Each row, column,
and block contains the numbers 1 through 4.

In a Shidoku, there are 4 ∗ 3 ∗ 2 ∗ 1 = 24 ways to fill in the first block. Let x be

the number of ways to fill in the remaining 3 blocks; this gives the total number of
Shidoku squares as 24x.

Definition 12. A Sudoku or Shidoku puzzle has an ordered first block if its entries are in
numerical order.

In a Shidoku there are 2 ∗ 2 = 4 ways of completing the first row and column
given that the first block is ordered. Now in order to get the total number of Shi-
doku boards, we must count the Shidoku squares whose first row, column, and

9
block appear as above and multiply that number by 24 ∗ 2 ∗ 2 = 96. As seen be-
low, there are only 3 different ways of completing the ordered Shidoku. Given that
there are 96 Shidoku squares represented by each ordered square, the number of
Shidoku squares is: 96 ∗ 3 = 288.

1 2 3 4

3 4 1 2

2 1 4 3

4 3 2 1

1 2 3 4

3 4 2 1

2 1 4 3

4 3 1 2

10
 1 2 3 4

3 4 1 2

2 3 4 1

4 1 2 3

Now, how does this apply to counting Sudoku puzzles? Label the 3 × 3 blocks
of a Sudoku as: B1 through B9, in numerical order as seen below.

B1 B2 B3

B4 B5 B6

B7 B8 B9

Here, each small square represents a 3 × 3 block in a Sudoku grid.

Let B1 be in standard, or ordered form. So it would read: 1, 2, 3, 4, 5, 6, 7, 8, 9.

B1 is the following:

1 2 3

4 5 6

7 8 9

There are 9! = 362, 880 other Sudoku squares obtainable from the standard form
square simply by relabelling. Once B1 is filled in in ordered form, there are 3
possibilities for the top row of block B2:

Case 1a: 4, 5, 6 in some order,

11
 Case 1b: 7, 8, 9 in some order,

Case 2: some combination of 4, 5, 6, 7, 8, 9 in some order.

In each of the 6 rows of blocks B2 and B3, we can choose any of the 3! permu-
tations of the 3 entries. In case 1a and 1b, filling in the rows of B2 and B3 would
become a 6-step process where each of the 6 mini rows can be completed in 3!
ways. This totals (3!)6 ways of completing the rows in each of the case 1 scenarios.
So there are 2 ∗ (3!)6 = 93, 312 ways of filling in blocks B2 and B3 for case 1.

1 2 3 (4)(5)(6)(7)(8)(9)
4 5 6 (7)(8)(9)(1)(2)(3)
7 8 9 (1)(2)(3)(4)(5)(6)

Here, the parenthesis around the numbers mean that any of the 3 choices in
that block’s row can be chosen for that cell. For example, the uppermost row in B2
reads: (4), (5), (6), but the numbers can be permuted.

The entries in the top row in blocks B2 and B3 are a mix of the numbers from
the second and third rows from block B1. We can conclude there are 3 ∗ (3!)6 ways
of filling in the first 3 rows in the scenario. In case 2, we must fill in the first
row of B2 with 3 digits from 4 through 9 but not 4, 5, 6 or 7, 8, 9. There are 18
ways of choosing 3 digits for case 2 for the first row of B2. There are a total of
18 ∗ 3 ∗ (3!)6 = 2, 519, 424 ways of filling in blocks B2 and B3 for case 2.

12
 Thus, combining both cases, there are 93, 312 + 2, 519, 424 = 2, 612, 736 ways of
filling in the first 3 rows of a Sudoku puzzle whose B1 block is in standard form.
Considering there are 9! ways of filling in the first block, there are 2, 612, 736 ∗ 9! =
948, 109, 639, 680 ways of filling in the first 3 rows of a Sudoku board. There are
(9!)9 different ways to fill in a 9 × 9 Sudoku with each number appearing once in
each block. The probability that a Sudoku with block-compliancy is additionally
row-compliant is:
(948, 109, 639, 680)
k= (1)
(9!)9

which is also the probability that it’s column-compliant.

Lemma 13. The probability of a puzzle being row-compliant and column-compliant is k2 ,

if the two probabilities are independent.

[2, Chapter 4, Page 67]

Compliant means that the Sudoku is valid; for example, row-compliant means
that each row contains 1 through 9. Column-compliant means each column con-
tains 1 through 9, and the same holds for block-compliance.

Randomly choose a Sudoku puzzle that is block-compliant. Then the probabil-

ity that it is additionally row-compliant is k. The probability that this Sudoku is
also column-compliant is also called k.

Denoting the probability that a randomly chosen Sudoku puzzle is row-compliant

by k and doing the same for column-compliance shows why the probability of both
row- and column-compliance probability is k2 . The two probabilities were simply
multiplied together.

Assuming independence, we could compute the number of Sudoku squares by

13
multiplying the total number of block-compliant squares by the probability that a
randomly selected square is both row- and column-compliant. This computation
would be:

(9!)9 ∗ k2 = (9!)9 ∗ ((948, 109, 639, 680)3 /(9!)9 )2 ≈ 6.6571 ∗ 1021 (2)

[2, Chapter 4, Page 68]

Swapping the columns within a block, or swapping the blocks themselves ends
up in a new configuration with the same number of completions. Each configura-
tion of the first 3 rows can be turned into a configuration whose first row is ordered
by following:

a) if necessary, permute the columns within B2 and B3 so that the entries in the
first row of each respective blocks are increasing;

b) if necessary, exchange B2 and B3 so that the upper left entry of B2 is smaller

than said entry in B3.

Following this procedure for case 1a) and 1b), there is only one possible way
to order the first row. Now both case 1) scenarios have been reduced from 2 ∗
(3!)6 = 93, 312 possible ways to (3!)4 = 1296 configurations, which is a reduction
of 72 times. Since there are 6 ways of permuting the columns in B2 and 6 ways of
permuting the columns in B3, step a) above implies there are 36 completions.

Researchers have found using computers that there are

6,670,903,752,021,072,936,960

possible Sudoku squares [5]. But, how many of these are truly different from one
another?

14
4 Equivalence Classes

Two things are said to be equivalent if they possess a common property which
allows us to treat them as identical for some purpose. For Sudoku, equivalence can
be seen as taking one puzzle and building another one from it via transformations,
which will be further discussed.

In working with Sudoku puzzles, it is imperative to remember that two puzzles

may not look alike, but a simple switching of a row or column of one puzzle can
produce the other.

Definition 14. Three horizontally adjacent blocks are known as a band. Three vertically
adjacent blocks are called a pillar.

A valid transformation of a Sudoku means that something in the puzzle was

switched to form another Sudoku that is row-, column-, and block-compliant.
Switching 2 rows or columns in the same band or pillar would be an example
of a valid transformation. On the other hand, switching rows and columns from
different bands or pillars does not produce a valid Sudoku transformation. We can
however permute the rows within a band or the columns within a pillar.

Any rotation or reflection through an axis of symmetry will lead to another

valid Sudoku puzzle. The following reflections lead to another valid Sudoku: 0 ◦ ,
90 ◦ , 180 ◦ , and 270 ◦ . There are 4 axes to choose: 1 vertical, 1 horizontal, and 2
diagonal.

A list of valid transformations include:

• Type 1 transformation: relabeling

15
 • Type 2 transformation: permuting the rows in a band or the columns in a
pillar

• Type 3 transformation: permuting the bands or pillars themselves

• Type 4 transformation: any rotation or reflection

• Type 5 transformation: composing any previous transformation

There are no other types of transformations that we will consider equivalent;

this list is complete.

Lemma 15. If 2 puzzles are fundamentally different, then one is not obtained by the other
via the list of transformations.

Thus, there is no way for one Sudoku puzzle to be transformed into another via
the list of transformations if they are considered fundamentally different.

Let a random Sudoku square be s which is equivalent to x other squares. Un-

fortunately we cannot just divide the number of Sudoku by x because x varies as s
does.

Lemma 16. Two squares are equivalent if they differ only by a Type 1 transformation (i.e.
relabeling of the digits).

In other words, just a simple relabeling of a Sudoku that leads to another Su-
doku means they are not truly fundamentally different.

Transformation types 2 through 5 are permutations of the Sudoku cells. Sev-

eral consecutive permutations lead to another valid transformation. At least two
transformations is known as a composition.

Some different types of transformations are: (these are for use with a triangle)

16
 • Identity = i = doing nothing

• Rotate = r = rotate 120 ◦

• Rotate = R = rotate 240 ◦

• Reflect = a = reflect vertically

• Reflect = b = reflect along right diagonal

• Reflect = c = reflect along left diagonal

This picture shows the different transformations.

[6]

A composition of symmetries is like a product; in this case, r ∗ a = b. The com-

position of any two of these transformations will return us to one of the original 6

17
symmetries. For instance, rotating by r and then R will return us back to the orig-
inal, which is the same as i, or doing nothing. When a, b, or c is composed with
itself, it returns the puzzle back to its original (which is equivalent to performing
i). Composing symmetries is not commutative however. So, performing r then a is
not the same thing as performing a then r.

Definition 17. Starting with a specific Sudoku puzzle and performing symmetry on it
until there are several puzzles are that not fundamentally different will form a group, called
an orbit.

In order to find the number of orbits in a given example, the use of Burnside’s
Lemma is needed. Burnside’s Lemma uses some notation: define G as a finite
group that acts on a set of elements X. For every g in the group G, let X g denote
the set of elements in X that are fixed by g. Hence, the number of orbits is equal
to the average number of points that are fixed by an element of the group G. Here,
Gx denotes the elements in G that fix specific x and X/G is the set of orbits.

Lemma 18 (Burnside’s Lemma).

1
| G | g∑
| X/G |= | Xg |
∈G

Proof.

|G|
∑ | X g |=| {( g, x ) ∈ G × X : g ∗ x = x } |= ∑ | Gx |= ∑ |G∗x|
=
g∈ G x∈X x∈X

1 1
|G| ∑ | Gx |
=| G | ∑ ∑
|A|
= G ∑ 1 =| G || X/G |
x∈X A∈ X/G x ∈ A A∈ X/G

18
 [7]

This lemma is important because it can help determine how many different
orbits there are. This will come in handy when deciphering how many Shidoku
exist that are fundamentally different.

Lemma 19. In order to calculate the number of orbits, the following process is used:

1. Make a thorough list of all the group’s elements; 2. For each one, count the number
of elements they fix; 3. Compute the mean of all the symmetries of the number of fixed
elements.

For showing how Burnside’s Lemma works, consider the following example.
Given one triangle, color each side either blue or red. All three sides can be one
color, or both red and blue can make up the triangle. Since each side of the trian-
gle has two color possibilities, there are 2 ∗ 2 ∗ 2 = 23 = 8 different triangles that
can be made. However, some of these triangles can be represented by a single or-
bit because their sides are colored the same, differing only by a rotation. The 4
possibilities are:

1. All sides are blue 2. One side is red, two sides are blue 3. One side is blue,
two sides are red 4. All sides are red

So, there are only 4 orbits. Using Burnside’s Lemma will help us arrive at this
same answer. Looking at certain triangles shows that some are fixed under a cer-
tain symmetry. For example, an all blue or all red triangle remains the same no
matter the symmetry performed on it. A triangle with a blue base and the other
two sides red will remain fixed when the symmetry a (or vertical rotation) is per-

19
formed on it. Going through each symmetry: i fixes all 8, r fixes 2, R fixes 2, and a,
b, and c all fix 4. So, the average number of colors fixed by the different symmetries
is found by:
8 + 2 + 2 + 4 + 4 + 4 24
= =4 (3)
6 6

Hence, 4 is the number of orbits, which was found above when the 4 possibili-
ties were stated. This is Burnside’s Lemma. [2, Chapter 5, Pages 88-90]

The number of fundamentally different Sudoku puzzles is equal to the number

of different orbits. Burnside’s Lemma can be used to help count mathematical
objects, and which are truly different from each other. Consider using Burnside’s
Lemma with Shidoku, as seen below.

Lemma 20. There are only 2 fundamentally different Shidoku puzzles.

These are seen below.

20
 Table 1: Type 1 Shidoku followed by Type 2 Shidoku:

1 2 3 4

3 4 1 2

2 1 4 3

4 3 2 1

Type 1 Shidoku

1 2 3 4

3 4 1 2

2 3 4 1

4 1 2 3

Type 2 Shidoku
Working with computers, Arnold and Lucas [10] showed with that a group of
128 Shidoku symmetries and given a first fixed block, there are 56 symmetries that
fix no Shidoku, 48 that fix 2, 9 that fix 4, 4 that fix 6, 6 that fix 8, 4 that fix 10, and
1 symmetry that fixes all 12 up to permutation. So, using Burnside’s Lemma [see
Lemma 18], the number of fundamentally different Shidoku squares is:

56 ∗ 0 + 48 ∗ 2 + 9 ∗ 4 + 4 ∗ 6 + 6 ∗ 8 + 4 ∗ 10 + 1 ∗ 12 256
= = 2.
128 128

21
 There are 96 Shidoku that are equivalent to type 1 and 192 equivalent to type 2.
[2, Chapter 5, Page 80]

Using computers, Russell and Jarvis found that there are 5,472,730,538 funda-
mentally different Sudoku squares. [11]

5 Graphs

Every Sudoku puzzle can be solved using graph coloring. For a 9 × 9 Sudoku with
81 cells, think of each of the 81 cells as a vertex. Each vertex creates a zone that
consists of eight other vertices in its row, eight in its column, and four vertices in
its block, but not in either the row or the column. For each vertex, add connecting
edges to each of the other vertices in its zone. When their corresponding cells
share a row, column, or block, two vertices share an edge. In Sudoku, each vertex
is connected by an edge to eight other vertices in its row, eight in its column, and
four in its block. Thus, each vertex is connected to twenty other vertices. The
81 ∗ 20
total number of edges in a 9 × 9 Sudoku is = 810 edges. When coloring the
2
graphs, assign colors to the vertices such that connected vertices are given different
colors. If all 81 cells are assigned a color and no two cells that share an edge have
the same color, then the Sudoku is solved.

Definition 21. If connected by an edge, two vertices are said to be adjacent.

Definition 22. If adjacent vertices are always given different colors, then the graph is said
to be properly colored. A proper coloring that uses n colors is called a proper n-coloring.
So, a proper coloring means that a graph is fully colored, with each vertex being colored
differently than its adjacent vertices.

22
 There is a perfect correlation between a proper 9-coloring Sudoku and a fin-
ished Sudoku.

Definition 23. The minimal number of colors required for a proper coloring is known as
the chromatic number.

Example 24. The chromatic number for a Sudoku puzzle is 9.

Example 25. A graph where every vertex is connected to all other vertices is called a com-
plete graph, denoted by Kn on n vertices. Each vertex in a complete graph is connected to
n-1 other vertices, so a proper coloring uses at least n − 1 colors. A Sudoku puzzle must
have at least eight starting clues in order to be completed.

If a Sudoku puzzle only contains starting clues with seven numbers, swapping
the remaining two numbers will also provide a sound solution. Thus, starting with
seven colors produces two solutions whereas starting with eight colors is needed
to produce a complete Sudoku.

Corollary 26. An n × n Sudoku must have at least n − 1 starting colors.

Suppose there’s a 9 × 9 Sudoku that only has the numbers 1 through 7 as part of
its initial starting clues. Starting with only n − 2 clues means starting with only n −
2 = 9 − 2 = 7 colors. These starting clues give no information about the numbers
8 or 9 in the puzzle. So, after completing the puzzle, relabeling every 8 as a 9 and
vice versa would produce another sound puzzle. Starting with at least 8 numbers
for initial starting clues will not allow for switching 2 numbers at the end because
these starting clues give information about all 9 numbers. Thus, there must be
n − 1 starting clues for an n × n Sudoku.

Theorem 27. Let G be a graph with its chromatic number X ( G ) and let C be a partial
coloring of G using X ( G ) − 2 colors. If the partial coloring can be finished to a proper

23
coloring of G, then there must be at least two different ways of completing the coloring
[14].

The two colors that aren’t used in the starting partial coloring can be switched
in the proper coloring to produce another solution, as stated previously.

6 Chromatic Polynomials

In an original mathematical exploration of Sudoku, Herzberg and Murty [14, The-

orem 1] related Sudoku to a graph and stated the following theorem.

Theorem 28. Let G be a finite graph that has v vertices, and let C be a partial proper
coloring of t vertices of G which uses do colors. Let PG,C (λ) denote the number of ways to
complete the coloring using λ colors to obtain a proper coloring of G. Then, PG,C (λ) is a
polynomial with coefficients of degree v − t.

Sudoku puzzles are colored graphs in disguise. Each of the 81 cells in a Sudoku
can be called a vertex. A colored graph is one where each vertex is given a color.
An edge between two vertices means that the vertices are in the same row, column,
and/or block. Using graph coloring for Sudoku means that each number is repre-
sented by a color. Thus, a colored vertex is connected to other vertices which are
colored differently.

Definition 29. A proper coloring is one where all adjacent vertices have different colors.

Definition 30. A partial coloring is one where only some vertices are colored.

Once a Sudoku is properly colored (meaning that no 2 adjacent vertices share

24
the same color) for all 81 cells, it is a completed and valid puzzle. When less than
81 cells are colored, the Sudoku has a partial coloring.

Before moving on, there are a couple definitions that are important.

Definition 31. A multiplicative function is one where f (nm) = f (n) f (m) if gcd(n, m) =
1 and f (1) = 1.

Proposition 32. The principle of inclusion-exclusion gives an organized way to find

the number of elements in a union of a group of sets, the size of every set, and the size of all
the possible intersections among said sets [8].

For example, if we are trying to find the size of X, where X is made up of the
overlapping sets A, B, C, and D, then the following equation would be used:

| X |=| A | + | B | + | C | + | D | − | A ∩ B | − | A ∩ C | ...+ | A ∩ B ∩ C | +...

Continue this until you have subtracted out | A ∩ B ∩ C ∩ D |. This equation

is finding the number of elements in X, which is made up of overlapping sets A
through D.

Definition 33. Define the Möbius function as



0; if there’s a square number greater than 1 that divides n

µ(n) =
(−1)ω (n) ; ω (n) is the number of distinct primes dividing n



25
Theorem 34. If f or g is multiplicative then

n
f (n) = ∑ f (d) ⇐⇒ g(n) = ∑ µ(d) g( )
d|n d|n
d

Using an example of

n
n = ∑ f (d) ⇐⇒ f (n) = ∑ µ(d)
d|n d|n
d

where f (d) =positive integers less than or equal to d, that are coprime to d, on the set of
integers.

Proving Möbius inversion:

y y
∑ µ( x ) g(y) = ∑ µ( x ) ∗ ( ∑ f (z))
y≤ x y≤ x z≤y

y
= ∑ µ( ) f (z)
x
z≤y≤ x

y
= ∑ f (z) ∗ ( ∑ µ( ))
x
z≤ x z≤y≤ x

= f ( x ).

[13]

Proving Theorem 28 involves the use of Möbius inversion on a poset of graphs.

A partially ordered set (or poset) is a set P in conjunction with a partial ordering
denoted by ≤ which satisfies the following:

1. x≤ x for all x that exists in P;

26
 2. x≤ y and y≤ x implies that x must equal y

3. x≤ y and y≤ x implies that x≤ z.

Using the function where f (d) =positive integers less than or equal to d, that
are coprime to d, on the set of integers, f (6) = 2 (because 1 and 5 are coprime to 6).
Another way to find this is by using the principle of inclusion-exclusion and the
equation: ∑d|n µ(d) nd as defined by our Möbius function. So,

6 6 6 6
f (6) = (1 ∗ ) + (−1 ∗ ) + (−1 ∗ ) + (1 ∗ ) = 6 − 3 − 2 + 1
1 2 3 6

Doing the same process for f(12) is as follows:

12 12 12 12 12 12
f (12) = (1 ∗ ) + (−1 ∗ ) + (−1 ∗ ) + (0 ∗ ) + (1 ∗ ) + (0 ∗ )
1 2 3 4 6 12

f (12) = 12 − 6 − 4 + 0 + 2 + 0 = 4

To make sense of this number, our equation says that there are 4 numbers that
are coprime to 12. This is correct because only the numbers less than or equal to 12
that are coprime to it are: 1, 5, 7, 11.

Next it is important to look at partially ordered sets (posets for short). Partial
ordering can occur in divisibility. For instance, n ≥ m if m divides n. So, it can easily
be seen that 4 ≥ 2 because 2 divides 4. But, how are 9 and 6 related? We cannot say
that 9 ≥ 6 nor that 9 ≤ 6 because one does not divide the other according to our
definition. This is an example of a partial ordered set.

Posets can be seen in graph theory as well. Define G ≥ H if connected vertices

can be contracted on G and edges ending on vertices and get H. In the images

27
below, call the first graph G and the second one H. If the lower two vertices are
morphed into one (since they are connected by an edge), thus removing an edge,
then this graph with one less edge is less than or equal to our original graph. Thus,
G ≥ H. This is an example of a poset within graph theory.

Given a finite poset P with partial ordering, ≤, we define the Möbius function
µ : P × P → Z recursively by setting

µ( x, x ) = 1, ∑ µ( x, y) = 0,
x ≤y≤z

if x 6= z [14].

The main theorem used in Möbius functions is the following. If f : P → C is

any complex function, then we define:

g(y) = ∑ f (x)
x ≤y

then
f (y) = ∑ µ(x, y) g(x)
x ≤y

and conversely [14].

The classic Möbius on graphs is as following. In the proof of 28, G is a graph

and C is a proper coloring of some of the vertices. Say that ( G 0 , C ) is a reduction of
( G, C ) if G 0 is formed by contracting some edges in G. For each ( G 0 , C ) of the poset,

28
let PG0 ,C (λ) denote the number of ways to properly complete the coloring G 0 with λ
colors. Next, let QG0 ,C (λ) be the number of ways to color (not necessarily properly)
0
the vertices of G 0 using λ colors. So, QG0 ,C (λ) = λ(v −t) where v0 is the number of
vertices of G 0 and t is the number of vertices on C. Contract away adjacent nodes
of same color until it’s proper of expand out from proper coloring of the subgraph.

Then:
0
QG0 ,C (λ) = λ(v −t) = ∑ PG0 ,C (λ)
C≤G0

This equation is saying that the number of ways to color (not necessarily prop-
erly) the vertices of G 0 using λ colors is equal to λ raised to the power of (v0 − t)
which is the number of vertices in G 0 − C.

By Möbius inversion,

0
PG0 ,C (λ) = ∑ 0 µ(C, G0 )λv −t
C≤G

[14]

which shows that is is a polynomial.

In expanding this to Sudoku puzzles, let G be a Sudoku graph and C is given by

the starting clues. Then the chromatic number of Sudoku would be nine because G
cannot be colored with fewer than nine different colors. Thus, Pg,c ( x )=0 if 1≤x≤8
because the number of ways of completing a partial coloring using eight or fewer
colors is impossible; so the number of times it could be completed would be zero.
A valid Sudoku puzzle has Pg,c (9)=1 because there is only one way to complete a
partially colored Sudoku using nine colors and if the polynomial equals one, then
this means the Sudoku is unique (i.e. only one valid solution). Now let s be the

29
number of different digits included in the initial starting clues. Then:

Pg,c ( x ) = ( x − s)[ x − (s − 1)][ x − (s + 2)]...( x − 8)q( x ) (4)

[2, Chapter 7, Page 136]

Here q( x ) is a polynomial that has integer coefficients. For instance, if only five
out of the nine digits were given in the initial starting clues, then s = 5. Then Pg,c ( x )
would be zero because the Sudoku graph cannot be colored with five, six, seven,
or even eight colors; it must be colored with nine. Hence, ( x − 5), ( x − 6), ( x − 7),
and ( x − 8) would be factors of the polynomial. Dividing Pg,c ( x ) by the previously
stated factors would produce another polynomial, which is denoted by q( x ). The
result is:

Pg,c ( x ) = ( x − 5)( x − 6)( x − 7)( x − 8)q( x ). (5)

[2, Chapter 7, Page 136]

As previously stated, a Sudoku graph must be colored with nine colors. So,
Pg,c (9)=1. Extending this to the polynomial equation gives:

Pg,c (9) = (9 − s)[9 − (s + 1)][9 − (s + 2)] · · · (9 − 8)q(9) = (9 − s)!q(9). (6)

[2, Chapter 7, Page 136]

If s ≤ 7 then the polynomial would be equal to a value that is greater than one,
which means it’s not possible to have a unique Sudoku solution when fewer than

30
eight digits are represented in the initial clues.

7 Extremes

The maximal number of starting clues a Sudoku can have is 81, although this is a
boring case because the puzzle is completely filled in. So then we can ask: what is
the maximal number of starting clues a Sudoku puzzle can have without having a
unique solution? The answer is 77 and can be seen with the following example. [2,
Chapter 9, Page 155]

7 3 5 6 1 2 4
6 4 9 3 8 5 1 2 7
1 2 8 4 7 9 3 5 6
2 5 1 9 6 3 7 4 8
4 9 6 8 2 7 5 3 1
8 7 3 1 5 4 2 6 9
9 8 4 2 3 1 6 7 5
5 1 2 7 4 6 3
3 6 7 5 9 8 4 1 2

Although this puzzle has a large number of initial clues, it does not have a
unique solution. The two pairs in each Sudoku puzzle without a clue are miss-
ing an 8 and a 9. Switching the 8s and 9s in this example provides two possible
solutions to the Sudoku.

In the above example, there are clearly two ways to finish the graph coloring
using 9 colors. But how many ways would there be to complete the coloring using
10 colors? This number would grow to 18 different ways to finish the coloring.
Using 11 colors, there are 84 different ways; for 12 colors there are 260 ways and

31
for 13 colors there are 630 ways to finish the coloring.

Due to the fact that this is a degree 4 polynomial (total cells - filled in cells = 81-
77= degree 4), there are 5 unknowns in the equation: y = ax4 + bx3 + cx2 + dx + e.
Plugging in the number of colors and their respective ways to finish the coloring,
the following polynomial is obtained:

y = x4 − 32x3 + 384x2 − 2047x + 4088

Here, x is the number of colors used in the coloring, and y is the number of
different ways to complete the coloring given x.

Lemma 35. For a Sudoku of size n × n, the largest number of clues that doesn’t produce
a unique solution is given by n2 − 4.

The reason the number 4 is being subtracted from the total number of cells (n2 )
is because 4 is the smallest ambiguity that can exist in a Sudoku. The switching of
these 2 sets of 2 squares will lead to a non-unique solution. Known as an unavoid-
able set, not including these 4 cells is guaranteed to lead to a solution that isn’t
unique. Thus, the largest number of cells that doesn’t produce a unique solution is
given by n2 − 4.

In the above Sudoku example, these two sets are known as unavoidable sets
because they are crucial to the outcome of the Sudoku. Without them included in
the initial starting clues, a Sudoku would have more than one solution.

Definition 36. A puzzle is irreducible if each clue is essential and plays a part in getting
to the unique Sudoku solution. These necessary clues are known as independent clues.

Adding more (unnecessary) clues to an irreducible puzzle will create a reducible

32
Sudoku puzzle. In this case, 77 is the bound for the maximal number of inde-
pendent starting clues. Looking at the extreme opposite case asks: what is the
minimum number of starting clues possible in a Sudoku puzzle with a unique
solution? Researchers have proved that a Sudoku square with 17 possible starting
clues can produce a unique solution, however 16 has never been proven to lead to a
unique solution. Researchers would have to check every 16-clue subset of the total
5,472,730,538 different Sudoku puzzles, totaling 183,851,407,423,359,414,572,057,730
different 16-clue candidates. [2, Chapter 9, Page 165]

8 Polynomials

In a 4 × 4 Shidoku, let w represent one of the sixteen cells. In order to satisfy a

single row, column, or block, the following holds true: (w − 1)(w − 2)(w − 3)(w −
4) = 0. Now let w, x, y, and z be four cells in a region. Then w + x + y + z = 10 and
wxyz = 24. Extending this to a 9 × 9 Sudoku, the following equations hold true:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 (7)

1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 ∗ 7 ∗ 8 ∗ 9 = 362, 880 (8)

However, the sum and product equations can still work using different numbers:

1 + 2 + 4 + 4 + 4 + 5 + 7 + 9 + 9 = 45 (9)

1 + 2 + 4 + 4 + 4 + 5 + 7 + 9 + 9 = 362, 880 (10)

33
These sum and product equations can no longer make certain that the nine cells in
the same region are filled with distinct values.

9 Magic and Multi-Magic Squares

Each row and column in a 9 × 9 Sudoku puzzle add to the number 45.

Definition 37. A magic square is an n × n array in which each row, column, and main
diagonal adds to the same number. A multimagic square is a magic square which remains
a magic square even when all the entries have been squared.

Just like magic squares, one aspect of a valid Sudoku puzzle is that the rows
and columns add to the same number. In the Sudoku case, this number is 45; in
magic squares, this number varies.

Definition 38. Let M be an m × m matrix that consists of the natural numbers from 1 to
m2 . M is a magic square if the sum of each element in the row, column, and main diagonal
is the same number; this number is called the magic number.

Definition 39. A magic square that uses the first m2 numbers is called normal.

Definition 40. M∗d is the resulting matrix when every element in the matrix M is raised
to the dth power. The M matrix is called an n-multimagic square if M∗d is a magic
square for d = 1, 2, ..., n.

[15]

For the previous definition, when d ≥ 1, the magic square will no longer contain
the first m2 numbers.

34
 Magic and multimagic squares can also be solved with graph coloring, however
they are an extreme case because each cell requires a different graph color. Unlike a
n × n Sudoku which uses n colors, a magic square of m × m size uses m2 colors. In
other words, the chromatic number for a magic square is m2 . Using graph coloring
to solve a magic or multimagic square can be beneficial because it is imperative
that no number (or color) is repeated in the process of creating a magic square.

The following is an example of a 3 × 3 magic square:

2 7 6

9 5 1

4 3 8

Adding the rows, columns, and the two main diagonals gives 15. Thus, the above
is a valid magic square.

Magic squares date back to the 1700s when Euler created a magic square from
a Greco-Latin square [3]. After superimposing two Latin squares, Euler came up
with the following Greco-Latin square:

[3].

Given a Greco-latin square, there is an easy algorithm described below that

produces a magic square.

35
 Take this magic square and label each entry as ordered pairs ( a, b) with the
given order n. Here, the order n is 5. Then, take each entry and perform the
following equation:
( a − 1)n + b.

Doing so will create a magic square. In this example, the rows and columns
sum to 65. More requirements are necessary if the diagonals must sum to 65 [3].

[3].

The earliest known multimagic squares was constructed by G. Pfeffermann in

1891, when he produced the following [15]. His differs from Euler’s because Pfef-
fermann’s includes the diagonal stipulation and it is also multimagic.

36
 [15].

Adding each individual row, column, and diagonal will be 260. After squaring
each entry, the rows, columns, and diagonals will all add up to 11180. Thus, it is a
valid multimagic square.

There are several algorithms to make magic squares. Euler has one included in
[3] which works for an odd × odd magic square.

Creating a magic square with large dimensions must be solved through an al-
gorithm, and sometimes even requiring a computer in order to save time. There is
a known algorithm for making multimagic squares.

A paper titled "Multimagic Squares" by Derksen, Eggermont, and van den Es-
sen, explains an algorithm for constructing multimagic squares. [15]

This paper denotes R as a finite ring containing q elements and provides the

37
following definition.

Definition 41. For c that exists in R, a bijection N : R → {0, 1, ..., q − 1} is of type c if

N ( a) + N (− a + c) = q − 1 for all a existing in R [15].

Bijections of type -1 always exist and will always be our choice. [15] Now that
we have a bijection, the next step is to find generator matrices. First, choose some
n. From the chosen n, choose q that is prime such that q ≥ 2n − 1.

Following a detailed proof in the paper [15], the matrix A must first be con-
structed. A is created with the following matrix given that n ≥ 2. The following is
the way to create matrix A. [15]

A=  
1 0 0 ... 0 
 
 
1 1 1 ... 1 
 
−
 
1 2 4 ... 2 n 1 
 
 
1 3 9 ... 3n −1
 

 
 
. . . ... . 
 
 
. . . ... . 
 
 
. . . ... . 
 
 
1 (2n − 2) (2n − 2)2

... (2n − 2)  n − 1 
 
 
0 0 ... 1

The dimensions of this matrix are 2n × n. Split up the matrix A into two n × n
matrices, and call the top half A1 and the bottom half A2. The next step in creating
our multimagic square is to make the matrix B. [15]

38
 B=  
 2 ∗ A1 
 
−2 ∗ A2

Thus, we now have our two generator matrices, A and B. The next step is to
create the matrix X which is done by:

X=
 
A B

We now use matrix X to fill in our multi-magic square M as follows. We fill in

#»
the (i, j) entry of our magic square as follows: solve for #»
a and b given i and j.

To find #»
a , whose dimensions are n × 1, choose a number between 0 and q − 1
for each entry. Once you have done every possible vector with its entries between
0 and q − 1, the multimagic square will be complete. Thus, only doing one possible
vector will only produce one entry value place. Once finished choosing the num-
#» #»
a is complete. Repeat this exact process for b . Now #»
bers, #» a and b are complete.

For #»
a , label the entries as #»
a 1 through #»
a n and compute the following equation:

1 + #»
a 1 ∗ q0 + #»
a 2 ∗ q1 + ... + #»
a n ∗ q n −1 (11)

The result of this equation is the row number of our entry in the eventual mul-
timagic square.
#» #» #»
Doing this for b , label the entries as b 1 through b n and compute the following
equation:
#» #» #»
1 + b 1 ∗ q0 + b 2 ∗ q1 + ... + b n ∗ qn−1 (12)

39
 The result of this will be the column number of the entry in the resulting mul-
timagic square.

Now that we have determined exactly which entry we are going to compute, it
is time to actually find the value of this entry place.
#»
In order to do this, first stack #»
a and b such that:

 
#»
a
 #»
b

Take the matrix X and multiply it by this 2n × 1 matrix. The resulting is a 2n × 1

matrix, where each entry is considered modulo q. Call this matrix D where each
entry is labeled D1 , D2 , ... , D2 n. In order to finally find our entry value for the
previous calculated row and column, calculate the following equation:

1 + D1 ∗ q0 + D2 ∗ q1 + ... + D2 n ∗ q2n−1 (13)

This calculation will give the number for the entry value in our multimagic
square. If doing a multimagic square completely by hand, each entry would be
calculated using this algorithm.

The following uses the algorithm for n = 2 and q = 5.

Matrix A is 2n × n = 4 ∗ 2 and looks like:

40
  
1 0
 
1 1
 
 
 
1 2
 
 
0 1

Matrix B is 2n × n = 4 ∗ 2 and looks like:

 
2 0
 
2 2
 
 
 
3 1
 
 
0 3

Thus, matrix X is 2n × 2n and looks like:

 
1 0 2 0
 
1 1 2 2
 
 
 
1 2 3 1
 
 
0 1 0 3

#»
To now find #»
a and b , the following uses numbers between 0 and q − 1, or
between 0 and 4 in this case.

Say #»
a=

 
0
 
1

41
 Then, using our equation:

1 + #»
a 1 ∗ q0 + #»
a 2 ∗ q1 + ... + #»
a n ∗ qn−1 = 1 + (0 ∗ 50 ) + (1 ∗ 51 ) = 6. (14)

So, here our #»

a = 6 means our entry place is in the 6th row.
#»
Additionally, say b =

 
1
 
1

Then, using our equation:

1 + #»
a 1 ∗ q0 + #»
a 2 ∗ q1 + ... + #»
a n ∗ qn−1 = 1 + (1 ∗ 50 ) + (1 ∗ 51 ) = 7. (15)

#»
So, here our b = 7 means our entry place is in the 7th column. Thus, when we
compute the entry value, it will be in the 6th row, 7th column.

Then, stacking our vectors, the result is:

 
0
 
1
 
 
 
1
 
 
1

The next step is to multiply our matrix X by this stacked vector matrix.

42
     
1 0 2 0 0 2
    
1 1 2 2 1 0
    
   =  
    
1 2 3 1
 1 1
   

    
0 1 0 3 1 4

The result of this is the matrix D. So, here D1 is 2, D2 is 0, D3 is 1, and finally

D2n is 4.

Then, using our equation:

1 + D1 ∗ q0 + D2 ∗ q1 + ... + D2 n ∗ q2n−1 (16)

1 + (2 ∗ 50 ) + (0 ∗ 51 ) + (1 ∗ 52 ) + (4 ∗ 53 ) = 1 + 2 + 0 + 25 + 500 = 528 (17)

Thus, this algorithm has shown that the entry value for the 6th row and 7th
#»
column is 528. Once this process has been completed for every possible #»
a and b ,
the multimagic square will be complete. This can be a very long process, so for the
use of MATLAB on a computer, see 11 for how to use this algorithm in a computer
program.

Our final multi-magic square for n = 2 and q = 5 can be seen on the next page.

43
 Sheet1

1 88 50 107 69 411 498 435 392 454 196 133 220 152 239 581 543 605 562 524 366 303 265 347 284
32 119 51 13 100 442 379 461 423 485 202 164 246 183 145 612 574 506 593 530 272 334 291 353 315
63 25 82 44 101 473 410 492 429 386 233 195 127 214 171 518 580 537 624 556 278 365 322 259 341
94 26 113 75 7 479 436 398 460 417 139 221 158 245 177 549 606 568 505 587 309 266 328 290 372
125 57 19 76 38 385 467 404 486 448 170 227 189 146 208 555 512 599 531 618 340 297 359 316 253
181 143 205 162 249 591 528 615 572 509 351 313 275 332 294 11 98 35 117 54 421 483 445 377 464
212 174 231 193 130 622 559 516 578 540 257 344 276 363 325 42 104 61 23 85 427 389 471 408 495
243 180 137 224 156 503 590 547 609 566 288 375 307 269 326 73 10 92 29 111 458 420 477 439 396
149 206 168 230 187 534 616 553 515 597 319 251 338 300 357 79 36 123 60 17 489 446 383 470 402
155 237 199 131 218 565 522 584 541 603 350 282 369 301 263 110 67 4 86 48 395 452 414 496 433
361 323 260 342 279 21 83 45 102 64 406 493 430 387 474 191 128 215 172 234 576 538 625 557 519
267 329 286 373 310 27 114 71 8 95 437 399 456 418 480 222 159 241 178 140 607 569 501 588 550
298 360 317 254 336 58 20 77 39 121 468 405 487 449 381 228 190 147 209 166 513 600 532 619 551
304 261 348 285 367 89 46 108 70 2 499 431 393 455 412 134 216 153 240 197 544 601 563 525 582
335 292 354 311 273 120 52 14 96 33 380 462 424 481 443 165 247 184 141 203 575 507 594 526 613
416 478 440 397 459 176 138 225 157 244 586 548 610 567 504 371 308 270 327 289 6 93 30 112 74
447 384 466 403 490 207 169 226 188 150 617 554 511 598 535 252 339 296 358 320 37 124 56 18 80
453 415 497 434 391 238 200 132 219 151 523 585 542 604 561 283 370 302 264 346 68 5 87 49 106
484 441 378 465 422 144 201 163 250 182 529 611 573 510 592 314 271 333 295 352 99 31 118 55 12
390 472 409 491 428 175 232 194 126 213 560 517 579 536 623 345 277 364 321 258 105 62 24 81 43
596 533 620 552 514 356 318 255 337 299 16 78 40 122 59 401 488 450 382 469 186 148 210 167 229
602 564 521 583 545 262 349 281 368 305 47 109 66 3 90 432 394 451 413 500 217 154 236 198 135
508 595 527 614 571 293 355 312 274 331 53 15 97 34 116 463 425 482 444 376 248 185 142 204 161
539 621 558 520 577 324 256 343 280 362 84 41 103 65 22 494 426 388 475 407 129 211 173 235 192
570 502 589 546 608 330 287 374 306 268 115 72 9 91 28 400 457 419 476 438 160 242 179 136 223

Figure 1: Our 25 × 25 Multi Magic Square

44
10 The Next Step

What does the future hold for magic squares? As previously seen, this algorithm
produces a multimagic square, but it only produces one unique multimagic square
for a given n and q. Are there more multimagic squares that can be made with or
without using this algorithm? In other words, does this algorithm produce every
possible multimagic square? These questions are valid, but the research behind
answering them would take a long time and a computer to answer.

11 Applications

What does a math puzzle have to do with the real world? In the opening line of his
article titled "The secrets of solving mathematical puzzles", Matt Parker answers
this question perfectly when he said, "Puzzles are the gateway drug of the world of
mathematics." [16]. Additionally, math puzzles stimulate the brain to a large extent
and are used with dementia and Alzheimer’s patients. The problem-solving aspect
involved in Sudoku is a cognitive exercise that has therapeutic value for people
living with cognitive disorders. The stimulation provided by the puzzle improves
brain function [17]. Puzzles such as Sudoku can teach our world more about not
only math, but problem solving, strategy, and creativity while completing a logic
puzzle.

45
References

[1] The History of Sudoku. GameHouse, RealNetworks, 2013.

[2] Jason Rosenhouse, and Laura Taalman. Taking Sudoku Seriously. Oxford Uni-
versity Press, New York, New York, 2011.

[3] Dominic Klyve, and Lee Stemkoski. Greco-Latin Squares and a Mistaken Conjec-
ture of Euler. Department of Mathematics, Dartmouth College, Hanover, New
Hampshire, 2003.

[4] Serge Ballif. Mutually Orthogonal Latin Squares. February 25, 2008.

[5] Bertram Felgenhauer, and Frazier Jarvis. Mathematics of Sudoku, I. Mathemat-

ical Spectrum, Vol. 39, No. 1, 2006-2007, pp. 15-22.

[6] Regular Triangle Symmetry Group Exploration. Math and the Art of MC Escher,
EscherMath, 2009.

[7] Burnside’s Lemma

[8] Principle of Inclusion-Exclusion. Art of Problem Solving, 2016.

[9] Möbius Inversion Formula. Proof Wiki, 2015.

[10] E. Arnold, S. Lucas, personal correspondence.

[11] E. Russell, and F. Jarvis. Mathematics of Sudoku II. Mathematical Spectrum, Vol.
39, No. 2, 2006/2007, pp. 54-58.

[12] Karger’s Algorithm Wikipedia, 2016.

[13] Möbius Inversion and Lattices. Chapter 6, pp. 1-9.

46
 [14] Agnes M. Herzberg, and M. Ram Murty. Sudoku Squares and Chromatic Polyno-
mials. Notices of the AMS, Vol. 54, No. 6, 2007, pp. 708-717.

[15] Harm Derksen, Christian Eggermont, and Arno van den Essen. Multimagic
Squares. 2008, pp. 1-17.

[16] Matt Parker. The secrets of solving mathematical puzzles. New Scientist, 2012.

[17] John Schmid. Puzzles for Alzheimer’s. March 2012.

Appendix A 11

This appendix includes how to make a multimagic square in the computer pro-
gram MATLAB.
#»
For b and our q, this code outputs the number a that is the bijection of integers
that is seen in Section 9

1 function [ a ] = addiebijection ( b , q )
2 a = 1;
3 for i = 1 : length ( b )
4 a = a + b ( i ) ∗q ^( i − 1) ;
5 end

#»
This code returns another vector that gives the remainder of entries of b when
divided by q.

1 function [ a ] = reductionvector ( b , q )
2 for i = 1 : length ( b )
3 a ( i ) = mod( b ( i ) , q ) ;
4 end
5 a = transpose ( a ) ;
6 end

47
 The following is the code for making matrices A1 and A2. Together A1 and A2
create the generator matrix A. In order to make A1 and A2, it requires inputs of n
and q.

1 f u n c t i o n [ A1 , A2 ] = makeA1A2 ( n , q )
2 A1 ( 1 , 1 ) = 1 ;
3 for i = 2:n
4 A1 ( 1 , i ) = 0 ;
5 end
6 for j = 2:n
7 for i = 1:n
8 A1 ( j , i ) = ( j − 1) ^( i − 1) ;
9 end
10 end
11 A2 ( n , n ) = 1 ;
12 f o r i = 1 : n−1
13 A2 ( n , i ) = 0 ;
14 end
15 f o r j = 1 : n−1
16 for i = 1:n
17 A2 ( j , i ) = ( n+ j − 1) ^( i − 1) ;
18 end
19 end
20 end

The code below is used for finding the matrix X, which is created from the
matrices A1, A2, and B. This code requires inputs of A1 and A2. This is described
in Section 9.

1 f u n c t i o n [ X ] = makeX ( A1 , A2 )
2 A = [ A1 ; A2 ] ;
3 B = [ 2 ∗A1 ; −2∗A2 ] ;

48
4 X = [ A B];
5 end

This code makes the matrix D which is the result of the stacked vector multi-
plied by the matrix X. D is used in Section 9.

1 f u n c t i o n [ d ] = makeD ( a , b , X , q )
2 c = [a;b];
3 d = X∗ c ;
4 d = reductionvector (d , q) ;
5 end

This code uses previous matrices to go through the algorithm and produce the
magic square M.

1 f u n c t i o n [ M ] = makeM( X , q , n )
2 f o r i = 1 : q^n
3 a = makeA ( i , q , n ) ;
4 f o r j = 1 : q^n
5 b = makeA ( j , q , n ) ;
6 M( i , j ) = a d d i e b i j e c t i o n ( makeD ( a , b , X , q ) , q ) ;
7 end
8 end

This is the inverse of the code addiebijection. It requires inputs of i, q, and n.

1 f u n c t i o n [ a ] = {\ c o l o r { red } makeA } ( i , q , n )
2 k = i − 1;
3 f o r index = n : − 1:1
4 a ( index ) = f l o o r ( k/q ^( index − 1) ) ;
5 k = rem ( k , q ^( index − 1) ) ;
6 end
7 a= t r a n s p o s e ( a ) ;

49
 8 end

This function is used to actually make the multi magic square for some given
n and q. Included in our code is that if q < 2 ∗ n − 1 then it will return the error
message (’q too small’). Additionally, if q is not a prime number, then the program
will return the message (’q not prime’).

1 f u n c t i o n [ M ] = makemultimagicsquare ( n , q )
2 i f l o g i c a l ( q < 2∗n − 1)
3 e r r o r ( ’ q too s m a l l ’ )
4 else
5 i f isprime ( q )
6 [ A1 A2 ] = makeA1A2 ( n , q ) ;
7 X = makeX ( A1 , A2 ) ;
8 M = makeM( X , q , n ) ;
9 else
10 e r r o r ( ’ q not prime ’ )
11 end
12 end

50