Mathematics of Sudoku.pdf

(3901 KB) Pobierz
Mathematics of Sudoku: Enumeration of the
16
×
16
Magic X Sudokus
A Major Qualifying Project Report:
submitted to the Faculty
of the
WORCESTER POLYTECHNIC INSTITUTE
in partial fulfillment of the requirements for the
Degree of Bachelor of Science
by
Ethan Thompson
Date: April 27, 2006
Approved:
Professor Brigitte Servatius, Major Adviser
Abstract
A 16
×
16 Magic X Sudoku is a Sudoku with the additional constraints that each block is a Magic
Square and each number appears once on the two long diagonals. Nine binary orthogonal symmetries
were discovered, for a reduction of the solution space by a factor of 512, and 1 non-orthogonal binary
symmetry, which further reduces the problem by a factor between 1 and 2. Enumerating the 16×16 Magic
X Sudokus requires significantly more computational resources than available even after optimization.
ii
Acknowledgments
Brigitte Sevatius, for encouraging me to follow my mind
as it wanders to new vistas, both in this endeavor and other.
Kathi Fisler, without whom Branch would still be a toy language of little value.
And to all those who serve as sounding board and compass while I wander.
iii
Contents
1 Introduction
2 Definitions
3 Simple Observations
4 Symmetry
5 Branch
6 Results
A Presentation
B Code
1
2
3
4
7
10
13
28
iv
1
Introduction
How many 16
×
16 “Magic X Sudokus” are there? Answering this question is, to the best
of anyone’s knowledge, equivalent to enumeration all the solutions: Takayuki Yato proved
the NP-completeness of Sudoku [Yat03], and no results suggest Magic Squares are otherwise.
As the question is equivalent to enumeration, heavy use of computers is needed to have any
hope of success. Even fast computers can have trouble on NP hard problems however, and
the size of the solution space, 16
256
, or about 1.8
∗
10
308
, dwarfs the processing power of any
current computer. Therefore a great deal of reduction is needed, and while much of it is easy,
by the use of specific types of computer algorithms in the constraint satisfaction field, these
are not enough because of the NP nature of the problem. Other, more complicated ways
to reduce the computation are needed. More difficult to encode, the representation of only
one element of the symmetry (automorphism) group can be a potential great help, rendering
many problems that otherwise are too slow feasible. The question remained whether this
problem was one of those made possible though careful use of the symmetry group would
render this problem possible. Though similar enumeration problems existed, Sudoku is new
enough that little work has been done in this area, and while a useful guideline, the work on
enumerating Sudokus has focused mostly on the 9
×
9 Sudoku, which has decidedly different
symmetries.
I arrived at this particular problem for this project in large part due to background: I
had done work in all 3 of the major parts involved. I was attempting to finish work for
my CS MQP on Branch, the programming language used for all the coding involved in
this investigation. Though that project is still unfinished as of this writing, I intend to
return to it, among other things using this problem as my guiding problem for the future
development of the language. I was already familiar with Sudokus, having been caught in
the current craze of solving them. Though I knew these two fit together well, it was the
Magic Square component that finally cemented the problem. I had, over the past five years,
been intermittently working at enumerating magic squares, culminating in my discovery of
the “Ring Swap” symmetry, and the listing of all 5
×
5 magic squares in a half hour. Even
more tantalizing was a surprise, and ultimately incorrect, conjecture: in hopes of reducing
the complexity of the problem slightly, I added the constraint known as an “X Sudoku”, and
proceeded to find no 16
×
16 Magic X Sudokus. In the end it was due to their relative rarity,
not a complete absence, and a fluke in the ordering of earlier search algorithms. In finial
tally, there are still too many, not too few, as enumeration requires too much computational
power.
1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin