Problem 44850. X O X O

Created by Rayner Saggers

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>On a noughts and crosses board, how many possible unique combinations are there given a square grid of length n?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Assumptions/constraints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>All squares are populated.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Number of naughts and number of crosses can only differ by a maximum of 1. I.E. The game was played until the board was full</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Minimum Grid size (n) = 1x1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a discrete maths question, which can be simplified by focussing on one of the options. If we look at the options for locating just the crosses on the grid, we know that the remaining locations must contain naughts and so similarly for the opposite condition. The maths is relatively simple, and is the solution to \"choose k from n\".</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>19-Feb-19 - Test suite updated to take into account solutions where the opposing player goes first.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

88 Solutions
36 Solvers

Last Solution submitted on Nov 28, 2022

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Vadim Smirnov on 3 Apr 2019

Rayner, by N do you include odds and even lengths ? what's the minimal length too? Cant imagine a game being fun with just one square )

Rayner Saggers on 8 Apr 2019

By 'n' I mean any length of square grid. You solution should still be valid for a 1x1 grid. (I've now added an extra test script for this case). Though in reality I agree such a game wouldnt be much fun!

https://www.mathworks.com/matlabcentral/cody/problems/44851 adds the dynamic of stopping play when someone wins, though Ciaran's test suite needs fixing before you can attempt this one

Reece Blunt on 30 May 2019

Lovely little problem Rayner, look forward to trying Ciaran's

Dyuman Joshi on 16 Mar 2022

Problem needs more test cases

Solution Comments

Solution 1729999

2 Comments

2 Comments

Martin Vatshelle on 19 Feb 2019

This is a nice problem, but the solution test suit is poor.
To get 126 for n = 3 one need to assume same player always starts.
If either player could start we get more solutions.
I.E. number of solutions with 4 x's and 5 o's + number of solutions with 5 x's and 4 o's

Rayner Saggers on 19 Feb 2019

https://www.mathworks.com/matlabcentral/cody/problems/44851 provides a more challenging extension that asks the user to take into account that games end when there's a "win".

My first attempt at producing a community problem so thanks for the feedback on improving the test suite.

Problem Recent Solvers36

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!