Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

For the moment I'm strictly speaking in Pseudocode. I'd only like to see if i'm on the right track. The game I'm talking about is similar to a application called FLOW.
In this game, you're given a nxn board(Always a square) and need to fill out each slot in the board. Similarly, when a board game is initialized, it will have objects like the set up below...

Board - 1 2 3 1
        0 0 0 0
        0 2 3 0
        0 0 0 0

In this example - the objects are 1 2 and 3.

A solution would be as follows...

Board - 1 2 3 1
        1 2 3 1
        1 2 3 1 
        1 1 1 1

The whole purpose is to fill out the board game by connecting the starting object to the end object. What I have in mind is the following...

CheckSolution(1d representation of the boards state, int totalcolors) {

  // I would loop through the colors, a 0 is not a color - empty. 
  // If the board has a 0 in the array, I would automatically return a false solution. 
  // Then, I would call DepthFirstSearch on the color. 
       // -- I would set a counter on this to count the # of colors, if this isn't equal to the total # of that particular color, I would return false.   
  // Else, the solution is valid.
}

Does this sound reasonable? Or is the better way to implement a solution checker.

share|improve this question
    
Its it always a single path for the connections? Or is it allowed to "flow" from a spot? The puzzle 1 . . . 2 3 . . . 3 . . . . 2 1 appears to have two solutions with a flood fill approach but likely only has one valid solution. –  MichaelT Mar 17 at 18:35
    
@MichaelT There can be multiple path connections. For instance, if instead of only having 2 1's, I put down 3 1's. Then it may form a T shape connection. The goal is to connect all the initialized 1's,2's,3's while filling up the board. –  user2908101 Mar 17 at 18:37
    
However, based on html5gamer.net/game/flow "Simple, but fun HTML5 puzzle game. Connect the dots by drawing a line with the mouse between the two dots with matching colors." which means that for my previous puzzle 1 1 1 1 2 3 1 1 2 3 1 1 2 2 2 1 is not a valid solution which would be accepted as such by your approach. (the proper solution is 1 1 1 1 2 3 3 1 2 3 3 1 2 2 2 1) –  MichaelT Mar 17 at 18:43
    
@MichaelT Is it the DFS that makes it not a valid solution? –  user2908101 Mar 17 at 18:44
    
If two starting points of the same color are at (0,0) and (1,2), is coloring (0,1), (0,2) and (1,1) a valid way of connecting them or not, in your game? –  Walter Tross Mar 17 at 20:18
add comment

2 Answers 2

up vote 1 down vote accepted

Based on flow, the rules read:

Simple, but fun HTML5 puzzle game. Connect the dots by drawing a line with the mouse between the two dots with matching colors. Lines can not cross and you must fill in every square to completely solve the puzzle. Game features fun audio and 150 different levels. Not to difficulty to beat, but fun to play through once or twice.

The flood fill approach does not take into consideration that there is a single line that needs to connect the spots and may accept invalid solutions.

Consider the puzzle:

1 . . .
2 3 . .
. 3 . .
. . 2 1

The flood fill approach will accept all of:

1 1 1 1    1 1 1 1    1 1 1 1
2 3 1 1    2 3 3 1    2 3 2 1
2 3 1 1    2 3 3 1    2 3 2 1
2 2 2 1    2 2 2 1    2 2 2 1

as valid. However, only the middle is a valid solution to the puzzle because no line was drawn to connect the 3s through other cells in the other two. Furthermore, the 2s didn't end on the proper spot on the one in the right.

As such, your solution finder is not correct. It needs the initial state of the puzzle, the solution, and ideally the path the line was drawn through in order to determine if a given solution is valid or not.

share|improve this answer
    
+1 for spotting the original puzzle ;-) –  Walter Tross Mar 17 at 18:59
    
@WalterTross I'm quite fond of chiark.greenend.org.uk/~sgtatham/puzzles and flow is closely related to those puzzles (also glance at the Nikoli puzzles en.wikipedia.org/wiki/Nikoli ) –  MichaelT Mar 17 at 19:03
    
I leave the details to you, but a flood fill from one of the two starting points of each color, ending at the other point (considered as a blocker), could be a way to check the solution. –  Walter Tross Mar 17 at 19:03
    
Thanks for those links :-) –  Walter Tross Mar 17 at 19:05
    
I would need to work on generating the proper starting puzzle, but it would be possible to construct one where there is only one path but multiple flood fills because a path wouldn't be able to touch all the proper spots in a given solution. –  MichaelT Mar 17 at 19:07
show 2 more comments

Your algorithm is essentially OK (although you could have expressed it much better...), if you mark all visited cells (e.g., by setting them to 0).

You can start the search (equivalent to a flood fill) while scanning the matrix, no need to make two passes.

I don't think that there is a way to avoid the "flood fill".

EDIT

Regarding "counting", you will rather have to check that each color is flood-filled only once. So, you would be better off allocating an array of booleans that tells you whether a color has been "filled" or not, initialized to false. So, each time you find a new start for a fill, you first check whether that color has not been seen already - if it has, it's not a solution. The only thing worthwhile counting is the number of fills. Instead of checking whether the array is "all trues" at the end, you can check that you have done totalcolors fills.

share|improve this answer
    
In the puzzle, the '2' and '3' are both forced moves - there are many improvements over the brute force that are possible. –  MichaelT Mar 17 at 18:24
1  
@MichaelT, the OP is looking for a solution checker, not a solution finder ;-) –  Walter Tross Mar 17 at 18:26
    
I missed that in the first pass. Thank you for alerting me to that clarification. –  MichaelT Mar 17 at 18:30
    
Would the 1D arraylist of the current board state be the easiest way to check the solution? Also, when I said I would have counter to check the # of color nodes = # of color nodes in DFS, would I need a static final int that resets to 0 whenever I check the next color? Thanks! –  user2908101 Mar 17 at 18:30
    
@user2908101 1d or 2d, it makes little difference since you can map one to the other. –  MichaelT Mar 17 at 18:38
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.