So college is on again. Not really happy news - it's mostly a boring waste of a lot of time that could have been profitably wasted instead...Case in point: I'll end up missing my TopCoder SRM tomorrow, because we have an 0800 lecture, and this prof is not the kind of person who turns up late. Looks like I've been reduced to just the weekend matches. Darn it all...
Note to Thite: All the best for your first SRM - just don't oversleep and miss it ;-)...Your notorious lack of punctuality might also work against you - be sure to be there at least 10 mins early - registration for an SRM ends 5 mins before the match begins.
I've made a couple of changes to the comment system - it always bugged me that comments could only be viewed on a new page if you were reading the main page. With a little help from Blogger Hacks, I've fixed it so the comments will kinda unroll when you click on the link...Be sure to gimme some feedback on it!
Looks like we've got Digital Signal Processing and Advanced Microprocessors this semester. Bad - I really don't like the electronics related subjects so much - software is still my major interest. I hear DSP is mostly maths - hope that's true, because I don't have much of a memory for circuit diagrams.
Began writing a little Java program this afternoon to do the Mumbai Mirror's daily Sudoku challenge. I've got it deducing things to the point where it correctly fills up about half the grid - the only problem is that it can't go any further. Looks like my friend Sagar was wrong - as far as I can see, there isn't enough information in the problem to uniquely determine each grid value. At some point, you probably have to guess and see if things work out that way...Of course, the other option would simply be to use a brute force combinatorial approach - generate all possible grids, and pick out the one that matches the puzzle data - but where's the fun in that? At least this way I'm still using logical reasoning - I've just outsourced the details to my computer. Maybe there's some kind of reasoning that I can't put my finger on just yet....
Hmmm....Wikipedia says that the general Sudoku problem on an n x n grid is NP complete - luckily, the simple case of n = 9 can be managed using state machines, so at least I'm not wasting my time...
This is interesting...Turns out that Sudoku is a variant of graph coloring problems - no wonder I kept thinking vaguely of graphs while I coded...Maybe I can use this - and it'll be a good excuse to read up on graph coloring and other such stuff. Will report future progress in a few days...
In other news, I have the TOEFL scheduled in 2 weeks time - not that it should be too much trouble, but it never hurts to be prepared...
And now to sleep, perchance to dream...
Subscribe to:
Post Comments (Atom)
2 comments:
You're right, brute force isn't necessary - my program looked at the entire grid(whole rows and columns) and each of the 3x3 subgrids. That in itself is not enough to uniquely determine numbers - in fact, I figured this out yesterday and mentioned it in my blog post. I just wasn't sure what the third bit of reasoning was...
I've got an idea from watching a friend of mine do a sudoku today - if it works, I should have a fully functional solver.
PS: This would have probably have gone a lot faster if I'd given sudokus more than a cursory glance before I decided on automating the solution. That way I might have stumbled upon some pretty good strategies...
Nice blog, BTW. Got it bookmarked now...
Yeah the comment thingy is good. Your navigation sucks - especially for those who decide to read from the begining and then move forward.
Post a Comment