A Pencil And Paper Algorithm For Solving Soduku

4765 words - 20 pages

A Pencil-and-Paper
Algorithm for Solving
Sudoku Puzzles
J. F. Crook

T

he puzzle Sudoku has become the passion of many people the world over in
the past few years. The interesting fact
about Sudoku is that it is a trivial puzzle
to solve. The reason it is trivial to solve
is that an algorithm exists for Sudoku solutions.
The algorithm is a tree-based search algorithm
based on backtracking in a tree until a solution is
found.
If all a person needs to do is sit down at their
personal computer, punch in the numbers given in
the puzzle, and then watch a computer program
compute the solution, we can reasonably ask why
a person would bother to struggle to solve Sudoku
puzzles. ...view middle of the document...

For example,
Sheldon (2006, p. xiv) names them partnerships,
whereas Mepham (2005, p. 9) names the concept number sharing. Here, we will use the name
preemptive sets, which is more precise from a
mathematical point of view. The theory developed
here applies to Sudoku boards of all sizes.1
1

Sudoku boards can be classified into regular and nonregular boards. The formula for regular Sudoku boards
is: Let m denote the width and height of a Sudoku subboard, where m ≥ 2. Then the width and height of a
regular Sudoku board is m2 . The sizes of regular subboards and boards are given for a few values of m in the
following table:

Definition of the Sudoku Board

Subboard Width
and Height
m
2
3
4
5
6

Sudoku is played on a 9 × 9 board. There are
eighty-one cells on the board, which is broken
J. F. Crook is professor emeritus of computer science,
Winthrop University, Rock Hill, SC. His email address is
crookj@winthrop.edu.
I thank John Hohn, Kathryn Cooper, David Gill, and
Libby Neely for reading my paper. I also thank Loretta
Nethercot for giving me my first two Sudoku books—on
Christmas Day, 2005, and on my seventieth birthday in
2007.

460

Board Width
and Height
m2
4
9
16
25
36

Number of Cells
on the Board
m2 × m2
16
81
256
625
1296

The most common nonregular Sudoku board is the
6 × 6, which consists of six nonoverlapping 2 × 3 subboards. The newspaper USA Today publishes 6 × 6
puzzles regularly.

Notices of the AMS

Volume 56, Number 4

Figure 1. The Sudoku board.

Figure 2. Example of a Sudoku puzzle.

Preemptive Sets and the Occupancy
Theorem
The single most important tool for solving Sudoku
puzzles is based on the definition of the solution
of a Sudoku puzzle.
Definition 1 (Sudoku Solution). The solution of
a Sudoku puzzle requires that every row, column, and box contain all the numbers in the set
[1, 2, . . . , 9] and that every cell be occupied by one
and only one number.
This definition implies that no row, column, or
box will have any number repeated. An example
of a Sudoku puzzle is shown in Figure 2. The more
difficult puzzles can only be solved efficiently by
writing down in each empty cell the possible numbers that can occupy the cell. This list of possible
numbers for each cell is called the markup of the
cell. The markup of the example puzzle in Figure
2 is shown in Figure 3.
We now define preemptive sets, which is the
primary tool for solving Sudoku puzzles up to
the point where either (1) a solution is found or
(2) continuation requires randomly choosing one
of two or more numbers from the markup of an
empty cell.
Definition 2 (Preemptive Sets). A preemptive set
is composed of numbers from the set [1, 2, . . . , 9]
and is a set of size m, 2 ≤ m ≤ 9, whose numbers are potential occupants of m cells exclusively,
where exclusively means that no other numbers in
the set [1, 2, . . . , 9] other than the members of the
preemptive set are potential occupants...

Other Papers Like A Pencil And Paper Algorithm For Solving Soduku

A Service Level Agreement For Provision Of Specified It Services Between Finman Account Management, Llc, Datanal, Inc., And Minertek, Inc

1508 words - 7 pages A Service Level Agreement for Provision of Specified IT Services Between Finman Account Management, LLC, Datanal, Inc., and Minertek, Inc. 1. Period of Service The service level agreement (SLA) is for a period of three years, commencing on July 1, 2011, and concluding on June 30, 2014, with provision for renewal and extension upon agreement of all parties and contingent upon satisfactory fulfillment of specified services, as determined by

Using Material From Item A And Elsewhere Assess The Usefulness Of Modernization Theory As An Explanation For Differences In The Levels Of Development Of Different Societies. (18 Marks)

811 words - 4 pages Using material from item A and elsewhere assess the usefulness of modernization theory as an explanation for differences in the levels of development of different societies. (18 marks) When the Second World War ended, it became clear that countries in Africa, Asia, Latin America and the Caribbean were remaining poor despite exposure to capitalism and the rational scientific ways of thinking that underpinned this economic system. There was

Outline The Process For Developing Nursing Standards Of Practice And Identify The Different Entities That Might Be Involved In Developing A Standard Of Practice

303 words - 2 pages When outlining the process for developing standards of practice the American Nurses Association relies on members as the first link in developing an official resource. Members are nominated to a working group that researches the issue at hand and writes a statement before going to the ANA for final approval. This bottom-up approach ensures the standards are current and accurately represent nurses across the nation (ANA 2014). The Department

Make A Rough Diagram Of Your Office At Your Place Of Work. Label Items In Your Office And Show How They Are Positioned. How Versatile Is Your Office For Handling Every Day Negotiations With...

