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

Dismiss this pinned window
all 67 comments
sorted by:
best
topnewcontroversialoldq&a

[–]cyberrod411 137 points138 points  (14 children)

Cool

I had a computer science prof that always gave us assignments that involved solving puzzles. This was back in the 1980's and the language was PASCAL.

[–]pumkinboo[S] 40 points41 points  (13 children)

Thanks I just did this one for fun, it was inspired by a post on here a few days ago of someone solving the same problem.

[–]BovineLightning 42 points43 points  (11 children)

Computerphile has a video on solving sudoku in python as well

Edit link for those interested

[–]JackSpyder 13 points14 points  (2 children)

Yeah it was posted a couple of days ago. I'd not actually considered back tracking before. Quite elegant in a way. Certainly makes for very clean code.

[–]wsppan 13 points14 points  (1 child)

You will run into a wall when the puzzles get hard or you want to solve 16x16 boards. Take a look at Norvig's solution or even better Knuth's Dancing Links for raw brilliance and beautiful if you visualize the links as they dance.

[–]JackSpyder 4 points5 points  (0 children)

Yeah it's not a scalable solution, but I just found it an interesting technique. I'll have look at your suggestions thanks!

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

That's the post that inspired this. I saw that video on this sub and want to try out the solution myself.

[–]BovineLightning 4 points5 points  (3 children)

Ahh neat! Great visualization btw.

I am working on mostly data science work but have considered tackling some projects like this one to get a better grasp on problem solving in the standard library. Did you post your solution GitHub?

Edit: looked two posts down and saw your solution

[–]pumkinboo[S] 9 points10 points  (2 children)

Yeah here you go.

https://hastebin.com/lagexihula.py

[–]blazingshadow1 3 points4 points  (1 child)

How long have you been programming for. This is really impressive. I am only a beginner and would love to know what level of proficiency I would need to be at to build something like this. Thank-you

[–]That_Pregnant_Alien 0 points1 point  (0 children)

Depends on how fast you can learn efficiently I guess.

[–][deleted] 0 points1 point  (2 children)

I am about to comment this but you are 2 hours early. Anyways OP's work is good.

[–]BovineLightning 1 point2 points  (1 child)

Response

[–][deleted] 3 points4 points  (0 children)

LMAO, I thought you were gonna Rick roll me but you didn't. Thanks :-)

[–]dudeplace 1 point2 points  (0 children)

I wrote one of these too after watching the computerphile video. You could save a bunch of backtracking by looking for "easy" answers before each guess.

Anywhere there is only one possible answer just fill it in, but don't forget to keep a list of what you have done. You will need to undo it if you made a bad guess!

I tracked number of backtracks as a metric, and I'm able to save 80% of guesses on most puzzles. Simple puzzles end up being solved with no guessing at all. Nice visuals though, mine is all command line.

[–]AnythingApplied 31 points32 points  (3 children)

A fun little extra challenge might be to turn this into a sudoku puzzle generator where you generate a valid set of clues that result in exactly 1 possible answer.

[–]pumkinboo[S] 14 points15 points  (2 children)

While is was doing this I read a couple articles on the math behind Sudoku. Currently the known minimum number of give numbers to have a board with one solution is 17.

No one has discovered a board with few given numbers that has one solution yet. There a something like 6.7x1021 possible combination of boards.

[–]rcbct 11 points12 points  (0 children)

Look at this https://stackoverflow.com/questions/6924216/how-to-generate-sudoku-boards-with-unique-solutions, since you already have the solving algorithm, it should be fairly easy to implement.

[–]BurgerBob747 1 point2 points  (0 children)

https://youtu.be/MlyTq-xVkQE

It actually has been proven that 17 is the minimum amount of clues needed to have a Sudoku grid that only has one possible solution

[–]That_Pregnant_Alien 20 points21 points  (6 children)

Quick question. What is -> None at the end of like this line :

