Tetris Tangrams

Question

Introduction

Tangrams are a classic puzzle involving arranging/fitting blocks into various shapes. From the Chinese 七巧板 - literally meaning "seven boards of skill". Let's take this idea and use the seven Tetrominos pieces to fill a grid.

Challenge

Write a function or program that takes an array of grid coordinates as input, and outputs a completed 10 by 20 grid filled with Tetris pieces except in the specified coordinates.

Optimize your score by attempting to keep the distribution of pieces uniform.

Criteria

Use this pastebin of coordinates to accomplish your task. There are five sets of coordinates. Feel free to modify the format in which the coordinates are written, but not the values.

Data set #2 cannot be solved - in this case, simply output the grid with input cells filled in (i.e., X's where the holes are).

Input

Grid coordinates represent 'holes' in the grid. These are cells which cannot contain any part of a Tetromino.

Grid coordinates:

(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)

• Use your programming language's array style of choice to input the coordinates.

• Represent holes in the grid with an X or other printable ASCII.

Output

Using a standard Tetris grid size of 10 cells wide by 20 cells tall, print a solution grid if and only if the grid can be filled completely and perfectly using Tetromino pieces.

Pieces constructed with letters I, O, L, J, T, Z, S as follows:

I          
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

---

Example

Output solution example with no input coordinates:

ZZIIIILLLI
JZZTTTLLLI
JJJSTLOOLI
SZZSSLOOLI
SSZZSLLJJI
TSOOSLLJII
TTOOSSLJII
TZOOSSLZII
ZZOOSSZZII
ZJJJJSZLLI
TTTJJOOILI
ITZJJOOILI
IZZTTTLIII
IZOOTZLIII
IJOOZZLLII
LJJJZSSTII
LLLTSSTTTI
LLLTTSSZJI
OOLTSSZZJI
OOIIIIZJJI

With distribution as follows:

I          
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

11   6     8     6      6     7      6

---

Notes

Coordinates represent a single X and Y position on the grid. The grid is 0 based, meaning coordinate (0,0) should either be the top left or the bottom left cell, author's choice.

Bricks can:

• be selected at author's discretion.
• be rotated as author sees fit.
• be placed on the grid anywhere at author's discretion (aka: no Tetris gravity)

Bricks cannot:

• be placed outside the bounds of the grid.
• overlap an existing brick or hole in the grid.
• be a non-standard Tetris tetromino piece.

---

Scoring

Your score is in the format:

( 1000 - [bytes in code] ) * ( M / 10 + 1 )

Where M is a multiplier for the distribution of pieces used in your solution sets.

Highest score by the Ides of March wins.

To calculate M, add the lowest individual tetromino distribution value for each set and then take the average rounded down to calculate M.

For example:

Set 1: 5
Set 2: 4
Set 3: 5
Set 4: 6
Set 5: 3

6 + 4 + 5 + 4 + 4 = 21 / 5 = 4.6

So you would use 4 as your M value.

Note: If a set has no solution, do not factor that set into calculating M, since it would have no tetromino distribution.

Answer 1

Python 3, 819 bytes, M=0, Score=181

This is a brute force DFS program. It builds a numpy array, and inserts all the inputted holes. It then takes the leftmost unfilled tile on the highest row that has one, and places a tetromino. Recursively, we now do it again - when we can't either we found a solution, or we backtrack and try another piece at the first opportunity.

This has an M of 0, since it tries to use pieces in a determined order, and almost always finds a solution without the last one in the list. I tried using a randomly ordered list each cycle to make a more even distribution, but I only got an M of 2, which wasn't worth the bytes required to import random.shuffle.

I can't comment the below code, since in my golfing I've long forgotten what much of it does. The general idea:

• Import numpy and itertools product, with 1-letter names
• Rename some builtins to be 1-letter functions, and define a lambda to save bytes
• Build the array of possible tetrominos as numpy nd-arrays, all rotations included
• In the recursive function:
  • Get the position of the unfilled tile desired, and cycle through the pieces list
  • For each piece, cycle through translations of it (moving it up and down)
  • If something doesn't work (piece goes off the board, hits another piece, hits a hole, etc.), try the next translation or the next entire piece
  • If it works, great. Try it, then recursively call the function.
  • If that path didn't work, it will return 'a', so we just try again. If it did work, it returns the board, and we pass it up the line.
• Finally, the program. We build the 10x20 board as a numpy array of 1's.
• The input is of the form (x1, y1);(x2,y2);... We put a 9 for each hole in it, then get the result of running the function on it.
• The print statement then displays either the successful result or the empty, original board line by line, substituting the appropriate letters or symbols for the numbers.

import numpy as n
from itertools import product as e
m,s=range,len
p=[n.rot90(a,k)for a,r in[([[2,2]]*2,1),([[3]*3,[1,3,1]],4),([[0]*4],2),([[1,1,6],[6]*3],4),([[7,1,1],[7]*3],4),([[4,4,1],[1,4,4]],2),([[1,5,5],[5,5,1]],2)]for k in m(r)]
o=lambda a:e(m(s(a)),m(s(a[0])))
def t(l,d=0):
	g=list(zip(*n.where(l==1)))[0]
	for a in p:
		for u,v in o(a):
			w,x=l.copy(),0
			for r,c in o(a):
				if a[r,c]!=1:
					i,j=g[0]+r-u,g[1]+c-v
					if any([i<0,i>19,j<0,j>9])or l[i,j]!=1:
						x=1
						break
					w[i,j]=a[r,c]
			if x==0:
				if len(w[w==1]):
					f=t(w,d+1)
					if type(f)==str:continue
					return f
				return w
	return'a'
b=n.ones((20,10))
b[list(zip(*[eval(k)[::-1]for k in input().split(';')]))]=9
a=t(b)
for r in(a,b)[type(a)==str]:
	print(''.join(map(dict(zip([0,2,3,4,5,6,7,9,1],'IOTZSLJX-')).get,r)))

Try it online!

Sample test:

In: (1,1);(8,1);(4,4);(5,8);(4,11);(5,15);(1,18);(8,18)
Out: 
IIIIOOOOLL
TXOOOOOOXL
TTOOOOOOTL
TOOIOOOOTT
TOOIXOOTTI
TTTITOOTTI
TTTITTTTII
OOTTTTTTII
OOTTTXOOII
TTTTOOOOII
TTTTOOOOII
TTTTXTOOII
ITTTTTTTII
ITTTTTTTII
IITTTLLTTI
IITOOXLTTI
IITOOTLTTI
IITTLTTTTI
IXTLLTJTXI
ILLLLLJJJI