2766 words - 12 pages underlying interests of the parties rather than their arbitrary starting positions, approaches negotiation as a shared problem rather than a personalized battle, and insists upon adherence to objective, principled criteria as the basis for agreement. The word integrative implies some cooperation. Integrative negotiation often involves a higher degree of trust and the forming of a relationship. It can also involve creative problem-solving that aims to

During My Three-Day Food Intake I Learned About Myself. There Are Many Benefits Of Good Nutrition. ”Medical Online” States “Besides Helping You Maintain A Healthy Weight, Good Nutrition Is Essential...

355 words - 2 pages During my three-day food intake I learned about myself. There are many benefits of good nutrition. ”Medical Online” states “besides helping you maintain a healthy weight, good nutrition is essential for the body and all its system to function optimally for a lifetime.” A healthy diet promotes good sleep, gives the body what it needs to stay healthy, and provides energy. According to “Mealtime Memo” Good nutrition means getting the calories

Entrepreneurship Management - My Employees, Buyers And Suppliers Like Working For My Company Because We Have A Lot Of Wins I Am Not Sure How They Will Take It When Our Company

1032 words - 5 pages Entrepreneurship Management Q1 Seems like a lot of work in writing articles and time in chat rooms. Although it might be a way of getting people to my website with only a small expense, do you think that this approach is worth the investment of time? Q2 What are the other benefits of this approach over and above simple a cost saving Q3 Are there particular businesses and products more suitable for this approach Q1 It is not

New Techniques In Design And Analysis Of Exponential Algorithm

1436 words - 6 pages : Given a set S and target t ,does there prevail a subset such that . 2.1.2 Exponential Time Algorithm Approaches: One exceptional feature to be noted about this problem is that the problem becomes polynomial if the size of S’ is given. For instance an exemplary question may be: Given a cluster of numbers we have to find two elements such that they add up to t

Letters

404 words - 2 pages grown in many ways here and will always treasure the opportunities provided for me by Pencil Corporation. I will be accepting a position as Computer Analyst with Tech Company. While I will miss my friends here at Pencil Corporation feel that it is time for a new challenge and experience. If you have any questions, please feel free to ask. Beat Wishes, Bella

Data Flow Graph Automation Using C-Atlas

877 words - 4 pages Abstract—This paper addresses the topic of methods for producing inter procedural static data flow graphs. The method used in this paper is a sort of progressive mining approach: A start location for the data flow edges is outlined, and through multiple iterations, the forward data flow step operation is taken on the universe, until no new paths have been found. I. INTRODUCTION New tools often provide novel approaches to longstanding

Zzzz Best Company

1260 words - 6 pages trees and processing them up to the splitoff point to yield 30,000 sheets of paper and 30,000 pencil casings is $1,500. Yakima's accounting department reported no beginning inventories and an ending inventory of 1,000 sheets of paper. 19) What is the sales value at the splitoff point for paper? A) $120 B) $1,160 C) $1,200 D) $1,950 20) What is the sales value at the splitoff point of the pencil casings? A) $300 B) $1,480 C) $3,000 D) $3,750

A Person Bad Habits

360 words - 2 pages A person bad habits. Nowadays, there are a lot of people with their own bad habits. Sometimes people begin to notice them and understand that it is not a good and some of them want to solve from them but they can not. There are a lot of kind of a person bad habits such us to glad hair, play with pen and pencil, swing on the chair, interrupt the other people and etc. But we well see only some of them and also some ways to solve from this bad

Related Essays

Project Selection Method And Flowchart For A Project

949 words - 4 pages Project Selection Method and Flowchart for a Project OPS/TM571 October 31, 2011 Project Selection Method and Flowchart for a Project My organization has a handful of customers, but because the product in the field is still immature, I receive a lot of support issues that need almost instant response on root cause analysis. These issues usually come through email or phone calls from the sales engineers. The steps I follow are, once the

Ellen Degeneres Sues Clean Clothes For Misappropriation And Right Of Publicity For The Use Of A Look Alike Model For The Slacks Advertisement. Clean Clothes Countersues For Product Disparagement....

315 words - 2 pages he three parties involved in this business matter are Ellen DeGeneres, Clean Clothes Company and Joseph A. Bank clothing store. Ellen DeGeneres is suing Clean Clothes Company for using her likeness and dance in a commercial video without her permission. The law that Ellen is presented in the court is misappropriation and right of publicity against the Clean Clothes Company. The Clean Clothes Company is countersuing Ellen DeGeneres for product

Regression Analysis: Tutorial For Calculating ‘A’ And ‘B’ Values In Casio Fx991 Es

537 words - 3 pages Tutorial for calculating ‘a’ and ‘b’ values in Casio FX991-ES Step 1: Press “mode” and the go to ‘STAT’ mode (press 3) Step 2: Select 2 (i.e. A+BX), since we are carrying out linear regression analysis Step 3: Now we have enter the values. I will explain you the method with these sample values X Y 1 6 2 7 3 8 4 9 Under the column, ‘X’, press 1 and then press ‘=’ and similarly for entering 2 (press “2” and “=”) and so on. Now for

There's No Room: A Look At Public Schools' Design For Science And Evolution

2088 words - 9 pages There’s No Room: A look at public schools’ design for science and evolution Nicole McCormick PHI103: Informal Logic (GSK1216H) Instructor Micheal Pelt May 21, 2012 The 1987 Supreme Court ruling on the case of Edward v Aguillard, struck down a Louisiana Law requiring “balanced treatment” between “creation science” and evolution. The Supreme Court found “creation science” to be unconstitutional, a statute that forbade teaching evolution