### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# sudoku

No description
by

## mostafa gaafar

on 16 June 2013

Report abuse

#### Transcript of sudoku

Game and Solver

-I. Lynce and J. Ouaknine. Sudoku as a SAT problem. In Proc. of the 9th International, Symposium on Artificial Intelligence and Mathematics (January 2006).

-Wrox-Beginning C# 3.0: An Introduction to Object Oriented Programming.

-Stuart, A. (2006, November 21). Sudoku Solver. Retrieved October 24, 2007, from Scanraid

-Bradley L.Jones, Sams Teach yourself The C# in 21 Days. 2004.

-Bau, D. (2006, September 4). Sudoku Generator. Retrieved October

-Crook, J. F. "A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles." Notices of the AMS 56 (2009): 460-468.

References

Mostafa Labib Gaafar
Mohamed Abd El-Rehim Sultan
Mohamed Hassan Mahmoud
Omar Ayman Ahmed
Kareem Tareq
History of Sudoku

Sudoku is a puzzle that became popular in Japan in 1986 and achieved international popularity in2005.
It is often described as "the Rubik's cube of the 21st century".
Project Members
Time Schedule Plan
2/10/2012
2/11/2012
Research
Background
Requirements
Analysis
02/01/2013
02/3/2013
Programming
1/5/2013
Algorithms
Mostafa Labib Gaafar
Omar Ayman Ahmed
Algorithm
Design
1/4/2013
Mohamed Sultan
Mohamed Hassan
Sudoku Puzzle Generating From Easy To Evil
How to Play
How is the Sudoku game played? You only need to know where you play the game and what your goal is.

The both simple aspects that help you join the game are specified as follows:
Game Environment: you may first get a general overview of this game board in Figure
1.Varying difficulty: essentially, the algorithm should be able to create puzzles in different levels of difficulty.
2. Unique solution: all generated Sudoku puzzles must be guaranteed to yield a unique solution by a solving algorithm.
3. Minimizing complexity: the programs of all these algorithms must finish their jobs in a short time accepted by users or players.
Metrics of Difficulty Level
In this section, we develop a metrics to determine the difficulty level of a Sudoku puzzle from both computing perspective and human logic deducing perspective.
Four factors affecting the difficulty level are taken into consideration in this metrics respectively as follows:
-The total amount of given cells,
-The lower bound of given cells in each row and column,
-Applicable techniques by human logic thinking.
-Enumerating search times by computer
By weighting the above four factors with scores, we grade a Sudoku puzzle in five levels as follows:
Level 1 Extremely Easy
Level 2 Easy
Level 3 Medium
Level 4 Difficult
Level 5 Evil
3. Applicable techniques by human logic thinking
The popular techniques solving Sudoku puzzle using human logic thinking are summarized in [1].
These techniques have been graded in basic, intermediate and advanced levels according to the efforts of logic thinking.
We score all these techniques and grade them into the five levels as Table 3 shows.
4. Enumerating search times by computer
Apart from logic-thinking techniques,
it is verified by our practice that a Sudoku puzzle can be solved by enumerating search within tolerable time.
The computer does a trial that filling an empty cell with a digit from 1 through 9, then check whether the filled digit can meet the three constraints in the game rules.
Digging Holes
The strategy of digging holes method is, as its name implies, to generate a Sudoku puzzle by erasing several digits in confirmed cells of a terminal pattern.
In addition, different mechanisms of digging holes lead to the diversity of constructed puzzles with various patterns or in varying difficulty level.
The sequence of digging holes
The sequence of digging holes regulates that which cell in a terminal pattern is first explored by the operation of digging holes, and which cell is the next.
Four types of sequence are concluded from our quantities of trials as below:
-Sequence 1: Left to Right then Top to Bottom (seen in Figure 5.3 (a))
-Sequence 2: Wandering along “S” (seen in Figure 5.3 (b))
-Sequence 3: Jumping one cell (seen in Figure 5.3 (c))
-Sequence 4: Randomizing globally
Backtracking Generation Algorithm

The basic principle of a backtracking algorithm:

In regards to Sudoku, is to work forwards, one square at a time to produce a working Sudoku grid.
When a problem occurs, the algorithm takes itself back one step and tries a different path.

Essentially it's like walking through a maze with some golden thread and going back and forth down dead ends until you find the right way out.

It's nearly impossible to produce a valid Sudoku by randomly plotting numbers and trying to make them fit.

Likewise, backtracking with a random placement method is equally ineffective.

Backtracking best works in a linear method.

It is fast, effective and reliable if done correctly.

Beside is a basic diagram showing the general flow of the algorithm

Solving Algorithm
One of the most favorite types of algorithms in computer science is recursive backtracking. You can solve complex problems in reasonable amounts of time, with no bookkeeping.
A recursive backtracking algorithm follows a really simple formula:
1.Find a possible solution. If out of possibilities, go up a level.
2.Move to the next cell.
3.PROFIT.
Recursive Algorithms for Better Problem Solving
The term recursive backtracking comes from the way in which the problem tree is explored. The algorithm tries a value, then optimistically recurs on the next cell and checks if the solution (as built up so far) is valid.

Abstract
Our project is to make a Sudoku Game and a Solver, that can help a player or (User) to solve the Sudoku puzzles and it will give much experiences in Sudoku solving in no time.
We are going to show you how we designed our Application and the Algorithm, and How We Implemented the Sudoku Generation and Solving, in Our Game.
Sudoku Game is an intelligent game, so it takes more to work on it .
The name Sudoku is the Japanese abbreviation of a longer phrase meaning "the digits must remain single". Other Japanese publishers refer to the puzzle as Nan pure (Number Place), which was its original title.
Importance of Sudoku Game Solving

