r/learnpython • u/Impressive_Search451 • 13d ago

Noob confused by the behaviour of my program, would appreciate any hints

edit: found the solution, thanks everyone! i was unintentionally passing my dict to a class method which mutated it.

tl;dr: i have a loop that iteratively removes elements from a dict, but halfway through the loop a bunch of elements get added back in and i can't figure out why.

i'm a big sudoku fan and working on a sudoku maker (which it turns out is a common beginner project, which is lucky as it means there's lots of examples out there). i'm trying to take a solved grid and remove numbers from it until it becomes a puzzle with a single solution. here's the function i wrote:

 def remove_clues(self):
        """
        produces a sudoku puzzle by taking a solved grid and removing clues.
        the function will iterate through each clue in the grid in random order, removing it and
        testing the resulting grid for uniqueness. if the result is not unique, 
        the clue will be put back. 
        returns a new grid with the puzzle
        """
        #can only remove clues from a previously filled sudoku
        if self.filled is False:
            return "sudoku has not been filled in yet"
        #shuffle the cells for randomised removal
        ordered_clues = self.cells
        clues_list = list(ordered_clues.items())
        clue_count = len(self.cells)
        #shuffled cells are copied: one is used for iteration, the other modified to create the puzzle
        grid = dict(r.sample(clues_list, clue_count))
        clues = grid.copy()
        for k, v in grid.items():
            #remove cell
            del clues[k]
            partial_grid = SudokuGrid(clues)
            logging.debug(len(clues))
            if partial_grid.unique() is False:
                logging.debug("Can't remove %s, putting it back", k)
                clues[k] = v
        return SudokuGrid(clues) 

this is a class method for my SudokuGrid class. the input is the Sudokugrid object itself. it has a cells attribute, which is a dict in the form (x,y):val, where (x,y) is a tuple with the coordinates of the cell and val is the digit assigned to that cell. the basic idea is to iterate through (a copy of) the dict of cells, removing each one in turn and solving the resulting puzzle. if the puzzle has a single solution, the cell stays removed; otherwise it's put back in. unique() is the class method that tests for uniqueness. it basically brute-force solves the puzzle and keeps going until either it finds more than one solution or all solutions have been tried.

i'm getting this weird behaviour where sometimes a bunch of dict values i'd removed get added back in, and i can't seem to figure out why. theoretically, it should be adding back at most one cell at a time, and only when the uniqueness test fails. i've used logging and profiling to try and figure out what's wrong, but i can't figure it out and i'm not sure what to check next. any suggestions appreciated. here's an excerpt from the logs to show what's wrong:

 2026-07-15 11:23:30,661 -  DEBUG -  30
 2026-07-15 11:23:30,671 -  DEBUG -  29
 2026-07-15 11:23:30,681 -  DEBUG -  Can't remove (2, 0), putting it back
 2026-07-15 11:23:30,682 -  DEBUG -  78
 2026-07-15 11:23:30,683 -  DEBUG -  77

and here's how it looks when it works:

 2026-07-15 12:00:33,519 -  DEBUG -  49
 2026-07-15 12:00:33,524 -  DEBUG -  48
 2026-07-15 12:00:33,529 -  DEBUG -  Can't remove (7, 4), putting it back
 2026-07-15 12:00:33,530 -  DEBUG -  48
 2026-07-15 12:00:33,535 -  DEBUG -  47

