Transcript Sudoku

Sudoku
Introduction
• In this presentation I will cover the Sudoku
puzzle, some basics of its complexity as well as
specifically discussing the complexity of order
2 and order 3 Sudoku puzzles. I will also show
and discuss the beginnings of NDFSMs for
order 2 Sudoku puzzles and order 3 Sudoku
puzzles to determine if a solution is correct.
Rules
• Most commonly, a sudoku puzzle is a 9x9 grid
of the numbers 1-9 where in each row,
column, and 3x3 grid each number is only
used once.
• This is an “order 3” sudoku – an order n
sudoku would be an n2xn2 grid of the numbers
1-n, with n2 nxn grids.
Example
7
3
3
6
5
6
8
4
7
7
6
3
8
7
6
2
9
9
1
1
1
5
8
2
4
6
2
4
8
5
5
2
5
9
7
4
Solution
1
5
7
3
8
9
6
2
4
3
2
4
5
6
7
9
8
1
9
6
8
1
4
2
3
7
5
8
7
3
4
5
6
2
1
9
4
9
2
7
1
8
5
6
3
5
1
6
2
9
3
7
4
8
7
3
5
8
2
4
1
9
6
2
4
9
6
3
1
8
5
7
6
8
1
9
7
5
4
3
2
How complex is it?
• For an order 3 sudoku you just have to be able
to count to 9, so how hard are they really?
• How many different answers can there be?
Order 2 sudoku
• For order 2 sudoku puzzles there are 288
possible answers
• When symmetries are considered there are
actually only 2 distinct puzzles with the
remainder being some variation
Order 3 sudoku
• For order 3 sudoku puzzles there are
6,670,903,752,021,072,936,960 possible
combinations
• Symmetrical operations only reduce this to
3,546,146,300,288
Beginnings of an order 2 DFSM
Basics of an order 3 DFSM
More complex data structure
• 2 dimensional array for checking
– Number the columns, rows, and interior grids
– Boolean
• 2 dimensional array for solving
– Number the columns, rows, and interior grids
– Each cell has a linked list of possible values
– Some sort of relationship among the rows,
columns, and grids to identify what cells are
affected by a change in each
Conclusion
• If you can solve sudoku puzzles you’re a
genius!
• Both a human or computer would take a
different approach to solve or verify a
solution, as FSMs are probably not the best
way to approach the problem
References
• “A Pencil-and-Paper Algorithm for Solving
Sudoku Puzzles” J.F. Crook
http://www.ams.org/notices/200904/tx09040
0460p.pdf
• American Scientist “Unwed Numbers” Brian
Hayes
http://www.americanscientist.org/issues/issu
e.aspx?id=3475&y=0&no=&content=true&pag
e=4&css=print