PierreQuentel
commented
1 year ago Thanks for the report, but I think you should take a second look at your code, isinstance() has been present in all versions of Brython since the beginning.
Closed hebozhe closed 1 year ago
PierreQuentel
commented
1 year ago Thanks for the report, but I think you should take a second look at your code, isinstance() has been present in all versions of Brython since the beginning.
lefranco
commented
1 year ago I confirm : I use it quite a lot (I am in 3.11.0)
hebozhe
commented
1 year ago I built the bulk of program in a .py first, completely error-free, and then exported it with proper spacing into the HTML doc. Is there another reason why undef isinstance undefined appears as an error?
PierreQuentel
commented
1 year ago Can you post a minimal example of an HTML page with embedded Python code that raises this error ?
hebozhe
commented
1 year ago It's fairly large, but this will throw the error, though the source file from which it comes throws no such errors and passes tests fine:
<html>
<head>
<title>RC's Sudoku Solver</title>
<meta charset="utf-8">
<script type="text/javascript" src="[https://cdn.jsdelivr.net/npm/brython@3.10.0/brython.min.js](view-source:https://cdn.jsdelivr.net/npm/brython@3.10.0/brython.min.js)"></script>
<script type="text/javascript" src="[https://cdn.jsdelivr.net/npm/brython@3.10.0/brython_stdlib.js](view-source:https://cdn.jsdelivr.net/npm/brython@3.10.0/brython_stdlib.js)"></script>
</head>
<body onload="brython(1)">
<table id="sudokuTable">
</table>
<form onsubmit="return false">
<input id="sudokuInput" size="90">
<br>
<button type="submit" title="Click here to update the sudoku grid."
onclick="updateSudokuTable();">Submit</button>
<button id="solveBtn" title="Click here to solve the current sudoku grid.">Solve</button>
<button title="Click here to clear the text." onclick="sudokuInput.value = ''">Clear</button>
</form>
<script src="[distrib/index.js](view-source:file:///home/hebozhe/Dropbox/DevProjects/TypeScriptProjects/SudokuSolver/distrib/index.js)"></script>
<script id="brythoncode" type="text/python">
from browser import document, bind
from itertools import combinations
unsolved_puzz: list[list[int]] = []
@bind(document['solveBtn'], 'click')
def read_out_sudokuTable(ev: str) -> list[list[int]]:
'''
summary: Both update the unsolved_puzz global with and return
the 9 x 9 matrix from inside the sudokuTable element.
params:
ev: str indicating the event to which it's tied.
return: list[list[int]] of the contents of the sudokuTable element,
represented as a 9 x 9 matrix.
'''
# global unsolved_puzz
sdk_table: browser.html.TABLE = document.getElementById('sudokuTable')
sdk_table_ints: list[int] = [int(c) for c in sdk_table.html if c.isdigit()]
sdk_mtx: list[list[int]] = [sdk_table_ints[n:n+9] for n in range(0, 81, 9)]
# unsolved_puzz is in our global scope. If we can avoid that, we should.
unsolved_puzz = [row for row in sdk_mtx if len(row) == 9]
print(unsolved_puzz)
return sdk_mtx
# <PASTE SOLVER HERE>
# START: The code below solves the sudoku puzzle.
# Constants
UnsolvedDict = dict[tuple[int, int], int | set[int]]
SolvedDict = dict[tuple[int, int], int]
# Functions
def convert_puzzle(puzz: list[list[int]]) -> UnsolvedDict:
'''
summary: Convert a normal sudoku puzzle from a 9 x 9 matrix
to a dictionary of coordinate keys and integer choice values.
params:
puzz: list[list[int]] of a (potentially) unsolved sudoku puzzle.
return: UnsolvedDict of a potential sudoku puzzle.
clarification:
coord_intorset_dict: UnsolvedDict = {}
for r in range(0, 9):
for c in range(0, 9):
if puzz[r][c] > 0:
coord_intorset_dict[(r, c)] = puzz[r][c]
else:
# set(range(1, 10)) means {1, 2, 3, 4, 5, 6, 7, 8, 9}
coord_intorset_dict[(r, c)] = set(range(1, 10))
'''
return {(r, c): (puzz[r][c] if puzz[r][c] > 0 else set(range(1, 10)))
for r in range(0, 9) for c in range(0, 9)}
def deconvert_puzzle(puzz: UnsolvedDict) -> list[list[int]]:
'''
TODO: Write the docstring.
'''
deconv_puzz: list[list[int]] = \
[[0 for _ in range(0, 9)] for _ in range(0, 9)]
for (_r, _c), val in puzz.items():
if isinstance(val, int):
deconv_puzz[_r][_c] = val
return deconv_puzz
def pick_row(row: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose row value matches the row parameter.
params:
row: int of the row whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the row.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
return {(r, c): v for (r, c), v in from_udict.items() if r == row}
def pick_col(col: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose column value matches the col parameter.
params:
col: int of the col whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the col.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
return {(r, c): v for (r, c), v in from_udict.items() if c == col}
def pick_blk(row: int, col: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose column value matches the col parameter.
params:
row: int of the row whose data we seek to update.
col: int of the col whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the col.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
row, col = (row // 3) * 3, (col // 3) * 3
return {(r, c): v for (r, c), v in from_udict.items()
if row <= r < row + 3 and col <= c < col + 3}
def pop_singles(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Convert the single-length set values
from an unsolved sudoku puzzle to their integers.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return UnsolvedDict with all single-length sets converted
to their int values.
'''
return {k: v.pop() if isinstance(v, set) and len(v) == 1 else v
for k, v in from_udict.items()}
def remove_knowns(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find the integers in the sudoku puzzle and remove all of them
from their found positions' corresponding rows, cols, and blks.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for (_r, _c), val in from_udict.items():
if isinstance(val, set):
continue
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
ucol: UnsolvedDict = pick_col(col=_c, from_udict=from_udict)
ublk: UnsolvedDict = pick_blk(row=_r, col=_c, from_udict=from_udict)
# v is a set, val is an int, and {val} is a set[int].
# This line freaking updates from_udict:
from_udict |= {k: v - {val} for k, v in (urow | ucol | ublk).items()
if isinstance(v, set)}
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
return remove_knowns(from_udict=popped_dict)
def remove_nakeds(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find all naked pairs, triples, and quadruples
and remove them from offending rows, cols, and blks of a sudoku puzzle.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for cell_count in range(2, 5):
for _r in range(0, 9):
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
urow_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(urow_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(urow_sets.keys(), r=cell_count))
# print(f'ROW {_r} COMBINATIONS', urow_sets, coord_combos)
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[urow_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED ROW {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in urow_sets.items()
if k not in combo}
from_udict |= update_dict
for _c in range(0, 9):
ucol: UnsolvedDict = pick_col(col=_c, from_udict=from_udict)
ucol_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(ucol_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(ucol_sets, r=cell_count))
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[ucol_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED COL {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in ucol_sets.items()
if k not in combo}
from_udict |= update_dict
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _r, _c in top_lefts:
ublk: UnsolvedDict = \
pick_blk(row=_r, col=_c, from_udict=from_udict)
ublk_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(ublk_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(ublk_sets, r=cell_count))
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[ublk_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED BLK {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in ublk_sets.items()
if k not in combo}
from_udict |= update_dict
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
popped_dict = remove_knowns(from_udict=popped_dict)
return remove_nakeds(from_udict=popped_dict)
def remove_hiddens(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find all hidden singles, pairs, triples, and quadruples
and remove them from offending rows, cols, and blks of a sudoku puzzle.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for h_size in range(1, 5):
for _r in range(0, 9):
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
urow_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*urow_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN ROW {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
for _c in range(0, 9):
ucol: UnsolvedDict = pick_row(row=_c, from_udict=from_udict)
ucol_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*ucol_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN COL {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _r, _c in top_lefts:
ublk: UnsolvedDict = \
pick_blk(row=_r, col=_c, from_udict=from_udict)
ublk_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*ublk_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN BLK {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
popped_dict = remove_knowns(from_udict=popped_dict)
return remove_hiddens(from_udict=popped_dict)
def is_valid(this_udict: UnsolvedDict) -> bool:
'''
summary: Assess a sudoku puzzle for validity.
A sudoku puzzle that is not invalid is still valid.
A sudoku puzzle is invalid if...
Duplicate numbers are in a row, column, or block.
A cell of available integers (a set of integers) is empty.
params:
this_udict: UnbsolvedDict of the sudoku puzzle being checked.
return: bool of True if it is valid and False if it is not.
'''
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _x in range(0, 9):
urow: UnsolvedDict = pick_row(row=_x, from_udict=this_udict)
urow_ints: list[int] = [v for v in urow.values() if isinstance(v, int)]
if len(urow_ints) > len(set(urow_ints)):
return False
ucol: UnsolvedDict = pick_col(col=_x, from_udict=this_udict)
ucol_ints: list[int] = [v for v in ucol.values() if isinstance(v, int)]
if len(ucol_ints) > len(set(ucol_ints)):
return False
_r, _c = top_lefts[_x]
ublk: UnsolvedDict = pick_blk(row=_r, col=_r, from_udict=this_udict)
ublk_ints: list[int] = [v for v in ublk.values() if isinstance(v, int)]
if len(ublk_ints) > len(set(ublk_ints)):
return False
if set() in this_udict.values():
return False
return True
def is_filled(this_udict: UnsolvedDict) -> bool:
'''
summary: Assess whether a sudoku puzzle is completely filled
with integers.
params:
this_udict: UnsolvedDict of the sudoku puzzle being checked.
return: bool of True if it is completely filled; False otherwise.
'''
return all(isinstance(v, int) for v in this_udict.values())
def build_guesses(from_udict: UnsolvedDict) -> list[UnsolvedDict]:
'''
summary: Find the first instance of a set of integers
(i.e., and unsolved cell) in an unsolved sudoku puzzle.
Build a list of guess sudoku puzzles that, rather than
keeping the set, replace it with one of the integers
from the first found instance.
params:
from_udict: UnsolvedDict from which other UnsolvedDicts will be
built.
return: list[UnsolvedDict] of those newly built guesses.
'''
subst_key: tuple[int, int] = (0, 0)
subst_set: set[int] = set()
for coord, val in from_udict.items():
if isinstance(val, set):
subst_key, subst_set = coord, val
break
guesses_list: list[UnsolvedDict] = []
for subst_int in subst_set:
guess_dict: UnsolvedDict = from_udict | {subst_key: subst_int}
guesses_list.append(guess_dict)
return guesses_list
def solve(this_puzz: list[list[int]]) -> list[list[int]]:
'''
summary: Using the basic functions and an iterative guesser,
find and return solutions to a sudoku puzzle.
params:
this_puss: list[list[int]] of the unsolved puzzle.
return: list[list[int]] of the solved puzzle.
'''
seed_udict: UnsolvedDict = convert_puzzle(puzz=this_puzz)
solved_dicts: list[UnsolvedDict] = []
unsolved_dicts: list[UnsolvedDict] = [seed_udict]
while unsolved_dicts:
try_dict: UnsolvedDict = unsolved_dicts.pop()
while is_valid(this_udict=try_dict):
if is_filled(this_udict=try_dict):
solved_dicts.append(try_dict)
break
upd_dict = remove_knowns(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
upd_dict = remove_nakeds(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
upd_dict = remove_hiddens(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
unsolved_dicts.extend(build_guesses(from_udict=try_dict))
break
print(f'\rGUESS COUNT: {len(unsolved_dicts)}',
f'SOLUTIONS COUNT: {len(solved_dicts)}', end='\n')
if solved_dicts:
return deconvert_puzzle(puzz=solved_dicts[0])
return deconvert_puzzle(puzz=seed_udict)
# END: The code above solves the sudoku puzzle.
# </PASTE SOLVER HERE>
# Run some procedural code to execute the function and solve the sudoku puzzle.
</script>
</body>
</html>Thanks @hebozhe.
I could not run the script because a script SudokuSolver/distrib/index.js is missing, but I found a Brython bug for the line
UnsolvedDict = dict[tuple[int, int], int | set[int]]The bug is fixed in the commit referenced above. Can you test your code with the latest development version ?
hebozhe
commented
1 year ago Thanks @hebozhe. I could not run the script because a script
SudokuSolver/distrib/index.jsis missing, but I found a Brython bug for the lineUnsolvedDict = dict[tuple[int, int], int | set[int]]The bug is fixed in the commit referenced above. Can you test your code with the latest development version ?
Has it been pushed to JsDelivr, or will I need to clone it?
PierreQuentel
commented
1 year ago The current development version should be available by
<script src="https://raw.githack.com/brython-dev/brython/master/www/src/brython.js"></script>
<script src="https://raw.githack.com/brython-dev/brython/master/www/src/brython_stdlib.js"></script>If it doesn't work you will have to clone the repository.
hebozhe
commented
1 year ago That did solve one of the problems. However, in remove_knowns() (and I suspect elsewhere), an incorrect error is thrown:
"RuntimeError: dictionary changed size during iteration."
I know from my testing from my .py side of things that this is not the case. The update via the |= seems to be tripping Brython up.
This can also be verified with print(len(from_udict)) statements before and after the |= operation. The length does not change.
Here's all the updated code:
<html>
<head>
<title>RC's Sudoku Solver</title>
<meta charset="utf-8">
<script type="text/javascript" src="https://raw.githack.com/brython-dev/brython/master/www/src/brython.js"></script>
<script type="text/javascript"
src="https://raw.githack.com/brython-dev/brython/master/www/src/brython_stdlib.js"></script>
</head>
<body onload="brython(1)">
<table id="sudokuTable">
</table>
<form onsubmit="return false">
<input id="sudokuInput" size="90">
<br>
<button id="sbmtBtn" type="submit" title="Click here to update the sudoku grid."
onclick="updateSudokuTable();">Submit</button>
<button id="solveBtn" title="Click here to solve the current sudoku grid.">Solve</button>
<button title="Click here to clear the text." onclick="sudokuInput.value = ''">Clear</button>
</form>
<script src="distrib/index.js"></script>
<script id="brythoncode" type="text/python">
from browser import document, bind
from itertools import combinations
unsolved_puzz: list[list[int]] = []
@bind(document['sbmtBtn'], 'click')
def read_out_sudokuTable(ev: str) -> None:
'''
summary: Both update the unsolved_puzz global with and return
the 9 x 9 matrix from inside the sudokuTable element.
params:
ev: str indicating the event to which it's tied.
return: list[list[int]] of the contents of the sudokuTable element,
represented as a 9 x 9 matrix.
'''
global unsolved_puzz
sdk_table: browser.html.TABLE = document.getElementById('sudokuTable')
sdk_table_ints: list[int] = [int(c) for c in sdk_table.html if c.isdigit()]
sdk_mtx: list[list[int]] = [sdk_table_ints[n:n+9] for n in range(0, 81, 9)]
# unsolved_puzz is in our global scope. If we can avoid that, we should.
unsolved_puzz = [row for row in sdk_mtx if len(row) == 9]
print(unsolved_puzz)
return None
# <PASTE SOLVER HERE>
# START: The code below solves the sudoku puzzle.
# Constants
UnsolvedDict = dict[tuple[int, int], int | set[int]]
SolvedDict = dict[tuple[int, int], int]
# Functions
def convert_puzzle(puzz: list[list[int]]) -> UnsolvedDict:
'''
summary: Convert a normal sudoku puzzle from a 9 x 9 matrix
to a dictionary of coordinate keys and integer choice values.
params:
puzz: list[list[int]] of a (potentially) unsolved sudoku puzzle.
return: UnsolvedDict of a potential sudoku puzzle.
clarification:
coord_intorset_dict: UnsolvedDict = {}
for r in range(0, 9):
for c in range(0, 9):
if puzz[r][c] > 0:
coord_intorset_dict[(r, c)] = puzz[r][c]
else:
# set(range(1, 10)) means {1, 2, 3, 4, 5, 6, 7, 8, 9}
coord_intorset_dict[(r, c)] = set(range(1, 10))
'''
return {(r, c): (puzz[r][c] if puzz[r][c] > 0 else set(range(1, 10)))
for r in range(0, 9) for c in range(0, 9)}
def deconvert_puzzle(puzz: UnsolvedDict) -> list[list[int]]:
'''
TODO: Write the docstring.
'''
deconv_puzz: list[list[int]] = \
[[0 for _ in range(0, 9)] for _ in range(0, 9)]
for (_r, _c), val in puzz.items():
if isinstance(val, int):
deconv_puzz[_r][_c] = val
return deconv_puzz
def pick_row(row: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose row value matches the row parameter.
params:
row: int of the row whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the row.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
return {(r, c): v for (r, c), v in from_udict.items() if r == row}
def pick_col(col: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose column value matches the col parameter.
params:
col: int of the col whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the col.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
return {(r, c): v for (r, c), v in from_udict.items() if c == col}
def pick_blk(row: int, col: int, from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Pick every item from a sudoku puzzle (as a dictionary)
whose column value matches the col parameter.
params:
row: int of the row whose data we seek to update.
col: int of the col whose data we seek to update.
from_udict: UnsolvedDict of the sudoku puzzle from which to fetch the col.
return: UnsolvedDict of the sought portion of the sudoku puzzle.
'''
row, col = (row // 3) * 3, (col // 3) * 3
return {(r, c): v for (r, c), v in from_udict.items()
if row <= r < row + 3 and col <= c < col + 3}
def pop_singles(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Convert the single-length set values
from an unsolved sudoku puzzle to their integers.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return UnsolvedDict with all single-length sets converted
to their int values.
'''
return {k: v.pop() if isinstance(v, set) and len(v) == 1 else v
for k, v in from_udict.items()}
def remove_knowns(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find the integers in the sudoku puzzle and remove all of them
from their found positions' corresponding rows, cols, and blks.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for (_r, _c), val in from_udict.items():
if isinstance(val, set):
continue
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
ucol: UnsolvedDict = pick_col(col=_c, from_udict=from_udict)
ublk: UnsolvedDict = pick_blk(row=_r, col=_c, from_udict=from_udict)
# v is a set, val is an int, and {val} is a set[int].
# This line freaking updates from_udict:
print(len(from_udict))
from_udict |= {k: v - {val} for k, v in (urow | ucol | ublk).items()
if isinstance(v, set)}
print(len(from_udict))
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
return remove_knowns(from_udict=popped_dict)
def remove_nakeds(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find all naked pairs, triples, and quadruples
and remove them from offending rows, cols, and blks of a sudoku puzzle.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for cell_count in range(2, 5):
for _r in range(0, 9):
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
urow_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(urow_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(urow_sets.keys(), r=cell_count))
# print(f'ROW {_r} COMBINATIONS', urow_sets, coord_combos)
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[urow_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED ROW {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in urow_sets.items()
if k not in combo}
from_udict |= update_dict
for _c in range(0, 9):
ucol: UnsolvedDict = pick_col(col=_c, from_udict=from_udict)
ucol_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(ucol_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(ucol_sets, r=cell_count))
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[ucol_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED COL {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in ucol_sets.items()
if k not in combo}
from_udict |= update_dict
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _r, _c in top_lefts:
ublk: UnsolvedDict = \
pick_blk(row=_r, col=_c, from_udict=from_udict)
ublk_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk.items()
if isinstance(v, set) and len(v) <= cell_count}
if len(ublk_sets) <= cell_count:
continue
coord_combos: list[tuple[tuple[int, int], ...]] = \
list(combinations(ublk_sets, r=cell_count))
for combo in coord_combos:
coord_set: set[int] = set()
coord_set = coord_set.union(*[ublk_sets[k] for k in combo])
if len(coord_set) != cell_count:
continue
# print(f'NAKED BLK {combo}: {coord_set}')
update_dict = {k: v - coord_set for k, v in ublk_sets.items()
if k not in combo}
from_udict |= update_dict
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
popped_dict = remove_knowns(from_udict=popped_dict)
return remove_nakeds(from_udict=popped_dict)
def remove_hiddens(from_udict: UnsolvedDict) -> UnsolvedDict:
'''
summary: Find all hidden singles, pairs, triples, and quadruples
and remove them from offending rows, cols, and blks of a sudoku puzzle.
params:
from_udict: UnsolvedDict of the sudoku puzzle.
return: UnsolvedDict of the (potentially) updated sudoku puzzle.
'''
for h_size in range(1, 5):
for _r in range(0, 9):
urow: UnsolvedDict = pick_row(row=_r, from_udict=from_udict)
urow_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*urow_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in urow_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN ROW {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
for _c in range(0, 9):
ucol: UnsolvedDict = pick_row(row=_c, from_udict=from_udict)
ucol_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*ucol_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ucol_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN COL {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _r, _c in top_lefts:
ublk: UnsolvedDict = \
pick_blk(row=_r, col=_c, from_udict=from_udict)
ublk_sets: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk.items() if isinstance(v, set)}
avail_ints: set[int] = set()
avail_ints = avail_ints.union(*ublk_sets.values())
set_combos: list[set[int]] = \
[set(c) for c in list(combinations(avail_ints, r=h_size))]
for combo in set_combos:
finds_dict: dict[tuple[int, int], set[int]] = \
{k: v for k, v in ublk_sets.items() if combo & v != set()}
if len(finds_dict) != h_size:
continue
# print(f'HIDDEN BLK {combo}: {tuple(finds_dict.keys())}')
if h_size == 1:
update_dict = {k: v.pop() for k, v in finds_dict.items()}
else:
update_dict = {k: combo & v for k, v in finds_dict.items()}
from_udict |= update_dict
popped_dict = pop_singles(from_udict=from_udict)
if popped_dict == from_udict:
return from_udict
popped_dict = remove_knowns(from_udict=popped_dict)
return remove_hiddens(from_udict=popped_dict)
def is_valid(this_udict: UnsolvedDict) -> bool:
'''
summary: Assess a sudoku puzzle for validity.
A sudoku puzzle that is not invalid is still valid.
A sudoku puzzle is invalid if...
Duplicate numbers are in a row, column, or block.
A cell of available integers (a set of integers) is empty.
params:
this_udict: UnbsolvedDict of the sudoku puzzle being checked.
return: bool of True if it is valid and False if it is not.
'''
top_lefts: tuple[tuple[int, int], ...] = \
((0, 0), (0, 3), (0, 6),
(3, 0), (3, 3), (3, 6),
(6, 0), (6, 3), (6, 6))
for _x in range(0, 9):
urow: UnsolvedDict = pick_row(row=_x, from_udict=this_udict)
urow_ints: list[int] = [v for v in urow.values() if isinstance(v, int)]
if len(urow_ints) > len(set(urow_ints)):
return False
ucol: UnsolvedDict = pick_col(col=_x, from_udict=this_udict)
ucol_ints: list[int] = [v for v in ucol.values() if isinstance(v, int)]
if len(ucol_ints) > len(set(ucol_ints)):
return False
_r, _c = top_lefts[_x]
ublk: UnsolvedDict = pick_blk(row=_r, col=_r, from_udict=this_udict)
ublk_ints: list[int] = [v for v in ublk.values() if isinstance(v, int)]
if len(ublk_ints) > len(set(ublk_ints)):
return False
if set() in this_udict.values():
return False
return True
def is_filled(this_udict: UnsolvedDict) -> bool:
'''
summary: Assess whether a sudoku puzzle is completely filled
with integers.
params:
this_udict: UnsolvedDict of the sudoku puzzle being checked.
return: bool of True if it is completely filled; False otherwise.
'''
return all(isinstance(v, int) for v in this_udict.values())
def build_guesses(from_udict: UnsolvedDict) -> list[UnsolvedDict]:
'''
summary: Find the first instance of a set of integers
(i.e., and unsolved cell) in an unsolved sudoku puzzle.
Build a list of guess sudoku puzzles that, rather than
keeping the set, replace it with one of the integers
from the first found instance.
params:
from_udict: UnsolvedDict from which other UnsolvedDicts will be
built.
return: list[UnsolvedDict] of those newly built guesses.
'''
subst_key: tuple[int, int] = (0, 0)
subst_set: set[int] = set()
for coord, val in from_udict.items():
if isinstance(val, set):
subst_key, subst_set = coord, val
break
guesses_list: list[UnsolvedDict] = []
for subst_int in subst_set:
guess_dict: UnsolvedDict = from_udict | {subst_key: subst_int}
guesses_list.append(guess_dict)
return guesses_list
def solve(this_puzz: list[list[int]]) -> list[list[int]]:
'''
summary: Using the basic functions and an iterative guesser,
find and return solutions to a sudoku puzzle.
params:
this_puss: list[list[int]] of the unsolved puzzle.
return: list[list[int]] of the solved puzzle.
'''
seed_udict: UnsolvedDict = convert_puzzle(puzz=this_puzz)
solved_dicts: list[UnsolvedDict] = []
unsolved_dicts: list[UnsolvedDict] = [seed_udict]
while unsolved_dicts:
try_dict: UnsolvedDict = unsolved_dicts.pop()
while is_valid(this_udict=try_dict):
if is_filled(this_udict=try_dict):
solved_dicts.append(try_dict)
break
upd_dict = remove_knowns(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
upd_dict = remove_nakeds(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
upd_dict = remove_hiddens(from_udict=try_dict)
if upd_dict != try_dict:
try_dict = upd_dict
continue
unsolved_dicts.extend(build_guesses(from_udict=try_dict))
break
print(f'\rGUESS COUNT: {len(unsolved_dicts)}',
f'SOLUTIONS COUNT: {len(solved_dicts)}', end='\n')
if solved_dicts:
return deconvert_puzzle(puzz=solved_dicts[0])
return deconvert_puzzle(puzz=seed_udict)
# END: The code above solves the sudoku puzzle.
# </PASTE SOLVER HERE>
@bind(document['solveBtn'], 'click')
def push_solution(ev: str) -> None:
'''
summary: Take the unsolved_puzz variable and use the solve()
function to solve it. Then, push the solution
into the table sudokuTable.
'''
global unsolved_puzz
solved_puzz = solve(this_puzz=unsolved_puzz)
print(solved_puzz)
return None
</script>
</body>
</html>Thanks again, this time I think I found where the bug was.
With the commit referenced above the script should run, however the performance can be improved so I keep the issue open.
PierreQuentel
commented
1 year ago The commits referenced above (complete rewriting of dict and set implementation) should greatly improve the execution speed.
I am closing the issue, but if you think there is still something wrong don't hesitate to comment again.
It appears not to be defined for the 3.9 or 3.10 implementations.