2022-10-21, Del B#
Del B handlar om spelet Sudoku. Din uppgift kommer vara att skriva en klass med namn Sudoku. Alla uppgifter B1-B8 kommer gå ut på att skriva någon del av klassen. Du behöver inte lämna in något efter varje uppgift. Istället lämnas hela klassen in på uppgift B8.
En sudoku kan se ut som i den vänstra figuren nedan. Spelet går ut på att fylla alla tomma rutor med siffror (eng. digits) på ett sådant sätt att alla rader, kolumner och vart och ett av de nio 3x3-blocken innehåller siffrorna 1 till 9. Den högra figuren visar lösningen till problemet.
Källa: Wikipedia
I alla uppgifter som följer representeras rutnätet (eng. grid) av en lista av listor. Var och en av de inre listorna svarar mot en rad i rutnätet. Deras element är siffrorna som just nu finns i rutnätet. Tomma rutor representeras med siffran 0.
Exempel: Den olösta sudokun i bilden till vänster skulle representeras med listan picture_grid:
# List-of-lists representation of the unsolved Sudoku puzzle above
picture_grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
B1 (1 poäng)#
Skapa en klass Sudoku med en konstruktor som tar en parameter grid och tilldelar dess värde till en instansvariabel grid.
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
class Sudoku:
def __init__(self, grid):
self.grid = grid
B2 (2 poäng)#
Lägg till en metod i Sudoku-klassen som gör att Sudoku-objekt skrivs ut på ett läsbart sätt.
Följande kod:
picture_grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
my_sudoku = Sudoku(picture_grid)
print(my_sudoku)
ska ge utskriften
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def __str__(self):
res = '\n'
for row in self.grid:
row_str = ' '.join([str(x) for x in row])
res += row_str + '\n'
return res
B3 (1 poäng)#
Färdigställ metoden get_column_as_list() och lägg in den i din klass.
def get_column_as_list(self, column_index):
"""Return a list of all entries in the input column.
"""
Med picture_grid definierad som i uppgift B2 ska följande kod
my_sudoku = Sudoku(picture_grid)
print(my_sudoku.get_column_as_list(0))
print(my_sudoku.get_column_as_list(4))
print(my_sudoku.get_column_as_list(8))
ge utskriften
[5, 6, 0, 8, 4, 7, 0, 0, 0]
[7, 9, 0, 6, 0, 2, 0, 1, 8]
[0, 0, 0, 3, 1, 6, 0, 5, 9]
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def get_column_as_list(self, column_index):
"""Return a list of all entries in the input column.
"""
return [row[column_index] for row in self.grid]
B4 (3 poäng)#
Färdigställ metoden get_block_as_list() och lägg till den i din klass.
def get_block_as_list(self, row_index, column_index):
"""Return a list of all entries in the 3x3 block
that contains the field (row_index, column_index).
Examples:
--------
The following calls ALL return the same thing:
a list of all entries in the top-left block.
sudoku_object.get_block_as_list(0, 0)
sudoku_object.get_block_as_list(0, 1)
sudoku_object.get_block_as_list(0, 2)
sudoku_object.get_block_as_list(1, 0)
sudoku_object.get_block_as_list(1, 1)
sudoku_object.get_block_as_list(1, 2)
sudoku_object.get_block_as_list(2, 0)
sudoku_object.get_block_as_list(2, 1)
sudoku_object.get_block_as_list(2, 2)
The following calls ALL return the same thing:
a list of all entries in the top-middle block.
sudoku_object.get_block_as_list(0, 3)
sudoku_object.get_block_as_list(0, 4)
sudoku_object.get_block_as_list(0, 5)
sudoku_object.get_block_as_list(1, 3)
sudoku_object.get_block_as_list(1, 4)
sudoku_object.get_block_as_list(1, 5)
sudoku_object.get_block_as_list(2, 3)
sudoku_object.get_block_as_list(2, 4)
sudoku_object.get_block_as_list(2, 5)
etc.
"""
Med picture_grid definierad som i uppgift B2 ska följande kod
my_sudoku = Sudoku(picture_grid)
print(my_sudoku.get_block_as_list(0, 2))
print(my_sudoku.get_block_as_list(4, 8))
print(my_sudoku.get_block_as_list(7, 1))
ge utskriften
[5, 3, 0, 6, 0, 0, 0, 9, 8]
[0, 0, 3, 0, 0, 1, 0, 0, 6]
[0, 6, 0, 0, 0, 0, 0, 0, 0]
Notera dock att ordningen på elementen i den lista som metoden returnerar inte spelar någon roll! Din metod tillåts ordna elementen i listan på vilket sätt som helst. Du behöver således inte matcha exempelutskriften element för element.
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def get_block_as_list(self, row_index, column_index):
"""Return a list of all entries in the 3x3 block
that contains the field (row_index, column_index).
"""
# Find indices for top-left field in the block
row_index_top_left = (row_index//3)*3
col_index_top_left = (column_index//3)*3
block_list = []
for i in range(row_index_top_left, row_index_top_left + 3):
for j in range(col_index_top_left, col_index_top_left + 3):
block_list.append(self.grid[i][j])
return block_list
B5 (4 poäng)#
Färdigställ metoderna all_rows_complete(), all_columns_complete() och all_blocks_complete() och lägg till dem i din klass.
def all_rows_complete(self):
"""Check whether all rows contain the digits 1 through 9"""
return True #REPLACE THIS
def all_columns_complete(self):
"""Check whether all columns contain the digits 1 through 9"""
return True #REPLACE THIS
def all_blocks_complete(self):
"""Check whether all blocks contain the digits 1 through 9"""
return True #REPLACE THIS
Metoden all_rows_complete() ska returnera True om alla rader i rutnätet innehåller siffrorna 1 till 9. Annars ska metoden returnera False. Metoderna all_columns_complete() och all_blocks_complete() ska fungera på samma sätt för kolumner respektive block.
OBS!: Du får använda metoder från B1-B4 för att lösa denna uppgift även om du inte lyckats implementera dem. Du kan anta att metoderna finns implementerade och fungerar som avsett.
Om du vill kan du använda följande funktion för att testa att dina metoder fungerar korrekt:
Testfunktion
def test_solution_checks():
solved_sudoku_grid = [[4, 5, 3, 8, 2, 6, 1, 9, 7],
[8, 9, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 7, 4, 9, 3, 5, 2, 8],
[7, 1, 4, 9, 5, 2, 8, 6, 3],
[5, 8, 6, 1, 3, 7, 2, 4, 9],
[3, 2, 9, 6, 8, 4, 7, 5, 1],
[9, 3, 5, 2, 1, 8, 4, 7, 6],
[6, 7, 1, 3, 4, 5, 9, 8, 2],
[2, 4, 8, 7, 6, 9, 3, 1, 5],
]
# Apply tests to a correctly completed sudoku
print('\n----------------------------------------------')
print('Running tests on a correctly solved sudoku...')
print('Incorrect methods will generate output below.')
print('No output indicates that your code passed the tests.')
solved_sudoku = Sudoku(solved_sudoku_grid)
rows_complete = solved_sudoku.all_rows_complete()
columns_complete = solved_sudoku.all_columns_complete()
blocks_complete = solved_sudoku.all_blocks_complete()
if not rows_complete:
print('TEST FAILED! all_rows_complete flagged a correctly solved sudoku as incorrect.')
if not columns_complete:
print('TEST FAILED! all_columns_complete flagged a correctly solved sudoku as incorrect.')
if not blocks_complete:
print('TEST FAILED! all_blocks_complete flagged a correctly solved sudoku as incorrect.')
# Apply tests to incorrect sudokus
print('\n----------------------------------------------')
print('Running tests on incorrect sudokus...')
print('Incorrect methods will generate output below.')
print('No output indicates that your code passed the tests.')
row_method_working = True
column_method_working = True
block_method_working = True
for i in range(9):
for j in range(9):
solved_sudoku_grid_copy = [[x for x in row] for row in solved_sudoku_grid]
solved_sudoku_grid_copy[i][j] += 1
sudoku_test = Sudoku(solved_sudoku_grid_copy)
rows = sudoku_test.all_rows_complete()
columns = sudoku_test.all_columns_complete()
blocks = sudoku_test.all_blocks_complete()
if rows:
row_method_working = False
if columns:
column_method_working = False
if blocks:
block_method_working = False
if not row_method_working:
print('TEST FAILED! all_rows_complete flagged one or more incorrect sudokus as correct.')
if not column_method_working:
print('TEST FAILED! all_columns_complete flagged one or more incorrect sudokus as correct.')
if not block_method_working:
print('TEST FAILED! all_blocks_complete flagged one or more incorrect sudokus as correct.')
print('\n----------------------------------------------')
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def contains_1to9(self, lst):
"""Check whether lst contains 1, 2, 3, ..., 9."""
return sorted(lst) == list(range(1, 10))
def all_rows_complete(self):
"""Check whether all rows contain the digits 1 through 9"""
for row in self.grid:
if not self.contains_1to9(row):
return False
return True
def all_columns_complete(self):
"""Check whether all columns contain the digits 1 through 9"""
for column_index in range(9):
column = self.get_column_as_list(column_index)
if not self.contains_1to9(column):
return False
return True
def all_blocks_complete(self):
"""Check whether all blocks contain the digits 1 through 9"""
row_indices = [0, 3, 6]
column_indices = [0, 3, 6]
for row_index in row_indices:
for col_index in column_indices:
block = self.get_block_as_list(row_index, col_index)
if not self.contains_1to9(block):
return False
return True
B6 (1 poäng)#
Färdigställ metoden is_solved() och lägg till den i din klass. Metoden ska returnera True om alla rader, kolumner och block innehåller siffrorna 1 till 9. Annars ska metoden returnera False.
def is_solved(self):
"""Check whether the current grid is a solved sudoku"""
OBS!: Du får använda metoder från B1-B5 för att lösa denna uppgift även om du inte lyckats implementera dem. Du kan anta att metoderna finns implementerade och fungerar som avsett.
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def is_solved(self):
"""Check whether the current grid is a solved sudoku"""
rows = self.all_rows_complete()
columns = self.all_columns_complete()
blocks = self.all_blocks_complete()
return rows and columns and blocks
B7 (4 poäng)#
Färdigställ metoden candidate_digits() och lägg till den i din klass. Metoden ska returnera ett lexikon vars nycklar är tupler med rad-index och kolonn-index för alla tomma rutor i rutnätet. Motsvarande värden i lexikonet ska vara listor med de ”kandidatsiffror” som kan tänkas passa i rutan. Som kandidatsiffror räknas alla siffror som ännu inte finns i samma rad, kolumn eller block som den aktuella rutan.
def candidate_digits(self):
"""Return a dict of candidate digits for
all of the currently empty fields.
All digits that are not yet in the same
row, column or box as the empty field
are considered candidate digits.
The returned dict has tuples of field
coordinates ((row_index, column_index))
as keys and lists of candidate digits
as values.
Example:
--------
For the grid below, which has only
3 empty fields, the method returns
{(0, 0): [8, 9], (0, 8): [9], (1, 0): [9]}
0 1 2 7 5 3 6 4 0
0 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
"""
Följande kod
nearly_solved_grid = [[4, 5, 0, 8, 2, 6, 1, 9, 7],
[8, 0, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 0, 4, 9, 3, 5, 2, 0],
[7, 1, 4, 9, 5, 0, 0, 6, 0],
[5, 0, 6, 1, 0, 7, 0, 4, 0],
[3, 0, 9, 0, 8, 4, 7, 5, 1],
[0, 0, 0, 2, 1, 0, 4, 7, 0],
[6, 0, 1, 3, 4, 5, 9, 8, 2],
[0, 4, 0, 7, 6, 0, 3, 1, 5]]
nearly_solved_sudoku = Sudoku(nearly_solved_grid)
print(nearly_solved_sudoku.candidate_digits())
ska ge utskriften
{(0, 2): [3], (1, 1): [9], (2, 2): [7], (2, 8): [8], (3, 5): [2], (3, 6): [2, 8],
(3, 8): [3, 8], (4, 1): [2, 8], (4, 4): [3], (4, 6): [2, 8], (4, 8): [3, 8, 9],
(5, 1): [2], (5, 3): [6], (6, 0): [9], (6, 1): [3, 8, 9], (6, 2): [3, 5, 8],
(6, 5): [8, 9], (6, 8): [6], (7, 1): [7], (8, 0): [2, 9], (8, 2): [8], (8, 5): [8, 9]}
OBS!: Du får använda metoder från B1-B6 för att lösa denna uppgift även om du inte lyckats implementera dem. Du kan anta att metoderna finns implementerade och fungerar som avsett.
Ingen inlämning här. Hela klassen Sudoku, med de bästa versionerna av de metoder du implementerat, lämnas in under uppgift B8.
Lösningsförslag
def candidate_digits(self):
"""Return a dict of candidate digits for
all of the currently empty fields.
"""
candidate_digits = {}
for row_index in range(9):
for column_index in range(9):
# Check if this box is empty
if self.grid[row_index][column_index] == 0:
# Check which digits are already in this row, column, and block
row = self.grid[row_index]
column = self.get_column_as_list(column_index)
block = self.get_block_as_list(row_index, column_index)
all_digits = row + column + block
# Construct list of candidates for this box
local_candidates = [x for x in range(1, 10) if x not in all_digits]
# Add list of candidates to dictionary
candidate_digits[(row_index, column_index)] = local_candidates
return candidate_digits
B8 (4 poäng)#
Färdigställ metoden random_solve() och lägg till den i din klass.
def random_solve(self):
"""Solve the sudoku by selecting one of the candidate digits
at random until a solution is found"""
Metodens uppgift är att lösa Sudokun genom att fylla i siffror i de tomma rutorna i instansvariabeln grid. Metoden ska använda följande algoritm:
Ta reda på kandidatsiffrorna för alla tomma rutor.
För varje tom ruta, slumpa fram en av kandidatsiffrorna och skriv in den i rutan.
Kontrollera om det rutnät du erhöll uppfyller alla kriterier för en löst sudoku. Om så är fallet är metoden klar. Annars: gå tillbaka till steg 2 och upprepa.
Den här algoritmen är inte optimal och kan därför bara lösa sudokus med relativt få tomma rutor inom rimlig tid. Använd den sudoku som definieras av nearly_solved_grid för att testa din metod. Om random_solve() är korrekt implementerad bör den lösa denna sudoku inom en sekund.
# Test your method on this grid
nearly_solved_grid = [[4, 5, 0, 8, 2, 6, 1, 9, 7],
[8, 0, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 0, 4, 9, 3, 5, 2, 0],
[7, 1, 4, 9, 5, 0, 0, 6, 0],
[5, 0, 6, 1, 0, 7, 0, 4, 0],
[3, 0, 9, 0, 8, 4, 7, 5, 1],
[0, 0, 0, 2, 1, 0, 4, 7, 0],
[6, 0, 1, 3, 4, 5, 9, 8, 2],
[0, 4, 0, 7, 6, 0, 3, 1, 5]]
OBS!: Du får använda metoder från B1-B7 för att lösa denna uppgift även om du inte lyckats implementera dem. Du kan anta att metoderna finns implementerade och fungerar som avsett.
Om du inte har löst B7, notera att kandidatsiffrorna för nearly_solved_grid ges i uppgift B7. Du kan använda dessa kandidatsiffror i random_solve() för att kontrollera att random_solve() fungerar.
Lösningsförslag
def random_solve(self):
"""Solve the sudoku by selecting one of the candidate digits
at random until a solution is found"""
import random # Can/should be placed outside class
candidate_digits = self.candidate_digits()
while not self.is_solved():
# Choose one of the candidate digits at random, for each empty field
for row_index, column_index in candidate_digits.keys():
local_candidates = candidate_digits[(row_index, column_index)]
random_index = random.randint(0, len(local_candidates)-1)
self.grid[row_index][column_index] = local_candidates[random_index]