Ponder This Challenge - March 2020 - Dic-dac-doe

In the classic 3x3 tic-tac-toe game, either player can win or at least force a draw if he plays correctly.
On a 3x4 board, the first player can always win if she plays correctly, but if the players are working together, it is possible to get a draw.

This month we define a new game (dic-dac-doe) played on a 10x10 board by three players (X, O, and +), where the first to get at least three consecutive squares with their sign (horizontally, vertically or diagonally) - wins.
Three peace-loving players are playing and trying together to get to a draw, but after 80 moves, an intensely competitive win-only demon takes over all of their minds and controls their remaining 20 moves, trying to get one of them to win. Can they play the first 80 moves in such a way that even the demon won't be able to prevent a draw?

Supply your answer as the status of the game after the 80th move as an 10x10 array of 'X', 'O', '+', and '.', where the first three symbols represent the moves of the players and the dots represent empty squares.

Bonus '*' for a solution that lets the demon act on the 186th move on a 15x15 board; and '**' for the 185th move.

Solution

• Click here to view the solution

  In order to force a draw, the players cannot leave more than one unplayed square in any given three consecutive squares.

  It is easy to check that to force draw, one cannot have more than five unplayed squares in a 5x5 board.
  Therefore there can not be a solution with more than 20 unplayed squares in a 10x10 board.
  You can find 20 unplayed squares and then solve for the remaining 80 squares.

  A possible solution is:

  X.+O+.XO.X
  .XO.+XOO+.
  O+OXO++XOO
  +XXO.+O+.X
  .O+XXO.+X+
  OXO.+XXO+.
  X.O+O.+OXO
  ++XXO+X+XX
  XO.+XO.+O.
  .O+X.O+X.+
  

  The second '*' goes for finding a solution for a 15x15 board with 41 unplayed squares:

  X.+X+.X+X+.X+.O
  .O+.XOO+.XOO+X.
  +XXOO+.XOO+XXO+
  O+O+XX+X+.XOX.O
  .+XX+.XOO+X.O++
  +O+.XOO+.XO++X.
  O.XOO+.X+X.OXOO
  X+X+.X++OO+OX.+
  .XOO++OOX.OX+XO
  OO+.XOX.O++X.O+
  +XX+X.O++X.OX+.
  XO.XO+OX.OXXO+O
  .X++OOX+XX++OX+
  ++O.X+X.O+O.X+.
  O.XOX.+XO.+OX.O
  

  Bertram Felgenhauer found an 18x18 board with 58 unplayed squares:

  +OX.O+O.+X+X.O++X.
  X.+XO.+XXO.+O+.XOX
  +XXO+X+O.+O+XXOX.O
  .O+O.+OXO+XXO.XO++
  XO.+XXO.+XO.X++OX.
  ++X+O.+O+.X++O.X+X
  X.+OXO+XXOXO.XOX.+
  OOXO.+XO.X++OX++OO
  .X++O+.X++O.X+O.X+
  +OX.+XOXO.XOX.+OX.
  X.+OOXX++OX++OOX+O
  OXOX.+XO.X+O.X+X.+
  .+O+XXO+OXO+OX.+OO
  +OX.O+O.X+O.X+OOX.
  X.+OX.+O+.XOX.+O+X
  OXX++OXX+OO++OOX+O
  .+OOX+.OX+.XO+.XO.
  X.OX.+O+.OX+.OX+.X
  

  and a 20x20 board with an optimal 71 unplayed squares:

  O.+X+X.+XXO.+XO.+X.O
  +XXO.XOO+.XOX.+OXO+.
  .O++OO+.XOO++OO+X+OX
  XXO.X+X+X+.XOX.+OX.+
  O.+XO+.XOO+X.O+X.O+O
  XO+O.XOO+.XO+OXO+OX.
  .+XX+O+.X+X.O+X.OX++
  OO+.XOX+XOO++XO++X.O
  +.XOO+.XO+.XOX.OXOX+
  X+X+.X+XOO+X.O++X.+O
  .XOO++OO+.XO++X.OX+.
  OO+.XOX.O+X.OXOXX+OX
  +.X+X.O++XO++X.+O+.O
  O+XOO++XOX.OXOX+.OXX
  .XO+.XOX.O++X.+OXX+.
  +X.O+X.O++X.OX+.O+O+
  XO++XO++X.OXX+OXO+.X
  +XXOX.OXOXX+O+.O+XXO
  .O+.O++X.+O+.OXX+O+.
  O.+XOX.OX+.X+O+.OX.+
  

Solvers

