Part 2a: State Space Describe how you plan to search for the Sudoku solution giv

Question

Part 2a: State Space

Describe how you plan to search for the Sudoku solution given a starting state.

Clearly define your state space here: What does a vertex in your state traversal tree represent?

Part 2b: Traversal Time Complexity

Assuming you were to naively traverse your state space, what is the upperbound time complexity (in terms of Big-O) of a brute force searching algorithm?

Present this result in terms of n and p where nxn is the size of the Sudoku board and p is the number of possible numbers (1–9) permitted in a square.

Part 2c: Heuristic Search

What type of heuristic search would you employ to search this state space in hopes to reduce the search time?

Think about the problem and how you might search this state-space tree.

Part 2d: Pseudocode

Create pseudocode that finds the solution to a Sudoku game using a brute force search or using your heuristic discussed above.

To simplify this task, assume that you have standard data structures available to you, such as stacks and queues.

Explanation / Answer

Describe how you plan to search for the Sudoku solution given a starting state.

The plan for searching for the sudoku solution with given starting state involves following steps:

i) For searching for solution we will adopt the heuristic search method because its provide the effective solution over other other traditional method like tree based search
ii) After selecting the search method as heuristic, we will try to find out the cell that having the small number of the digit. With small number of digit there will be less chances of collision. And accordingly we will proceed further.

What type of heuristic search would you employ to search this state space in hopes to reduce the search time?

We can think of following two heuristic search techniquies.
1) Blind Search Technique (Direct Technique)
2) Weak Technique

In above mentioned techniquies the first "blind search technique" is not every where possible and also its required more efforts in term of time as well as money, so we can not go with this technique. We will select "Weak technique" due to following reasons:

i) Its more effective
ii) Required less memory as well as time if applied correctly

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.