Is this Tic-Tac-Toe board valid?

Question

Challenge

Given a tic-tac-toe board in any format, determine if it is valid or not. If a board can be the result of a tic-tac-toe game, then it is valid. For example, this board is valid:

X O X
O X O
X O X

On the contrary, this board is invalid:

X X X
X X O
O O O

Input

• A full (9/9) tic tac toe board (the outcome, not the game).

Rules

• The input format must be able to depict all 512 possible input boards. It must be specified, along with the instructions to create it if it is obscure/unclear. You must state the marks of the board individually though.
• There must be two possible outputs, one for validity and one for invalidity.
• You can assume the board does not have empty spots.

Test cases

Valid:

X O X
O X O
X O X

X O X
X O X
O X O

X O O
O O X
O X X

O X O
X O X
O X O

Invalid:

X X X
X X X
X X X

O O O
O O O
O O O

X X X
O O O
X X X

O O O
O O X
X X X

X X O
O X O
O O X

A little help?

A board is considered valid (for this challenge) if and only if the following two conditions hold:

• There are 5 X and 4 O, or 4 X and 5 O. For example,

  X X X
  O X O
  X X X

  is considered invalid, because there are 7 Xs and 2 Os.
• Only the player with 5 marks has won, or none of them have won. For example,

  X X X
  O O O
  O O X

  is considered invalid, since either the row of Os or the row of Xs will be formed first. The two players can't have their turn simultaneously.

The current winner is...

...ais523's Jelly answer, at an astounding 26 bytes!

Answer 1

Jelly, 26 bytes

ṢŒrṪ4=$$Ðfx3ðœ-µẆm€6R¤;/µL

Try it online!

The input format is a little unusual; it's a string representing the board, but with Windows newlines (carriage return followed by newline). For example, XXO\r\nOXO\r\nOOX. (Actually, any two-character padding string between the lines works, but Windows newlines are much more defensible than the other options.)

The basic idea is that we look for characters that appear 4 times in the input, but don't have three evenly spaced occurrences in the original string. With two or more characters of padding between the lines of a 3×3 grid, all horizontal, vertical, and diagonal lines are evenly spaced, but no other evenly spaced line can have three elements.

Explanation:

The ð and µs are chain separators, which split the program into multiple parts that are each independent. I've replaced them with spaces below, to make things a bit clearer.

ṢŒrṪ4=$$Ðfx3 œ- Ẇm€6R¤;/ L
Ṣ                           sorted version of the input
 Œr                         run-length-encode it
        Ðf                  keep only elements where
   Ṫ                        delete the last element, and it was
    4=                      equal to 4
      $$                    parse Ṫ4= as a group
          x3                repeat each element three times

                Ẇ           all sublists of the input
                 m€         take every nth element of each (€) sublist
                   6R       for each n in 1..6
                     ¤      parse 6R as a group
                      ;/    flatten one level (m€ creates a nested structure)

             œ-             multiset difference
                         L  length of that difference

