Sudoku Java project - part 4

ANALYSIS DOCUMENT

SYSTEM ANALYSIS

Brute Force Solving Method

A simple way to solve a Sudoku puzzle is to simply trying each blank square with the numbers 1 to 9 until a valid solution is found. I ended u p devising three different implementations of this method as shown below

Method 1

The first and most naive solver starts at the top-left square and moves rom left to right top-to bottom filling each blank square with a number 1 to 9 until the grid is invalid (that is, a number is duplicated in a row.column or If the grid 3x3 region) or until the grid is filed and that is solved is invalid, the solver will backtrack until it is and continue forward again.

Method 2

Domain Concept

The second implementation introduces the concept of 'domains'. Each square in a grid has a domain of up to 9 values (1 to 9) that is reduced a according to numbers already present in the intersecting row, column and region.

In this grid, we can reduce the domain of the top-left square to (1,4} since 2 and 3 already appear in the first column.

Likewise, we can restrict the domain of the top-right square to (2). Since 3 and 1 occur in the rightmost column and 4 appears in the top-right region.

This solver acts in the same way as the previous implementation except that it restricts the domains of the grid before it starts, only using numbers present in the initial domains. While the domain restriction require s computation, it should result in significantly less backtracking to find t the solution of a graph, illustrating the process

Research Methodology

Requirement for User

The basic requirement was to create a simple Sudoku game, where user can able to get different puzzles, able to check and get solution for those puzzles, able to get solution for their own puzzles. Considering this requirement a simple 9x9 grid layout has been made and discussed with the users to find out what exactly they expect the user interface to be. Some of the questions which are raised during the discussion are.

❖ Layout

❖ Interaction either from mouse or keyboard

❖ Type of menus

❖ Resizable window or not

❖ Kind of help support

❖ Timer

Logic behind Sudoku:

The Generator is for creating qualified Sudoku arrays. Combining with the Silver, we could start to make your own Sudoku puzzles. The main technique in this algorithm is using permutations, based on one qualified pattern to enumerate qualified Sudoku arrays. Here, we only use Band permutations (3! times variations), Row permutations within times variations), Stack permutations (3! Times variations), a band (3! and Column permutations within a stack (3 times variations) to get the arrays Finally, put the qualified Sudoku array into a text file. (Ex: 3! =3*2*1=6 ---123,132,213,231,312 321).

Sudoku Database

This part of the system comprises the collection of puzzles obtained from different sources in a text file. The system also allows the user to store and retrieve the unfinished puzzles.