Transversal achievement game on a square grid

Importance: Medium ✭✭
Author(s): Erickson, Martin
Subject: Combinatorics
Keywords: game
Recomm. for undergrads: yes
Posted by: Martin Erickson
on: June 29th, 2010
Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times  n $ grid. The first player (if any) to occupy a set of $ n $ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Bibliography



* indicates original appearance(s) of problem.

Are there a simple solution?

I suspect, there are no simple answer and it can be solved only by heavy calculations, that is essentally there is no solution to this problem.

history and application

i'm not sure but i think to solve this problem, i was wondering if any body gives me some information about the history and application of this problem

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.