A simple algorithm, which I have just now implemented, is the following:
- Define the 19 pieces
I defined each piece as beginning with the coordinates of the topmost and leftmost part of the piece and then giving the relative coordinates of the 3 remaining "parts" of that piece in an array. An "L" piece, lying down with its "head" to the right, would then have coordinates (2,0), (2,1), (1,1), (0,1).
- Given a square size N and given K Tetris pieces, find all possible positions of each Tetris piece in the square
For each piece, find the coordinates at which its topmost and leftmost part could be located. For the above piece, in a square of size 4, the possible positions would be (2,0), (3,0), (2,1), (3,1), (2,2), (3,2). This assumes the square starts at (0,0).
- Make a recursive function which attempts to place piece k at the first possible position where it doesn't overlap an existing piece.
At each moment, the function must know which positions in the square have already been taken.
If piece k can be placed, place it and attempt to place the next piece. If piece k cannot be placed, return and see if the previous piece can be moved to its next position.
If all K pieces have been placed, you are done. Otherwise (i.e. if the first piece has no other possible positions left to move to), no solution is possible.
The above algorithm is very simple but it does manage to solve N=7 cases within 5 seconds. When N=8, it can take over an hour. And the algorithm is done in Visual Basic for Excel, so other implementations could be much faster.
Below are some examples of its solutions:
- N=7, K=12:
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/WGP80.png)
- N=5, K=6:
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/AwQA1.png)
If you are interested, I can post the code.
EDIT
Below is my attempt at pasting my code. I would appreciate any help in making it look better.
Dim Tetra(19, 6) As Integer
Dim N As Integer
Dim Pieces As Integer
Dim Piece(19) As Integer
Dim PosOfPiece(19, 49, 2) As Integer
Dim Positions(19) As Integer
Dim Grid1() As Boolean, Found As Boolean
Dim PiecePositioned(19) As Integer
Dim GridPosTrue(4, 2) As Integer
Sub Macro1()
'
' Macro1 Macro
'
' Keyboard Shortcut: Ctrl+a
'
Init
Init2
End Sub
Sub Init()
Tetra(1, 1) = 0: Tetra(1, 2) = 1: Tetra(1, 3) = 0: Tetra(1, 4) = 2: Tetra(1, 5) = 0: Tetra(1, 6) = 3
Tetra(2, 1) = 1: Tetra(2, 2) = 0: Tetra(2, 3) = 2: Tetra(2, 4) = 0: Tetra(2, 5) = 3: Tetra(2, 6) = 0
Tetra(3, 1) = 1: Tetra(3, 2) = 0: Tetra(3, 3) = 1: Tetra(3, 4) = 1: Tetra(3, 5) = 2: Tetra(3, 6) = 1
Tetra(4, 1) = 0: Tetra(4, 2) = 1: Tetra(4, 3) = -1: Tetra(4, 4) = 1: Tetra(4, 5) = -1: Tetra(4, 6) = 2
Tetra(5, 1) = 1: Tetra(5, 2) = 0: Tetra(5, 3) = 0: Tetra(5, 4) = 1: Tetra(5, 5) = -1: Tetra(5, 6) = 1
Tetra(6, 1) = 0: Tetra(6, 2) = 1: Tetra(6, 3) = 1: Tetra(6, 4) = 1: Tetra(6, 5) = 1: Tetra(6, 6) = 2
Tetra(7, 1) = 1: Tetra(7, 2) = 0: Tetra(7, 3) = 1: Tetra(7, 4) = 1: Tetra(7, 5) = 0: Tetra(7, 6) = 1
Tetra(8, 1) = 0: Tetra(8, 2) = 1: Tetra(8, 3) = 1: Tetra(8, 4) = 1: Tetra(8, 5) = 0: Tetra(8, 6) = 2
Tetra(9, 1) = 0: Tetra(9, 2) = 1: Tetra(9, 3) = 1: Tetra(9, 4) = 1: Tetra(9, 5) = -1: Tetra(9, 6) = 1
Tetra(10, 1) = 0: Tetra(10, 2) = 1: Tetra(10, 3) = 0: Tetra(10, 4) = 2: Tetra(10, 5) = -1: Tetra(10, 6) = 1
Tetra(11, 1) = 1: Tetra(11, 2) = 0: Tetra(11, 3) = 2: Tetra(11, 4) = 0: Tetra(11, 5) = 1: Tetra(11, 6) = 1
Tetra(12, 1) = 0: Tetra(12, 2) = 1: Tetra(12, 3) = 0: Tetra(12, 4) = 2: Tetra(12, 5) = 1: Tetra(12, 6) = 2
Tetra(13, 1) = 0: Tetra(13, 2) = 1: Tetra(13, 3) = -1: Tetra(13, 4) = 1: Tetra(13, 5) = -2: Tetra(13, 6) = 1
Tetra(14, 1) = 1: Tetra(14, 2) = 0: Tetra(14, 3) = 1: Tetra(14, 4) = 1: Tetra(14, 5) = 1: Tetra(14, 6) = 2
Tetra(15, 1) = 0: Tetra(15, 2) = 1: Tetra(15, 3) = 1: Tetra(15, 4) = 0: Tetra(15, 5) = 2: Tetra(15, 6) = 0
Tetra(16, 1) = 0: Tetra(16, 2) = 1: Tetra(16, 3) = 0: Tetra(16, 4) = 2: Tetra(16, 5) = -1: Tetra(16, 6) = 2
Tetra(17, 1) = 0: Tetra(17, 2) = 1: Tetra(17, 3) = 1: Tetra(17, 4) = 1: Tetra(17, 5) = 2: Tetra(17, 6) = 1
Tetra(18, 1) = 1: Tetra(18, 2) = 0: Tetra(18, 3) = 0: Tetra(18, 4) = 1: Tetra(18, 5) = 0: Tetra(18, 6) = 2
Tetra(19, 1) = 1: Tetra(19, 2) = 0: Tetra(19, 3) = 2: Tetra(19, 4) = 0: Tetra(19, 5) = 2: Tetra(19, 6) = 1
End Sub
Sub Init2()
Dim i As Integer
N = Cells(6, 2).Value
Pieces = Cells(7, 2).Value
For i = 1 To Pieces
Piece(i) = Cells(7 + i, 2)
Next i
AllocatePositions
ReDim Grid1(N, N)
Found = False
PlacePiece 1, Grid1, Found
If Not Found Then
MsgBox "No solution found"
End If
End Sub
Sub AllocatePositions()
Dim p As Integer, W As Integer, H As Integer, StartX As Integer, NumX As Integer, NumY As Integer
Dim pos As Integer, X As Integer, Y As Integer
For p = 1 To Pieces
Select Case Piece(p)
Case 1
W = 1: H = 4: StartX = 0
Case 2
W = 4: H = 1: StartX = 0
Case 3
W = 3: H = 2: StartX = 0
Case 4
W = 2: H = 3: StartX = 1
Case 5
W = 3: H = 2: StartX = 1
Case 6
W = 2: H = 3: StartX = 0
Case 7
W = 2: H = 2: StartX = 0
Case 8
W = 2: H = 3: StartX = 0
Case 9
W = 3: H = 2: StartX = 1
Case 10
W = 2: H = 3: StartX = 1
Case 11
W = 3: H = 2: StartX = 0
Case 12
W = 2: H = 3: StartX = 0
Case 13
W = 3: H = 2: StartX = 2
Case 14
W = 2: H = 3: StartX = 0
Case 15
W = 3: H = 2: StartX = 0
Case 16
W = 2: H = 3: StartX = 1
Case 17
W = 3: H = 2: StartX = 0
Case 18
W = 2: H = 3: StartX = 0
Case 19
W = 3: H = 2: StartX = 0
End Select
NumX = N - W + 1: NumY = N - H + 1
pos = 1
For Y = 0 To NumY - 1
For X = 0 To NumX - 1
PosOfPiece(p, pos, 1) = StartX + X
PosOfPiece(p, pos, 2) = Y
pos = pos + 1
Next X
Next Y
Positions(p) = pos - 1
Next p
End Sub
Sub PlacePiece(ByVal pp As Integer, Grid() As Boolean, SolutionFound As Boolean)
Dim Grid2() As Boolean
Dim Fail As Boolean
Dim pos As Integer, StartX As Integer, StartY As Integer, BoxNo As Integer, i As Integer
pos = 1
' Can piece pp be placed in position Pos?
Do While Not SolutionFound And pos <= Positions(pp)
StartX = PosOfPiece(pp, pos, 1): StartY = PosOfPiece(pp, pos, 2)
If Grid(StartX, StartY) Then
GoTo End1
Else
GridPosTrue(1, 1) = StartX: GridPosTrue(1, 2) = StartY
BoxNo = 0
Fail = False
Do While Not Fail And BoxNo <= 2
GridPosTrue(BoxNo + 2, 1) = StartX + Tetra(Piece(pp), 2 * BoxNo + 1): GridPosTrue(BoxNo + 2, 2) = StartY + Tetra(Piece(pp), 2 * BoxNo + 2)
If Not Grid(StartX + Tetra(Piece(pp), 2 * BoxNo + 1), StartY + Tetra(Piece(pp), 2 * BoxNo + 2)) Then
BoxNo = BoxNo + 1
Else
Fail = True
End If
Loop
If Fail Then
GoTo End1
Else
PiecePositioned(pp) = pos
Grid2 = Grid
'Update Grid2
For i = 1 To 4
Grid2(GridPosTrue(i, 1), GridPosTrue(i, 2)) = True
Next i
If pp < Pieces Then
PlacePiece pp + 1, Grid2(), SolutionFound
Else
SolutionFound = True
'MsgBox "Success!"
For i = 1 To Pieces
'MsgBox "Piece " & Piece(i) & " at (" & PosOfPiece(i, PiecePositioned(i), 1) & ", " & PosOfPiece(i, PiecePositioned(i), 2) & ")"
DrawPiece i, PiecePositioned(i), 2 + i
Next i
End If
End If
End If
End1:
pos = pos + 1
Loop
End Sub
Sub DrawPiece(p As Integer, pos As Integer, C_Index As Integer)
Dim i As Integer, StartX As Integer, StartY As Integer
StartX = 30: StartY = 10
Cells(StartY + PosOfPiece(p, pos, 2), StartX + PosOfPiece(p, pos, 1)).Interior.ColorIndex = C_Index
For i = 0 To 2
Cells(StartY + PosOfPiece(p, pos, 2) + Tetra(Piece(p), 2 * i + 2), StartX + PosOfPiece(p, pos, 1) + Tetra(Piece(p), 2 * i + 1)).Interior.ColorIndex = C_Index
Next i
End Sub