UserPreferences

Sudoku

1. Sudoku: History, Theory, & Algorithms

Michelle Beard Advisor: Deepak Kumar Senior Project 2010

1.1. February 9, 2010

To show a decision problem is NPC

Show that the problem is NP

Non-deterministic process that generates a possible solution to the problem.
Look at the output of above and determine if true solution.
Loop if not true

Show that a known NPC problem can be transformed to the problem in question in polynomial time.

Graph Coloring --> Sudoku in polynomial time

1.2. February 8, 2010

1.2.1. Progress Report

Frankly did not do as much research as I would have liked to do. And this week it doesn't look good either.
For another class, need to write an C# application for the Microsoft Surface table.

Maybe thinking of writing a Sudoku app for the surface and incorporate that into my thesis.

Still not understanding the difference between NP and NPC
While it has all ready be proven that Sudoku is a NPC problem, would like to understand why that is
This and next week: begin writing rough draft of thesis

I can write most of it all ready except for parts on the theory since that is harder to understand

Started to read many of my sources and begin to write literature survey
Extended abstract (6-8 pages) due this week!

1.2.2. All about the NPC

A major aspect of my thesis is understanding what is the best algorithm to solve a Sudoku puzzle.
However, there really is no optimal solution

only can search through all possible designs
basically prove that NO algorithm can possibly solve a Sudoku puzzle quickly.
most interested in a general algorithm to solve all Sudoku puzzles other than an exhaustive search

Algorithm to solve all Sudoku puzzles? Not yet determined/proved by experts

However, there are strategies that work well in some instances on a sudoku board

Checking row/column
Elimination, etc can solve easy to medium puzzles
Need advanced techniques to solve harder puzzles.
Thus, can tell not one technique can solve all Sudoku puzzles

Complexity Classes

P Class

deterministic polynomial time complexity
tractable
can get an exact solution to a problem in a reasonable amount of time (polynomial)

NP Class

non-deterministic time complexity
intractable
currently no algorithm that will solve the problem in any reasonable amount of time
2 Step Process for NP

NP process that generates a possible solution to a problem

like a random guess (good/bad) optimal solution

Look at output of 1) and determine if it is a true solution

While both steps run in polynomial time, we don't know how many times this process will be repeated before we get a solution

individual steps are polynomial, but calling them can be exponential or n factorial time

NPC Class

hardest of problems in class NP
the problem of determining if a partially filled square can be completed to form a Latin Square
given a Sudoku puzzle and an intended solution, it is NPC to determine whether there is another solution

We can not determine in polynomial time whether or not there is another solution to the instance of a Sudoku puzzle

can search "forever" and not find one

testing uniqueness of Suduoku solutions to an partially filled Sudoku board is also NPC.

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
Size of problem for Sudoku (the number of puzzles to solve)

the placement of the numbers in the grid --> difficulty
number of givens does not determines difficulty level of game
Solve puzzle by changing size of board. Ex: 9x9 puzzle; easy to solve with computer < few seconds

nxn puzzle? How long will algorithm solve problem when n becomes larger?

1.3. February 4, 2010

1.3.1. Progress Report

Started writing historical introduction to Sudoku.

Will post it once completed.

1.3.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
Each sudoku puzzle has one unique solution

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.
July 6, 1895, Le Sičcle's rival, La France
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.
$http://upload.wikimedia.org/math/f/5/4/f54c868d5fe682d273dfaaf4c20c67ec.png$
Sudoku: a completed Sudoku puzzle is a type of Latin square with an additional constraint on the sub-grids.

Unique Solution

To be a proper Sudoku puzzle, it has to have a unique solution.
Puzzles that do not yield a unique solution are not considered a proper Sudoku puzzle.

Remember the logic rule of Sudoku + no guessing?

A Sudoku puzzle with more than one solution requires trial and error which is not the logical way to solve a proper Sudoku puzzle.

1.4. Jan. 25, 2010

1.4.1. The Beginnings

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

1.4.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.4.3. Motivation

Why this topic?

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

1.4.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.4.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.4.6. List Resources Here