Describe how you plan to search for the sudoku solution

Assignment Help Data Structure & Algorithms

Reference no: EM131099741

• Specifically, your company has asked your team to design an app that will complete a Sudoku game, given any starting state of the game. See this Web sitefor the rules. https://www.sudoku.com/

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?

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.

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.

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: EM131099741

Questions Cloud

Question regarding the male chromosome : A geneticist conducts her survey and calculates hat p = 0.512. Which of the following is the most correct interpretation of this statistic? a) There is a 51.2% chance that a randomly selected gamete cell will have the male chromosome.

Ece 472-561 robotics and vision : Devise a wire frame representation of a house. Specifically, the house is represented by 10 or more vertices in world coordinates. Simulate a camera and compute the pixel coordinates for each vertices. Draw the house using these pixel coordinates and..

If demand surges and pushes up the market price : If demand surges and pushes up the market price to $20, industry-wide output will rise IN THE SHORT RUN due to..

Formulate the null and alternate hypothesis : (1) In this exercise how would you formulate the null and alternate hypothesis? Is this a one-tailed test, or a two-tailed test? (2) Based on the output, can we conclude at the 5% level of significance that the machine used in shift 1 overcuts the ce..

Describe how you plan to search for the sudoku solution : 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?

Calculating the benefits and costs from the merger : Two Cournot duopolists produce in a market with demand P = 100 − Q. The marginal cost for firm 1 is constant and equals 10. The marginal cost for firm 2 is also constant and it equals 25. Given this information, would you recommend the merger? Explai..

Flagging my words against a french dictionary : Right in the middle of a Word 2007 document I am typing, Word started flagging my words against a French dictionary. Why? How can I turn this off? I've changed my default language to English (U.S.), but that applies to future documents. Thanks.

Equal access to coolness for all coalition : Assume that consumers are uniformly distributed along a one-mile stretch of beach. A number of ice cream vendors are pondering where to position their carts. If the price they are allowed to charge is fixed by the Equal Access to Coolness For All Coa..

Consider firm with the production function : Consider a firm with the production function, q = (K^(0.5) + L^(0.5))^2. In the short-run, the level of capital is fixed. Determine the equations for MPL and APL. Solve for the short-run cost function (i.e. total costs as a function of output) Solve ..

User Account

All Pages