Strata is a puzzle game in which you lay coloured ribbons across a grid. When two ribbons intersect, the cell under the intersection takes on the colour of the uppermost ribbon. Here's an example puzzle, ready to solve:
After laying the first ribbon, no cells have been assigned a colour yet:
Laying a perpendicular ribbon colours a cell in:
Notice that, if the uppermost ribbon isn't the correct colour, the cell isn't filled in to let you know you've got it wrong. Also, if a cell doesn't have a target colour, it doesn't matter what colour ends up on top of it; the cell remains colourless when the second ribbon is laid across it:
And a completed solution:
The object of this challenge is to write a program or function that will provide a step-by-step solution for a Strata puzzle. Here is the layout for the example puzzle provided above, rotated 45 degrees clockwise and with letters a-c substituted for the cell colours:
For ease of the following discussion, I've labelled the columns 1-3 and the rows A-C.
The notation for the output commands will be a single character representing the row or column to lay a ribbon upon, and then another character representing the ribbon type. For example, the command
Cb represents laying a ribbon of type
b on the rightmost column of this layout.
One of a number of valid solutions for this puzzle is
3a, Cc, 1a, 2a, Bb, Aa. Another is
Ca, 3c, 2a, 1a, Aa, Bb.
Input will consist of the layout for a Strata puzzle. The puzzle will always form a square, with side length of 2-9 inclusive. Each character in the input will be one of the following:
- a lower case letter, representing the ribbon type which should be laid on top of the intersection in the completed puzzle
- a space, representing a cell where the type of the uppermost ribbon does not matter
Note that a puzzle can use between 2-26 (inclusive) ribbon types, and that the types will not necessarily a the first nth letters of the alphabet. Your program/function won't be provided these separately, and should be acquired from the puzzle layout if required.
Input may be provided in any reasonable form that is convenient for your chosen language. For example, you may accept input as single newline-delimited string, as an array or list of strings, etc. Please provide a description of how your submission will expect its input for testing purposes.
Similarly, input can be provided in any appropriate manner. For example, as command line arguments, function arguments, as a stream via STDIN, etc. You should only specify this if it is not immediately obvious.
Output should consist of a valid solution for the given puzzle. It should consist of an ordered series of instructions, each consisting of two characters:
- The first character should be a number or upper case letter; a number represents a row, starting with 1 for the uppermost row, a letter represents a column, starting with A for the leftmost column (e.g., in the puzzle above, the instruction
4a would be invalid as there are only 3 rows)
- The second character should be the type of the ribbon to lay on the grid; this should be a lower case character, corresponding to one of the types provided on the input (e.g., in the example puzzle above, the instruction
Az would be invalid as
z is not one of the types used in the grid)
Your program/function can provide the output pairs in any reasonable form, and on any reasonable medium. For example, as a series of comma, space, or newline separated values on STDOUT, as an array for return from a function, written to a file with specified name, etc.
- A puzzle is only considered complete when all rows and columns have had a single ribbon laid across them, and no row or column can have more than one ribbon laid on it. This means that your output will consist of
2 * (side length) instructions.
- This is code golf, so the winner is the shortest solution in bytes. In the event of a tie, the earliest submission wins.
3a, Cc, 1a, 2a, Bb, Aa
This is my first PPCG question, so I tried to make sure every angle was covered. I think I may have gone overboard though, do you think I should get rid of any sections?
As this isn't a puzzle of my own invention, would there be any problems with posting in-game screenshots?
This puzzle is actually pretty easy to work out if you employ a backtracking technique - find a row or column consisting of a single colour, ignoring spaces and cells which have been crossed once. Add this instruction pair to the end of the prototype solution, then mark all the cells as having been crossed once (or twice). Repeat this
2 * (side length) times and you'll have a solution, if there is one to be found.
I want to discourage brute force solutions, so I'm going to come up with a 9x9 test case with more than 10 different types. My stats skills aren't up to much, but I think that, for a puzzle with side length
n and number of ribbon types
t, the total number of possible ways to lay ribbons on the grid is:
(2n)! * (2n)^t
Could anyone double check that for me? Also, if I were to put in a 9x9, 10-type test case, would that be big enough to rule out a brute force solution? Should I impose some form of computation time limit, and if so, how long on what sort of machine?