As much as I would like to believe that programming has developed my analytical thinking, I am quite terrible at solving sudoku puzzles, so I decided try writing a sudoku solver instead.

Here is a simple backtracking solver written in Python 3:

def rows(puzzle):
    return [puzzle[9 * i:9 * i + 9] for i in range(9)]

def columns(puzzle):
    return [puzzle[i::9] for i in range(9)]

def boxes(puzzle):
    return [puzzle[i:i + 3] +
            puzzle[i + 9:i + 9 + 3] +
            puzzle[i + 9 + 9:i + 9 + 9 + 3] for i in
            (j * 3 + k * 27 for j in range(3) for k in range(3))]

def valid_group(group):
    digits = [d for d in group if d != '.']
    return len(set(digits)) == len(digits)

def valid(puzzle):
    return all(valid_group(group) for group in rows(puzzle)) and all(
        valid_group(group) for group in columns(puzzle)) and all(
        valid_group(group) for group in boxes(puzzle))

def solved(puzzle):
    return valid(puzzle) and '.' not in puzzle

def permutations(puzzle):
    return [puzzle.replace('.', f'{i}', 1) for i in range(1, 10)]

def solve(puzzle):
    stack = [puzzle]
    while stack:
        curr = stack.pop()
        if solved(curr):
            return curr
        stack.extend(perm for perm in permutations(curr) if valid(perm))

def valid_input(inp):
    return len(inp) == 81 and not set(inp) - set('.123456789')

def main():
    puzzle = input()
    if not valid_input(puzzle):
        print('Invalid input!')
    solved_puzzle = solve(puzzle)
    if not solved_puzzle:
        print('No solution!')

if __name__ == '__main__':

It’s also available as a GitHub gist at


The solver takes a sudoku puzzle written in one line with blanks denoted by periods like this from standard input:


And writes the solution in a similar format:

$ echo ....5.264..7..9..35..62....8......9.7..34..86.....2.3....9.....9.476........3.... | python3 

For testing, I came across this website which can generate sudoku puzzles in the appropriate format:

QQWing - Generate Sudoku Puzzles
Generate Sudoku in your web browser using QQWing.

It can also solve them too, which helped me check the correctness of the solver’s output.

Handling adversarial input

The Wikipedia page Sudoku solving algorithms has a section on the backtracking method used by this solver, and mentions that inputs that are likely to take significantly longer for such a solver compared to random can be constructed.

The linked reference, showing a visualisation of a backtracking solver working on such an adversarial input, also includes a sample which the author described as taking 6 hours to run on his machine in 2008:


Converting it to the right format and trying it with my solver on my 2018 MacBook Pro, it clearly does take longer than the first input shown earlier:

$ time echo ....5.264..7..9..35..62....8......9.7..34..86.....2.3....9.....9.476........3.... | python3

real	0m0.717s
user	0m0.697s
sys	0m0.016s
$ time echo ..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9 | python3

real	0m6.235s
user	0m6.203s
sys	0m0.019s

However, technology has come a long way in more than 10 years—the code is unlikely to win any performance awards, but instead of taking 6 hours, it takes just over 6 seconds on my machine today!