In other words, we find the list of characters that appear exactly four times in the input, and make a list consisting of three copies of each of those; we find the list of all subsequences that are evenly spaced in the original string; and if we subtract the second from the first, we want the result to have length 1 (i.e. a player played four times but didn't win). Note that as we're on a 3×3 grid and every square is full, it's impossible for both players to have played four times. In Jelly, 1 is truthy, 0 is falsey, so we don't need to do anything special to convert the resulting list to a boolean. (The µL is required, though, because otherwise both “XXX” and “OOO” would be possible truthy output values, and the question requires that all valid boards give the same output.)

Answer 2

JavaScript (ES6), 88 87 bytes

s=>(a=[...s]).sort()[5]-a[3]&[7,56,73,84,146,273,292,448].every(j=>j&i,i=`0b`+s^~-a[4])

Takes input as a string of 9 0 and 1 characters and returns 1 for valid, 0 for invalid. We sort the characters into order. If the middle three characters are now the same then the board is invalid as there are too many of one piece. Otherwise, we convert the original board into binary, flipping the bits if there are more 0s than 1s. At this point the board is valid if 0 does not have a line of three, so we simply test all eight lines via an array of bitmasks. Edit: Saved 1 byte thanks to @ETHproductions.

Answer 3

Python 3, 131 127 125 100 96 bytes

For a different algorithmic approach (and one that will be really suited to these multi-byte golfing languages with built-in compression), instead of calculating if the board is valid, let's have a 512-bit number where each bit represents whether or not a particular board is valid or not, and pass in a binary value representing the board. Furthermore, due to symmetry, the second half of the table can be eliminated, along with a bunch of zeros:

def z(b):return int('agqozfx67wwye6rxr508ch2i8qicekpreqkap0725pk',36)<<24&1<<b+(b>255)*(511-b-b)

The test value:

X X X
O X O
X X X

Is represented as the binary value 0b111010111, and the function returns a non-zero value if the board is valid.

Answer 4

Batch, 140 bytes

@set/aXXX=OOO=O=0
@for %%l in (%* %1%2%3 %1%4%7 %1%5%9 %2%5%8 %3%5%7 %3%6%9 %4%5%6 %7%8%9)do @set/a%%l+=1
@cmd/cset/a!XXX*!(O-=5)+!OOO*!~O

Takes input as nine separate command-line arguments and outputs 1 for valid and 0 for invalid. Works by tracking the number of times it sees an O and a orthogonal line of OOO or XXX. Conveniently Batch allows us to perform integer arithmetic indirectly, so we're not incrementing %%l but some variable instead (although we're only interested in the three variables mentioned). We then need to test that either X has not won and there are five Os or that O has not won and there are four Os.

Answer 5

Mathematica, 82 75 bytes

Thanks to Martin Ender for saving 7 bytes!

t=Total;3<(b=#~t~2)<6&&{t[c=If[b>4,1-#,#]],t/@c,Tr@c,Tr@Reverse@c}~FreeQ~3&

Unnamed function taking a 3x3 nested list of 1s and 0s as input and outputting True or False.

Uses some handy flexibility of the Total function (here golfed to t): given an example array e = { {1,2,3} , {4,5,6} , {7,8,9} }, the command t[e] sums the three vectors (here yielding {12,15,18}); the command t/@e sums each sublist individually (here yielding {6,15,24}); and the command e~t~2 sums all nine elements (here yielding 45).

So first we test, with 3<(b=#~t~2)<6, whether the total number of 1s is 4 or 5; if not we exit with False. If so, we use c=If[b>4,1-#,#] to force there to be four 1s, not five. Then we compute the column sums t[c], the row sums t/@c, the sum of the main diagonal Tr@c, and the sum of the opposite diagonal Tr@Reverse~c, and use ~FreeQ~3 to check that 3 fails to appear at any level in those computed sums.

Amusing side note: unlike most appearances on this site, here Tr is not used to sum a one-dimensional list but is actually used as designed—to calculate the trace of a two-dimensional matrix!

Answer 6

Pyth - 36 bytes

I include diagas and use two ternaries instead.

JsM+sCBQm@VdU3_BQ?q5KssQ*FJ?qK4!}3JZ

Test Suite

Answer 7

Python 2, 158 132 109 92 91 123 bytes

def v(b):f=sum(b,());w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1};return sum(map(`b`.count,w))==len(w)*5

Input is a list/tuple of rows, each a three-tuple of strings, e.g.:
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]

Saved some bytes by ignoring diagonals per @Maltysen's answer, which also shortened the following expression.

Thanks @vaultah for saving 17 18 bytes.

Checking diagonals turns out to be necessary, which removed a lot of the savings above.

Try it here.

Explanation

def v(b):
  f=sum(b,())
  w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1}
  return sum(map(`b`.count,w))==len(w)*5

f is the flattened input for slicing.
w contains the characters with winning sequences.
Count the occurrences of each winning character, which will either be 0 if w is empty or 5 if len(w) is 1. The 10 sum when both have a winning sequence is impossible. The winner having 5 implies the loser has 4. You can't have >5 without a winning sequence.

Answer 8

JavaScript (ES6), 101 bytes

Takes input as a 9-bit binary mask where X = 1 and O = 0 (MSB = top left cell, LSB = bottom right cell).