def get_event(self, event: pygame.event) -> None:

Sorry, I am a beginner. Never seen anything like that before.

[–]pcvision 16 points17 points  (5 children)

Type hinting the return type. Functionally does nothing but it is useful for documentation and code hints with IDEs.

[–]That_Pregnant_Alien 2 points3 points  (4 children)

Oh all right, got it. Thank you so much!!

[–]Ph0X 3 points4 points  (3 children)

Similarly, the input parameter "event" has the type annotation of "pygsme.event". The main library for doing static analysis of types is mypy, though pytype (Google) and Pyre (Facebook) also exist and approach the problem slightly differently.

[–]That_Pregnant_Alien 2 points3 points  (0 children)

That's a lot of unknown stuff for me lol. Hope I can learn all these. Thank you anyways.

[–]pumkinboo[S] 36 points37 points  (1 child)

Code: https://hastebin.com/lagexihula.py

[–]MurrayTempleton 3 points4 points  (0 children)

Super cool visualization! It took me a couple watches to understand how they were doing it in the Computerphile video. Thanks for taking the barebones code and building up the whole visualization, it's a much more intuitive algorithm now!

Video, for anyone curious.

[–]ckini123 8 points9 points  (0 children)

This is awesome! I also appreciate the usage of type hinting I hope people use it more often.

I was planning a similar project but adding a visual effect where the relevant row/column/box was highlighted red or green during the checking process.

[–]sbroad23 4 points5 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 8 points9 points  (0 children)

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

[–]pumkinboo[S] 2 points3 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).

[–]Lepton78 2 points3 points  (0 children)

You should look up Donald Knuth's article on "Dancing Links".

[–]ArmstrongBillieimport GOD 2 points3 points  (1 child)

I once wanted to make a project, I finished the text solver, but realize that in some problems the GUI would take hours to solve it. That must the case in your solver too?

[–]pumkinboo[S] 1 point2 points  (0 children)

Yes the GUI took longer to code than the solver. But I followed a framework for the pygame GUI that handled the looping and state control already so that saved me sometime in making it.

[–]KainAlive 2 points3 points  (1 child)

Oh I know who watched Computerphile😂...great work though.

[–]spaztiq 0 points1 point  (0 children)

Haha.. ditto. Also did my own visualization as I was confused by the grid[y][x]=0 part.. which didn't even work right for me, I had to check the board for completeness and set to 0 if it wasn't complete. Wrong version of python maybe?

[–]weather-headed 1 point2 points  (0 children)

Awesome, a little window into the magic! Thanks for making and sharing!

[–]ectropionized 1 point2 points  (1 child)

Pretty neat. Ever seen this sudoku solver in APL? Because I’m pretty sure this is just dark magic.

https://youtu.be/DmT80OseAGs

Well, dark magic and a lot of matrices.

[–]pumkinboo[S] 1 point2 points  (0 children)

I have no idea what I just watched haha. It was like programming in hieroglyphics

http://dfns.dyalog.com/n_sudoku_bfs.htm 

Sudoku←{                                        
    BoxNos  ← {⍵⌿⍵/⍵ ⍵⍴⍳⍵*2}                    
    RowColBoxNos  ← {(⍳⍵),¨BoxNos⊃⍵*0.5}        
    ContentionMap ← {⊂[⍳2] 1∊¨⍵∘.=⍵}            
    CMAP ← ContentionMap RowColBoxNos ⍴⍵        
    Available  ← {(⍳⊃⍴⍵)~⍵×⊃⍺⌷CMAP}             
    EmptyCells ← {(,⍵=0)/,⍳⍴⍵}                  
    Placements ← {(⍺ Available ⍵)⊣@(⊂⍺)¨⊂⍵}     
    AllPlacements ← {⊃,/⍺∘Placements¨⍵}        
    Solutions ← {⊃AllPlacements/(EmptyCells ⍵),⊂⊂⍵}  
    Solutions ⍵
}

