In the game of tic-tac-toe, two players take turns marking squares of an initially empty
3 ¡Á 3 grid with either X¡¯s or O¡¯s. The first player always marks squares using X¡¯s, whereas the second player
always marks squares using O¡¯s. If at any point during the game either player manages to mark three
consecutive squares in a row, column, or diagonal with his/her symbol, the game terminates.
Given a board configuration, your goal is to determine whether the board configuration represents the
possible final state of a valid tic-tac-toe game.
The input test file will contain multiple cases. Each test case consists of a single line containing 9
characters, which represent the 9 squares of a tic-tac-toe grid, given one row at a time.
Each character on the line will either be ¡®X¡¯, ¡®O¡¯ (the letter O), or ¡®.¡¯ (indicating an unfilled square).
The end-of-file is marked by a single line containing the word ¡°end¡±.
For each input test case, write a single line containing either the word ¡°valid¡± or ¡°invalid¡± indicating
whether the given board configuration is the final state of some possible tic-tac-toe game.
Stanford Local 2006