Main page Problems Volumes Ranking Mess Wiki Help News

Tic-Tac-Toe

Volumes:   Game Logic

Who solved this?

Emulation of console-based implementation of Tic-Tac-Toe

At this time we are not programming computer opponent for the game of Crosses and Noughts, but an important part for such an algorith - the checking function, which can tell whether the game is ended and won by one or another side.

The game is played on the square field 3 x 3. Let us suppose that the cells are numerated in the following way:

 1 | 2 | 3
---+---+---
 4 | 5 | 6
---+---+---
 7 | 8 | 9

Two players put their marks (X for first and O for second) in turns into any of free cells remaining. One who completes the straight line of three marks (three X-s or three O-s) immediately wins. Lines could be filled either in rows or columns or one of two diagonals (8 lines possible in total). For example suppose the following moves were performed:

 X   O
-------
 7
     5
 4
     1
 9
     2
 8

Which leads to the following position:

 O | O |  
---+---+---
 X | O |  
---+---+---
 X | X | X

with first player (Crosses) winning by completing the third row.

Problem statement

You will be given the sequence of moves (supposing the first move is always done by X) - by the numbers of cells where marks are placed - and your task is to determine, at which step the first line was completed (by any side).

Input data contain the number of test-cases in the first line.
Next lines have one test-case each - exactly 9 numbers, describing cells to which moves are performed in order.
Answer should contain the number of the move at which game is won by one of players (starting from 1) or 0 if the game is drawn (no winner) after the last move.

Example:

input data:
3
7 5 4 1 9 2 8 3 6
5 1 3 7 6 4 2 9 8
5 1 2 8 6 4 7 3 9

answer:
7 6 0
You need to login to get test data and submit solution.