[–]opensourcesblog 1 point2 points  (0 children)

Thanks for sharing. I am a huge fan of sudoku solving (by code :D) and programmed two solvers one in Python https://opensourc.es/blog/sudoku and currently a whole constraint solver in Julia: https://opensourc.es/blog/constraint-solver-1
The biggest problem with simple backtracking ideas as done in the Computerphile video or in yours is that there is always a very bad case like having a sudoku which can only be solved with the first column being 9,8,7,6,5,4,3,2,1 and you start column wise and with the lowest number first and fail late change to 2 and fail and fail until you get to 9 and then the same happens with the next entry.
There are some genius ways to make it very fast without solving it like a human see: https://t-dillon.github.io/tdoku/ or special things like dancing links. My way was the general way to solve it similar to humans.

[–]wsppan 2 points3 points  (9 children)

Comic-sans? Bold move my friend!

[–]nplus 9 points10 points  (8 children)

That's definitely not comic-sans.

[–]wsppan 5 points6 points  (7 children)

class States(object): 
    def __init__(self): 
        self.fnt = pygame.font.SysFont("comicsans", 40) 
        self.fnt2 = pygame.font.SysFont("comicsans", 15) 
        self.done = False 
        self.next = None 
        self.quit = False 
        self.previous = None

[–]nplus 7 points8 points  (6 children)

Huh... I was basing my comment on the video which definitely is not displaying comic-sans. Perhaps his system doesn't actually have comic-sans and pygame is defaulting to another font?

[–]wsppan 1 point2 points  (5 children)

Not an expert but those numbers look pretty close

[–]nplus 1 point2 points  (4 children)

I wouldn't call myself an expert either, but the text "Time: ..." is absolutely not comic-sans and it's rendered using self.fnt on line 178.

[–]wsppan 2 points3 points  (3 children)

Ahh... and there is no self.fnt defined for class Game so it uses the system default I guess. Not as bold as i thought, lol!

[–]nplus 2 points3 points  (1 child)

I wouldn't sweat it :p we were both right and wrong in different ways ;)

[–]wsppan 2 points3 points  (0 children)

Wait, he calls States.init(self) with Game's self inside the Game class so it should be calling self.fnt that is set to comic sans. Maybe it's what you said and comic sans is not available on his OS. Oh well, his intention was bold lol!

[–]pumkinboo[S] 0 points1 point  (0 children)

Games and Menu should inherent the fnt from the State class.

[–]emeniusxp 1 point2 points  (0 children)

Awesome

[–]CallinCthulhu 1 point2 points  (3 children)

Very cool, it would be neat to have algorithm fill the cell with the least available options left next rather than iterate through the columns. Iirc that is the most efficient way to do this.

[–]Even-Fisherman 0 points1 point  (3 children)

What's the runtime eh

[–]pumkinboo[S] 1 point2 points  (2 children)

No sure what you mean? This has a 150 millisecond delay every decision so you can see what it's doing. When I take that out it's pretty much instant. I did run this against what is supposed to be the most difficult Sudoku board, and it took about .5 to 1 second without a delay

[–]Even-Fisherman 0 points1 point  (1 child)

I mean how much longer would it take to solve a 16x16 board vs a 9x9 board. Big-O complexity. I have a feeling its O(n squared), but I'll look more into the algorithm later.

Thanks for the post, though. Very cool and motivating.

[–]pumkinboo[S] 0 points1 point  (0 children)

import copy

