Python Sudoku Solver - Computerphile
Why Stack Overflow recommends it
Stack Overflow users link it because many ask about, port, or debug the exact code from the video, especially why the solver resets cells to zero and prints the grid instead of returning it.
Recommended by 3 people across 3 different months, 2010 to 2023.
What it is
Professor Thorsten Altenkirch of the University of Nottingham walks through a short recursive backtracking Sudoku solver written in Python, explaining how it tries digits cell by cell and undoes them when it hits a dead end. It is a Computerphile episode, filmed and edited by Sean Riley.
What people said
Recommends grokus · 2010-08 · Stack Overflow · on “Difference between back tracking and dynamic programming”
Dynamic problems also requires "optimal substructure". According to Wikipedia: Dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of 1) overlapping subproblems which are only slightly smaller and 2) optimal substructure. Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution. For a detailed discussion of "optimal substructure", please read the CLRS book
Recommends sveculis · 2020-04 · Stack Overflow · on “Python method variable not updating”
A helpful resource to better know what you're doing is to compare your code to someone else's successful code. [this video] might help you out.
Recommends Jorge Luis · 2023-03 · Stack Overflow · on “Python Sudoku Generator infinite loop”
Of course you will reach an infinite loop almost for sure. By putting random numbers in your table its very (very) likely you write a wrong number. That is: a number that makes your Sudoku impossible to resolve. By the time you write the wrong number, it might seem a legit number because there are too many free position to notice the Sudoku is impossible. In your while True you have no way of reach a break if there are no valid numbers for you current row , col position. When would you know you have tried all the possibilities? Instead of looping and asking a random integer every time pick a number randomly from 1 to 9 and break the loop as soon as you have tried all the possibilities. for g
Cites user3196284 · 2020-02 · Stack Overflow · on “Javascript Recursive Backtracking Sudoku Solver”
I recently wrote this same code in Golang with some help from here. If you are familiar with go you can see the working code here. Go Playground [LINK] Here is what I am trying to accomplish in python. Computerphile Video [this video] I am now trying to port this to javascript. I initialize the gameState. var gameState = [ [5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], [0, 9, 8, 0, 0, 0, 0, 6, 0], [8, 0, 0, 0, 6, 0, 0, 0, 3], [4, 0, 0, 8, 0, 3, 0, 0, 1], [7, 0, 0, 0, 2, 0, 0, 0, 6], [0, 6, 0, 0, 0, 0, 2, 8, 0], [0, 0, 0, 4, 1, 9, 0, 0, 5], [0, 0, 0, 0, 8, 0, 0, 7, 9] ] This is the grid taken from the sudoku Wikipedia page. Sudoku Wiki [LINK] I wrote the following helper functions to ge
Cites user3196284 · 2020-02 · Stack Overflow · on “Sudoku Recursive Backtracking in Go”
I am trying to solve a sudoku puzzle in Go using a recursive backtracking algorithm. I created helper functions that check if a certain row, column, or block are valid (i.e no repeated values), as well as a function to print out the current state. I have tested all of these many times so I don't think they are causing the issue. I created the following function to test if a potential game board would be possible. func cellValid(gameBoard *[9][9]int, value int, y int, x int) bool { oldVal := gameBoard[y-1][x-1] gameBoard[y-1][x-1] = value row := getRow(gameBoard, y) col := getCol(gameBoard, x) block := getBlock(gameBoard, x, y) possible := unitValid(row) && unitValid(col) && unitValid(block)
Cites Walid · 2020-03 · Stack Overflow · on “How to use a variable in a function that returns None?”
I have the following function, it is used to solve a sudoku grid. How can I change the code such that it returns the solved matrix so that I can use it for something else, instead of only printing it? The function basically uses recursion to try out all possible solutions for the sudoku grid and fills in a number if it belongs in a certain position. source: [this video] matrix = np.array([[9,0,7, 1,0,0, 0,0,0], [0,0,0, 0,0,0, 0,0,0], [5,0,0, 3,0,0, 0,6,9], [0,0,1, 6,5,0, 8,0,0], [0,3,0, 0,8,0, 0,4,0], [0,0,6, 0,3,9, 1,0,0], [4,2,0, 0,0,6, 0,0,8], [0,0,0, 0,0,0, 0,0,0], [0,0,0, 0,0,2, 5,0,7]]) def grid(i,j): # function which splits the matrix up into 9 grids if i < 3 and j < 3: return matrix[0:3,0
Cites Walid · 2020-03 · Stack Overflow · on “How to use a variable in a function that returns None?”
I am trying to create a GUI where the user inputs the starting numbers, hits enter, and the GUI displays the solved grid. however, when trying to use the function solve(), it returns None so I can't use the solved grid array to display the filled in grid, if that makes sense.. The code is from the following video: [this video]
Cites Michael687 · 2020-04 · Stack Overflow · on “How do I remove 'None' from beneath returned value of function?”
I'm relatively new to python and the concept of recursion. The following code has been taken from a computerphile video (link below). I'd like to understand why the solve function returns a none after the desired output of the solved sudoko, could someone clarify? Is there anyway I can tweak the code to remove it? Thanks. [this video] def solve(sudoko): for i in range(9): for j in range(9): if sudoko.board[i][j] == 0: for m in range(1, 10): if sudoko.possible(i, j, m): sudoko.board[i][j] = m solve(sudoko) sudoko.board[i][j] = 0 return print(sudoko.show())
Cites snatchysquid · 2020-05 · Stack Overflow · on “How does the following recursive Sudoku solving function work?”
I recently watched this [this video] video showing a recursive function to solve sudoku and this seems irrational, since at the end we always change the value back to zero in the end. How come the function worked in the video but doesnt work for me? Should the grid remain the same for both of us since at the end we use grid[y][x] = 0 which resets the grid discarding all changes made? The idea of this code is to iterate over each number cell and each number (1-9) and check if it is possible to put the number in that cell. if we reach a dead end we backtrack. Here's the code I manually copied: import numpy as np global grid grid = [[5,3,0,0,7,0,0,0,0], [6,0,0,1,9,5,0,0,0], [0,9,8,0,0,0,0,6,0], [8,0
Cites Komoka · 2020-05 · Stack Overflow · on “How can I edit a matrix recursively given certain conditions?”
grid = [[5 3 0 0 7 0 0 0 0];[6 0 0 1 9 5 0 0 0];[0 9 8 0 0 0 0 6 0];[8 0 0 0 6 0 0 0 3];[4 0 0 8 0 3 0 0 1];[7 0 0 0 2 0 0 0 6];[0 6 0 0 0 0 2 8 0];[0 0 0 4 1 9 0 0 5];[0 0 0 0 8 0 0 7 9]]; function ov = possibility(grid,x,y,n) ov = true; for i = 1:9 if (grid(x,i) | grid(i,y)) == n ov = false; return end end xO = floor((x-1)/3)*3; yO = floor((y-1)/3)*3; for m = 1:3 for k = 1:3 if grid(xO + m, yO + k) == n ov = false; return end end end end function solve(grid) for x = 1:9 for y = 1:9 if grid(x,y) == 0 for n = 1:9 if possibility(grid,x,y,n) grid(x,y) = n; solve(grid) else grid(x,y) = 0; end end end end end end Just a disclaimer, this code is not my original work, I'm only trying to figure out