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
Jan 12 '20
Is this tkinter?
4
u/alittleb3ar Jan 12 '20
No its PyQt5
1
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
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
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
3
5
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
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
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