What does a vertex in your state traversal tree represent

Assignment Help Data Structure & Algorithms

Reference no: EM132088473

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.

Reference no: EM132088473

Questions Cloud

Create an html web page contains an image : Add a form to your web page from Part 1. The action of the form should be to the formmail.cgi script on the personal web server .

Analyse available purchase methods : MBA404 - Consumer Behaviour and Marketing Psychology - Evaluate alternatives and narrow down the attributes of the FMCG product that satisfy the need or want

What is the predefined class for non-digits : Test that the form is submitted correctly when the quantities are numeric or empty, and that an error message is produced otherwise.

Write a cpu class that has one member function : Write a CPU class that has one member function, ‘Execute,' which simply gets called to execute the process.

What does a vertex in your state traversal tree represent : 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.

What are follicle cells : What are follicle cells? What hormone is secreted by developing follicle cells?

Anatomy and physiology : If a section of a DNA template stand contained the sequence TGAGAC, what would be the sequence of bases of the complementary mRNA strand

Design a database based on client requirements : The volunteer golfers get donors to sponsor them. The donors are asked to pledge a specific amount of money for each hole that the golfer plays.

Complexity stephen carver and harvey maylor : PPMP20014 - Complex Project Management - Complexity Stephen Carver and Harvey Maylor apply a flying analogy of four generic types of management

User Account

All Pages