Fill out sudoku board - backtracking solution question

Question

I wrote the following solution for the Leetcode question copied below:

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character '.'. Note:

The given board contain only digits 1-9 and the character '.'. You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always 9x9.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        EMPTY_CELL = '.'
        target = set(str(n) for n in range(1, 10))

        def _validate():
          cols = [[board[r][c] for r in range(9)] for c in range(9)]
          boxes = []
          for i in (0, 3, 6):
            for j in (0, 3, 6):
              boxes.append([board[a][b] for a in range(i, i + 3) for b in range(j, j + 3)])

          valid_rows = all(set(row) == target for row in board)
          valid_cols = valid_rows and all(set(col) == target for col in cols)
          valid_boxes = valid_cols and all(set(box) == target for box in boxes)
          return valid_boxes


        def helper(r, c):
          if c == len(board[0]):
            return helper(r + 1, 0)

          if r == len(board):
            return _validate()

          if not board[r][c] == EMPTY_CELL:
            return helper(r, c + 1)

          for n in range(1, 10):
            board[r][c] = str(n) 
            if helper(r, c + 1):
              return True 

          return False

        helper(0, 0)

Here's my strategy in plain English. For every cell that is empty, I try placing a number in that cell, and recursing on the remainder of the board. If that doesn't lead to a valid solution, I backtrack, increment the number, and recurse having placed that number in the empty cell instead.

My validate function is returning False for everything, and I'm ending up with a board with 9's in the empty spaces. The problem guarantees that there IS a correct solution for every test case. I've walked through this code dozens of times and am unable to see what the issue is.

(I understand that I could use constraint propagation to speed up the solution, but the current problem isn't that my solution is too slow - it is that its incorrect).

Anyone see why? Also, in case this is unclear from the problem statement, each digit is supposed to be a string.

Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. Minimal, complete, verifiable example applies here. We cannot effectively help you until you post your MCVE code and accurately specify the problem. We should be able to paste your posted code into a text file and reproduce the problem you specified. — Prune

olooney olooney · Accepted Answer · 2019-04-26T21:15:45

Your validate function will return true if you feed it a correct solution. You can verify this yourself by feeding it a solved sudoku board:

solved_text = '''435269781
682571493
197834562
826195347
374682915
951743628
519326874
248957136
763418259'''

solved_board = [ list(line) for line in solved_text.split('\n') ]

There are two problems. First, you do not actually search the complete space of solutions. If you print each complete board passed into _validate(), you will notice something odd: the whole board is always in lexical order! This is not the 10^81 set of possible boards. This can be fixed by simply omitting these two lines of code:

if not board[r][c] == EMPTY_CELL:
    return helper(r, c + 1)

These are causing a problem because you mutate board state as a side affect as you go but do not clean-up (put back empty cells) while backtracking. You can simply omit those two lines (so that the algorithm in helper() never cares about what is to the right in the (r,c) lexical ordering) or by adding code to set board[r][c] = EMPTY_CELL when back-tracking.

The other problem is that because you only run validation on complete boards, and because your validation function can only check complete boards for correctness, your algorithm really will have to plow through all 10^81 possible boards before it finds a solution. This isn't just slow, it's completely intractable! Instead, you should rewrite your validation function so that it can validate a partial board. For example, if the first row is ['1', '1', '.', ..., '.'], it should return False, but if the first row is ['1', '2', '.', ..., '.'] it should return True because there are no problems so far. Obviously, you will also have to call _validate() at every step now, not just when the board is complete... but this is worth it because otherwise you will spend enormous amounts of time exploring boards which are obviously never going to work.

You will need to fix both problems before your algorithm will work.

Fill out sudoku board - backtracking solution question

2 Answers