r/Python • • Jan 11 '20

Sudoku App

1.4k Upvotes

61 comments sorted by

75

u/alittleb3ar Jan 11 '20

Gui is made using PyQt5. The beginning board is hard coded but the solve does actually use an algorithm to solve the board and would work with any solvable starting board

43

u/mweitzel Jan 12 '20

Instead of an input field, why don’t you present a dialog with 9 buttons representing the numbers? Should be easy enough, no? Love it otherwise though.

34

u/alittleb3ar Jan 12 '20

In trying to learn PyQt5 there have been a lot of things that I thought should be easy but were the opposite. I do want to work on the input though

8

u/mweitzel Jan 12 '20

Awesome, sounds you e got the right attitude towards learning!! Good luck and lots of fun!!

2

u/passerbycmc Jan 12 '20

You bet used to it over time, I use PySide2 for a lot of UI it's pretty easy and flexible but also yeah it's very verbose.

4

u/wastakenanyways Jan 12 '20

I'd make the cell itself be the input field instead of a dialog

3

u/Rocky87109 Jan 12 '20

I was thinking you could move around a colored square with arrow keys (if you are on pc/mac) and just punch in a number on your keyboard in the square is at. Now I think I might want to make me one of these lol. I need a project.

1

u/roberto257 Jan 12 '20

Can I ask where you learned PyQt5? Tkinter has really great documentation/reference sites, do you know of any for PyQt5?

4

u/alittleb3ar Jan 12 '20

Honestly my method for learning it was doing the first few tutorials at http://zetcode.com/gui/pyqt5/, and then I just used the c++ documentation at https://doc.qt.io/ and figured it out. I didnt use any actual pyqt documentation because I found it all lacking

1

u/xd1142 Jan 13 '20

What's with the timer at line 290?

1

u/alittleb3ar Jan 13 '20

You cant quit a PyQt program using Ctrl+C while it's running, so if it hangs you have to kill the process. This was a workaround I found on a website that's supposed to allow you to quit it with Crtl+C. Doesn't work though, I need to play around with it

2

u/xd1142 Jan 13 '20 edited Jan 13 '20

there's a very good reason why you can't quit it with Ctrl-C. What you have there is not a workaround. It's a crash that happens when a separate thread is forced to handle a keyboard exception, fucks up, and somehow the whole thing crashes.

You can't exit with Ctrl-C because in an event driven application, all exceptions reach the event loop and are printed and discarded. That's how it's supposed to work.

What you want to do, if you really, really want to quit on Ctrl-C, is to install an event filter for that and call quit()

1

u/alittleb3ar Jan 13 '20

What I was looking for was just an easier way of killing it if it hangs. Does the timeout method not provide information of that happening? Could I better handle the timeout event to actually close the program?

1

u/xd1142 Jan 13 '20

if it hangs because there's a bug, fix it. If it hangs because you are running heavy calculations in the main thread, put it on a separate thread or process.

It's not a "timeout method". It's a broken way of exploiting a crash to stop the application, because you are misunderstanding the fundamentals of UI programming.

UI interaction must handle an event and go back to the event loop in less than 150 ms, otherwise the application will feel sluggish. If you have a long running task, you can't have it execute on the main thread.

1

u/alittleb3ar Jan 13 '20

What you're saying makes a lot of sense, thank you for explaining it.

2

u/thedeats Jan 12 '20

I've Find a lot of doc in this site like this example :)

https://doc.qt.io/qtforpython/PySide2/QtWidgets/QTreeWidget.html

Stack overflow really help me too just tipping what do you want to do like "Building a file tree in Pyqt" just be carefull some PyQt4 code might not work.

6

u/69shaolin69 Jan 12 '20

Instead of inputting the number select the box and wait for user to type something

Btw great job, I barely make GUI using python and if I do I usually use pygame it tkinter what library are you using? Or did you make one?

2

u/alittleb3ar Jan 12 '20

That's a good idea, I'll probably work on the user input next. I used the PyQt5 library for the gui

1

u/RufusAcrospin Jan 12 '20

I’d probably just add an ordered list of the available numbers to the top of the popup menu and test it to see how fast/convenient to use just the mouse for input.

2

u/[deleted] Jan 12 '20

Is this tkinter?

4

u/alittleb3ar Jan 12 '20

No its PyQt5

1

u/kiwiboy94 Jan 12 '20

Do you think it's possible to recreate this using PySimpleGUI?

1

u/alittleb3ar Jan 12 '20

I wouldn't see why not

1

u/[deleted] Jan 12 '20

Yes it is

2

u/barkerd25017 Jan 12 '20

just let them enter the number while hovering over the box instead of clicking

1

u/alittleb3ar Jan 12 '20

Not a bad idea. My goal is to put this on my RasPi and play around with the touchscreen so I do want to keep a tap/click input before you can select a number

2

u/youre-kidding Jan 12 '20

Were you inspired by this video by chance OP? I watched it minutes before seeing your post!

1

u/alittleb3ar Jan 12 '20

I love Tim! I actually found this video in the middle of working on my project and tweaked my algorithm with its help. I was originally using a queue but I liked the recursion better

60

u/Gwenju31 Jan 11 '20

I'll grab this occasion to talk about the easiest way of solving a sudoku (IMO). You can use constraint programming, and with 3 simple constraints you can solve every board effortlessly : AllDiff on rows, cols and squares :)

21

u/StevieWondering1000 Jan 12 '20

Are you sure?

I think I did that once and found that only works for easy to medium difficulty. I might be wrong tho.

7

u/Gwenju31 Jan 12 '20