• **Bert Dobbelaere (27/02/2020 10:23 PM IDT)
• Guillermo Wildschut (27/02/2020 11:11 PM IDT)
• **George Lasry (28/02/2020 01:00 AM IDT)
• Kevin Bauer (28/02/2020 02:58 AM IDT)
• Anders Kaseorg (28/02/2020 05:41 AM IDT)
• **Alper Halbutogullari (28/02/2020 12:46 PM IDT)
• Alex Fleischer (28/02/2020 04:32 PM IDT)
• Paul Revenant (28/02/2020 07:13 PM IDT)
• Todd Will (28/02/2020 09:18 PM IDT)
• *Lorenz Reichel (29-02-20 01:48 PM IDT)
• Paul Shaw (29-02-20 01:59 PM IDT)
• Graham Hemsley (01-03-20 04:41 PM IDT)
• *David Greer (01/03/2020 09:53 PM IDT)
• Kevin Naslund (02/03/2020 12:51 AM IDT)
• **Bertram Felgenhauer (02/03/2020 03:19 AM IDT)
• Pern Jie Quah (02/03/2020 01:40 PM IDT)
• *Mathieu Roget (02/03/2020 11:35 PM IDT)
• Yifan Xu (03/03/2020 03:27 AM IDT)
• John Tromp (03/03/2020 10:58 AM IDT)
• *Walter Sebastian Gisler (03/03/2020 12:18 PM IDT)
• Willem H Hendriks (03/03/2020 03:15 PM IDT)
• Andrew Mullins (04/03/2020 11:13 PM IDT)
• *Joerg Schepers (06/03/2020 12:09 AM IDT)
• Eden Saig (06/03/2020 05:17 PM IDT)
• Dominik Reichl (07/03/2020 12:39 AM IDT)
• Keith Kaplan (08/03/2020 06:56 AM IDT)
• Serino Dario (08/03/2020 11:15 AM IDT)
• Eric Manalac (09/03/2020 02:04 AM IDT)
• **Latchezar Christov (09/03/2020 10:28 AM IDT)
• Daniel Chong Jyh Tar (12/03/2020 06:43 PM IDT)
• *Kang Jin Cho (13/03/2020 11:58 AM IDT)
• **Jacoby Jaeger (14/03/2020 07:13 AM IDT)
• **Vladimir Volevich (15/03/2020 06:42 PM IDT)
• Reda Kebbaj (15/03/2020 07:54 PM IDT)
• *Florian Fischer (15/03/2020 10:38 PM IDT)
• Robert Lang (16/03/2020 02:10 PM PM IDT)
• Govind Jujare (17/03/2020 02:58 AM PM IDT)
• Dipto Thakurta (17/03/2020 09:43 AM IDT)
• Daniel Bitin (20/03/2020 02:34 AM IDT)
• **Stanislav Grudnitskiy (23/03/2020 07:26 AM IDT)
• Pål Hermunn Johansen (24/03/2020 09:18 PM IDT)
• David Kelly (25/03/2020 09:56 PM IDT)
• *Erik Wünstel (25/03/2020 10:45 PM IDT)
• **Thomas Pensyl (26/03/2020 04:16 AM IDT)
• **Noa Avidar (26/03/2020 08:28 PM IDT)
• Li Wang (27/03/2020 12:10 AM IDT)
• Thomas Egense (27/03/2020 11:04 AM IDT)
• Yongxing Jim Wang (28/03/2020 05:52 AM IDT)
• Devora Rochberger (29/03/2020 04:11 PM IDT)
• Ken Dsouza (30/03/2020 07:25 PM IDT)
• Vincent Beaud (30/03/2020 11:34 PM IDT)
• Dan Ismailescu (01/04/2020 01:54 AM IDT)
• Daniel Jeon (01/04/2020 02:16 AM IDT)
• Booyeon (Brian) Choi (01/04/2020 03:48 AM IDT)
• Kelvin Kim (01/04/2020 05:20 AM IDT)
• Eric W. (01/04/2020 05:55 AM IDT)
• David Park (02/04/2020 05:00 PM IDT)
• Andreas Puccio (04/04/2020 10:48 PM IDT)
• *Walter Schmidt (05/04/2020 03:29 PM IDT)
• Marco Bellocchi (13/04/2020 02:20 AM IDT)
• Stéphane Higueret (20/04/2020 12:39 PM IDT)
• John Goh (22/04/2020 07:52 AM IDT)
• **Nyles Heise (25/04/2020 08:07 AM IDT)
• **Chris Shannon (27/04/2020 07:51 PM IDT)
• *Oscar Volpatti (29/04/2020 07:33 AM IDT)
• **Shawn Ligocki (29/04/2020 09:19 AM IDT)
• David Friedman (29/04/2020 04:28 PM IDT)
• **Li Li (01/05/2020 07:51 AM IDT)
• Clive Tong (01/05/2020 05:12 PM IDT)
• Radu-Alexandru Todor (02/05/2020 11:39 PM IDT)