Ponder This Challenge - July 2024 - Tiling with balanced black and white tiles

This riddle was suggested by Evert van Dijken - thanks, Evert!

Consider square tiles made of $4\times 4$ squares that can be either black (0) or white (1), such that each tile has an equal number of black and white squares.

We call two tiles equivalent if one can be rotated and/or reflected in order to obtain the other. It is easy to see that a tile can have 1, 2, 4 or 8 equivalent tiles (including itself).

Your goal: Find a tiling of a 16\times 16 squares board (4 x 4 of such tiles, with 4 x 4 squares in each tile) such that:

1. In each row and column, there are no more than two consecutive squares of the same color.

2. The total number of pairs of adjacent same color squares is minimal. Remember to count both vertical and horizontal pairs.

3. All tiles included in the tiling must be non-equivalent

4. As stated earlier, each tile must have the same number of black and white squares. Give your solution by first writing the number of pairs from constraint 2, and then the $16\times 16$ grid of squares (no need to describe the individual $4\times 4$ tiles). e.g.

A bonus "*" will be given for solving the above problem, but for a $20\times 20$ squares board with the additional constraint that one can only use tiles which have exactly 4 equivalent ones as defined above.

Solution

• Click here to view the solution

  July 2024 Solution:

  This is a search problem with a very large search space, so solutions can impose further restrictions which guide the search towards an optimal solution, in the case one exists. Computing the number of adjacent values inside the tiles themselves gives an intrinstic "cost" to using a tile, even when its connection to its neighbrors is only "01" and "10". For example, the cost of

  0010 
  
  0101 
  
  1010 
  
  1101
  

  Is 4. Ordering all tiles by their cost and summing the costs yields a minimum of 66 and 184 for both problems. Luckily, both values are achievable. For one to obtain the 66, 184 solutions, two additional constraints are added to the problem:

  1. One must use only the small-cost tiles (e.g. tiles with a cost of 8 or 10 are discarded)
  2. Two adjacent tiles must not have a "00" or "11" connection. This makes the 66 problem solvable quickly using backtracking, while the 184 problems remains more challanging. A solution with value 66:

  1101001010010101 
  
  0010110101101011 
  
  1010101010010100 
  
  0101010101101001 
  
  1010101010010110 
  
  0110110101101001 
  
  1001001010101010 
  
  0101010101010101 
  
  1010101010101010 
  
  0101010101101001 
  
  1010101010010101 
  
  1010100101101010 
  
  0101011010010101 
  
  1010110101101010 
  
  0101001010110101 
  
  0011010101001010
  

  A solution with value 184:

  10101101011010010101 
  
  01010010101101101101 
  
  01010101010101010010 
  
  10101001001010101100 
  
  01010110110101010011 
  
  10010110100101010010 
  
  00101001001010101101 
  
  11010110110010101010 
  
  00101001001101010101 
  
  11010110110100110010 
  
  10101001011011001101 
  
  01101001001010101100 
  
  10010110110101010011 
  
  10101010101010101101 
  
  01010101010010010010 
  
  10010110100101101010 
  
  01101001011010010101 
  
  00110010101100110110 
  
  11001100110011001011 
  
  01101101010010010100
  

Solvers

• Lazar Ilic (2/7/2024 12:52 PM IDT)
• Michał Franczak (2/7/2024 9:31 PM IDT)
• Alex Fleischer (2/7/2024 10:33 PM IDT)
• King Pig (3/7/2024 1:06 AM IDT)
• *Yi Jiang (3/7/2024 3:01 AM IDT)
• *Bert Dobbelaere (3/7/2024 6:12 AM IDT)
• *Bertram Felgenhauer (3/7/2024 12:40 PM IDT)
• Yury Volvovskiy (3/7/2024 4:44 PM IDT)
• Jiri Spitalsky (4/7/2024 12:00 PM IDT)
• Loukas Sidiropoulos (4/7/2024 4:51 PM IDT)
• Joaquim Carrapa (5/7/2024 1:12 AM IDT)
• Gary M. Gerken (5/7/2024 5:07 AM IDT)
• *Yan-Wu He (5/7/2024 8:13 PM IDT)
• *Jared Kittleson (5/7/2024 8:14 PM IDT)
• *Vladimir Volevich (6/7/2024 1:22 AM IDT)
• *John Spurgeon (6/7/2024 9:22 PM IDT)
• *Sanandan Swaminathan (8/7/2024 8:36 AM IDT)
• *Daniel Chong Jyh Tar (8/7/2024 10:22 AM IDT)
• Alper Halbutogullari (8/7/2024 2:59 PM IDT)
• Guglielmo Sanchini (8/7/2024 7:17 PM IDT)
• *Daniel Bitin (9/7/2024 1:40 AM IDT)
• Lorenz Reichel (9/7/2024 8:16 PM IDT)
• *Lawrence Au (11/7/2024 6:56 PM IDT)
• Kipp Johnson (12/7/2024 4:47 PM IDT)
• Alain Michiels (12/7/2024 6:26 PM IDT)
• *Mark Pervovskiy (13/7/2024 1:43 AM IDT)
• Evert van Dijken (13/7/2024 8:35 AM IDT)
• *Hakan Summakoğlu (14/7/2024 1:20 AM IDT)
• *Ido Meisner (14/7/2024 11:34 PM IDT)
• Hugo Pfoertner (16/7/2024 6:14 PM IDT)
• *Adrian Neacsu (17/7/2024 12:09 AM IDT)
• *Nyles Heise (17/7/2024 7:13 AM IDT)
• *Latchezar Christov (17/7/2024 4:31 PM IDT)
• *Todd Will (17/7/2024 5:22 PM IDT)
• *David F.H. Dunkley (18/7/2024 3:35 PM IDT)
• *Dieter Beckerle (18/7/2024 6:58 PM IDT)
• Julian Ma (19/7/2024 6:32 PM IDT)
• *David Greer (20/7/2024 6:29 PM IDT)
• *Franciraldo Cavalcante (23/7/2024 12:18 AM IDT)
• *Martin Thorne (23/7/2024 7:37 AM IDT)
• Guillaume Escamocher (23/7/2024 2:59 PM IDT)
• *Andreas Stiller (24/7/2024 6:34 PM IDT)
• *Harald Bögeholz (24/7/2024 9:14 PM IDT)
• Tim Walters (24/7/2024 10:54 PM IDT)
• *Zoltan Haindrich (25/7/2024 8:55 PM IDT)
• Robin Guilliou (26/7/2024 11:33 AM IDT)
• Shouky Dan & Tamir Ganor (26/7/2024 12:29 PM IDT)
• Kang Jin Cho (27/7/2024 2:07 PM IDT)
• Paul Lupascu (27/7/2024 7:23 PM IDT)
• Marco Bellocchi (29/7/2024 12:44 AM IDT)
• Andreas Knüpfer (29/7/2024 11:17 PM IDT)
• Victor Chang (31/7/2024 5:16 AM IDT)
• *Oscar Volpatti (31/7/2024 7:32 AM IDT)
• Justin Snopek (31/7/2024 12:30 PM IDT)
• Kai Guttmann (31/7/2024 9:33 PM IDT)
• Evan Semet (1/8/2024 3:34 AM IDT)
• Blaine Hill (1/8/2024 3:56 AM IDT)
• Radu-Alexandru Todor (1/8/2024 3:33 PM IDT)
• *Motty Porat (2/8/2024 12:37 AM IDT)
• *Thomas Ilsche (2/8/2024 10:53 PM IDT)
• Reiner Martin (3/8/2024 4:20 PM IDT)
• Amos Guler (5/8/2024 8:38 PM IDT)