classic sudoku, the objective is to fill a 9 × 9 grid with digits so that each column

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Introduction

In classic sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Sudoku has 81 variables, i.e., 81 tiles. The variables are named by row and column and are valued from 1 to 9 subject to the constraints that two cells in the same row, column, or box may be the same.

Frame your problem in terms of variables, domains, and constraints. We will represent a Sudoku using a Python dictionary or hash map, where each key is a variable name based on location, and value of the tile placed there. For instance, for the Sudoku above, we have the following:

• sudoku_dict[“B3”] = 7

• sudoku_dict[“F1”] = 7

• sudoku_dict[“D1”] = 0 (we assign 0 to empty cells)

 Running your program

Your program needs to execute as follows:

python3 sudoku.py <input_string>

You will be provided with a file named sudoku_boards.txt that contains samples of unsolved Sudoku boards, and sudoku_boards_solved.txt with their corresponding solutions. Each board is represented as a single line of text, starting from the top-left corner of the board, and listed left-to-right, top-to- bottom.

For instance, the string

003020600900305001001806400008102900700000008006708200002609500800203009005010300

is equivalent to the following Sudoku board:

0 0 3 0 2 0 6 0 0

9 0 0 3 0 5 0 0 1

0 0 1 8 0 6 4 0 0

0 0 8 1 0 2 9 0 0

7 0 0 0 0 0 0 0 8

0 0 6 7 0 8 2 0 0

0 0 2 6 0 9 5 0 0

8 0 0 2 0 3 0 0 9

0 0 5 0 1 0 3 0 0

Your program will generate output.txt, containing a single line of text representing the finished Sudoku board. E.g.:

483921657967345821251876493548132976729564138136798245372689514814253769695417382

Test your program using sudoku_boards_solved.txt, which contains the solved versions of all of the same puzzles.

Backtracking Algorithm

Implement backtracking search using the minimum remaining value heuristic. Pick your own order of values to try for each variable and apply forward checking to reduce variables domains.

• Test your program on sudoku_boards.txt.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of