n=>[7,56,73,84,146,273,292,448,o=x=0].map((m,i)=>(c-=n>>i&1,m&n^m?m&n||o++:m&&x++),c=4)&&!(c|x&&~c|o)

Test cases

let f =

n=>[7,56,73,84,146,273,292,448,o=x=0].map((m,i)=>(c-=n>>i&1,m&n^m?m&n||o++:m&&x++),c=4)&&!(c|x&&~c|o)

// valid
console.log(f(0b101010101));
console.log(f(0b101101010));
console.log(f(0b100001011));
console.log(f(0b010101010));

// invalid
console.log(f(0b111111111));
console.log(f(0b000000000));
console.log(f(0b111000111));
console.log(f(0b000001111));
console.log(f(0b110010001));

Answer 9

R, 88 82 bytes

x=scan();`if`(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)

All combinations of three integers from 1 to 9 that sum up to 15 are the rows/columns/diagonals of the square shown below.

2 7 6
9 5 1
4 3 8

The function takes input as a vector of booleans, T for "X", F for "O", which is the flattened representation of the board. BUT, these are reordered so that their index is the same as the number in the square, in the the order (2,7,6,9,5,1,4,3,8). That order might be achieved by flattening the board in the normal way, and then slicing by c(6,1,8,7,5,3,2,9,4). So this

X O X
O X O
X O X

is represented as:

c(T, F, T, F, T, F, T, F, T)[c(6,1,8,7,5,3,2,9,4)]

which is:

c(F, T, F, T, T, T, F, T, F)

The function first determines whether there is a player with exactly four marks. If so, the function uses the fact-of-things-that-add-up-to-15 to determine whether that player has a three-in-a-row (the board is invalid iff that player does).

If you wanted to take a conventionally-flattened board as input, the code would look like this instead:

f=function(x)ifelse(sum(x)%in%4:5,all(apply(combn(c(2,7,6,9,5,1,4,3,8)[which(x==(sum(x)<5))],3),2,sum)!=15),F)

I'm new at this, advice would be appreciated.

Answer 10

JavaScript (ES6), 145 139 131 127 bytes

s=>!(q="XO"[s.split`O`.length-5])|![...s].some((c,i)=>c==q&!/(.)(\1|..(\1|.(\1|.\1.).)..)\1/.test(s.slice(0,i)+0+s.slice(i+1)))

Input as a space-separated string, such as "XOX OXO XOX". Outputs 1 for an invalid board, 0 for a valid one. This obviously isn't the best technique, at least not with JavaScript...

This basically checks whether both the following hold:

• There are exactly 4 or 5 Os, AND
• there is at least one of the 5-instance piece which creates an undecided game when removed.

The regex is to check whether a game has been decided. It matches a board iff there are any runs of length three of one character with 0 (row), 2 (down-right diagonal), 3 (column), or 4 (down-left diagonal) chars separating each pair.

Test snippet

f=s=>!(q="XO"[s.split`O`.length-5])|![...s].some((c,i)=>c==q&!/(.)(\1|..(\1|.(\1|.\1.).)..)\1/.test(s.slice(0,i)+0+s.slice(i+1)))

g=s=>console.log(f(s))

// Valid boards (outputs 0)
g("XOX OXO XOX")
g("XOX XOX OXO")
g("XOO OOX OXX")
g("OXO XOX OXO")

// Invalid boards (outputs 1)
g("XXX XXX XXX")
g("OOO OOO OOO")
g("XXX OOO XXX")
g("OOO OOX XXX")
g("XXO OXO OOX")

Answer 11

Ruby, 104 99 91 bytes

->x{[7,56,448,292,146,73,84,273].none?{|y|b=x.to_i 2;((a=x.count'1')==4?b:a==5?~b:7)&y==y}}

Input format: binary string of 9 symbols (0s and 1s) representing the board, for example the first test case is 101010101. First convert it to a binary number, check if popcount is 4 or 5, if it's 5 invert the number so we always have 4. Check if three of them are aligned (masking witn horizontal, vertical, diagonal).

