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.

• user40980: 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.
• user2908101: @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.
• user40980: 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)
• user2908101: @MichaelT Is it the DFS that makes it not a valid solution?
• Walter Tross: 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?

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.

• user40980: @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 )
• Walter Tross: 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.
• user40980: 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.
• Walter Tross: I think I understand what you mean, but I also think it should be somehow reversed. What you mean is that an area that can be flood-filled is not necessarily a valid path. E.g., starting points at (0,0) and (1,2), and invalid path at (0,1), (0,2) and (1,1)
• user40980: @WalterTross in the right solution, the 2s can be flood filled, but the line doesn't connect the puzzle 2s as endpoints. Thus, a simple flood fill doesn't identify the solution.

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.

• user2908101: 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!
• user40980: @user2908101 1d or 2d, it makes little difference since you can map one to the other.
• Walter Tross: @user2908101, a 1D array (ArrayList in Java) is as easy as a matrix, if you use x + width * y as the index for point (x,y). Regarding the second question, your algorithm was not very clear on the counting part, anyways I'll edit my answer.