Another Flash puzzle game  Jim Huggins
[Recent Entries][Archive][Friends][Profile]
11:08 am
[Link] 
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 bruteforce 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 NPhard.  From:  jkhuggins 
Date:  May 27th, 2006 06:56 pm (UTC) 

  Bad link.  (Link) 

Sigh. The link above to the Sudoku is NPhard 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 subDFA'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.
 From:  jkhuggins 
Date:  May 27th, 2006 09:33 pm (UTC) 

  Solutions  (Link) 

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. Bruteforce means you have to check each of the 2^(n*n) solutions; that's exponential time. From:  (Anonymous) 
Date:  May 28th, 2006 03:46 am (UTC) 

  Re: Solutions  (Link) 

Aye there's the rub. Thank you for another flash game to keep me occupied! I'm supposed to be jobsearching!
I'll take your bet and raise you one: www.miniclip.com. Ha!
Amy 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 teaseware games ...) 
