北美代写,Homework代写,Essay代寫-准时✔️高质✔最【靠谱】1.1. Aims. The purpose of the assignment is to: ? design and implement an interface based on the desired behaviour of an application program; ? practice the use of Python syntax; ? develop problem solving skills. 1.2. Submission. Your program will be stored in a file named sudoku.py. After you have developed and tested your program, upload it using Ed (unless you worked directly in Ed). Assignments can be submitted more than once; the last version is marked. Your assignment is due by August 9, 10:00am. 1.3. Assessment. The assignment is worth 13 marks. It is going to be tested against a number of input files. For each test, the automarking script will let your program run for 30 seconds. Late assignments will be penalised: the mark for a late submission will be the minimum of the awarded mark and 13 minus the number of full and partial days that have elapsed from the due date. The outputs of your programs should be exactly as indicated. 1.4. Reminder on plagiarism policy. You are permitted, indeed encouraged, to discuss ways to solve the assignment with other people. Such discussions must be in terms of algorithms, not code. But you must implement the solution on your own. Submissions are routinely scanned for similarities that occur when students copy and modify other people’s work, or work very closely together on a single implementation. Severe penalties apply. 1 2 2. Background A sudoku grid consists of 9 lines and 9 columns, making up 81 cells, that are grouped in nine 3x3 boxes. In a sudoku puzzle, some but not all of the cells already contain digits between 1 and 9. Here is an example of a sudoku puzzle. 1 9 8 6 8 5 3 7 6 1 3 4 9 5 4 1 4 2 5 7 9 1 8 4 7 7 9 2 Solving a sudoku puzzle means completing the grid so that each digit from 1 to 9 occurs once and only once in every row, once and only one in every column, and once and only once in every box. For instance, the previous puzzle has the following solution. 3 3 4 1 9 2 7 5 6 8 6 9 2 1 8 5 7 3 4 8 5 7 4 6 3 1 9 2 1 3 4 2 9 6 8 7 5 2 7 8 5 3 4 6 1 9 5 6 9 7 1 8 4 2 3 4 2 5 3 7 1 9 8 6 9 1 6 8 4 2 3 5 7 7 8 3 6 5 9 2 4 1 Solving a sudoku puzzle is a very common assignment; it is not difficult and moderately interesting as a “solution” (the completed grid) tells nothing about how the solution was reached. More interesting solvers are logical in the sense that they (possibly partially only) solve the puzzle in steps and at every step, explain how they made some progress; they do so by using some of the well known techniques that most people who solve sudoku puzzles apply. Two remarks are in order. ? Methods that only discover digits in empty cells are fairly limited; most methods need to keep track of the list of possible digits that can go into a given cell, and making progress might mean reducing that list. To apply techniques of the second kind, it is necessary to first mark the grid. ? Often, it is not possible to completely solve a puzzle using exclusively the chosen methods; at some point no progress can be made and then a random guess has to be made to either put a digit into a given empty cell, or to remove a digit from the list of possible digits that can go into a given cell. It might subsequently be necessary to backtrack and make alternative guesses if the earlier guesses turn out to be inconsistent with a solution. For this assignment, you will have to implement two such techniques, based on the notions of forced digits and preemptive sets described in the paper A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles by J. F. Crook, Notices of the AMS, 56(4), pp. 460–468. Before anything else, you should study this paper. The forced digits technique is applied first, followed by the preemptive set technique. When no progress can be made, the forced digits techniques could be applied again, but that might not yield anything; an alternative would be to try and fill some empty cell with one of the possible digits for that cell and apply the preemptive set technique applied again, knowing that that guess might prove wrong and that other possible digits might have to be used instead. In this assignment, we will stop at the point where the preemptive set technique can no longer be applied; hence we can expect that our implementation will only partially solve most puzzles. But the technique is very powerful and as explained in the article, subsumes many of the well known techniques. You will design and implement a program that will read a sudoku grid whose representation is stored in a file filename.txt and create a Sudoku object, with a number of methods: 4 ? a method preassess() that prints out to standard output whether the representation is correct and has no digit that occurs twice on the same row, on the same column or in the same box; ? a method bare_tex_output() that outputs some Latex code to a file, filename_bare.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid; ? a method forced_tex_output() that outputs some Latex code to a file, filename_forced.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits technique has been applied; ? a method marked_tex_output() that outputs some Latex code to a file, filename_marked.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits technique has been applied and that has been marked; ? a method worked_tex_output() that outputs some Latex code to a file, filename_worked.tex, that can be compiled by pdflatex to produce a pictorial representation of the grid to which the forced digits technique has been applied, that has been marked, and to which the preemptive set technique has been applied. The input is expected to consist of 9 lines of digits, with possibly lines consisting of spaces only that will be ignored and with possibly spaces anywhere on the lines with digits. If the input is incorrect, that is, does not satisfy the conditions just spelled out, then the program should generate a SudokuError with Incorrect input as message. Here is a possible interaction: $ python3 ... >>> from sudoku import * >>> Sudoku('sudoku_wrong_1.txt') ... sudoku.SudokuError: Incorrect input >>> Sudoku('sudoku_wrong_2.txt') ... sudoku.SudokuError: Incorrect input >>> Sudoku('sudoku_wrong_3.txt') ... sudoku.SudokuError: Incorrect input
Note: Be sure to adhere to the University’s Policy on Academic Integrity as discussed in class. Programming assignments are to be written individually and submitted programs must be the result of your own efforts. Any suspicion of academic integrity violation will be dealt with accordingly. Objective: Expressing the problem as a search problem and identifying proper solving methods. Specifying, designing and implementing uninformed & informed search methods. Assignment Details: In this programming assignment you will implement a set of search algorithms (BFS, DFS, Greedy, A*) to find solution to the sliding puzzle problem: Theoretically solving the problems as a search process includes progressive construction of a solution: ? Establish the problem's components o Initial state o Final state o Operators (successor functions) o Solution ? Defining the search space ? Establish the strategy for search a solution into the search space. Let’s start by defining the sliding puzzle problem: For a given puzzle of n x n squares with numbers from 1 to (n x n-1) (one square is empty) in an initial configuration, find a sequence of movements for the numbers in order to reach a final given configuration, knowing that a number can move (horizontally or vertically) on an adjacent empty square. You will solve the puzzle for size n = 2 (2 x 2 squares), 3 (3 x 3 squares) and 4 (4 x 4 squares). The final configuration/goal state for each puzzle of size n is as follows: Important: Solvability of the sliding puzzle problem Not all initial boards can lead to the goal board by a sequence of moves, including these two: Remarkably, we can determine whether a board is solvable without solving it! To do so, we count inversions, as described next. ? Inversions: Given a board, an inversion is any pair of tiles i and j where i < j but i appears after j when considering the board in row-major order (row 0, followed by row 1, and so forth). ? Odd-sized boards: If a board has an odd number of inversions, it is unsolvable because the goal board has an even number (zero) of inversions. It turns out that the converse is also true: if a board has an even number of inversions, then it is solvable. In summary, when n is odd, an n-by-n board is solvable if and only if its number of inversions is even. ? Even-sized boards: Now, we’ll consider the case when the board size n is an even integer. In this case, the parity of the number of inversions is not invariant. However, the parity of the number of inversions plus the row of the blank square (indexed starting at 0) is invariant: each move changes this sum by an even number. That is, when n is even, an n-by-n board is solvable if and only if the number of inversions plus the row of the blank square is odd. Assignment Summary: The search algorithms you are expected to implement are: ? Breadth-first search (BFS) ? Depth-first search (DFS) – depth-first search needs to check for cycles, or a solution will most likely never be found. ? Greedy best-first search (GBFS), using Manhattan Distance as the heuristic. ? A* (AStar) using Manhattan Distance (discussed during lecture session) as the heuristic. Input: Your program will accept instructions from the command line. The program should accept the following inputs in the following format: ? Sliding puzzle problem: [size] “[initialstate]” [searchmethod] o [size] of sliding puzzle problem (2,3 or 4) o [initialstate] must characters, namely the digits 1-9, letters A-F (only for size 4) and a space, in any order. Make sure the initial state is solvable from the given goal state. o [searchmethod] can be: BFS, DFS, GBFS, AStar. o Examples: § 2 “ 321” DFS § 3 “47315862 ” GBFS § 4 “123456789AB DEFC” BFS Output: Your program will generate 2 different outputs – one to the console & and another to a readme file. ? Console Output: Show solution path to the sliding puzzle. Remember planning is part of the simulation process and on console (to user) we simply want to show the final solution path from initial state to the goal state for each search method. ? Readme.txt: The Readme should include – o You need to include size, initial and goal state of the problem. o And for each state and size of the problem, include searchmethod and report a comma-separated list of integers listed in the following format. This format should represent the state of your search tree at the moment the solution was discovered: [depth], [numCreated], [numExpanded], [maxFringe] o [depth] represents the depth in the search tree where the solution is found. The integer will be zero if the solution is at the root and it will be “-1” if a solution was not found. o [numCreated] is the counter that is incremented every time a node of the search tree is created (output 0 if depth == -1). o [numExpanded] is the counter that will be incremented every time the search algorithm acquires the successor states to the current state, i.e., every time a node is pulled off the fringe and found not to be the solution (output 0 if depth == -1). o [maxFringe] is the maximum size of the fringe at any point during the search (output 0 if depth == -1). Hints: ? The successors of a state in this problem depend greatly on the position of the blank spot. Rather than think about which tiles can move into the blank spot, try considering where the blank spot can move. Certain numerical qualities about this position will determine whether or not the blank can move left, right, up, or down. If a blank spot moves up, then its location is being swapped with the location above it. ? The heuristics can be generated by comparing the state being evaluated to the goal state. The number of misplaced tiles is easily calculated in time linear to the number of tiles in the puzzle, but the simple solution to the Manhattan distance requires time quadratic to the number of tiles in the puzzle. ? If you plan to start from scratch, spend a lot of time thinking about what data structures you will use for your fringe. Much of the variation between the algorithms comes in how to determine which elements to pull off the fringe next. ? Many of these algorithms are more similar than different. Think about how you can use polymorphism & fringe (one queue/list for all) to make your life easier. Submission Guidelines: Zip and upload the following files on Canvas using the Programming Assignment 1 submission link: ? Board.java/Board.py: Source code that models an n-by-n board with sliding tiles. Your heuristic function resides in this file. ? Solver.java/Solver.py: Source code that implements BFS, DFS, GBFS, AStar to solve n-by-n sliding puzzle. ? Tester.java/Tester.py: A tester file that connects your Board and Solver code. ? Readme.txt: Output for each of the algorithm and problem size in the format explained in the output section. Please refer to the grading rubric for breakdown of the points.