title: Weird Sudoku validation bug
body: <p>I'm currently trying to program a recursive sudoku solving algorithm in Python. I made a class for Sudokus which contains some methods to help me manipulate the sudoku grid.</p>
  
  <p>Here is my code :</p>
  
  <pre><code>class Sudoku:
      def __init__(self, input, tokens = None):
          self.data = {}
          if tokens is None:
              self.tokens = list(range(1, 10))
          else:
              self.tokens = tokens
  
          assert len(self.tokens) == 9
          if type(input) == dict:
              self.data = input
          else:
              for i, cell in enumerate(input):
                  if cell in self.tokens:
                      self.data[i % 9, i // 9] = cell
  
      def __repr__(self):
          string = ''
          canvas = [['.'] * 9 for line in range(9)]
          for (col, row), cell in self.data.items():
              canvas[row][col] = str(cell)
          for y, row in enumerate(canvas):
              if not y % 3:
                  string += "+-------+-------+-------+\n"
              string += '| {} | {} | {} |\n'.format(' '.join(row[:3]), ' '.join(row[3:6]), ' '.join(row[6:]))
          string += "+-------+-------+-------+"
          return string
  
      @classmethod
      def sq_coords(cls, cell_x, cell_y):
          #returns all coordinates of cells in the same square as the one in (cell_x, cell_y)
          start_x, start_y = cell_x // 3 * 3, cell_y // 3 * 3
          for dx in range(3):
              for dy in range(3):
                  yield (start_x +dx, start_y + dy)
  
      def copy(self):
          return Sudoku(self.data)
  
      def clues(self, cell_x, cell_y):
          assert not self.data.get((cell_x, cell_y))
          allowed = set(self.tokens)
          #Remove all numbers on the same row, column and square as the cell
          for row in range(9):
              allowed.discard(self.data.get((cell_x, row)))
          for col in range(9):
              allowed.discard(self.data.get((col, cell_y)))
          for coords in self.sq_coords(cell_x, cell_y):
              allowed.discard(self.data.get(coords))
          return allowed
  
      def get_all_clues(self):
          clues = {}
          for row in range(9):
                  for col in range(9):
                      if not self.data.get((col, row)):
                          clues[col, row] = self.clues(col, row)
          return clues
  
      def fill_singles(self):
          still_going = True
          did_something = False
          while still_going:
              still_going = False
              for (col, row), clues in self.get_all_clues().items():
                  if len(clues) == 1:
                      still_going = True
                      did_something = True
                      self.data[col, row] = clues.pop()
          return did_something
  
      def place_finding(self):
          still_going = True
          did_something = False
          while still_going:
              still_going = False
              for token in self.tokens:
                  for group in self.get_groups():
                      available_spots = [coords for coords, cell in group.items() if cell == None and token in self.clues(*coords)]
                      if len(available_spots) == 1:
                          self.data[available_spots.pop()] = token
                          still_going = True
                          did_something = True
          return did_something
  
      def fill_obvious(self):
          still_going = True
          while still_going:
              a = self.fill_singles()
              b = self.place_finding()
              still_going = a or b
  
      def get_groups(self):
          for y in range(9):
              yield {(x, y) : self.data.get((x, y)) for x in range(9)}
          for x in range(9):
              yield {(x, y) : self.data.get((x, y)) for y in range(9)}
          for n in range(9):
              start_x, start_y = n % 3 * 3, n // 3 * 3
              yield {(x, y) : self.data.get((x, y)) for x, y in self.sq_coords(start_x, start_y)}
  
      def is_valid(self):
          for group in self.get_groups():
              if any([list(group.values()).count(token) &gt; 1 for token in self.tokens]):
                  return False
          return True
  
      def is_solved(self):
          return self.is_valid() and len(self.data) == 9 * 9
  
  def solve(sudoku):
          def loop(su):
              if su.is_solved():
                  print(su)
              elif su.is_valid():
                  su.fill_obvious()
                  print(su)
                  for coords, available_tokens in sorted(su.get_all_clues().items(), key=lambda kv: len(kv[1])):
                      for token in available_tokens:
                          new_su = su.copy()
                          new_su.data[coords] = token
                          loop(new_su)
          loop(sudoku)
  
  with open('input.txt') as f:
      numbers = ''
      for i, line in enumerate(f):
          if i &gt;= 9:
              break
          numbers += line.rstrip().ljust(9)
  
  s = Sudoku(numbers, tokens='123456789')
  
  print(s)
  solve(s)
  print(s)
  </code></pre>
  
  <p>Sorry if this seems messy but I'd rather give you everything I have than only some data that may or may not contain the problem.</p>
  
  <p>As you can see, the first thing it does is filling the Sudoku with only 100% sure numbers using the methods fill_singles (fills every cell that can only be filled with number x, eg the 8 other possibilities are in its row, column or block) and place_finding (checks all tokens and see if there's only one space in a group - row, column or block - where they can fit). It loops through both of those until nothing can be done.</p>
  
  <p>Afterwards, it tries every possibility in spaces that have least and tries to solves the newly made grid with the same method. That's where my problem is. Currently, for debug purposes, the program prints grids it comes across whenever they're valid (no same number twice in a group). Actually that's what I'd like it to do. However it doesn't work like this; with this input : </p>
  
  <pre><code>+-------+-------+-------+
  | . . . | . 2 6 | . . 4 |
  | . . . | 7 9 . | 5 . . |
  | . . . | . . . | 9 1 . |
  +-------+-------+-------+
  | . 8 . | 1 . . | . . . |
  | 2 3 6 | . . . | 1 8 5 |
  | . . . | . . 3 | . 7 . |
  +-------+-------+-------+
  | . 4 7 | . . . | . . . |
  | . . 3 | . 7 8 | . . . |
  | 5 . . | 6 3 . | . . . |
  +-------+-------+-------+
  </code></pre>
  
  <p>It outputs grids such as this one, which is obviously not valid:</p>
  
  <pre><code>+-------+-------+-------+
  | 1 4 9 | 3 2 6 | 7 3 4 |
  | 3 2 4 | 7 9 1 | 5 1 8 |
  | 3 7 5 | 3 2 4 | 9 1 2 |
  +-------+-------+-------+
  | 7 8 6 | 1 1 4 | 3 2 5 |
  | 2 3 6 | 9 4 7 | 1 8 5 |
  | 4 1 7 | 2 3 3 | 6 7 4 |
  +-------+-------+-------+
  | 2 4 7 | 1 1 3 | 5 4 6 |
  | 1 3 3 | 4 7 8 | 2 5 1 |
  | 5 5 4 | 6 3 2 | 1 3 7 |
  +-------+-------+-------+
  </code></pre>
  
  <p>I really cannot understand why it allows such grids to pass the is_valid test, especially considering that when I manually input the grid above, it doesn't pass the test :</p>
  
  <pre><code>&gt;&gt;&gt; s
  +-------+-------+-------+
  | 1 4 9 | 3 2 6 | 7 3 4 |
  | 3 2 4 | 7 9 1 | 5 1 8 |
  | 3 7 5 | 3 2 4 | 9 1 2 |
  +-------+-------+-------+
  | 7 8 6 | 1 1 4 | 3 2 5 |
  | 2 3 6 | 9 4 7 | 1 8 5 |
  | 4 1 7 | 2 3 3 | 6 7 4 |
  +-------+-------+-------+
  | 2 4 7 | 1 1 3 | 5 4 6 |
  | 1 3 3 | 4 7 8 | 2 5 1 |
  | 5 5 4 | 6 3 2 | 1 3 7 |
  +-------+-------+-------+
  &gt;&gt;&gt; s.is_valid()
  False
  </code></pre>
  
  <p>Can anyone see an error in my code that I haven't noticed? I'm sorry I'm not really being specific but I tried looking through every piece of my code and can't seem to find anything.</p>
  
  <p>For @AnandSKatum : </p>
  
  <pre><code>    26  4
     79 5
        91
   8 1
  236   185
       3 7
   47
    3 78
  5  63
  </code></pre>