Tratando de encontrar una manera de comparar números en una matriz de 9×9 usando matrices de 3×3

Así que estoy tratando de resolver un problema que te hace comparar números en la cuadrícula de sudoku de 9×9 para ver si el juego de Sudoku tiene una cuadrícula de números válida / solucionable (lo que significa que las reglas de Sudoku se aplican a la cuadrícula dada). He resuelto bastante el problema, pero estoy atascado en esta última parte. He descubierto cómo resumir cada elemento en cada columna / fila, pero no puedo resolver completamente este problema hasta que realmente pueda verificar cada cuadrícula de 3×3 para ver si no hay números duplicados en ellos. Aquí es donde estoy atascado porque parece que no puedo obtener el algoritmo correcto para iterar a través de la matriz de una manera 3×3.

Intenté controlar la iteración completamente utilizando una serie de bucles para boost el número de índice determinado para que se mueva a lo largo de la matriz. Déjeme saber qué estoy haciendo mal, o si hay alguna otra forma posible y más elegante de resolver este problema (el uso de tantos bucles hace que mi código parezca largo y feo / menos eficiente).

def sudoku(grid): grid = [[1,3,2,5,4,6,9,8,7], [4,6,5,8,7,9,3,2,1], [7,9,8,2,1,3,6,5,4], [9,2,1,4,3,5,8,7,6], [3,5,4,7,6,8,2,1,9], [6,8,7,1,9,2,5,4,3], [5,7,6,9,8,1,4,3,2], [2,4,3,6,5,7,1,9,8], [8,1,9,3,2,4,7,6,5]] duplicate = set() numHolder = 0 for a in range(0,9): for b in range(0,9): numHolder+=grid[b][a] if numHolder!=45: return False numHolder=0 for b in range(0,9): for x in range(0, 9): numHolder += grid[b][x] if numHolder != 45: return False numHolder = 0 for b in range(0,3): for c in range(0,3): if grid[b][c] in duplicate: return False else: duplicate.add(grid[b][c]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d][c+3] in duplicate: return False else: duplicate.add(grid[d][c+3]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[b][c+6] in duplicate: return False else: duplicate.add(grid[d][c+6]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+3][c] in duplicate: return False else: duplicate.add(grid[d+3][c]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+3][c+3] in duplicate: return False else: duplicate.add(grid[d+3][c+3]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+3][c+6] in duplicate: return False else: duplicate.add(grid[d+3][c+6]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+6][c] in duplicate: return False else: duplicate.add(grid[d+6][c]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+6][c+3] in duplicate: return False else: duplicate.add(grid[d+6][c+3]) duplicate.clear() for d in range(0,3): for e in range(0,3): if grid[d+6][c+6] in duplicate: return False else: duplicate.add(grid[d+6][c+6]) return True 

Puede obtener una lista de 3×3 de su 9×9 con

 mats_3x3x9 = [grid[3*i:3*i+3] for i in range(3)] mats_9x3x3 = [ [row_1x9[3*i:3*i+3] for row_1x9 in rows_3x9] for i in range(3) for rows_3x9 in mats_3x3x9 ] 

A continuación, puede comprobar que cada 3×3 contiene el número del 1 al 9 con, por ejemplo,

 for mat_3x3 in mats_9x3x3: if not sorted([i for row in mat_3x3 for i in row]) == list(range(1,10)): return False return True 

Aunque probablemente podrías obtener las matrices más pequeñas con números

 import numpy as np mats_9x3x3 = np.array(grid) [mats_9x3x3[3*i:3*i+3, 3*j:3*j+3] for i in range(3) for j in range(3)] 

Entonces podría encontrar valores duplicados como en esta pregunta , por ejemplo,

 from collections import Counter for mat_3x3 in mats_9x3x3: if [item for item, count in Counter(mat_3x3).iteritems() if count > 1]: return False return True 

Esto se puede resolver fácilmente en NumPy:

 import numpy as np import skimage grid = [[1,3,2,5,4,6,9,8,7], [4,6,5,8,7,9,3,2,1], [7,9,8,2,1,3,6,5,4], [9,2,1,4,3,5,8,7,6], [3,5,4,7,6,8,2,1,9], [6,8,7,1,9,2,5,4,3], [5,7,6,9,8,1,4,3,2], [2,4,3,6,5,7,1,9,8], [8,1,9,3,2,4,7,6,5]] # Create NumPy array grid = np.array(grid) # Cut into 3x3 sublocks, and flatten each subblock subgrids = skimage.util.view_as_blocks(grid, (3, 3)).reshape(3, 3, -1) # Sort each subblock then compare each one with [1, 2, ..., 9]. If all are equal, it is a valid subblock valid_blocks = np.all(np.sort(subgrids, axis=-1) == np.arange(1, 10), axis=-1) # array([[ True, True, True], # [ True, True, True], # [ True, True, True]]) # Sort rows, then compare each one valid_rows = np.all(np.sort(grid, axis=1) == np.arange(1, 10), axis=1) # array([ True, True, True, True, True, True, True, True, True]) # Sort columns, then compare each one valid_columns = np.all(np.sort(grid, axis=0) == np.arange(1, 10)[:, None], axis=0) # array([ True, True, True, True, True, True, True, True, True]) # Check if all comparisons were all true all_valid = np.all(valid_blocks) & np.all(valid_rows) & np.all(valid_columns) # True 

Si desea verificar todas las restricciones de un sudoku en python plano, es mejor generar todas las restricciones como listas de valores que se pueden resumir:

 def check_constraints(constraints, target_sum): for _constraint in constraints: if sum(_constraint) != target_sum: return False return True 

Para extraer submatrices de una cuadrícula organizada como lista de filas, una iteración anidada sobre un conjunto de rangos horizontales y un conjunto de rangos verticales es suficiente:

 def get_grid_constraints(grid, h_ranges, v_ranges): constraints = [] for h_start, h_end in h_ranges: for v_start, v_end in v_ranges: _constraint = [] constraints.append(_constraint) for _line in grid[v_start:v_end]: _constraint.extend(_line[h_start:h_end]) return constraints 

Los dos conjuntos de rangos se generan con la función make_ranges :

 def make_ranges(h_step, v_step, length): return (make_range(h_step, length), make_range(v_step, length)) 

que llama a make_range para cada dirección:

 def make_range(step, width): range_ = [] _start = 0 for _end in range(step, width+1, step): range_.append((_start, _end)) _start = _end return range_ 

Para mantener el algoritmo flexible, los parámetros de la cuadrícula se definen como variables:

 SUDOKU_WIDTH = 3 SUDOKU_HEIGHT = 3 CONSTRAINT_LEN = SUDOKU_WIDTH * SUDOKU_HEIGHT CONSTRAINT_SUM = sum(range(CONSTRAINT_LEN + 1)) 

Los conjuntos de rangos generics se crean como:

 row_ranges = make_ranges(CONSTRAINT_LEN, 1, CONSTRAINT_LEN) col_ranges = make_ranges(1, CONSTRAINT_LEN, CONSTRAINT_LEN) quad_ranges = make_ranges(SUDOKU_WIDTH, SUDOKU_HEIGHT, CONSTRAINT_LEN) 

Las restricciones respectivas se extraen de la cuadrícula:

 rows = get_grid_constraints(GRID, *row_ranges) cols = get_grid_constraints(GRID, *col_ranges) quads = get_grid_constraints(GRID, *quad_ranges) 

para verificar contra el CONSTRAINT_SUM :

 is_valid = check_constraints(rows + cols + quads, CONSTRAINT_SUM) 

Esto permite una salida de depuración detallada para verificar el funcionamiento correcto de los algoritmos:

 dbg_fwid = 11 dbg_sep = '\n {1:<{0}s}'.format(dbg_fwid, '') def dbg_lists(lists): return dbg_sep.join((str(_l) for _l in lists)) def sformat(fmt, *args, **kwargs): return fmt.format(*args, **kwargs) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "CONSTRAINT_SUM", (CONSTRAINT_SUM))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "row_ranges", (row_ranges))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "col_ranges", (col_ranges))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "quad_ranges", (quad_ranges))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "rows", dbg_lists(rows))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "cols", dbg_lists(cols))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "quads", dbg_lists(quads))) print(sformat("# "":DBG: {1:<{0}s}: ]{2!s}[", dbg_fwid, "is_valid", (is_valid))) 

