189 lines
5.1 KiB
Python
189 lines
5.1 KiB
Python
import sys
|
|
import json
|
|
from pydantic import BaseModel
|
|
from itertools import count
|
|
|
|
class Sudoku(BaseModel):
|
|
field: list[list[int]]
|
|
num_fields: int
|
|
row_block: int = 0
|
|
col_block: int = 0
|
|
|
|
def inCol(array:list[list[int]], col: int, num: int) -> bool:
|
|
"""Docstring for inRow.
|
|
:array: Representation of the sudoku array
|
|
:col: number of the column
|
|
:num: number searched in column
|
|
:returns: True if column contains num, otherwise False
|
|
"""
|
|
iter = (row[col] for row in array)
|
|
return (num in iter)
|
|
|
|
|
|
def inRow(array: list[list[int]], row: int, num: int) -> bool:
|
|
"""Docstring for inRow.
|
|
:array: Representation of the sudoku array
|
|
:row: number of the row
|
|
:num: number searched in row
|
|
:returns: True if row contains num, otherwise False
|
|
"""
|
|
assert(len(array)> row)
|
|
return (num in array[row])
|
|
|
|
def inBlock(
|
|
array: list[list[int]], row: int, col: int, rb: int, cb: int, num: int
|
|
) -> bool:
|
|
"""Docstring for inRow.
|
|
:array: Representation of the sudoku array
|
|
:row: vertical dimension of the block
|
|
:col: horizontal dimension of the block
|
|
:rb: row dimension of a block
|
|
:cb: col dimension of a block
|
|
:num: number searched in row
|
|
:returns: True if block contains num, otherwise False
|
|
"""
|
|
iter = (array[x][y] for x in range(rb*row, rb*(row+1)) for y in
|
|
range(cb*col, cb*(col+1)))
|
|
return (num in iter)
|
|
|
|
|
|
def readSudoku(filename: str) -> Sudoku | None:
|
|
"""Docstring for readSudoku.
|
|
|
|
:filename: filename of the soduko in json
|
|
:returns: list of list arrays
|
|
|
|
"""
|
|
with open(filename, "r+") as fd:
|
|
try:
|
|
obj = json.load(fd)
|
|
except ValueError:
|
|
return None
|
|
a = Sudoku(**obj)
|
|
sq = ((x,x*x) for x in count())
|
|
for x,y in sq:
|
|
if y == a.num_fields:
|
|
a.row_block = x
|
|
a.col_block = x
|
|
break
|
|
if y > a.num_fields:
|
|
break
|
|
rows = a.row_block
|
|
cols = a.col_block
|
|
assert (rows*cols == a.num_fields)
|
|
return a
|
|
|
|
def find_positions(array: list[list[int]]) -> list[tuple[int,int]]:
|
|
"""TODO: Docstring for find_positions.
|
|
|
|
:array: TODO
|
|
:returns: TODO
|
|
|
|
"""
|
|
return [(x,y) for x in range(len(array)) for y in range(len(array[x]))
|
|
if array[x][y] == 0
|
|
]
|
|
def fits(S: Sudoku, x, y):
|
|
"""TODO: Docstring for fits.
|
|
|
|
:Sudoku: TODO
|
|
:returns: TODO
|
|
|
|
"""
|
|
b = S.field[x][y]
|
|
S.field[x][y] = 0
|
|
cond = inRow(S.field, x, b)
|
|
cond = cond or inCol(S.field, y, b)
|
|
cond = cond or inBlock(
|
|
S.field, x // S.row_block, y // S.col_block, S.row_block, S.col_block, b
|
|
)
|
|
# Reset variable
|
|
S.field[x][y] = b
|
|
return not cond
|
|
|
|
def solve(Sudoku) -> bool:
|
|
num_pos = 0
|
|
poss: list[tuple[int,int]] = find_positions(Sudoku.field)
|
|
while num_pos < len(poss) and num_pos >= 0:
|
|
x = poss[num_pos][0]
|
|
y = poss[num_pos][1]
|
|
Sudoku.field[x][y]+=1
|
|
if Sudoku.field[x][y] > Sudoku.num_fields:
|
|
num_pos -= 1
|
|
Sudoku.field[x][y] = 0
|
|
continue
|
|
elif fits(Sudoku, x, y) :
|
|
num_pos+= 1
|
|
else:
|
|
continue
|
|
|
|
return num_pos == len(poss)
|
|
|
|
def check_array(Sudoku : Sudoku) -> bool:
|
|
num_rows = len(Sudoku.field)
|
|
if num_rows != Sudoku.num_fields:
|
|
return False
|
|
for row in range(num_rows):
|
|
num_cols = len(Sudoku.field[row])
|
|
if num_cols != Sudoku.num_fields:
|
|
return False
|
|
return True
|
|
|
|
|
|
def main(argv: list[str]) -> None:
|
|
if len(argv) < 1 :
|
|
return
|
|
filename = argv[1]
|
|
a = readSudoku(filename)
|
|
if a is None:
|
|
print("Read failed")
|
|
return
|
|
s : Sudoku = a
|
|
if not check_array(s) :
|
|
sys.exit(-1)
|
|
if not solve(s):
|
|
print("Not solvable")
|
|
else:
|
|
for row in s.field:
|
|
for col in row:
|
|
print(col, end=" ")
|
|
print()
|
|
return
|
|
|
|
|
|
def initSudoku() -> Sudoku:
|
|
field = [
|
|
[1, 2, 3, 4, 5, 0, 7, 8, 9],
|
|
[4, 5, 0, 7, 8, 9, 1, 2, 3],
|
|
[7, 8, 9, 1, 2, 3, 4, 5, 6],
|
|
[0] * 9,
|
|
[0] * 9,
|
|
[0] * 9,
|
|
[1, 2, 3, 4, 5, 0, 7, 8, 9],
|
|
[4, 5, 0, 7, 8, 9, 1, 2, 3],
|
|
[7, 8, 9, 1, 2, 3, 4, 5, 6],
|
|
]
|
|
return Sudoku(field=field, num_fields=9, row_block=3, col_block=3)
|
|
def test():
|
|
s = initSudoku()
|
|
assert inBlock(s.field, 0, 1, 3, 3, 6) == False
|
|
assert inBlock(s.field, 0, 2, 3, 3, 6) == True
|
|
assert inBlock(s.field, 0, 0, 3, 3, 6) == False
|
|
assert inBlock(s.field, 2, 0, 3, 3, 6) == False
|
|
assert inBlock(s.field, 2, 1, 3, 3, 6) == False
|
|
assert inBlock(s.field, 2, 2, 3, 3, 6) == True
|
|
assert inRow(s.field, 0 ,6) == False
|
|
assert inRow(s.field, 1 ,6) == False
|
|
assert inRow(s.field, 2 ,6) == True
|
|
assert inRow(s.field, 6 ,6) == False
|
|
assert inRow(s.field, 7 ,6) == False
|
|
assert inRow(s.field, 8 ,6) == True
|
|
assert inCol(s.field, 0, 6) == False
|
|
assert inCol(s.field, 1, 6) == False
|
|
assert inCol(s.field, 2, 6) == False
|
|
assert inCol(s.field, 7, 6) == False
|
|
assert inCol(s.field, 8, 6) == True
|
|
|
|
if __name__ == "__main__":
|
|
main(sys.argv)
|