Another Flash puzzle game - Jim Huggins
Another Flash puzzle game|
Love this game when I see it in puzzle books ... Picross
Depending on how you look at it, you could brute force the solution to a generic Picross puzzle with a DFA.
Yeah, but that's not really saying much. Any puzzle like this admits a brute-force solution ... sometimes called the Infinite Monkey Theorem
What would be more interesting is an analysis of how long such a solution would take to execute ... and in particular, is it polynomial time or not?
It's surprising what you can get into with simple puzzles like this. There's an article, for example, that shows that Sudoku is NP-hard
|Date:||May 27th, 2006 06:56 pm (UTC)|| |
Sigh. The link above to the Sudoku is NP-hard
reference is bogus. Try this one. (Why can't I edit my own replies?)
Well, I'd think my solution would certainly be NP, (Have a DFA made up of one DFA for each row, column, that accepts a regex matching the definition of the row, column when all sub-DFA's accept, then the outer DFA accepts)
My thought is this is still somewhat feasable because of the nature of the Picross grid. The language could be limited in length to the number of columns and rows in the grid. The fact that each language has a definite length, would trim a huge amount of test cases from the generate and test model.
|Date:||May 27th, 2006 09:33 pm (UTC)|| |
What've you've constructed is a machine which verifies that a given grid of (n*n) squares is (or isn't) a valid solution in O(n) time. That's reasonable, and certainly makes the problem in NP.
The next problem, of course, is figuring out whether you could *solve* the problem in O(n) time, making the problem in P. Brute-force means you have to check each of the 2^(n*n) solutions; that's exponential time.
|Date:||May 28th, 2006 03:46 am (UTC)|| |
Aye there's the rub.
Thank you for another flash game to keep me occupied! I'm supposed to be job-searching!
I'll take your bet and raise you one: www.miniclip.com. Ha!
I've known about Miniclip for a long time ... actually, I'm mostly annoyed by it now ... other than Sudoku, there isn't much interesting for me there anymore. (Maybe it's the overabundance of tease-ware games ...)