que muestra:

 CONSTRAINT_SUM: ]45[ row_ranges : ]([(0, 9)], [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)])[ col_ranges : ]([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)], [(0, 9)])[ quad_ranges: ]([(0, 3), (3, 6), (6, 9)], [(0, 3), (3, 6), (6, 9)])[ rows : ][1, 3, 2, 5, 4, 6, 9, 8, 7] [4, 6, 5, 8, 7, 9, 3, 2, 1] [7, 9, 8, 2, 1, 3, 6, 5, 4] [9, 2, 1, 4, 3, 5, 8, 7, 6] [3, 5, 4, 7, 6, 8, 2, 1, 9] [6, 8, 7, 1, 9, 2, 5, 4, 3] [5, 7, 6, 9, 8, 1, 4, 3, 2] [2, 4, 3, 6, 5, 7, 1, 9, 8] [8, 1, 9, 3, 2, 4, 7, 6, 5][ cols : ][1, 4, 7, 9, 3, 6, 5, 2, 8] [3, 6, 9, 2, 5, 8, 7, 4, 1] [2, 5, 8, 1, 4, 7, 6, 3, 9] [5, 8, 2, 4, 7, 1, 9, 6, 3] [4, 7, 1, 3, 6, 9, 8, 5, 2] [6, 9, 3, 5, 8, 2, 1, 7, 4] [9, 3, 6, 8, 2, 5, 4, 1, 7] [8, 2, 5, 7, 1, 4, 3, 9, 6] [7, 1, 4, 6, 9, 3, 2, 8, 5][ quads : ][1, 3, 2, 4, 6, 5, 7, 9, 8] [9, 2, 1, 3, 5, 4, 6, 8, 7] [5, 7, 6, 2, 4, 3, 8, 1, 9] [5, 4, 6, 8, 7, 9, 2, 1, 3] [4, 3, 5, 7, 6, 8, 1, 9, 2] [9, 8, 1, 6, 5, 7, 3, 2, 4] [9, 8, 7, 3, 2, 1, 6, 5, 4] [8, 7, 6, 2, 1, 9, 5, 4, 3] [4, 3, 2, 1, 9, 8, 7, 6, 5][ is_valid : ]True[ 

Una solución simple que utiliza 2 pasos puede ser la siguiente:

1)

 # extract tuples of 3, row-wise x = 0 listTuple=[None]*9*3 for i in range(9): for j in range(3): listTuple[x] = grid[i][j*3:j*3+3] x += 1 

2)

 # Take the 3 tuples which form a box and compare with 1-9 numbers rangeList = list(range(1,10)) idx = 0 for i in range(1,10): box = sorted(listTuple[idx]+listTuple[idx+3]+listTuple[idx+6]) print(box == rangeList) if i%3 == 0: idx = idx + 6 idx += 1