Masyu - it's like pathfinding?

[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

[AF]

First, what's masyu?

[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?

[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]

[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?

[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.

[kiki]

oop + backtracking

[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.

[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.