**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

Modern Academy In Ma'adi Computer Department

A Propsed Project For Graduation

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**

Task By :

Mostafa Labib Gaafar

Omar Ayman Ahmed

Algorithm

Design

1/4/2013

Task by :

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

Our Tasks

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 CS6

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

- Screen shot for linking the Adobe

photo shop's Graphical design on

Microsoft Visual studio's Forms

Function Requirements

1) The main menu contains four navigational buttons link to the new game, load Game, options, and how to play.

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

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.

2) Open puzzle (Load Game):

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

Task By :

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

Linking

and

Documentation

20/5/2013

Testing

and

Presentation

10/6/2013