237 lines
7.8 KiB
Python
Executable File
237 lines
7.8 KiB
Python
Executable File
#!/bin/python3.10
|
|
from dataclasses import dataclass, field
|
|
from typing import Union, Iterator
|
|
from random import choices, choice
|
|
from math import prod
|
|
|
|
ansii_red = "\u001b[31;1m"
|
|
ansii_red_bg = "\u001b[41;1m"
|
|
ansii_green = "\u001b[32;1m"
|
|
ansii_green_bg = "\u001b[42;1m"
|
|
ansii_yellow = "\u001b[33;1m"
|
|
ansii_yellow_bg = "\u001b[43;1m"
|
|
ansii_blue = "\u001b[34;1m"
|
|
ansii_blue_bg = "\u001b[44;1m"
|
|
ansii_magenta = "\u001b[35;1m"
|
|
ansii_magenta_bg = "\u001b[45;1m"
|
|
ansii_reset = "\u001b[0m"
|
|
|
|
thermo_colors = [
|
|
[ ansii_red, ansii_red_bg ],
|
|
[ ansii_yellow, ansii_yellow_bg ],
|
|
[ ansii_blue, ansii_blue_bg ],
|
|
[ ansii_magenta, ansii_magenta_bg ]
|
|
]
|
|
checker_colors_even = [ ansii_green_bg, ansii_green_bg ]
|
|
checker_colors_odd = [ ansii_reset ]
|
|
|
|
@dataclass(frozen=True, repr=False)
|
|
class Cell:
|
|
row: int
|
|
col: int
|
|
|
|
@dataclass(frozen=True)
|
|
class FilledCell(Cell):
|
|
value: int
|
|
def __repr_(self):
|
|
return f"f{self.value}"
|
|
|
|
@dataclass(frozen=True, repr=False)
|
|
class GivenCell(FilledCell):
|
|
def __repr__(self):
|
|
return f"{self.value}"
|
|
|
|
@dataclass(frozen=True, repr=False)
|
|
class SolvedCell(FilledCell):
|
|
def __repr__(self):
|
|
return f"{self.value}"
|
|
|
|
@dataclass(frozen=True, repr=False)
|
|
class EmptyCell(Cell):
|
|
def __repr__(self):
|
|
parity = ((self.row // 3) + (self.col // 3)) % 2 == 0
|
|
color = checker_colors_odd[0] if parity else checker_colors_even[0]
|
|
return f"{color}.{ansii_reset}"
|
|
|
|
@dataclass(frozen=True, repr=False)
|
|
class Thermo(Cell):
|
|
value: int
|
|
color: int
|
|
def __repr__(self):
|
|
parity = ((self.row // 3) + (self.col // 3)) % 2
|
|
color = thermo_colors[self.color][parity]
|
|
return f"{color}{self.value}{ansii_reset}"
|
|
|
|
@dataclass(frozen=True)
|
|
class Link:
|
|
fr: FilledCell
|
|
to: FilledCell
|
|
|
|
def pp(c: Cell):
|
|
if isinstance(c, GivenCell):
|
|
return f"{c.value!s}"
|
|
if isinstance(c, SolvedCell):
|
|
return f"{ansii_green}{str(c.value)}{ansii_reset}"
|
|
if isinstance(c, EmptyCell):
|
|
return " "
|
|
return "_"
|
|
|
|
Path = list[Link]
|
|
|
|
def empty_grid() -> list[list[Cell]]:
|
|
return [ [ EmptyCell(i,j) for j in range(9)] for i in range(9) ]
|
|
|
|
class Sudoku:
|
|
def __init__(self, grid):
|
|
self.grid = grid
|
|
|
|
def _row_values(self, i):
|
|
return [ cell.value for j in range(9) if isinstance(cell := self.grid[i][j], FilledCell) ]
|
|
|
|
def _col_values(self, j):
|
|
return [ cell.value for i in range(9) if isinstance(cell := self.grid[i][j], FilledCell) ]
|
|
|
|
def _blk_values(self, i,j):
|
|
return [ cell.value for ioff in range(3) for joff in range(3) if isinstance(cell := self.grid[(i//3)*3 + ioff ][(j//3)*3 + joff], FilledCell) ]
|
|
|
|
def _possible(self, i, j, v):
|
|
return (v not in self._row_values(i)) and (v not in self._col_values(j)) and (v not in self._blk_values(i,j))
|
|
|
|
def __repr__(self):
|
|
return "\n".join(map(lambda x: "".join(str(x)), self.grid))
|
|
|
|
def solve(self):
|
|
for i in range(9):
|
|
for j in range(9):
|
|
if isinstance(self.grid[i][j], EmptyCell):
|
|
for v in range(1,10):
|
|
if self._possible(i, j, v):
|
|
self.grid[i][j] = SolvedCell(row=i, col=j, value=v)
|
|
yield from self.solve()
|
|
self.grid[i][j] = EmptyCell(row = i, col = j)
|
|
return
|
|
yield [ [ entry for entry in row ] for row in self.grid ]
|
|
|
|
@classmethod
|
|
def read_grid(cls) -> list[list[Cell]]:
|
|
grid : list[list[Cell]] = empty_grid()
|
|
for i in range(9):
|
|
row = input()
|
|
for j in range(9):
|
|
if row[j] == " " or row[j] == "0":
|
|
grid[i][j] = EmptyCell(row=i, col=j)
|
|
else:
|
|
grid[i][j] = GivenCell(row=i, col=j, value=int(row[j]))
|
|
return grid
|
|
|
|
grid: list[list[Cell]] = Sudoku.read_grid()
|
|
s = Sudoku(grid)
|
|
solution: list[list[FilledCell]] = [x for x in s.solve()][0]
|
|
|
|
offset_list = [ [0, 1], [1, 0], [1, 1], [-1, 1] ]
|
|
def gen_links(grid) -> Iterator[Link]:
|
|
for i in range(9):
|
|
for j in range(9):
|
|
for offset in offset_list:
|
|
c1 = grid[i][j]
|
|
x, y = i + offset[0], j + offset[1]
|
|
if (x < 0 or x > 8 or y < 0 or y > 8):
|
|
continue
|
|
c2 = grid[x][y]
|
|
if (c1.value > c2.value):
|
|
yield Link(c2, c1)
|
|
if (c1.value < c2.value):
|
|
yield Link(c1, c2)
|
|
|
|
|
|
printable_solution = [ " ".join(list(map(pp, row))) for row in solution ]
|
|
print("\n".join(printable_solution))
|
|
|
|
# build implicit graph
|
|
links = [link for link in gen_links(solution)]
|
|
adj = [ ([ [] for j in range(9) ]) for i in range(9) ]
|
|
#print(links)
|
|
for link in links:
|
|
#print(link)
|
|
adj[link.fr.row][link.fr.col].append(link.to)
|
|
|
|
neighbor_matrix = [[-1,-1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]
|
|
def neighbors(board: list[list[FilledCell]], cell: Cell) -> Iterator[FilledCell]:
|
|
for offset in neighbor_matrix:
|
|
x, y = cell.row + offset[1], cell.col + offset[0]
|
|
if (x < 0 or x > 8 or y < 0 or y > 8):
|
|
continue
|
|
yield board[x][y]
|
|
|
|
def all_cells_of_value(board: list[list[FilledCell]], filter: int) -> Iterator[FilledCell]:
|
|
fields = all_cells(board)
|
|
for field in [ f for f in fields if f.value == filter ]:
|
|
yield field
|
|
|
|
def all_cells(board: list[list[FilledCell]]) -> Iterator[FilledCell]:
|
|
yield from [ field for row in board for field in row ]
|
|
|
|
def pP(path: Path) -> str:
|
|
return " ".join(list(map(lambda link: str(link.to.value), path)))
|
|
|
|
paths: dict[FilledCell, list[Path]] = {}
|
|
for cell in all_cells_of_value(solution, 9):
|
|
paths[cell] = []
|
|
|
|
for value in range(8,0, -1):
|
|
cells = all_cells_of_value(solution, value)
|
|
for cell in cells:
|
|
paths[cell] = []
|
|
for neighbor in neighbors(solution, cell):
|
|
if neighbor.value <= cell.value: continue
|
|
# neighbor is larger
|
|
new_path: Path = [Link(cell, neighbor)]
|
|
extended_paths : list[Path] = [ new_path + path for path in paths[neighbor]]
|
|
all_paths = [new_path] + extended_paths
|
|
paths[cell].extend(all_paths)
|
|
|
|
all_paths : list[Path] = [ path for cell in all_cells(solution) for path in paths[cell] ]
|
|
|
|
def get_cells(path: Path) -> Iterator[FilledCell]:
|
|
yield path[0].fr
|
|
for link in path:
|
|
yield link.to
|
|
|
|
def ilike(path: Path) -> bool:
|
|
if len(path) < 4: return False
|
|
#def four_fold_link(link: Link) -> bool:
|
|
# return abs(link.fr.row - link.to.row) + abs(link.fr.col - link.to.col) == 1
|
|
cells = [cell for cell in get_cells(path) ]
|
|
given_cells = [ cell for cell in cells if isinstance(cell, GivenCell)]
|
|
if isinstance(cells[0], GivenCell) or isinstance(cells[-1], GivenCell): return False
|
|
|
|
#neighboring_values = list(zip(solved_values, solved_values[1:]))
|
|
#combinations = prod( map(lambda x: x[1] - x[0] - 1, neighboring_values) )
|
|
#print(combinations, solved_values)
|
|
#all_four_fold = all( [ four_fold_link(link) for link in path] )
|
|
max_one_solved = len(given_cells) < 2
|
|
return max_one_solved
|
|
|
|
# print("all paths are", len(all_paths), "paths")
|
|
|
|
hints : list[list[Thermo | Cell]] = empty_grid()
|
|
used_cells: set[FilledCell] = set()
|
|
num_paths = 4
|
|
while num_paths > 0:
|
|
while True:
|
|
path: Path = choice([path for path in all_paths])
|
|
cells = [ cell for cell in get_cells(path)]
|
|
if not all([ cell not in used_cells for cell in cells ]): continue
|
|
if not ilike(path): continue
|
|
for index, cell in enumerate(cells):
|
|
used_cells.add(cell)
|
|
row, col = cell.row, cell.col
|
|
hints[row][col] = Thermo(row, col, index, num_paths - 1)
|
|
num_paths -= 1
|
|
break
|
|
|
|
strs = [ " ".join([str(entry) for entry in row]) for row in hints]
|
|
|
|
|
|
print("\n".join(strs))
|