用Backtracking算法来解Sudoku游戏，整个作业分为三种难度，解Sudoku时间需要在10秒内。BackgroundSudoku is a puzzle that has gained much popularity since its first release in a US Newspaper in 2004. The object of the original Sudoku is to fill in a partially-completed 9x9 grid with numbers 1-9 such that each row, column, and the nine 3x3 sub-grids contain no duplicate numbers. In this assignment, you will implement a variation on Sudoku where, instead of filling the grid with numbers, you will fill the grid with words. You will be given a word bank, or a list of words that must be used exactly once (unless otherwise specified), and you must arrange them so that every cell in the grid contains a letter. Note that words will take up multiple cells in the grid and can be oriented either horizontally or vertically, and words are allowed to overlap. Following the rules of Sudoku, each row, column, and 3x3 cell cannot contain duplicate letters. To familiarize yourself with this game, we recommend playing it for yourself at http://dkmgames.com/WordSudoku.htm. The only difference between the online game and the game in this assignment is that in the online version, you are given the orientation of the words, but in this assignment, your code must be able to determine this for itself.Word Sudoku gameThe word bank will contain one word per line. The grid files will contain nine lines of nine characters each. If the character is an underscore “_”, assume that the letter that goes in that cell is unknown. Otherwise, assume that the character belongs in the corresponding grid cell.Your task is to implement backtracking search to solove the puzzles below. First, you need to determine your formulation of the CSP and include it in your report. What are the variables, domains, and constraints in your formulation? With these in mind, implement any ordering heuristics that make sense for your formulation to make your search efficient. Briefly describe your implementation.For each of the inputs below, please include in your report:Your solution, the filled 9x9 grid that satisfies all the constraints. Please either include an image of the filled grid, or inline it in a monospace font (Courier New, for instance).In order, the sequence of assignments made, where each assignment contains the word, the coordinate of the top/left letter, and the orientation. Please follow the format in the example file, corresponding to the sample grid above. The lines are formatted as O,R,C: WORD, where O is the orientation (either H or V) and R and C are the row/column for the top-left coordinate of the first letter in the word. If you did not place this word on your grid (see Part 3), use (N/A) instead.The number of nodes expanded in the search tree. A state (either a partial or full set of assignments) is considered expanded when its children states, if any, are computed. This definition is equivalent to the definition of expanding a node in a search tree.The execution time of your search algorithm, in seconds or milliseconds.Input 1 (for everybody): Start Grid with HintsIn this input, some of the cells in the grid will already be filled in for you.Input 2 (for everybody): Empty Start GridSolve another puzzle this time, except that unlike last time, you will not be given hints in the starting grid.Input 3 (for four credits only): Decoy WordsIn this puzzle, you will be given a word bank and a non-empty start grid. The challenge here is that some of the words in the word bank (you don’t know which ones) will not be used in the final solution. You will need to find which words should be placed and which ones shouldn’t. Your solution should place as few words as possible. This requires traversing the entire search tree and generating all possible solutions, so think carefully about how you want to implement this in order to achieve a solution in a decent amount of time. In your report, briefly describe any modifications to your implementation you needed to make, and as part of your solution, also include in your sequence of assignments the words that were not placed, according to the notation above.本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论