finding possible entries in Sudoku empty cells

Question

I have been packaging a script to calculate all possible entries in the empty cells of a sudoku game. While the algorithm to screen the vertical column and the horizontal row works, it seems that my script is not able to screen the relevant box where the empty cell is located. The code that I am using is the following:

def possible(y,x,n):
    global grid
    for i in range(0,9):
        if grid[y][i] == n:
            return False
    for i in range(0,9):
        if grid[i][x] == n:
            return False
    x0 = (x//3)*3
    y0 = (y//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if (grid[y0+i][x0+j] == n):
                #print((x0+j),end=' ')
                #print((y0+i),end='  ')
                return False
            list.append(y+1)
            list.append(x+1)
            list.append(n)

            return True

It seems that there is some problem with the append procedure..... Any assistance is welcome

what is `list` here? which list are you trying to append to? — Adam.Er8, Aug 09 '22 at 12:17
All the soduko logic is not related to it, what you really should be googling for is how to work with Python lists, there's plenty of material. Best of luck :) — Adam.Er8, Aug 09 '22 at 12:18
list is where i store all possible entries for the empty cell — Gulliver05, Aug 09 '22 at 13:04
Well, there isn't a list variable or parameter in this code, and `list` is the name of the type `list` — Adam.Er8, Aug 09 '22 at 13:49
Try renaming your `list` variable to something else, you'll get clearer errors. — Adam.Er8, Aug 09 '22 at 13:55

kasztp · Answer 1 · 2022-08-26T15:17:35.617

My general comments:

Seems like you are trying to append to a list which might or might not be defined outside of the possible() function (it's not in the supplied code). However, as it is not defined within the scope of that function, you generally can't access it from the inside. Related read.)
Also you should change a variable name as list is a built-in type of Python and it is not recommended to use builtin types as variable names unless you absolutely need to do so for some reason.
Generally it is not a best practice to use global variables.

My suggestion would be to move the gathering of possible numbers outside of this function. Example:

    def possible(grid: list[list[int]], num: int, pos: tuple[int, int]) -> bool:
        # Check row
        if num in grid[pos[0]]:
            return False

        # Check column
        if num in [item[pos[1]] for item in grid]:
            return False

        # Check box
        box_x = pos[1] // 3
        box_y = pos[0] // 3

        for i in range(box_y * 3, box_y * 3 + 3):
            if num in grid[i][box_x * 3: box_x * 3 + 3] \
                and (i, grid[i].index(num)) != pos:
                return False

        return True

Then run this 'cleaner' function in a for loop or list comprehension to collect possible numbers for a given position on the Sudoku grid.

For example (for cycle):

possible_values = []

for i in range(1,10):
    if possible(grid, i, (x, y)):
        possible_values.append(i)

Or this (list comprehension):

possible_values = [n for n in range(1,10) if possible(grid, n, (0, 2))]

score 0 · Answer 2 · answered Nov 03 '22 at 10:47

In the Sudoku game world one call the "possible entries" of the empty cells, candidates or pencil-marks. Here is how we can identify the candidates of the empty cells.

    grid = [
        [0, 0, 0, 6, 0, 8, 9, 1, 0],
        [6, 0, 2, 0, 9, 0, 3, 4, 0],
        [1, 9, 8, 3, 0, 0, 0, 6, 7],
        [0, 5, 9, 0, 0, 0, 4, 2, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 1, 3, 0, 2, 0, 8, 0, 0],
        [9, 6, 0, 5, 3, 7, 2, 8, 0],
        [2, 0, 0, 4, 1, 0, 0, 3, 0],
        [3, 4, 0, 2, 8, 0, 1, 7, 9],
    ]

candidates=bytearray(729)

def identifyCandidates():
    
    for  cell in range(81):
        row,col=divmod(cell,9)
        if grid[row][col] == 0 :
            for kan in range(1,10):
                if not clueInSector(cell,  kan):
                    candidates[9*cell+(kan - 1)]=1   

def clueInSector(cell,  clue):
    
    cellrow,cellcol = divmod(cell,9)
    
    for  col in range(9):
        if (col != cellcol and grid[cellrow][col] == clue) :
            return True
        
    for  row in range(9):
        if (row != cellrow and grid[row][cellcol] == clue) :
            return True
        
    rowB = 3 * ((cellrow) // 3)
    colB = 3 * ((cellcol) // 3)
    for  row in range (rowB,rowB + 3) :
        for  col in range(colB,colB +3) :
            if (col != cellcol and row != cellrow and grid[row][col] == clue) :
                return True        
    return False

Print of the 13 first cells:

cell:0 candidates: 5.
cell:1 candidates: 3.7.
cell:2 candidates: 4.5.7.
cell:3 no candidate.
cell:4 candidates: 4.5.7.
cell:5 no candidate.
cell:6 no candidate.
cell:7 no candidate.
cell:8 candidates: 2.5.
cell:9 no candidate.
cell:10 candidates: 7.
cell:11 no candidate.
cell:12 candidates: 1.7.

finding possible entries in Sudoku empty cells

2 Answers2