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
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 CommentsShow comments
Problem Recent Solvers2