8 ms·
Magic Sudoku – Solve Sudoku with the power of AR
- yeldarb 9y agoHi, thanks for submitting. I'm the developer of the app! Happy to answer any questions (I was going to write up a medium post about the technical side of building the app but haven't gotten a chance yet)
- olympus 9y agoHi yeldarb! This is a really neat app. I don't want to diminish your creation, so please don't think I'm trying to put you down with this question: How much of this was just glue-code to integrate a few modules, vs. how much did you have to do from scratch? I'm asking to try to get an idea to see if ARkit is within the reach of an average joe- sudoku solver code could be a copy/paste, digit recognition could be a copy/paste, and ARKit should provide you with some environment/location info.
- yeldarb 9y agoIt's mostly glue (but some of it is special glue). Oddly enough, digit recognition was one of the harder parts. iOS11's Vision API has character recognition but it only gives you a bounding box, it doesn't do the OCR! So for that I ended up ripping up a whole bunch of Sudoku puzzle books from the second hand book store and scanning them in to create a dataset. Then I trained my own nerual network in Keras and converted it to CoreML. The actual ARKit part was really easy, even for me who has never done iOS programming before.
- generic_T 9y agoYour app is awesome! What type of neural network did you use? Please write a post, I’m teaching myself machine learning and iOS development, and would love to learn from a successful developer!
- yeldarb 9y agoThanks! It's using a convolutional neural network which I minimally adapted from an MNIST tutorial (one of the reasons I picked this project to start with is that there are so many MNIST tutorials for how to do digit recognition out there and it seemed like a good way to dip my toe into ML). Converting it to CoreML after it was trained was really easy. The hardest part was actually creating the dataset and wrestling with pixel buffers to get the image data into a format CoreML liked.
- sdrothrock 9y agoWere there any particular advantages in using a neural network to solve the sudoku as opposed to an existing algorithm?
- yeldarb 9y agoActually the solving of the puzzle itself is just done with a simple recursive algorithm. I trained a neural network to do the computer vision part to interpret the puzzles. And there are a bunch of pre-trained networks built into iOS11's Vision API and ARKit that the app just uses black box.
- sdrothrock 9y agoahh, sorry for the misunderstanding. Does the network do well with handwriting, e.g. puzzles that have been half-solved?
- yeldarb 9y agoWell I wasn't going to spill the beans just yet but if you promise to keep a secret.. working on that for v2 :) Edit: Although so far I've learned that some people have VERY bad handwriting. I'm having a hard time sanitizing a dataset because I can't even tell what digit they were trying to write
- ianamartin 9y agoI'm that guy. Sorry :( I have the worst handwriting. People are like, "Dude, wtf?" when I try to whiteboard stuff.
- yeldarb 9y agoAll good; validates that I'm at least on the right track! Had to pare back my ambitions quite a bit to get _something_ finished before the iOS11 launch. I didn't expect the reception to be so enthusiastic for v1 tbh; but I guess I chose a good place to call it an "MVP"
- M4v3R 9y agoHey, congrats on shipping! Unfortunately your app doesn't work for me :(. I've tried it on few sudoku designs on my laptop screen (don't have anything on hand right now) and there were two problems - the camera would not focus on the screen which resulted in blurry image, and second - it didn't recognize the puzzle correctly and returned incorrect results. I did put my screen flat on the table to simulate a paper laying on it, because I noticed the app doesn't work when the screen was upright - it rendered the results horizontally anyway.
- yeldarb 9y agoThanks for giving it a shot! Sorry it's not working for you. I'm working on a hack to get non-horizontal puzzles working right now. Unfortunately ARKit can only detect horizontal planes at this point so I'm trying to find a workaround since I now realize most people won't have a paper sudoku laying around to try it out and will logically go to the web to find one. I suspect what's happening with the bad reads is that my neural network for digit classification is trained only on paper puzzles (I chopped up a bunch of books and scanned them to make my dataset). I'll have to get some scans of computer screen puzzles to get better accuracy. Can you let me know what site you tried to use so I can make sure to get that font included in the dataset as well? Hoping to get v1.1 submitted tonight yet that will fix the horizontal plane deficiency. Collecting, labeling, and retraining the network may take a bit longer than that.
- krilnon 9y agoAre you the same yeldarb as the one from kirupaForum?
- yeldarb 9y agoI am! Good to see you :) I miss that place; I feel like we grew up there.
- krilnon 9y agoAwesome! It's surreal to see a familiar name making such a neat app. I saw this earlier today and had a small moment of triumph since I'm terrible at solving sudokus myself. A few people visit kF every once and a while; feel free to stop by!
- kirupac 9y agoSmall world! Congrats on the app launch :-)
- pveierland 9y agoHave you tried to render individual digits in the existing empty squares instead of rendering a whole new grid? Coupled with a font detection algorithm this could end up looking more magical.
- yeldarb 9y agoOriginally that was the goal. Unfortunately it wouldn't align exactly perfect (either the size was slightly off due to whether the rectangle detection snagged the inside or outside of the borders or the depth was slightly off so there was slippage when moving around). Didn't quite work right. I do have some things on my to-do list to experiment with though that might help the magic
- vegardx 9y agoJust tried it out, and it looks very good. It was a perfect way to demonstrate ARKit to colleagues. But for some reason it flips the board upside down.
- yeldarb 9y agoSorry about that! That was happening when the phone traveled to the other side of the scene's origin from where it started. The angle calculation got confused. I just got that fixed and submitted to Apple in v1.1 this morning. Should be inbound today or tomorrow as soon as they approve it.
- rawnlq 9y agoI remember using Google Goggles for this back in 2011 or so. The cool new thing is projecting the solution onto the paper and having it track correctly!
- jdoliner 9y agoOh god mods, please add the word "magic" to the title, it's painful to read.
- gattilorenz 9y agoOr remove "like", which is probably what was intended and slightly less sensationalist
- ocdtrekkie 9y agoOn the contrary, the author almost certainly intended to say "like magic", since that's what it says on the page: "Solve sudoku like magic with the power of AR."
- unkown-unknowns 9y agoI think what parent meant was that the word magic was removed from the HN post to make it less sensational, but that whoever removed that word overlooked removing the word "like".
- DanBC 9y agoEmail them. They don't see it otherwise.
- iamflimflam1 9y agoDid something similar some time back before ARKit and vision frameworks were around. Are you using the rectangle detection from Vision? https://www.youtube.com/watch?v=wt96OomJY9A https://www.youtube.com/watch?v=wt96OomJY9A
- yeldarb 9y agoNice! Yeah, I am using Vision's rectangle detection.. but it's really touchy. I've got a lot of heuristics in there to throw out bad results and smooth things out. It doesn't do well if there's something near the puzzle though (like a horizontal rule or text like you might see in a newspaper layout). Any suggestions on a better way to segment the rectangles? Or any preprocessing tips (I couldn't really find anything that made it detect things more reliably)
- iamflimflam1 9y agoI've got a very old and slightly broken blog post on what I was doing: https://www.cmgresearch.com/2009/08/14/How-does-it-all-work.html https://www.cmgresearch.com/2009/08/14/How-does-it-all-work.... My approach was to adaptive threshold the image and then assume that that the object of interest was the biggest connected region in the image. Then run that though rectangle detection. Have you tried setting the aspect ratio and minimum width on the Vision rectangle detector? That might filter out any nonsense.
- yeldarb 9y agoThe parameters are not very well documented. (Or at least it wasn't when I was coding that part). But yeah I did get those set finally. Whatever I do though I can't get it to recognize any rectangles here: http://www.telegraph.co.uk/news/science/science-news/9359579/Worlds-hardest-sudoku-can-you-crack-it.html http://www.telegraph.co.uk/news/science/science-news/9359579... For our demo video we ended up photoshopping out the horizontal line right above it and that seemed to work.
- iamflimflam1 9y ago
- splike 9y agoHow would HN attack the problem of solving a crossword using this type of tech + character recognition?
- yeldarb 9y agoA crossword solver was what I originally set out to build. iOS11's Vision APIs for rectangle detection weren't good enough to even have a shot at it though. With better rectangle detection I think it'd be pretty doable!
- splike 9y agoI had assumed that the AR side of the problem would be the easy bit and that the real issue would be solving the riddles.
- yeldarb 9y agoI think that bit would be easy; but I'd probably cheat. You don't need to understand the context of the clues. You just need a big enough wordlist to brute force with. Start with the longest words since they will have the least options. I'll bet you could scrape all the previously used words/phrases from the last 100 years of NYTimes, etc to get things rolling.
- wlll 9y agoI feel like this is solving the symptom, and not the actual problem which is that newspapers are printing sudoku with some of the numbers missing.
- dmichulke 9y agoRelated: https://www.theregister.co.uk/2013/08/06/xerox_copier_flaw_means_dodgy_numbers_and_dangerous_designs/ https://www.theregister.co.uk/2013/08/06/xerox_copier_flaw_m...
- cultavix 9y agoHey, what if I don't have a Sudoku puzzle to provide? Can't you just generate one on the table ? :P
- yeldarb 9y agoI just submitted v1.1 to the App Store that supports puzzles on a vertical plane so once that lands you can load up https://websudoku.com https://websudoku.com on your computer monitor to try it out! Sneak peek of that update: https://twitter.com/braddwyer/status/910861205442527233 https://twitter.com/braddwyer/status/910861205442527233 Several bug fixes included as well based on input from early users.
- sowbug 9y agoOther good ideas: - point at a board game and either do all the boring scorekeeping for me, or else advise me on best strategy - take a photo of a bunch of lottery tickets and tell me whether I've won
- yeldarb 9y agoLove these ideas! I have a long list of ARKit apps I want to build.. if only there were more months in a year. I think my favorite is a Mario Kart style "ghost mode" for running. Where you could tell it what pace you wanted to go and it'd show ghost running in front or behind you at that pace!
- pricechild 9y agoThe UK's national lottery android (and maybe Apple?) app already does the second one. It's just done with a QR code. Unfortunately... there was a bug and it told people they hadn't won: http://www.independent.co.uk/news/uk/home-news/national-lottery-players-binned-winning-tickets-app-technical-issue-a7386186.html http://www.independent.co.uk/news/uk/home-news/national-lott...
- cableshaft 9y agoWow, I was at a hack night and saw a demo by someone who had made exactly this type of app on his computer using its webcam. He built a neural network and trained it, and it could even handle angles that weren't straight on. I don't think he's the same guy, but yeah, it's a clever idea.
- opendomain 9y agoDo you have a link or other info on the hack night?
- cableshaft 9y agoIt's a group called OpenHack organized on Meetup.com and it's located in the southwest suburbs of Chicago. It was just one of like 30 people who attended it.