Goals of the Assignment
The goal of this assignment is to practice using Python sets. You will write an algorithm that determines whether or not a Sudoku puzzle solution is valid.
Sudoku is a puzzle game that challenges players to fill each of the squares in a 9×9 grid with the digits between 1 and 9. The rules state that the same digit cannot appear twice in any row or column. In addition, the board is divided into 3×3 regions, each of which must not include the same digit twice.
A partially completed Sudoku puzzle. The boxes indicate examples of a row, a column, and one of the 3×3 regions on the board, each of which must contain only unique integers from 1-9. In this example, the number 7 in the center of the top row is in each of the highlighted areas.
Every square on the board exists in exactly one row, one column, and one region. The number written in each square must be unique to all three. The set data structure stores unique values, and can therefore be used to determine whether or not a number has already been used.
Activities
This activity deals with the Sudoku of an NxN grid with the digits between 1 and N, where N = 9, 16, 25, 36, …. In this extended version of the game, the board is divided into nxn regions, where n = sqrt(N), each of which must not include the same digit twice. As usual, the same digit cannot appear twice in any row or column.
A Sudoku puzzle comprises four components: a two-dimensional board and three lists of sets storing values at each row, column, and region. Those sets will be used to verify the board in an efficient manner. As you attempt to place a digit between 1 and N on the board, only a valid move should update the puzzle.
Open the provided file named “sudoku.py” and examine the code. Write the following functions:
1. make_puzzle(N)– builds an initial puzzle data structure and returns it.
a. Create a board as a two-dimensional list filled with zeros indicating empty squares. Then add N digits between 1 and N to the board at randomly chosen locations such that the puzzle is valid.
b. Create a list of sets named row_sets, where row_sets[k], 0<=k
