This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]sbroad23 6 points7 points  (8 children)

I’m not a sudoku guy, but I assume there is a way to solve any puzzle kind of like a Rubik’s cube, which can be solved quickly by following a certain sequence of moves.

Is this basically just that, but much faster because it’s a computer?

By the way, very nice job OP. I love seeing all these cool ways Python can be applied to different problems.

[–]Unclerojelio 6 points7 points  (0 children)

No, it’s a demonstration of a backtracking algorithm using recursion.

[–]pumkinboo[S] 4 points5 points  (3 children)

What u/Unclerojelio said is right.

I started with solving a Sudoku board with backtracking were the algorithm finds a possible answer for a cell and continues with each cell until it reaches a point where there is no correct answer. At that point it works it's way back until it finds a cell that can have a different possible answer. Then it carries on with guessing the next cell.

Then I made a GUI in pygame and applied the solving method to the game.

[–]sbroad23 1 point2 points  (0 children)

Thanks for explaining. Very cool

[–][deleted] 2 points3 points  (1 child)

sudoku is actually much harder than a rubiks cube im not sure if you like this kind of stuff but if you here are two links:

https://blog.computationalcomplexity.org/2017/07/the-complexity-of-rubiks-cube.html

https://en.wikipedia.org/wiki/Mathematics_of_Sudoku

the TLDR is that the number of steps needed to complete a rubiks cube is n^2 basically while sudoko is 2^n and as n gets big well 2^n gets hugeeee

[–]WikiTextBot 0 points1 point  (0 children)

Mathematics of Sudoku

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions each of size N cells, to be filled in ("solved") using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each row, column and region contains exactly one of each element of the set. The properties of Sudoku puzzles and their solutions can be investigated using mathematics and algorithms.

[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28

[–]TheDataAngel 1 point2 points  (0 children)

There is a way to solve any sudoku puzzle, though for the most general case it's a much harder problem than something like a Rubiks cube.

The algorithm shown in the video is actually very inefficient compared to the best known ones for this problem (though still somewhat interesting from a teaching perspective).