TL;DR: Return false if player with 4 marks won, true otherwise.

Thanks Jordan for the comments,

I can't reproduce the UTF-8 string which would save another byte.

Answer 12

Perl 6, 103 99 bytes

{my \c=%(.flat.Bag.invert)<5>;?all c,|(.[0]===c if [eq] $_ for |.flat[<0 4 8>,<2 4 6>],|$_,|.&zip)}

A lambda that accepts a list of lists like (('X','O','X'), ('O','X','O'), ('X','O','X')), and returns a Bool.

It works like this:

1. Check which mark appears exactly 5 times, and store it in c. (If no mark appears exactly 5 times, this will contain a falsy value)
2. Iterate over all diagonals, rows, and columns, and filter out the "winning" ones (i.e. those where all three letters are equal).
3. Check if c is truthy, and each winning line is of type c.

Answer 13

PHP, 125 bytes

for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;foreach([7,56,448,73,146,292,273,84]as$m)$n&$m^$m?$n&$m||$o++:$x++;echo!$x|!$o&&2>$i^=4;

I had the same idea as Arnauld: The board is valid if there are either 4 or 5 bits set and either X or O or nobody has a streak (but not both).

To generate input from field replace X with 1 and O with 0, join lines and convert binary to decimal, provide as command line argument.

prints 1 for valid; empty output for invalid. Run with -r.

breakdown

// count set bits
for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;
    /* ($p/=2 takes longer than $p>>=1, but eventually
       $p will come close enough to 0 for the loop to finish */
// count streaks for X and O
foreach([7,56,448,73,146,292,273,84]as$m)
    $n&$m^$m            // ($n masked with streak)!=streak <=> no streak for X
        ?$n&$m||$o++    // true: O has a streak if ($n masked with streak) is empty
        :$x++;          // false: X has a streak
echo!$x|!$o&&2>$i^=4;   // valid if not both have a streak
                        // AND $i is 4 or 5 (toggle 4 -> result 0 or 1)

Answer 14

Swift, 178 bytes

func t(i:String)->Bool{let r=i.characters.filter({$0=="X"}).count;let g=i.characters.split(separator:"\n").map(String.init).contains;return(r==5||r==4)&&(!g("XXX") && !g("OOO"))}

Answer 15

ES6 (Javacript), 130, 138, 117 bytes

EDITS:

• 21 bytes off thanks to excellent advice from @Neil !
• Initial version was prone to a bug, which should now be fixed at cost of +8 bytes. (Thanks @ETHproductions for pointing it out)

An extremelly straighforward approach. Can probably be golfed a bit further.

Accepts input as 9 separate arguments, 1es and 0es

• 1 is for X
• 0 is for O

Arguments: 1-3 - first row, 4-6 - second row, 7-9 - third row.

Golfed

(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j])

Interactive "Test Bed"

var a=b=c=d=e=f=g=h=j=0;

T=(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j]);

function test() {
  if(T(a,b,c,d,e,f,g,h,j)) {
     grid.style.backgroundColor='green';
     msg.innerHTML="GOOD"
  } else {
     grid.style.backgroundColor='red';
     msg.innerHTML="BAD"
  }
}

<table id=grid style="background: red">
<thead>
  <tr>
     <td id=msg align="center" colspan="3">BAD</td>
    </tr>
  </thead>
  <tr>
      <td><input type="checkbox" onchange="a=this.checked*1;test();" id="ca"/></td>
      <td><input type="checkbox" onchange="b=this.checked*1;test();" id="cb"/></td>
      <td><input type="checkbox" onchange="c=this.checked*1;test();" id="cc"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="d=this.checked*1;test();" id="cd"/></td>
      <td><input type="checkbox" onchange="e=this.checked*1;test();" id="ce"/></td>
      <td><input type="checkbox" onchange="f=this.checked*1;test();" id="cf"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="g=this.checked*1;test();" id="cg"/></td>
      <td><input type="checkbox" onchange="h=this.checked*1;test();" id="ch"/></td>
      <td><input type="checkbox" onchange="j=this.checked*1;test();" id="cj"/></td>
    </tr>
 </table>