Masyu - it's like pathfinding?

Masyu - it's like pathfinding?

Here is where ideas can be collected for the skirmish AI in development

Moderators: hoijui, Moderators

Post Reply
pktm
Posts: 57
Joined: 05 Aug 2006, 15:49

Masyu - it's like pathfinding?

Post by pktm »

Hello!

I'm trying to write a Masyu solver, but it's really hard. It reminds me of pathfinding, so i thought, i could ask someone here :)

Does anyone has any suggestion how to solve a Masyu puzzle?

My approaches always have some bugs, they don't work out.

regards, pktm
User avatar
AF
AI Developer
Posts: 20687
Joined: 14 Sep 2004, 11:32

Re: Masyu - it's like pathfinding?

Post by AF »

First, what's masyu?
pktm
Posts: 57
Joined: 05 Aug 2006, 15:49

Re: Masyu - it's like pathfinding?

Post by pktm »

It's a puzzle: http://en.wikipedia.org/wiki/Masyu

You have to connect all pearls by watching certain rules.

But, how do you compute a solution?
User avatar
SinbadEV
Posts: 6475
Joined: 02 May 2005, 03:56

Re: Masyu - it's like pathfinding?

Post by SinbadEV »

Looks like "Maze" solver Algorithm would probably work... just with the added rules. Another idea would be to calculate all the possible paths and see if any of them don't break any of the rules.

edit:
Okay, standard maze solver algorithm says you move to a new square you have 3 options, (any direction but where you came from) in this case if a square is blank you have all three options, if it's black you only have 1 (strait) and if it's white you have 2 (not strait)...
pktm
Posts: 57
Joined: 05 Aug 2006, 15:49

Re: Masyu - it's like pathfinding?

Post by pktm »

[quote="SinbadEV"]Looks like "Maze" solver Algorithm would probably work... just with the added rules. Another idea would be to calculate all the possible paths and see if any of them don't break any of the rules.

edit:
Okay, standard maze solver algorithm says you move to a new square you have 3 options, (any direction but where you came from) in this case if a square is blank you have all three options, if it's black you only have 1 (strait) and if it's white you have 2 (not strait)...[/quote]

But how to add the option, that you have to turn at least oncew if you cross a white pearl?
User avatar
SinbadEV
Posts: 6475
Joined: 02 May 2005, 03:56

Re: Masyu - it's like pathfinding?

Post by SinbadEV »

Ok, so, then with a standard maze solver you remove the option of Up Down, Left or Right based on where walls are, in this you remove them as you enter the square for the particular path...

so if you enter a n empty grid from the top you need to try left right and down, if you enter a black perl from the top you only need to check down, and if you enter a white perl from the top you only need to test left or right.

you continue the path until you reach an already entered suqare... then you check to see if the path has entered all the perls and abandon it if it hasn't.
User avatar
kiki
Posts: 859
Joined: 05 Nov 2007, 03:06

Re: Masyu - it's like pathfinding?

Post by kiki »

oop + backtracking
imbaczek
Posts: 3629
Joined: 22 Aug 2006, 16:19

Re: Masyu - it's like pathfinding?

Post by imbaczek »

this one is NP-complete (wikipedia even provides link to a proof.) IOW, no easy way to find a solution, maze path finding algorithms are useless here. smart backtracking is the only option.
User avatar
Error323
AI Developer
Posts: 237
Joined: 28 Nov 2006, 16:46

Re: Masyu - it's like pathfinding?

Post by Error323 »

Yes it's NP-Complete, that basically means that you have to make it compute all the possibilities, and check each for correctness, using perhaps Genetic Algorithms or something. This means only relatively small boards can be solved in a reasonable amount of time.
Post Reply

Return to “AI”