Recently, much of my time has been taken up by an addicting game on my phone, called Logic Dots, which inspired me to write this challenge. It's easier to explain the rules if I show you the game display, so here is a screenshot of an unsolved, and solved puzzle:
Now here, there are three main things to notice.
- The game board (the 4x4 grid of squares in the center)
- The required shapes (the linked dots in the second bar from the top, under the score and menu, etc.), which are all lines, or
aby 1 rectangles
- The numbers over the rows and columns, which denotes how many dots need to be in the column, for a solution
The objective of the game is to fit the required shapes into the grid. You can rotate the shapes, but they cannot go in diagonally.
In the solution, notice that all shapes are created exactly once (because they are only in the required shapes once), and in this case they are all horizontal but they can also be vertical. The pink filled in squares denote squares not used.
Here is a bigger, and slightly more complicated grid:
Notice that in the unsolved puzzle, there are already a few squares filled i.n The greyed out squares signify blocked squares that you CANNOT place a dot on. The dots with tails tell you that a dot is in that spot, and it links to at least one more dot in the direction of the tail, but not in any other direction (including the opposite direction).
For the rest of this post, I will refer to the board using the following symbols:
- <, >, ^, v - Signifies a pre-placed dot with a tail extending in the direction of the point
- * - Signifies a dot. If given on an unsolved grid (input), it is an individual shape. If in output, then it is connected to the dots around it.
- # - Signifies a blocked grid square (where you cannot place a dot)
- -, | (hyphen and bar) - Signify a dot with a right and left tail, and a dot with an up and down tail respectively
- ** (space character) -** Signifies an empty space
Using these symbols, the latter example case (unsolved) can be represented as follows:
< # ^ #
And the solution can be represented as:
*< * * * * * * * *#* ^ # *
Note that no two shapes can touch horizontally, vertically or diagonally, so the following case is not valid:
*** ** **
Your challenge is to solve any logic dots puzzle, from 4x4 to 9x9 inclusive. You will receive four lines of input, then the game board. The lines will be as follows:
- 1st line, Shapes - The shapes to find, each given in the form
3x2for two shapes of length three) and separated by a space. Example line:
3x1 2x1 1x1
- 2nd line, Columns - A space separated list of the required dot count for each column. Example line:
1 1 2 2
- 3rd line, Rows- A space separated list of the required dot count for each row. Example line:
3 0 3 0
- 4th line, Board size - A single integer, the board size,
The board is then given, and is
B lines of input representing the board using the notation mentioned above. For example, the complete input for the latter example case is as follows:
4x1 3x1 2x2 1x2 1 4 0 3 0 5 4 1 1 2 3 2 6 < # ^ #
Your program will then output the solved board, in the same notation. The matching output for the above input is as follows:
** * * * * * * * *#* * # *
Note that a game board can have multiple solutions. In this case, just output one valid solution. Also, your program must output a correct solution within 10 seconds on a reasonable desktop computer for a complicated 10x10 grid.
This is code golf, so least bytes wins.
3x2 1x4 2 2 3 1 2 4 0 3 0 3 5 # # *
*** * ***# # * * *
3x1 1x6 2 0 4 0 3 3 1 2 1 2 5 * #
* * * * * * * # * *
5x1 4x1 2x1 1x2 1 2 3 3 2 2 0 5 0 4 0 4 6 # - # <
# ***** **** # * ** *