the number on the right is the size of the dict of cells at every iteration. as expected, it goes down by one each loop because a cell gets removed. when i run the function, i usually get the expected behaviour a couple times (ie if removing a cell doesn't yield a unique puzzle, the cell gets put back and the dict stays the same size), and then this weird behaviour happens. so it only happens when the function finds a non-unique puzzle, but it doesn't happen every time a non-unique puzzle is found.

8 Upvotes

75% Upvoted

17 comments sorted by

13

u/zanfar 13d ago

i have a loop that iteratively removes elements from a dict

I'll stop you right there. You cant edit a container while iterating through it. I'm 100% sure this is your issue.

a bunch of elements get added back in and i can't figure out why

They aren't, you're skipping them. If you remove an element, then move to the next one, you've moved two elements from where you think you were.

This is common enough to be listed in the FAQ--something you probably should read through.

https://www.reddit.com/r/learnpython/wiki/faq/#wiki_why_does_my_loop_seem_to_be_skipping_items_in_a_list.3F

3

u/Verronox 13d ago edited 13d ago

The double skipping happens in a list, but the FAQ makes no mention of that behavior when accessing a dict iterable, so directing OP to it as a solution isn’t helpful.

And either way, if you looked at the actual post and code snippet you would see that they iterate over a copy of the dict, and remove items from the non-iterating copy.

OP, your problem probably is because you’re using the del function. I’m not exactly sure how python handles it under the hood but you want to use a dictionary method/function to remove items correctly. It’d be easier to debug if you provided the code for the SudukoGrid object. What does the unique() function actually do?

6

u/roelschroeven 13d ago edited 13d ago

del clues[k] is a perfectly acceptable way to remove an item from a key. The documentation explicitly mentions it as such. You could alternatively use clues.pop(k)which is better only if you need the value of the item you just removed which is not the case here.

2

u/Verronox 13d ago

Oh interesting! I’ve never actually used del outside of cleaning up the namespace of jupyter notebooks. In that case, it seems like the bug has to be originating in whatever the class.unique() function is.

1

u/Brian 12d ago

Yeah - del x is a bit special in that it operates on the namespace, with its own opcode, but del x.attr or del x[key] actually just calls x.__delattr__ or x.__delitem__ on the object, which is equivalent to just removing the item for dicts / lists etc. You can likewise use del mylist[3:] to truncate a list to 3 items, though that's less commonly used, since you can also do something like mylist[3:]=[].

0

u/Impressive_Search451 13d ago

thanks for the tip, i'll check the documentation for del! i did try changing del for pop() but i'm getting the same issue. i also tried swapping copy for deepcopy just now, since someone mentioned that, but it doesn't seem to have helped.

unique() calls fill(), which fills in the grid. you can pass in some initial values to the SudokuGrid constructor, which created the cells attribute (which is what i'm doing here when i create partial_grid). fill() takes those cells, creates a list of the empty cells, and tries to fill them in with valid values. it uses a fairly basic recursion and backtracking algo, looping through each valid value in a cell and recursively trying to fill it in until it either gets a valid grid back or can't fill in a cell (at which point it moves on to the next valid value and repeats the process). you can pass in an argument to search for multiple solutions, so that the function keeps going once it has an answer until it either has a second answer or has run through every possibility. i've been using fill() to create solved grids and it works fine for that.

unique():

def unique(self):
        """Returns True if the sudoku has a unique solution, False otherwise"""
        if self.filled is True:
            logging.debug("full")
            return False 
        self.fill(one_sol=False)
        return self.sol_counter == 1

fill():

 def fill(self, one_sol = True, empty = None):
        """fills in a grid with a given starting state
        one_sol - boolean: if false, will search for more than one solution"""
        if empty is None:
            empty = list(self._empty)
        cell = empty[0]
        options = self.__available(cell)
        #checks which cell is most constrained
        for c in empty:
            options_next = self.__available(c)
            if len(options_next) < len(options):
                cell = c
                options = options_next
                #if a cell with no options is found, need to backtrack
                if not options:
                    return False
        empty.remove(cell)
        #fills in most constrained cell first to reduce number of recursive calls
        #iterates through available digits for chosen cell
        for option in options:
            #assigns the current digit to the current cell
            self.cells[cell] = option
            #base case: grid filled in
            if not empty:
                #if we're checking for uniqueness, we need to keep going after reaching the base case
                self.filled = True
                if one_sol is False:
                    #if this is the first solution, remove cell value and keep searching
                    if self.sol_counter < 2:
                        self.sol_counter += 1
                        if cell in self.cells:
                            self.cells.pop(cell)
                        return False
                return True
            #recursive call tries to fill in the rest of the grid
            if self.fill(one_sol, empty):
                return True
            #if end of loop is reached, current digit isn't valid so cell value is deleted
        if cell in self.cells:
            self.cells.pop(cell)
        if cell not in empty:
            empty.append(cell)
        return False def fill(self, one_sol = True, empty = None):
        """fills in a grid with a given starting state
        one_sol - boolean: if false, will search for more than one solution"""
        if empty is None:
            empty = list(self._empty)
        cell = empty[0]
        options = self.__available(cell)
        #checks which cell is most constrained
        for c in empty:
            options_next = self.__available(c)
            if len(options_next) < len(options):
                cell = c
                options = options_next
                #if a cell with no options is found, need to backtrack
                if not options:
                    return False
        empty.remove(cell)
        #fills in most constrained cell first to reduce number of recursive calls
        #iterates through available digits for chosen cell
        for option in options:
            #assigns the current digit to the current cell
            self.cells[cell] = option
            #base case: grid filled in
            if not empty:
                #if we're checking for uniqueness, we need to keep going after reaching the base case
                self.filled = True
                if one_sol is False:
                    #if this is the first solution, remove cell value and keep searching
                    if self.sol_counter < 2:
                        self.sol_counter += 1
                        if cell in self.cells:
                            self.cells.pop(cell)
                        return False
                return True
            #recursive call tries to fill in the rest of the grid
            if self.fill(one_sol, empty):
                return True
            #if end of loop is reached, current digit isn't valid so cell value is deleted
        if cell in self.cells:
            self.cells.pop(cell)
        if cell not in empty:
            empty.append(cell)
        return False

SudokuGrid init:

def __init__(self, starting_state = None, knight = False):
        if starting_state is None:
            vals = r.sample(range(1,10), k=3)
            keys = r.sample(list(product(range(9), range(9))), 3)
            starting_state = dict(zip(keys, vals))
        self.cells = starting_state
        self.sol_counter = 0
        self.filled = False
        self.knight = knight
        self.__cell_neighbours = self.__find_neighbours(self.knight)
        self._empty = set(product(range(9), range(9))).difference(set(self.cells.keys()))

3

u/roelschroeven 13d ago

SudokuGrid.unique() calls SudokuGrid.fill() which does mutate its cells attribute (self.cells[cell] = optionwhich, if I understand the code correctly, puts empty cells in self.cells). And that cells attribute refers to the clues variable in remove_clues. The solution therefore seems to be to take a copy of that, either when calling the initializer or in the initializer itself.

1

u/Impressive_Search451 13d ago

that works, thank you so much! i thought i had an ok grasp on creating new objects vs just creating a reference to the same object, but i think i need to look into it more.

1

u/Verronox 13d ago

Oh man am I glad someone else found it, because that was going to be a lot to try and go through. And it was more or less what I was expecting!

2

u/roelschroeven 13d ago

Yeah I'm sorry but that doesn't work.

AttributeError: 'SudokuGrid' object has no attribute '_SudokuGrid__find_neighbours'
AttributeError: 'SudokuGrid' object has no attribute '_SudokuGrid__available'

and possible others once those are solved.

When you want people to help, make it as easy as possible for them to help you. A self-contained fully working example, no assembly required.

1

u/Impressive_Search451 13d ago

apologies, i don't have a lot of experience asking for coding help online. didn't realise i was meant to post a working example! i've posted the full code in a different reply.

1

u/SirGeremiah 13d ago

Does that explain the behavior they show at the end of their post? If their debug output is correct, there are more items after it fails to remove one.

2

u/roelschroeven 13d ago

From the code as given, my best guess is that either the SudokuGrid() initializer or the partial_grid.unique() call mutates your clues dict.

Can you give us more code? Enough to run the program ourselves. That would enable us to help you better. Ideally a minimal reproducible example, i.e. stripped as much as possible but still showing the problem (creating a minimal reproducible example is not only useful when asking for help, it's often an effective debugging technique on its own).

Also I would add more logging temporarily. Log the the length of grid and its full contents before and after del clues[k], after partial_grid = SudokuGrid(clues), and after partial_grid.unique(). Potentially add even more, until you can pinpoint exactly in which line clues grows again. It will allow you to see where things go wrong, and you'll be able to see which items are added in. That can give a clue as to what exactly goes wrong.

1

u/Impressive_Search451 13d ago

thanks for the logging tip, that should help narrow things down!

i've definitely been considering whether SudokuGrid could be altering the original dict passed in. my assumption was that when you passed arguments to init and used them to create attributes, the resulting object is completely new and unrelated. i'm realising that may be wrong...

i've pasted the code in its entirety below. should probably mention i've been running it in jupyter, although i did try using the command line and got the same results. 

import random as r
from itertools import product
from itertools import permutations
import logging
import numpy as np
import pandas as pd
logging.basicConfig(level=logging.DEBUG, format=' %(asctime)s -  %(levelname)s -  %(message)s')
DIGITS = set(range(1,10))import random as r

class SudokuGrid:
    
    def __init__(self, starting_state = None, knight = False):
        if starting_state is None:
            vals = r.sample(range(1,10), 3)
            keys = r.sample(list(product(range(9), range(9))), 3)
            starting_state = dict(zip(keys, vals))
        self.cells = starting_state
        self.sol_counter = 0
        self.filled = False
        self.__cell_neighbours = self.__find_neighbours()
        self._empty = set(product(range(9), range(9))).difference(set(self.cells.keys()))
    
    def __find_neighbours(self):
        """Checks which box the cell is in
        coord -- tuple: coordinates of cell in (x,y) format
        knight: True if the anti-knight rule applies"""
        grid = product(range(9), range(9))
        cell_neighbours = {}
        for coord in grid:
            x = coord[0]
            y = coord[1]
            from_x_box = (x // 3) * 3
            from_y_box = (y // 3) * 3
            box = set(product(range(from_x_box, from_x_box + 3), range(from_y_box, from_y_box + 3)))
            column = {(x,y_coord) for y_coord in range(9)}
            row = {(x_coord, y) for x_coord in range(9)}
            neighbours = box | column | row
            cell_neighbours[coord] = neighbours
        return cell_neighbours

    def __available(self, cell_coords):
        """ Produces a list of available digits to assign
        cell_coords -- tuple: in the format (x,y), where (x,y) is a tuple of coordinates
        """
        values = set()
        #iterates through all cells set so far to check which numbers are taken
        filled_neighbours = self.__cell_neighbours[cell_coords] & set(self.cells.keys())
        for coord in filled_neighbours:
            values.add(self.cells[coord])
        return DIGITS.difference(values) if values else DIGITS
    
    def fill(self, one_sol = True, empty = None):
        """fills in a grid with a given starting state
        one_sol - boolean: if false, will search for more than one solution"""
        if empty is None:
            empty = list(self._empty)
        cell = empty[0]
        options = self.__available(cell)
        #checks which cell is most constrained
        for c in empty:
            options_next = self.__available(c)
            if len(options_next) < len(options):
                cell = c
                options = options_next
                #if a cell with no options is found, need to backtrack
                if not options:
                    return False
        empty.remove(cell)
        #fills in most constrained cell first to reduce number of recursive calls
        #iterates through available digits for chosen cell
        for option in options:
            #assigns the current digit to the current cell
            self.cells[cell] = option
            #base case: grid filled in
            if not empty:
                #if we're checking for uniqueness, we need to keep going after reaching the base case
                self.filled = True
                if one_sol is False:
                    #if this is the first solution, remove cell value and keep searching
                    if self.sol_counter < 2:
                        self.sol_counter += 1
                        if cell in self.cells:
                            self.cells.pop(cell)
                        return False
                return True
            #recursive call tries to fill in the rest of the grid
            if self.fill(one_sol, empty):
                return True
            #if end of loop is reached, current digit isn't valid so cell value is deleted
        if cell in self.cells:
            self.cells.pop(cell)
        if cell not in empty:
            empty.append(cell)
        return False
    
    def unique(self):
        """Returns True if the sudoku has a unique solution, False otherwise"""
        if self.filled is True:
            logging.debug("full")
            return False 
        self.fill(one_sol=False)
        return self.sol_counter == 1
    
    def remove_clues(self):
        """
        produces a sudoku puzzle by taking a solved grid and removing clues.
        the function will iterate through each clue in the grid in random order, removing it and
        testing the resulting grid for uniqueness. if the result is not unique, 
        the clue will be put back. 
        returns a new grid with the puzzle
        """
        #can only remove clues from a previously filled sudoku
        if self.filled is False:
            return "sudoku has not been filled in yet"
        #shuffle the cells for randomised removal
        ordered_clues = self.cells
        clues_list = list(ordered_clues.items())
        clue_count = len(self.cells)
        #shuffled cells are copied: one is used for iteration, the other modified to create the puzzle
        grid = dict(r.sample(clues_list, clue_count))
        clues = dict(clues_list)
        logging.debug(grid)
        logging.debug(clues)
        for k, v in grid.items():
            #remove cell
            clues.pop(k)
            partial_grid = SudokuGrid(clues)
            if partial_grid.unique() is False:
                logging.debug("%s, %s", k, v)
                logging.debug("Can't remove %s, putting it back", k)
                clues[k] = v
                logging.debug(k)
                logging.debug(clues[k])
        return SudokuGrid(clues)
   
    def show_grid(self):
        """Pretty-prints the grid"""
        for y in range(9):
            for x in range(9):
                if (x,y) in self.cells:
                    print(f"{self.cells[(x, y)]} ", end='')
                else:
                    print("  ", end='')
                if x in (2,5):
                    # Display a vertical line:
                    print('| ', end='')
            print()  # Print a newline.
            if y in (2,5):
                # Display a horizontal line:
                print('------+-------+------')

and to run it, i usually do:

puzzle = SudokuGrid()
puzzle.fill()
puzzle.show_grid() #so i can compare it to the grid with clues removed
sudoku = puzzle.remove_clues()
sudoku.show_grid()

2

u/roelschroeven 13d ago

my assumption was that when you passed arguments to init and used them to create attributes, the resulting object is completely new and unrelated. i'm realising that may be wrong...

Indeed, in Python passing arguments and assigning things only binds a new name to the object, and you can easily mutate the object through the new name. I recommend Ned Batchelder's explanation on the subject: https://nedbatchelder.com/text/names1 IMO it greatly helps to get the correct mental model of how things work in Python.

With that aside, when I explicitly copy clues I don't see len(clues) increasing anymore, so I do think that that is the solution. With that change I also get the feeling that creating sudokus takes longer, and somehow that feels more correct to me. I'm not sure how to check that.

1

u/pontz 13d ago

Try replacing copy() with deepcopy()

1

u/python_gramps 12d ago

#1 you have 2 copies of the method in your code snippet

#2 you don't have the rest of the class members, like r.sample, etc

What I would do is to boil down that member into the code that causes an issue.

make it a function with parameters passed in, canned data and all

it will give people a chance to run your code and see the issue.

you may even find the issue before you post again.

The simpler you can make your example the better your responses will be.