数字建模-模拟一：数独(陈丽娟、蒋鑫、陈德进).doc

Page PAGE 13 of 14 Team#3 Team Creating Sudoku Puzzles Summary Sudoku puzzle is an attractive game which is very popular in the world now. At current, creating and evaluating the difficulty level of Sudoku puzzles is a significant problem. In our paper we design an algorithm that based on improvement backdating method and can produce different difficulty Sudoku with a unique solution, then evaluate the complexity of it. First, we define the basic operation of finding the smallest candidate number and judging whether the layout is final layout or death layout. On this basis, using the search algorithm minimum candidate number and backtracking exhaustively state space to minimize algorithm complexity. Then, construct a decision tree and use backdating method to define difficulty evaluation from three aspects. The three aspects are the number of known grids in original layout, the smallest known number of each row and each line, the search number in solving the final layout. Through a lot of experiments we endow them with corresponding weights, and use the weights to calculate the difficulty grade of each original layout. Finally, design an algorithm to produce an original layout which satisfies the rules of Sudoku. Solve it and get all the final layouts of it, then use backtracking to seek an original layout with unique solution meeting the chosen difficulty level. key words: the search algorithm minimum candidate; decision tree; weights; backtracking Content TOC \o 1-3 \h \z \u 1. Introduction 3 2. Description and Analysis 3 3. Assumptions 4 4. Symbols and Terms 5 4.1 Symbols 5 4.2 Terms [1] 5 5. Model Design and Solve 5 5.1 Basic Operation [1] 5 5.2 The search algorithm based on the minimum number of candidates 6 5.3 The Measurement for Difficulty Grades [2] 8 5.4 Original Layout Creation[1] 9 5.4.1 Create the original layout having solutions 9 5.4.2 Creat the original layout with unique solution 10 5.6 Analyze the Complicacy 11 5.6.1 Space