Solution Checker Algorithm for a Game

Question

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.

Answer 1

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.

Answer 2

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.