I guess it depends on the solver you use. I'm using the Mistral solver through Numberjack lib, and it can solve the hardest deterministic sudoku (16 or 17 clues, 1 unique solution) almost instantly, but I did not experiment with harder, multi-solution boards.

8

u/Piece_of_Crap Jan 12 '20

It doesn't have to do with multi-solution. There are starting layouts that even applying the 3 basic rules don't get you a final solution. When doing it on paper usually you find the patterns of common numbers and start working by exclusion, programmatically your best option is backtracking i guess.

4

u/Gwenju31 Jan 12 '20

Oh I get your point now. Yeah of course the solver cannot guess the solution in one go. It starts by restraining the domain of each variable (each cell on the board) with arc consistency, then affect each variable with some value of its domain (using heuristics like "most constrained variable first"). During this process, every time the current affectation breaks one of the constraints, the solver indeed has to backtrack

1

u/SP_Man Jan 12 '20

Why didn't it work for harder instances? Did it take too long, or run into some practical limitation like that? Those 3 all diff constraints should be sufficient to solve any instance, right?

1

u/itsjakerobb Jan 14 '20

The constraints are sufficient to check a solution, but there are puzzles (usually tagged medium or high difficulty) for which you can't iteratively eliminate the impossible via the constraints and arrive at the solution. You'll find points at which, after eliminating the impossible, two or more possibilities remain for one or more cells. At that point, one option (which works great for computers, since Sudoku puzzles are small and computers are fast) is to pick one of the aforementioned cells and guess the correct answer. Apply the constraints again, and repeat recursively. If you end up at a valid solution, great! If not, backtrack and guess differently.

1

u/StevieWondering1000 Jan 19 '20

I basically had it run the the board thru the contraints and then I had a break if it eventually never got any further. It did fine till about halfway through and then coulden't find any way to progress. Since it had completed easier sodukos earlier and I wasen't able to find any progression from the point of which it had stopped I naturally concluded that other constraints were needed.

Take this with a grain of salt tho. It was some quick code I threw together in an afternoon for fun and I diden't do any digging. But judging from the other commenters it does seem that harder sodokus cant always be solved with the simple three constraints alone

14

u/Ruben_NL Jan 12 '20

My method was giving each cell a list of possible numbers(1 to 9), and removing until there was only one left. I made a solver, and a generator in Node.JS, which I might port to python.

9

u/knestleknox I hate R Jan 12 '20

That's a pretty standard way to solve CSPs. It's similar to methods like forward checking and arc consistency

1

u/[deleted] Jan 12 '20

Here is an excellent set of lectures that include CSPs, along with many other introductory AI topics.

4

u/EquationTAKEN Jan 12 '20

That's a decent way of doing it, but there are cases where it will fail.

Some times, there will be cases where you can't reduce any squares to just one possibility. You'll have two or three squares with two or more possibilities, and the only way of solving it is trial (and possibly error). In that case, you have to either go down the road and fail, and come back, or you have to try to think a few steps ahead and see it without actually "making the moves".

2

u/Zomunieo Jan 12 '20

It also works to encode the Sudoku puzzle as a SAT problem and solve it with a SAT solver. For many problems the encoding to SAT is difficult, but it's pretty straightforward for Sudoku.

1

u/Gwenju31 Jan 12 '20

My "heuristic" to reduce a problem to SAT clauses is pretty simple: "Can I use a graph to represent this problem?". If yes, then SAT encoding is *almost* trivial, if no, then I don't bother aha

2

u/Omrimg2 Jan 12 '20

I don’t think this applies for hard sudokus

1

u/rcfox Jan 12 '20

Constraint satisfaction programming looks like magic, but all of those fancy algorithms require your data be in a standard form. To convert a general problem into the standard form, you essentially have to enumerate the entire space.

But damn, does it look elegant.

8

u/heyjoeo Jan 12 '20

This is cool! You could also add an option to set “possible” matches as another goal. Like you might if you were using a pencil.

For example if you knew a space was either a two or a one you could let the user add these in the top left or right of the box (maybe up to four, one for each corner?).

That way they can narrow it down as they solve!

1

u/SeanBrax Jan 12 '20

Would be neat if you could visualise step by step how your algorithm solves the puzzle. Good stuff though!

1

u/alittleb3ar Jan 12 '20

That's a good idea! It might be too fast though, the time between me clicking solve and the answer populating is actually the time it takes to solve

1

u/SeanBrax Jan 12 '20

Could you not place a delay between each step of the algorithm?

1

u/alittleb3ar Jan 12 '20

Probably could. The algorithm would theoretically work for any size square board so I might try with a bigger board than 9x9 to see what happens

0

u/[deleted] Jan 12 '20

[deleted]

3

u/vlplbl Jan 12 '20

I made something similar with pygame

https://github.com/vlplbl/Sudoku?files=1

5

u/[deleted] Jan 12 '20

I see Ubuntu. I upvote.

2

u/surajmanjesh Jan 12 '20

Neat! I have a suggestion - using different colors for the numbers that were part of the puzzle and for ones that were filled in by the player will be helpful while solving!

2

u/CraigAT Jan 12 '20

Great work. I agree the number input could be improved, but I'd like to make another suggestion - when solving the puzzle, fill in the numbers one at a time with a very brief pause - it looks more convincing, like the computer or program is working out out in real time.

2

u/fernly Jan 12 '20

Obligatory reference to Peter Norvig's Sudoku Solver in Python which is now 8 years old.

1

u/Lepton78 Jan 12 '20

Super cool.

Did you write the solver yourself, or did you use a solver that was already available?

1

u/[deleted] Jan 18 '20

Use a virtual environment