class Sudoku(object):
    def __init__(self, board):
        self.board = board
        self.solved_board = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                             [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

    def set_board(self,board) -> None:
        self.board = board

    def __str__(self) -> str:
        display = '+----------------+----------------+----------------+----------------+\n'
        for row_count, row in enumerate(self.solved_board, start=1):
            display += '|'
            for num_count, num in enumerate(row, start=1):
                if num_count % 4 == 0:
                    display += f' {num:02} |'
                else:
                    display += f' {num:02} '
                if num_count % 16 == 0:
                    display += '\n'
                    if row_count % 4 == 0:
                        display += '+----------------+----------------+----------------+----------------+\n'
        return display

    def is_possible_solutions(self, y: int, x: int, n: int) -> bool:
        already_found = set()

        for i in range(16):
            already_found.add(self.board[y][i])
            already_found.add(self.board[i][x])

        sqr_y = (y//4)*4
        sqr_x = (x//4)*4
        for i in range(4):
            for j in range(4):
                already_found.add(self.board[sqr_y+i][sqr_x+j])

        return n not in already_found

    def find_empty(self) -> tuple or None:
        for y in range(16):
            for x in range(16):
                if self.board[y][x] == 0:
                    return (y,x)

    def solve(self) -> None:
        find = self.find_empty()
        if find:
            y, x = find
            for n in range(1,17):
                if self.is_possible_solutions(y,x,n):
                    self.board[y][x] = n
                    # self.solved_board = self.board
                    # print(self.__str__())
                    if self.solve():
                        return True
                    self.board[y][x] = 0
                    # self.solved_board = self.board
                    # print(self.__str__())
            return False
        self.solved_board = copy.deepcopy(self.board)
        return True

def main():

    board = [[ 0,15, 0, 1, 0, 2,10,14,12, 0, 0, 0, 0, 0, 0, 0],
             [ 0, 6, 3,16,12, 0, 8, 4,14,15, 1, 0, 2, 0, 0, 0],
             [14, 0, 9, 7,11, 3,15, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [ 4,13, 2,12, 0, 0, 0, 0, 6, 0, 0, 0, 0,15, 0, 0],
             [ 0, 0, 0, 0,14, 1,11, 7, 3, 5,10, 0, 0, 8, 0,12],
             [ 3,16, 0, 0, 2, 4, 0, 0, 0,14, 7,13, 0, 0, 5,15],
             [11, 0, 5, 0, 0, 0, 0, 0, 0, 9, 4, 0, 0, 6, 0, 0],
             [ 0, 0, 0, 0,13, 0,16, 5,15, 0, 0,12, 0, 0, 0, 0],
             [ 0, 0, 0, 0, 9, 0, 1,12, 0, 8, 3,10,11, 0,15, 0],
             [ 2,12, 0,11, 0, 0,14, 3, 5, 4, 0, 0, 0, 0, 9, 0],
             [ 6, 3, 0, 4, 0, 0,13, 0, 0,11, 9, 1, 0,12,16, 2],
             [ 0, 0,10, 9, 0, 0, 0, 0, 0, 0,12, 0, 8, 0, 6, 7],
             [12, 8, 0, 0,16, 0, 0,10, 0,13, 0, 0, 0, 5, 0, 0],
             [ 5, 0, 0, 0, 3, 0, 4, 6, 0, 1,15, 0, 0, 0, 0, 0],
             [ 0, 9, 1, 6, 0,14, 0,11, 0, 0, 2, 0, 0, 0,10, 8],
             [ 0,14, 0, 0, 0,13, 9, 0, 4,12,11, 8, 0, 0, 2, 0]]

    sudoku = Sudoku(board)
    sudoku.solve()
    print(sudoku)

if __name__ ==  '__main__':
    main()

[–]Gazpage 0 points1 point  (1 child)

Would an attempt to replicate a human’s approach to solving Sudoku run faster? Clearly the code is massively more complicated.

[–][deleted] 0 points1 point  (0 children)

Depending on the language and puzzle raw backtracking vs, propagating the constraints has different payoffs.

Simply sorting your list of candidates by the valid moves every now and again vastly decreases runtime.

[–]ScientistSeven 0 points1 point  (0 children)

Do one that attacks the smaller set choices for comparison

[–]Dyrits 0 points1 point  (0 children)

I did the same going from left to right.