-
Notifications
You must be signed in to change notification settings - Fork 0
/
Algorithm.doc
37 lines (34 loc) · 2.08 KB
/
Algorithm.doc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Introduction
Sudoku is a puzzle of 9x9 numbers. There are 9 columns and 9 rows in a Sudoku. The Sudoku is further divided in to 9 equal boxes. To solve a Sudoku, each column, row and box should have a permutation of numbers from 1 to 9. There are different algorithms to solve a Sudoku such as: Backtrack solver, Rule based solver, and Boltzman machine. However in this book we use the combination of backtrack and rule based algorithm.
Definitions
Cell: Cell is the smallest square in the Sudoku puzzle. There are
81 cells in the puzzle.
Box: A box is a square consisting of 9 cells (3x3). There are 9
boxes in the puzzle.
Poss: Possibility of numbers in a cell which will not conflict
with row, column or the box which the cell is in.
Algorithm
1) Insert the Sudoku. In place of empty cell insert a zero.
2) Call Read function: Read the Sudoku
3) Call Validate function: Validates the input Sudoku(su_in)
i) Check the conflicts of possible numbers in boxes, rows and columns.
4) Call Display function: Displays the input Sudoku.
5) Solve function: Initialize all possibilities in an empty cell.
i) Call Eliminate function: Eliminate all conflict
possibilities.
ii) Call Assign function: Assigns possibility if
only one possibility is present in a cell, row or a box.
iii) Call Check function: Check whether the Sudoku is solved.
If true return to main function else continue the loop.
iv) Loop (while time<10 sec):
a. Call the Guess function: Find the best cell with least possibilities.
b. Call Backup function: Back up the initial state of the Sudoku with possibilities, before performing the guess.
c. Perform the guess: Assign the first possibility of the best cell to output Sudoku (su_out).Guess_No++;
d. Loop while 10 times: Eliminate function, Assign function.
e. Loop until Conflict function: returns 0:
1.Guess_No--;
2.Call Backtrack function:
a) Call Restore function:
b) Eliminate the failed possibility.
f. Call Check function: If it returned 1, break.
6) Check the output. If solved>Display function: output. Else display> not solved.