UserPreferences

Sudoku: History, Theory, & Algorithms

1. Sudoku: History, Theory, & Algorithms

1.1. February 4, 2010

1.1.1. Progress Report

Started writing historical introduction to Sudoku.

Will post it once completed.

1.1.2. Topics Covered in Historical Introduction

Common misconceptions of Sudoku

Belief that Sudoku is a type of magic square
Sudoku is a Japanese logic game

Misconception : Sudoku originated from Japan
In 1984, popularized by Nikoli

first puzzle magazine in Japan

created the name Sudoku
Suuji wa dokushin ni kagiru --> the numbers must be single

Sudoku-like puzzles appeared in French magazines
However, each puzzle was a magic square (1892) and was not Sudoku
The puzzles required arithmetic, not logic to solve.
However, modern Sudoku was designed by Howard Garnes(died 1989)
Magic Squares

arrangement of numbers such that the values of the rows, columns, and diagonals sum to the same number.
For a 3x3 matrix, the magic number is 15.
Magic Sum = n(n*n + 1) / 2

Latin Squares

A nxn table with n number of symbols arranged such a way that each symbol occurs only once in each row and column.
Sudoku: a completed Sudoku puzzle is a type of Latin square with an additional constraint on the sub-grids.

1.1.3. NP Complete Problem Class

NPC Definition for Sudoku:

the problem of determining if a partially filled square can be completed to form a Latin Square

NPC - any given solution to the problem can be verified quickly in polynomial time

No known efficient way to locate a solution

time required to solve the problem using any algorithm increases very quickly as size of problem grows
give an answer in polynomial time for some inputs
Not only the size of problem for Sudoku (the number of puzzles to solve), but the level of difficulty

number of givens determines difficulty level of game

1.2. Jan. 25, 2010

1.2.1. The Beginnings

Beginning to write rough draft of abstract due this Friday.
Layout of Thesis

1.2.2. Introduction

Begin with brief history of Sudoku puzzles and its predecessor, the Latin square.
Define the constraints of the logic game.
Theoretical and Algorithmic approach to Sudoku

1.2.3. Motivation

Why this topic?

Love/Obsession of the game.
Interest in search algorithms.

1.2.4. Abstract

What would I like to study for this thesis?
NP complexity of sudoku

Proof? --> Why is sudoku a NP problem?

Interested in approaches to solving sudoku by computer scientists.

What kind of algorithms to scientists use to solve these puzzles?

Brute Force Algorithms
Constraint Propagation algorithms
Depth-First search algorithms with CP

Also interested in analyzing the complexity of the algorithms

1.2.5. Future Plan of Attack

Complete analysis of Norvig's Sudoku solver algorithm

Run test scripts to determine complexity of algorithm

Improve upon Norvig's algorithm

Create GUI
Also algorithm to exit gracefully when encountering an unsolvable puzzle

Study of human approaches to solving sudoku puzzles.

Logical steps/human approach

Learn Latex and bash
Review dictionaries
Review Depth-First Search
Research constraint propagation

1.2.6. List Resources Here