Problem 56548. IQpuzzler Challenge #1: Find all possible solutions with 2 pieces already on the board and fixed orientation of all other pieces
IQpuzzler is a one player board game. The 2D version provides a rectangular board with 5-by-11 spaces and 12 colored pieces (consisting of 3 to 5 elements) which have to be arranged on the board so that all spaces are filled (see complete set of pieces and example solution below). More than 1 million solutions exist if the pieces can be flipped and rotated.
In this challenge, you are given a board with some of the pieces already in place, and the other pieces in their required orientation (different from the picture below), so you don't need to worry about flipping or rotating them. Your task is to find all possible solutions within Cody time.
The board is a 5-by-11 matrix, where zeros represent empty spaces and values 1 to 12 represent the different pieces on the board.
The remaining pieces are provided as cell array with P cells. Each cell contains an N-by-M matrix with zeros and one unique value (the piece number) representing the positions of the 3 to 5 elements that define each piece.
For example, the dark blue piece (piece number 2 by definition) in the picture below would be represented as
[ 2 2
2 0
2 0 ]
Your solution set needs to be provided as a 3D array with 5 rows, 11 columns and S layers, where S is the number of possible solutions with the provided inputs. Each solution needs to have the same non zero elements as the input board (the pieces which are already in place), and the remaining pieces completely distributed on the board, using the provided shapes and numbers from the input cell array.
The order of your solution set along the 3rd dimension does not matter, as long as it provides all valid solutions without repetitions.
Please provide your entire search algorithm, not just hard coded solutions.
Hint: Brute force search might take too much time. Maybe some functions from the preparation phase can speed things up. You can find a C++ implementation for the entire puzzle on https://github.com/deverw/IQpuzzler
Solution Stats
Problem Comments
-
1 Comment
Richard Zapor
on 3 Aug 2023
Robust Breadth recursive solves in 26ms. More lines but 0.5% of time.
Solution Comments
Show commentsProblem Recent Solvers2
Suggested Problems
-
Return elements unique to either input
761 Solvers
-
Change a specific color in an image
71 Solvers
-
How many monitors are connected ?
151 Solvers
-
The Answer to Life, the Universe, and Everything
519 Solvers
-
Given a matrix, swap the 2nd & 3rd columns
1039 Solvers
More from this Author5
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!