Return to Answer

Morpion Solitaire (this lists several variants - we're talking about 5T here) is an interesting, unsolved "single-player game" (more like a mathematical puzzle). It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

Morpion Solitaire is an interesting, unsolved "single-player game". (The linked site lists several variants - we're talking about 5T here.) It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (+), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (.), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

+ + + + + + + + + + + +
                       
+ + + + o-o-o-o-# + + +
        |/     /       
+ + + + o + + o + + + +
       /|    /         
+ + + # o + # o + + + +
     /  |  /           
+ o-o-o-o-# + o o o o +
   /    |/             
+ o + + # + + + + + o +
        |              
+ o + + # + + + + + o +
        |              
+ o o o o + + o o o o +
        |              
+ + + + o + + o + + + +
        |              
+ + + + o + + o + + + +
                       
+ + + + o o o o + + + +
                       
+ + + + + + + + + + + +

. . . . . . . . . . . .

. . . . o-o-o-o-# . . .
        |/     /       
. . . . o . . o . . . .
       /|    /         
. . . # o . # o . . . .
     /  |  /           
. o-o-o-o-# . o o o o .
   /    |/             
. o . . # . . . . . o .
        |              
. o . . # . . . . . o .
        |              
. o o o o . . o o o o .
        |              
. . . . o . . o . . . .
        |              
. . . . o . . o . . . .

. . . . o o o o . . . .

. . . . . . . . . . . .