You are implementing a board game where you are given a size N x M for the board, where N is the number of rows and M is the number of columns.
In this board game you are playing with some fixed size lego pieces, where each player places 1 piece on the board every turn until no more piece can fit onto the board, and the last player to move wins.

The problem is to implement a method for making a move on this board, placing a piece wherever there is space available, and returns a boolean indicating whether or not the player that has just made the move has won.

Follow up question: The method should also find if there is any move that can be made that will make it so that the next player is unable to place a piece anywhere on the board in their next turn, and make that move.

You choose how to represent the board and lego pieces in the problem, during my interview I chose to use a 2D array of booleans for the board, where each boolean indicates whether that spot on the board is occupied, and for the lego piece I asked the interviewer if I could assume the lego piece would be rectangular, which he agreed to.

Simple example (small board for demonstration purposes, board length = 2 x 3, lego piece length = 1 x 2):
Empty Board:
O O O
O O O
Board after player 1 makes move, placing lego piece at top right corner:
O X X
O O O
At this point, player 2 can make a move that will prevent player 1 from placing another piece:
O X X
X X O
and so the method should be able to find and make that winning move, rather than an alternative move that would
miss an opportunity for a win:
O X X
O X X

I devised something like the following outline for my solution during the interview based on the requirements:

Piece = collections.namedTuple('Piece', ['x', 'y'])
class BoardGame:
	def __init__(self, n, m, x_length, y_length):
		self.board = [[False] * m for _ in range(n)]
		self.pieceRows = x_length
		self.pieceCols = y_length
		
	# returns a boolean indicating whether a winning move was made
	def makeMove(self):
		...

In my code x and y are parameters for the size of the lego piece to be used in the game.

My solution used a brute force approach checking every possible spot in the board to make a move and check if this would be a winning move, but could not come up with an efficient implementation, even now after the interview. Can anyone come up with an efficient approach that would solve the problem more effectively than a brute force approach?