?

Log in

No account? Create an account
Another Flash puzzle game - Jim Huggins
May 27th, 2006
11:08 am
[User Picture]

[Link]

Previous Entry Share Next Entry
Another Flash puzzle game
Love this game when I see it in puzzle books ... Picross

(8 comments | Leave a comment)

Comments
 
[User Picture]
From:darthdingus
Date:May 27th, 2006 05:44 pm (UTC)
(Link)
Depending on how you look at it, you could brute force the solution to a generic Picross puzzle with a DFA.
[User Picture]
From:jkhuggins
Date:May 27th, 2006 06:53 pm (UTC)
(Link)
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.
[User Picture]
From:jkhuggins
Date:May 27th, 2006 06:56 pm (UTC)

Bad link.

(Link)
Sigh. The link above to the Sudoku is NP-hard reference is bogus. Try this one. (Why can't I edit my own replies?)
[User Picture]
From:darthdingus
Date:May 27th, 2006 09:12 pm (UTC)

Re: Bad link.

(Link)
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.
[User Picture]
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. Brute-force 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.
From:gamerchick02
Date:May 30th, 2006 09:43 pm (UTC)
(Link)
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!

Amy
[User Picture]
From:jkhuggins
Date:May 30th, 2006 09:56 pm (UTC)
(Link)
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 ...)
My Website Powered by LiveJournal.com