Python Sudoku Solver - Computerphile

No captions available for this video.

Channel: Computerphile

Views: 1,053,046

Rating: 4.9292884 out of 5

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Professor Thorsten Altenkirsch, Sudoku, Python, Recursion, 4K, UHD

Id: G_UYXzGuqvM

Length: 10min 52sec (652 seconds)

Published: Wed Feb 12 2020

Reddit Comments

[u/wsppan]

I like Peter Norvig's python solution. Does a much better job solving the really difficult puzzles compared to a brute force back tracking algorithm. But by far the most elegant and fastest solver is Donald Knuth's Dancing Links implementation of his Algorithm X solution to the exact cover problem.

[u/1h8fulkat]

A fellow redditor. The secret is hidden in his whiteboard chicken scratch

[u/gotchanose]

This isn’t solving the problem in ten lines. He is calling the function named possible in his recursion function. You see this function in the beginning of the video. His recursion function named solve, AkA the ten line of code, is only for moving around the Soduku grid.

It’s a great video none the less for furthering ones python knowledge

[u/tepg221]

A bit off topic but anyone really get bothered by the extra space before his colons?

def solver() :
    for i in range(9) :

[u/MisterBlggs]

Ah crazy code style man is back

[u/RomanRiesen]

Wrote a Sudoku solver in python in HS.

Was proud of figuring it out myself for waaaayy too long.

[u/Octopuscabbage]

Checking the validity of a state is most of the programming, just backtracking is fairly simple.

[u/grensley]

Here's sombody's 8 line abomination:

def sudoku(P):
    for row, col in [(r, c) for r in range(9) for c in range(9) if not P[r][c]]:   
        rr, cc = (row // 3) * 3, (col // 3) * 3     
        use = {1,2,3,4,5,6,7,8,9} - ({P[row][c] for c in range(9)} | {P[r][col] for r in range(9)} | {P[rr+r][cc+c] for r in range(3) for c in range(3)})
        if len(use) == 1:
            P[row][col] = use.pop()
            return sudoku(P)
    return P

[u/021jn]

About 10 lines and didn’t bother to count how many exactly. Well done.