The elements of this square grid are the first 25 positive integers. Choose five elements — no two from the same row or column — so that the largest of the five elements is as small as possible.

A square grid containing integers that are all different.

Sidney Penner of Bronx Community College (CUNY, Bronx, New York) found the solution by crossing out all elements higher than 11. This eliminates all elements in row 2, except the element 8. Selecting element 8 means we have to forswear every other element in row 2 and column 4. Here, we have indexed the rows from top to bottom and the columns from left right, each time starting from zero.

Square grid where integer 8 has been selected. As a result, all other integers in row 2 and column 4 can be crossed out.

We mark selected elements with a gold background color and elements that can still be selected with a gray background color. The elements that can no longer be selected are crossed out by a thick red line and marked with a white background color. Now, there's only one element left in row 3 that is still open for selection and is not higher than 11. Again, selecting element 3 means that all other elements on row 3 and column 0 can be crossed out.

Square grid where integers 3 and 8 have been selected. The integers that can still be selected are marked with a gray background color.

If we continue in this way, we finally select the elements 1, 3, 6, 8 and 11.

Square grid where integers 1, 3, 6, 8 and 11 have been selected. Two selected integers are never in the same row or in the same column.

No five elements can be found that are all on different rows and columns, with the largest element being less than 11.

Assignment

Define a class Grid that can be used to represent square grids. The elements of the grid must be integers that are all different. It must be possible to select elements in the grid that are all on different rows and on different columns. The rows of the grid are indexed from top to bottom and the columns from left to right, each time starting from zero.

When instantiating objects of the class Grid, a list (list) containing integers (int) that are all different must be passed. These integers are used to fill the cells of the grid from left to right and from top to bottom. As a result, the number of integers in the list must be a square number¹. If the argument that is passed when instantiating an object of the class Grid does not meet the set conditions, an AssertionError must be raised with the message invalid elements. In addition, the class Grid must at least support the following methods:

A method element that takes a row and a column index. The method must return the element in the cell at the given row and the given column.
A method position that takes an integer (int). The method must return a tuple containing the row and column index of the cell that contains the given integer.
A method select that takes an integer (int). The method must make sure that the given integer is selected in the grid. This means that after selection, all integers on the same row or the same column can no longer be selected (including the integer that was passed to the method). The method must return a reference to the object on which the method was called. In case the given integer cannot be selected, an AssertionError must be raised with the message invalid selection.
A method is_crossed_out that takes a row and a column index. The method must return a Boolean value that indicates if the element in the cell on the given row and column has been crossed out by selecting other elements. Note that elements that are selected are not crossed out themselves. Only the other elements on the same row and the same column as the selected integer are crossed out.

If the row and column index that are passed to the methods number or is_crossed_out do not indicate a valid position of a cell in the grid, an AssertionError must be raised with the message invalid position.

If the integer that is passed to the methods position or select does not occur in the grid, an AssertionError must be raised with the message element not found.

Make sure that the built-in function str returns a string representation of the objects of the class Grid, where all rows of the grid are on separate lines. The columns of the grid must have a fixed width that equals the maximum width of the string representations of all integers in the grid, and the integers must be right aligned in the columns. Columns must be separated by a single space. Integers that have been crossed out (as defined by the method is_crossed_out) must be represented by a dash (-).

Example

        >>> grid = Grid([2, 13, 16, 11, 23, 15, 1, 9, 7, 10, 14, 12, 21, 24, 8, 3, 25, 22, 18, 4, 20, 19, 6, 5, 17])
>>> print(grid)
 2 13 16 11 23
15  1  9  7 10
14 12 21 24  8
 3 25 22 18  4
20 19  6  5 17
>>> grid.element(2, 3)
24
>>> grid.element(4, 1)
19
>>> grid.element(5, -2)
Traceback (most recent call last):
AssertionError: invalid position
>>> grid.position(24)
(2, 3)
>>> grid.position(19)
(4, 1)
>>> grid.position(42)
Traceback (most recent call last):
AssertionError: element not found
>>> print(grid.select(1))
 2  - 16 11 23
 -  1  -  -  -
14  - 21 24  8
 3  - 22 18  4
20  -  6  5 17
>>> grid.select(1)
Traceback (most recent call last):
AssertionError: invalid selection
>>> print(grid.select(3).select(6))
 -  -  - 11 23
 -  1  -  -  -
 -  -  - 24  8
 3  -  -  -  -
 -  -  6  -  -
>>> grid.select(2)
Traceback (most recent call last):
AssertionError: invalid selection
>>> print(grid.select(8).select(11))
 -  -  - 11  -
 -  1  -  -  -
 -  -  -  -  8
 3  -  -  -  -
 -  -  6  -  -

>>> grid = Grid([2, 13, 16, 11, 23])
Traceback (most recent call last):
AssertionError: invalid elements
>>> grid = Grid([1, 2, 2, 1])
Traceback (most recent call last):
AssertionError: invalid elements

Resources

Bankoff L (1976). Problem department: puzzle 377 proposed by Charles W. Trigg, San Diego, California. Pi Mu Epsilon Journal 6(5), 306–324. ⁴
Bankoff L (1977). Problem department: puzzle 377 solution by Sidney Penner, Bronx Community College of CUNY, Bronx, New York. Pi Mu Epsilon Journal 6(7), 417–437. ⁵
Bankoff L (1977). Problem department: puzzle 377 computer solution by Jeanette Bickley, Webster Groves Senior High School, Webster Groves, Missouri. Pi Mu Epsilon Journal 6(7), 417–437. ⁶

Assignment

Example

Epilogue

Resources