Here is a look at more benefits of Sudoku :

When you play Sudoku over long periods of time, your capability of thinking logically and critically improves.
Sudoku does not require the use of any special calculations or math skills.
It is a fun and captivating game that has a distinctive solution that is reached logically devoid of guessing.
Developing and enhancing logical and critical skills helps children solve other problems effectively

We define several basic components of the board as Figure illustrates.

The whole board is actually a 9-by-9 grid made of nine smaller 3-by-3 grids called blocks.
The smallest unit square is called a cell which has two types of states:

empty, and confirmed by a digit from 1 through 9.
We mark the whole gird with rows and columns from top-left corner.
These limitations for placing digits in three locations are respectively called row constraint, column constraint and block constraint.
Logical skills
Develops patience
There is always a great feeling after you have successfully completed any puzzle. Nevertheless, patience is required for outsmarting the tricky and challenging Sudoku.
This aids to develop temperament in players, especially as you move to advanced levels of Sudoku

Enhances mental sharpness
Scientists recommend Sudoku for every person as it improves mental sharpness significantly. It has been proven that we require about ten to fifteen hours daily of effective mental exercise to properly enhance mental sharpness.
Even for elderly people, this numbers game is also beneficial since it keeps them alert, thereby adding worth to their lives.

Provides good alternative
Introducing children to Sudoku offers a very good alternative to spending time from digital devices like the TV, computers and video games.
Sudoku offers an enjoyable, educational and productive past time that will benefit the children. It may even enhance their mathematical skills and confidence after extensive use.

Sudoku Game And Solver
Recursive Backtracking
How Did We Begin ?!
The First thing we did is making analysis
on our Project Idea , and how it can be Designed and Implemented and we are going to show you how we did .

Adobe Photoshop was Chosen for designing
the Graphical Interface because :
- it is Easy to design and easy to learn
- It is Easy in Linking
- Can be Compatible with Almost every
Programs format
-Images can be Saved
at almost all formats

The Tools used
for
Implementation
we are going to show what tools we used to make our project and how did we
use them.
Microsoft Visual Studio
The Programming language Used Is C#
Microsoft Visual Studio is a workspace for programming
We Chose Microsoft Visual Studio ( C# ) Because :
It is Object Oriented
Better Data Types , C# Libraries are included in Visual Studio and doesn't need download.
Properties & Events are better in C#.
We have a Background about Microsoft Visual studio and how it can be used
Application Design
And
Implementation

Graphical Interface
The Graphical Interface is Consisted of Two
Major Steps :
1) Designing the graphical shape on Adobe
Photoshop.
2)Implementing the graphical shapes on
Microsoft Visual Studio Windows Forms,
and linking them together and here are some
screen shots that describes that process :
-Screen shot for designing the
Game play Form Shape on Photoshop
-Screen shot for designing the
Game play Form Shape on
Microsoft Visual Studio
photo shop's Graphical design on
Microsoft Visual studio's Forms
Function Requirements

2) players can play a new game and save game and continue a unfinished game(load Game).
3) The application contains a help (How to Play) menu with the rules of the game.
4) number Generation : user will have a one in one thousand chance of having a puzzle repeat.

5) Puzzle generation is dependent on the difficulty setting from the main menu.

6) The numbers are inserted by the user in the cells using a scroll bar from 1 to 9.

7) Player can (show answer) when he does not know how to continue with the game.

8) Application can Solve all the Puzzle in No time with right answer.

9) The Application Shows a Sign if a Number is (wrong) or duplicated within a row or column .

10) A Timer is executed in the beginning of the game to calculate the time taken to solve the puzzle.

11) When timer is paused , player cannot put inputs in the cells .

Non Functional Requirements
1. The interface of the application should be attractive and enjoyable.
2. Navigation through the application should be easy and obvious.
3. Dialogue boxes and error messages should be obvious.
4. The application must be easy to learn and easy to use for the end user.
5. The application must provide an easy to read user manual.

6. The application should respond to a user’s requests in a reasonable time.

Software System Requirements
Operating system : "Microsoft Windows 7 or Above"
Processor : 1 Gigahertz (GHZ or faster 32 - bit (x86)
or 64-bit(x64)
RAM : 1 gigabyte (GB) (32-bit) or 2 GB RAM (64-bit)

Available Hard Disk Space :100MB (32-bit) or 200MB (64-bit)

DirectX 9 graphics device with WDDM 1.0 or higher driver
Task analysis is used to determine how the users interact with our application.
Description of use cases
A use case is the task that a user wants the application to perform.

1) Create new puzzle:
It allows the user to create a new puzzle depending on a difficulty the user chooses or to enter a custom typed in puzzle.
It allows the user to open and load a puzzle from a file.
3) Save puzzle:
It allows the user to save the current puzzle with its given entries into a file.
4) Solve puzzle:
It allows the user to show the solution of the puzzle.
5) Play puzzle:
It allows the user to fill the empty cells of the puzzle and display a message if the user successfully solved the puzzle.

Future Work
Karim Tareq
In Our Project we used sequential algorithm and programming techniques.

In the future, we can make a challenge and implement correct parallel version on the three separate algorithm will not be trivial.

The back tracking algorithm will need to consider how to distribute the work optimally on the other hand the rule based algorithm we will need to consider balancing between distributing.

Make A Statistics Option to the Game
We can Also Make A Statistic Option in the Game ( High Scores Menu ) ,So User can play the puzzles and define his progress in playing the game , and comparing his results with other players so it can have the competitive gaming method , it was planned to be done but it was not because of lack of time.
Import Puzzles
A User can Input Puzzles that he did not know how to solve ,So the Game Solver can Solve it .
Game Sequence Design
25/11/2012
Graphical
Interface