risorse | suggeritore per sudoku
Alcuni giorni fa ho affrontato il mio primo Sudoku:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ 1 │ │ 7 ║ │ 9 │ ║ 6 │ 5 │ 8 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 3 ║ │ 6 │ 7 ║ │ │ 4 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ 4 │ 1 │ ║ 9 │ 7 │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ ║ 9 │ 3 │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ │ ║ │ │ ║ 3 │ 8 │ 6 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 7 │ │ ║ 4 │ │ 1 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 3 │ │ ║ 6 │ │ 1 ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 5 │ ║ │ │ ║ 1 │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 4 │ │ 1 ║ 3 │ │ ║ 7 │ │ 2 ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Lo schema iniziale del Sudoku, classificato come facile.
Poiché mi sono inceppato in più punti, ho deciso di realizzare un programma che suggerisca la prossima mossa. Di risolutori in rete ne ho trovato molti, ma nessun “suggeritore” – non che abbia cercato molto, per la verità. La strategia iniziale è banale: evidenziare le caselle per le quali esiste un solo possibile candidato.
Le righe, colonne e quadrati dello schema di gioco sono indicizzati come in figura:
0 1 2 3 4 5 6 7 8
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
0 ║ ║ ║ ║
╟─ ─╫─ ─╫─ ─╢
1 ║ 0 ║ 1 ║ 2 ║
╟─ ─╫─ ─╫─ ─╢
2 ║ ║ ║ ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
3 ║ ║ ║ ║
╟─ ─╫─ ─╫─ ─╢
4 ║ 3 ║ 4 ║ 5 ║
╟─ ─╫─ ─╫─ ─╢
5 ║ ║ ║ ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
6 ║ ║ ║ ║
╟─ ─╫─ ─╫─ ─╢
7 ║ 6 ║ 7 ║ 8 ║
╟─ ─╫─ ─╫─ ─╢
8 ║ ║ ║ ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Numerazione delle righe, delle colonne e dei quadrati.
Ognuna delle caselle contiene l'elenco dei possibili candidati che può ospitare. Inizialmente l'insieme dei candidati è formato da tutti i numeri compresi tra 1 e 9:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
class Cell:
def __init__(self):
self.value = None
self.candidates = [*range(1, 10)]
def set(self, n):
self.value = n
self.candidates = []
def remove_candidate(self, n):
if n in self.candidates:
self.candidates.remove(n)
La classe Board rappresenta lo schema di gioco. Ha il compito di inizializzare tutte le caselle e raggrupparle nelle righe, colonne e quadrati che caratterizzano il Sudoku. Offre inoltre accesso alle stesse attraverso la classica indicizzazione matriciale:
class Board:
def __init__(self):
self.cells = [[Cell() for col in range(9)] for row in range(9)]
self.rows = self.cells
self.cols = [[self.cells[row][col] for row in range(9)]
for col in range(9)]
self.sqrs = [[self.cells[square_top + row][square_left + col]
for row in range(3) for col in range(3)]
for square_top in [0, 3, 6] for square_left in
[0, 3, 6]]
def __getitem__(self, key):
return self.rows[key]
La classe Board ha anche la responsabilità di aggiornare l'elenco dei candidati delle caselle. Quando un numero viene inserito in una casella questo va rimosso dall'elenco dei candidati delle caselle appartenenti alla stessa riga, colonna e quadrato di quella appena chiusa:
class Board:
...
def set(self, row, col, n):
cell = self.cells[row][col]
if cell.value:
print('invalid move')
return
cell.set(n)
self._remove_candidate_from_row(row, n)
self._remove_candidate_from_col(col, n)
square = 3 * int(row / 3) + int(col / 3)
self._remove_candidate_from_square(square, n)
def _remove_candidate_from_row(self, row, n):
for cell in self.rows[row]:
cell.remove_candidate(n)
def _remove_candidate_from_col(self, col, n):
for cell in self.cols[col]:
cell.remove_candidate(n)
def _remove_candidate_from_square(self, square, n):
for cell in self.sqrs[square]:
cell.remove_candidate(n)
È giunto il momento di visualizzare lo schema di gioco sul terminale:
class Terminal:
def print_cell(self, cell):
if cell.value:
return ' {} '.format(str(cell.value))
elif len(cell.candidates) == 1:
return '<{}>'.format(cell.candidates[0])
else:
return ' '
def print_board(self, board):
print('╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗')
for r, row in enumerate(board.rows):
print('║', end='')
for c, cell in enumerate(row):
print('{}{}'.format(
self.print_cell(cell), '║' if c % 3 == 2 else '│'), end='')
if r == 8:
print('\n╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝')
elif r % 3 == 2:
print('\n╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣')
else:
print('\n╟───┼───┼───╫───┼───┼───╫───┼───┼───╢')
Una casella vuota è rappresentata da uno spazio, una chiusa dal valore ad essa assegnato. Se una casella è ancora vuota e ha un unico candidato in elenco allora questo viene mostrato tra parentesi angolari a mo' di suggerimento.
Il codice per caricare la configurazione iniziale è il seguente:
board = Board() board.set(0, 0, 1) board.set(0, 2, 7) board.set(0, 4, 9) board.set(0, 6, 6) board.set(0, 7, 5) board.set(0, 8, 8) board.set(1, 2, 3) board.set(1, 4, 6) board.set(1, 5, 7) board.set(1, 8, 4) board.set(2, 3, 4) board.set(2, 4, 1) board.set(2, 6, 9) board.set(2, 7, 7) board.set(3, 3, 9) board.set(3, 4, 3) board.set(4, 0, 9) board.set(4, 6, 3) board.set(4, 7, 8) board.set(4, 8, 6) board.set(5, 2, 2) board.set(5, 3, 7) board.set(5, 6, 4) board.set(5, 8, 1) board.set(6, 0, 3) board.set(6, 3, 6) board.set(6, 5, 1) board.set(7, 1, 5) board.set(7, 6, 1) board.set(7, 8, 9) board.set(8, 0, 4) board.set(8, 2, 1) board.set(8, 3, 3) board.set(8, 6, 7) board.set(8, 8, 2) terminal = Terminal() terminal.print_board(board)
L'effetto è mostrato qui sotto:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ 1 │ │ 7 ║<2>│ 9 │ ║ 6 │ 5 │ 8 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 3 ║ │ 6 │ 7 ║<2>│ │ 4 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ 4 │ 1 │ ║ 9 │ 7 │<3>║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ ║ 9 │ 3 │ ║ │<2>│ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ │ ║ │ │ ║ 3 │ 8 │ 6 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 7 │ │ ║ 4 │<9>│ 1 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 3 │ │ ║ 6 │ │ 1 ║ │<4>│<5>║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 5 │ ║ │ │ ║ 1 │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 4 │ │ 1 ║ 3 │ │ ║ 7 │<6>│ 2 ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Lo schema iniziale con i suggerimenti in evidenza.
Conviene estendere il programma per consentire all'utente di chiudere una casella. Per semplicità la mossa è costituita da una sequenza di tre cifre che rappresentano le coordinate della casella da chiudere e il numero da inserire (per comodità le coordinate partono da 1 anziché da zero):
class Terminal:
...
def read_move(self, prompt):
return input(prompt)
terminal = Terminal()
terminal.print_board(board)
while True:
terminal.print_board(board)
move = terminal.read_move('Your move (RCN): ')
board.set(int(move[0]) - 1, int(move[1]) - 1, int(move[2]))
Seguendo i suggerimenti in breve si completa lo schema:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ 1 │ 4 │ 7 ║ 2 │ 9 │ 3 ║ 6 │ 5 │ 8 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 8 │ 9 │ 3 ║ 5 │ 6 │ 7 ║ 2 │ 1 │ 4 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 2 │ 6 │ 5 ║ 4 │ 1 │ 8 ║ 9 │ 7 │ 3 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 6 │ 1 │ 8 ║ 9 │ 3 │ 4 ║ 5 │ 2 │ 7 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ 7 │ 4 ║ 1 │ 2 │ 5 ║ 3 │ 8 │ 6 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 5 │ 3 │ 2 ║ 7 │ 8 │ 6 ║ 4 │ 9 │ 1 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 3 │ 2 │ 9 ║ 6 │ 7 │ 1 ║ 8 │ 4 │ 5 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 7 │ 5 │ 6 ║ 8 │ 4 │ 2 ║ 1 │ 3 │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 4 │ 8 │ 1 ║ 3 │ 5 │ 9 ║ 7 │ 6 │ 2 ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Soluzione dello schema iniziale ottenuta seguendo i suggerimenti proposti dal programma.
Scarica questa versione del suggeritore.
La settimana successiva la stessa rivista ha pubblicato questo schema:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ │ 4 │ ║ │ │ ║ │ 2 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ │ ║ │ │ ║ │ │ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 5 ║ 7 │ │ 2 ║ 6 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 8 ║ 6 │ │ 9 ║ 4 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 3 │ │ 7 ║ 5 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 6 ║ 5 │ │ 8 ║ 1 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 1 │ │ ║ │ │ ║ │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 7 │ ║ │ │ ║ │ 4 │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Il secondo Sudoku, di media difficoltà.
Ho modificato il programma per caricare la nuova configurazione e con stupore ho notato che esso non fornisce alcun suggerimento. Appare infatti chiaro che ci sono almeno due caselle che possono essere subito chiuse:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ │ 4 │ ║ │ │ ║ │ 2 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ 2 │ ║ │ │ ║ │ │ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 5 ║ 7 │ │ 2 ║ 6 │ │ 4 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 8 ║ 6 │ │ 9 ║ 4 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 3 │ │ 7 ║ 5 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 6 ║ 5 │ │ 8 ║ 1 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 1 │ │ ║ │ │ ║ │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 7 │ ║ │ │ ║ │ 4 │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Almeno due caselle possono essere immediatamente chiuse.
Riflettendoci un po' sopra mi rendo conto che l'unicità del candidato è solo uno dei casi che consente la chiusura di una casella. Una casella può infatti essere chiusa anche quando è l'unica a possedere un candidato rispetto alle caselle della stessa riga, della stessa colonna o dello stesso quadrato. Per esempio, sebbene la casella centrale del quadrato in alto a sinistra annoveri tra i suoi candidati i numeri 1, 2, 6 e 8, essa è l'unica della seconda riga (e pure del primo quadrato) a contemplare il 2, perciò deve necessariamente contenere tale numero. Similmente, l'ultima casella della terza riga ha candidati i numeri 1, 4 e 8, ma è l'unica dell'ultima colonna (e anche del quadrato in alto a destra) ad ammettere il 4; per tale ragione essa non può che ospitare il 4.
Occorre quindi modificare il programma tenendo conto di questa nuova casistica. Estendo innanzitutto la classe Cell con un nuovo attributo lone_candidate che contiene l'eventuale candidato “solitario”:
class Cell:
def __init__(self):
self.value = None
self.candidates = [*range(1, 10)]
self.lone_candidate = None
def set(self, n):
self.value = n
self.candidates = []
self.lone_candidate = None
...
Prima di ogni mossa il programma deve verificare la presenza di candidati solitari in ognuna delle righe, delle colonne e dei quadrati dello schema. La classe Board offre un accesso a questi aggregati di caselle:
class Board:
...
def cell_clusters(self):
return self.rows + self.cols + self.sqrs
Il metodo find_lone_candidates ha il compito di trovare i candidati solitari:
import collections
...
def find_lone_candidates(cells):
histogram = collections.defaultdict(set)
for cell in cells:
for candidate in cell.candidates:
histogram[candidate].add(cell)
return [(v.pop(), k) for k, v in histogram.items() if len(v) == 1]
La funzione prepara dapprima un dizionario che associa ad ogni candidato l'elenco delle caselle in cui è stato trovato; ritorna un elenco di tuple (casella, candidato) per ognuna delle caselle che contengono un candidato solitario. Il programma principale utilizza questa informazione per inizializzare l'attributo lone_candidate delle caselle così trovate:
...
while True:
for cluster in board.cell_clusters():
for cell, candidate in find_lone_candidates(cluster):
cell.lone_candidate = candidate
terminal.print_board(board)
move = terminal.read_move('Your move (RCN): ')
board.set(int(move[0]) - 1, int(move[1]) - 1, int(move[2]))
Non resta che mostrare questi nuovi candidati:
class Terminal:
def print_cell(self, cell):
if cell.value:
return ' {} '.format(str(cell.value))
elif len(cell.candidates) == 1:
return '<{}>'.format(cell.candidates[0])
elif cell.lone_candidate:
return '[{}]'.format(cell.lone_candidate)
else:
return ' '
...
L'effetto del nuovo codice è quello sperato:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ │ 4 │ ║ │ │ ║ │ 2 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │[2]│ ║ │ │ ║ │ │ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 5 ║ 7 │ │ 2 ║ 6 │ │[4]║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 8 ║ 6 │ │ 9 ║ 4 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 3 │ │ 7 ║ 5 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 6 ║ 5 │ │ 8 ║ 1 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 1 │ │ ║ │ │ ║ │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 7 │ ║ │ │ ║ │ 4 │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Il programma ora riconosce i candidati solitari.
Applicando i suggerimenti proposti dal programma si giunge a alla soluzione:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ 6 │ 4 │ 7 ║ 1 │ 3 │ 5 ║ 9 │ 2 │ 8 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ 2 │ 1 ║ 8 │ 6 │ 4 ║ 7 │ 5 │ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 3 │ 8 │ 5 ║ 7 │ 9 │ 2 ║ 6 │ 1 │ 4 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 5 │ 3 │ 8 ║ 6 │ 2 │ 9 ║ 4 │ 7 │ 1 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 7 │ 6 │ 9 ║ 4 │ 5 │ 1 ║ 3 │ 8 │ 2 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 4 │ 1 │ 2 ║ 3 │ 8 │ 7 ║ 5 │ 9 │ 6 ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 2 │ 9 │ 6 ║ 5 │ 4 │ 8 ║ 1 │ 3 │ 7 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 1 │ 5 │ 4 ║ 2 │ 7 │ 3 ║ 8 │ 6 │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 8 │ 7 │ 3 ║ 9 │ 1 │ 6 ║ 2 │ 4 │ 5 ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Soluzione del secondo Sudoku ottenuta grazie ai suggerimenti.
Il programma non ha sfigurato nemmeno con un paio di Sudoku trovati in rete e classificati rispettivamente difficile e molto difficile. Nel secondo schema si riconoscono i suggerimenti relativi ai candidati singoli e quelli solitari:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ │ │ ║ 3 │ 6 │ 7 ║ │ 9 │ ║ ║ │[1]│ 2 ║ 5 │ │[8]║ │ 7 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║[2]│ │ 4 ║ 5 │ │ ║ ║ │ │ 4 ║ 1 │ 6 │ ║ │ 8 │[5]║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 2 │ ║ │ 9 │ ║ │ │ ║ ║ │ 5 │ 8 ║[2]│ │ ║ │ 4 │[1]║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 3 │ │ 8 ║ │ 2 │ ║ │ │ 9 ║ ║ │[8]│<7>║ │ 2 │ 5 ║ │[1]│ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ │ 8 ║ │ 5 │ ║ ║[2]│ │ ║ │ 8 │ 1 ║ │ │ 7 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 4 │ │ ║ 6 │ │ ║[8]│ 7 │ ║ ║ 1 │ 6 │ ║ │ │ ║ │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ 9 │ │ ║ │ │ ║ │ 6 │ ║ ║ 8 │ │ ║ │ │ 7 ║ 1 │[3]│ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 5 ║ │ │ 3 ║[9]│ │ 8 ║ ║ │ │ 9 ║ 3 │ │ 2 ║ 7 │<6>│[8]║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 7 ║ │ │[6]║ 1 │ │ ║ ║ 3 │ │[1]║[8]│ │[6]║ 5 │ │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Schema difficile a sinistra, molto difficile a destra.
Scarica questa versione del suggeritore.
L'algoritmo è sempre efficace? Penso dipenda da come è stato predisposto lo schema: se questo offre un'unica via verso la soluzione – come tutti i (pochi) Sudoku sui quali l'ho collaudato –, l'algoritmo dà buona prova di sè. Se viceversa la strada non è univoca e può accadere di dover tornare sui propri passi, allora l'algoritmo potrebbe non essere d'aiuto. Uno di questi casi è lo schema proposto in World's hardest sudoku: can you crack it?:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ 8 │ │ ║ │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 3 ║ 6 │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 7 │ ║ │ 9 │ ║ 2 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ 5 │ ║ │ │ 7 ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ 4 │ 5 ║ 7 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ 1 │ │ ║ │ 3 │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 1 ║ │ │ ║ │ 6 │ 8 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 8 ║ 5 │ │ ║ │ 1 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 9 │ ║ │ │ ║ 4 │ │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
Il programma in questo caso non emette alcun suggerimento. Non sono un esperto di Sudoku, ma immagino che lo schema contenga alcune ambiguità che vanno risolte scartando quelle che portano a situazioni inconsistenti.
Anziché mostrare i suggerimenti direttamente nello schema, è preferibile che sia l'utente a richiederli; il programma allora gliene propone uno a caso tra quelli disponibili.
Il primo intervento riguarda la visualizzazione del contenuto delle caselle:
class Cell:
def __init__(self):
self.value = None
self.candidates = [*range(1, 10)]
self.lone_candidate = None
def set(self, n):
self.value = n
self.candidates = []
self.lone_candidate = None
...
class Terminal:
def print_cell(self, cell):
if cell.value:
return ' {} '.format(str(cell.value))
elif len(cell.candidates) == 1:
return '<{}>'.format(cell.candidates[0])
elif cell.lone_candidate:
return '[{}]'.format(cell.lone_candidate)
else:
return ' '
L'utente chiede un suggerimento immettendo il carattere «H» come mossa:
... terminal = Terminal() terminal.print_board(board) while True:for cluster in board.cell_clusters(): for cell, candidate in find_lone_candidates(cluster): cell.lone_candidate = candidate terminal.print_board(board)move = terminal.read_move('Your move (RCN or `H` for help): ') if move == 'H': show_hint(board) else: board.set(int(move[0]) - 1, int(move[1]) - 1, int(move[2])) terminal.print_board(board)
Il metodo show_hint, dopo aver verificato la disponibilità di almeno un suggerimento, ne sceglie uno a caso e lo propone all'utente sottoforma di terna (riga, colonna, valore):
...
import collections
import random
...
class Hint:
def __init__(self, cell, value):
self.cell = cell
self.value = value
def find_lone_candidates(cells):
histogram = collections.defaultdict(set)
for cell in cells:
for candidate in cell.candidates:
histogram[candidate].add(cell)
return [Hint(v.pop(), k) for k, v in histogram.items() if len(v) == 1]
def show_hint(board):
hints = find_hints(board)
if not hints:
print('Sorry, no help available.')
return
hint = random.sample(hints, 1)[0]
print('{}{}{}'.format(hint.cell.row + 1, hint.cell.col + 1, hint.value))
Il metodo appena introdotto richiede che ogni casella conosca le proprie coordinate:
...
class Cell:
def __init__(self, row, col):
self.row = row
self.col = col
self.value = None
self.candidates = [*range(1, 10)]
...
class Board:
def __init__(self):
self.cells = [[Cell(row, col) for col in range(9)] for row in range(9)]
self.rows = self.cells
...
L'individuazione dei suggerimenti è a carico del metodo find_hints che unisce in un unico insieme i suggerimenti derivati dalla presenza di un solo candidato con quelli associati ai candidati solitari così da eliminare eventuali duplicati:
...
def find_single_candidates(cells):
return [Hint(cell, cell.candidates[0]) for cell in cells
if len(cell.candidates) == 1]
def find_hints(board):
return set([hint for row in board.rows for hint in
find_single_candidates(row)] + [hint for cluster in
board.cell_clusters() for hint in
find_lone_candidates(cluster)])
Il programma ora non mostra più i suggerimenti, ma ne fornisce uno a richiesta:
╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ║ │ 4 │ ║ │ │ ║ │ 2 │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 9 │ │ ║ │ │ ║ │ │ 3 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 5 ║ 7 │ │ 2 ║ 6 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 8 ║ 6 │ │ 9 ║ 4 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ ║ │ │ ║ │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ │ 2 ║ 3 │ │ 7 ║ 5 │ │ ║ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ║ │ │ 6 ║ 5 │ │ 8 ║ 1 │ │ ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ 1 │ │ ║ │ │ ║ │ │ 9 ║ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ║ │ 7 │ ║ │ │ ║ │ 4 │ ║ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝ Your move (RCN or `H` for help): H 394 Your move (RCN or `H` for help): H 222 Your move (RCN or `H` for help): H 222 Your move (RCN or `H` for help): H 394 Your move (RCN or `H` for help): H 394 Your move (RCN or `H` for help):
La nuova modalità d'uso del programma.
Scarica questa versione del suggeritore.
Il programma è ancora incompleto: non è possibile annullare una mossa o semplicemente svuotare una casella. Potrebbe essere interessante aggiungere un'opzione che impedisca all'utente di effettuare mosse non valide, o per lo meno le evidenzi in qualche modo. Il programma potrebbe arrestarsi automaticamente al completamento dello schema indicando se la configurazione finale rappresenta una soluzione accettabile. L'interazione con l'utente è in generale piuttosto macchinosa e sarebbe preferibile una soluzione punta-e-clicca.
Pagina modificata il 18/08/2020