Recursively Generate Every Tic-Tac-Toe game in Python












6















I am working on a project where I generate every possible tic-tac-toe array. As a proof of concept, I am working on code to fill an array with 9 subarrays. Each subarray will have two values, the first one being 0 or 1 (for x and o respectively), and the second one being from 1 to 9 (representing when it was placed).
An example of an array I would like to get out would look like:



[[0, 0], [1, 1], [0, 2], [1, 3], [0, 4], [1, 5], [0, 6], [1, 7], [0, 8]]


I have already written code, using 9 for loops, each one nested in the one above, which gives me the desired results (every possible array, and each one unique). But I am trying to write code, using recursion, and avoiding writing tons of nested loops.



When I run the code below, it is only able to generate the array above, and cannot create other combinations. My code is below:



print("running...")

allGames =
checkCurrentGame = [5, 5, 5, 5, 5, 5, 5, 5, 5]
stepsDown = 0

def cleanGame(move, currentGame):
for j in range(9):
if (currentGame[j][1] >= move):
currentGame[j] = [5, 0]

def completeMove(moveNumber, currentGame):
global stepsDown
stepsDown = stepsDown + 1
for i in range(9):
cleanGame(moveNumber, currentGame)
if (currentGame[i][0] == 5):
currentGame[i][0] = i % 2
currentGame[i][1] = moveNumber
allGames.append(currentGame)
break
if (stepsDown < 9):
generateGame(currentGame)

def generateGame(currentGame):
for i in range(9):
completeMove(i, currentGame)

generateGame([[5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0]])

for x in range(len(allGames)):
print(allGames[x])









share|improve this question





























    6















    I am working on a project where I generate every possible tic-tac-toe array. As a proof of concept, I am working on code to fill an array with 9 subarrays. Each subarray will have two values, the first one being 0 or 1 (for x and o respectively), and the second one being from 1 to 9 (representing when it was placed).
    An example of an array I would like to get out would look like:



    [[0, 0], [1, 1], [0, 2], [1, 3], [0, 4], [1, 5], [0, 6], [1, 7], [0, 8]]


    I have already written code, using 9 for loops, each one nested in the one above, which gives me the desired results (every possible array, and each one unique). But I am trying to write code, using recursion, and avoiding writing tons of nested loops.



    When I run the code below, it is only able to generate the array above, and cannot create other combinations. My code is below:



    print("running...")

    allGames =
    checkCurrentGame = [5, 5, 5, 5, 5, 5, 5, 5, 5]
    stepsDown = 0

    def cleanGame(move, currentGame):
    for j in range(9):
    if (currentGame[j][1] >= move):
    currentGame[j] = [5, 0]

    def completeMove(moveNumber, currentGame):
    global stepsDown
    stepsDown = stepsDown + 1
    for i in range(9):
    cleanGame(moveNumber, currentGame)
    if (currentGame[i][0] == 5):
    currentGame[i][0] = i % 2
    currentGame[i][1] = moveNumber
    allGames.append(currentGame)
    break
    if (stepsDown < 9):
    generateGame(currentGame)

    def generateGame(currentGame):
    for i in range(9):
    completeMove(i, currentGame)

    generateGame([[5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0]])

    for x in range(len(allGames)):
    print(allGames[x])









    share|improve this question



























      6












      6








      6








      I am working on a project where I generate every possible tic-tac-toe array. As a proof of concept, I am working on code to fill an array with 9 subarrays. Each subarray will have two values, the first one being 0 or 1 (for x and o respectively), and the second one being from 1 to 9 (representing when it was placed).
      An example of an array I would like to get out would look like:



      [[0, 0], [1, 1], [0, 2], [1, 3], [0, 4], [1, 5], [0, 6], [1, 7], [0, 8]]


      I have already written code, using 9 for loops, each one nested in the one above, which gives me the desired results (every possible array, and each one unique). But I am trying to write code, using recursion, and avoiding writing tons of nested loops.



      When I run the code below, it is only able to generate the array above, and cannot create other combinations. My code is below:



      print("running...")

      allGames =
      checkCurrentGame = [5, 5, 5, 5, 5, 5, 5, 5, 5]
      stepsDown = 0

      def cleanGame(move, currentGame):
      for j in range(9):
      if (currentGame[j][1] >= move):
      currentGame[j] = [5, 0]

      def completeMove(moveNumber, currentGame):
      global stepsDown
      stepsDown = stepsDown + 1
      for i in range(9):
      cleanGame(moveNumber, currentGame)
      if (currentGame[i][0] == 5):
      currentGame[i][0] = i % 2
      currentGame[i][1] = moveNumber
      allGames.append(currentGame)
      break
      if (stepsDown < 9):
      generateGame(currentGame)

      def generateGame(currentGame):
      for i in range(9):
      completeMove(i, currentGame)

      generateGame([[5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0]])

      for x in range(len(allGames)):
      print(allGames[x])









      share|improve this question
















      I am working on a project where I generate every possible tic-tac-toe array. As a proof of concept, I am working on code to fill an array with 9 subarrays. Each subarray will have two values, the first one being 0 or 1 (for x and o respectively), and the second one being from 1 to 9 (representing when it was placed).
      An example of an array I would like to get out would look like:



      [[0, 0], [1, 1], [0, 2], [1, 3], [0, 4], [1, 5], [0, 6], [1, 7], [0, 8]]


      I have already written code, using 9 for loops, each one nested in the one above, which gives me the desired results (every possible array, and each one unique). But I am trying to write code, using recursion, and avoiding writing tons of nested loops.



      When I run the code below, it is only able to generate the array above, and cannot create other combinations. My code is below:



      print("running...")

      allGames =
      checkCurrentGame = [5, 5, 5, 5, 5, 5, 5, 5, 5]
      stepsDown = 0

      def cleanGame(move, currentGame):
      for j in range(9):
      if (currentGame[j][1] >= move):
      currentGame[j] = [5, 0]

      def completeMove(moveNumber, currentGame):
      global stepsDown
      stepsDown = stepsDown + 1
      for i in range(9):
      cleanGame(moveNumber, currentGame)
      if (currentGame[i][0] == 5):
      currentGame[i][0] = i % 2
      currentGame[i][1] = moveNumber
      allGames.append(currentGame)
      break
      if (stepsDown < 9):
      generateGame(currentGame)

      def generateGame(currentGame):
      for i in range(9):
      completeMove(i, currentGame)

      generateGame([[5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0]])

      for x in range(len(allGames)):
      print(allGames[x])






      python arrays recursion






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 24 '18 at 15:53









      גלעד ברקן

      12.4k21441




      12.4k21441










      asked Nov 22 '18 at 20:23









      Luke SchultzLuke Schultz

      464




      464
























          3 Answers
          3






          active

          oldest

          votes


















          2














          If I understand your question correctly this should do, however this is not recursion -



          import itertools
          [zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]


          The code first generates a board (9 0's or 1's) -



          itertools.product([0, 1], repeat=9)


          and then add the index data to it.



          I recommend having a look in itertools






          share|improve this answer
























          • This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

            – handras
            Nov 23 '18 at 6:46











          • Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

            – handras
            Nov 23 '18 at 7:10











          • It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

            – Tom Ron
            Nov 23 '18 at 10:53











          • But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

            – handras
            Nov 23 '18 at 11:29






          • 1





            It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

            – גלעד ברקן
            Nov 24 '18 at 16:02





















          0














          This is fun. Here's a method that plays the game, branching off each possible move (or at any rate, that's the intention).



          Although my preference is usually to concat and return a pure result, to allow for an early exit and inspection, this recursion accumulates in a global variable.



          import copy
          import json
          import time

          s = set()
          rs =

          def f():
          """
          111
          111000
          111000000
          1001001
          10010010
          100100100
          1010100
          100010001
          """
          wins = [0007,0070,0700,0111,0222,0444,0124,0421]
          def winner(board):
          # check xs or os individual board for a win
          for i in wins:
          if not (i ^ (board & i)):
          return True
          return False

          # xs board, os board, move-number, game
          def g(xs, os, move, result):
          # allow for early exit
          global rs
          if (len(rs) > 20000):
          return

          # base case, win or draw
          if winner(xs) or winner(os) or move == 9:
          #print "{0:b}".format(xs)
          #print "{0:b}".format(os)
          #print (result, xs, os)
          #print

          # confirm we're not duplicating results
          enc = json.dumps(result)
          if enc in s:
          print "Duplicate!"
          print result
          s.add(enc)

          # accumulate results
          rs.append((result, xs, os))
          return

          board = xs | os

          for i in xrange(9):
          # candidate move
          m = 1 << i

          # valid move
          if not (m & board):
          _result = copy.deepcopy(result)

          # 'O' plays on odd numbered moves
          if move & 1:
          _result[i] = [1, move]
          g(xs, os | m, move + 1, _result)

          # 'X' plays on even numbered moves
          else:
          _result[i] = [0, move]
          g(xs | m, os, move + 1, _result)

          # start the recursion
          g(0, 0, 0, [[-1, -1]] * 9)

          start_time = time.time()
          f()
          print("--- %s seconds ---" % (time.time() - start_time))


          Output:



          """
          rs[2002]

          => ([[0, 0], [1, 1], [-1, -1],
          [-1, -1], [1, 5], [0, 2],
          [0, 4], [1, 3], [-1, -1]], 97, 146)

          x--
          ---
          ---

          xo-
          ---
          ---

          xo-
          --x
          ---

          xo-
          --x
          -o-

          xo-
          --x
          xo-

          xo-
          -ox
          xo-
          """





          share|improve this answer































            0














            I recommend you watch this video on youtube. The professor teaches really nicely about recursion. I think it will benefit for you more, then getting a working code. He uses sudoku as an example, but both games are just 2D arrays.



            If you watched the video, you will know how to modify this example to better suit your needs.
            A pseudo code:



            def place(who, when, where, table):
            if (None, None) not in table: # the table is full
            print(table)
            return

            if table[where] not (None, None): # this cell is already marked
            return

            table[where] (who, when) # can place our mark on the cell
            # make the recursive calls
            for i in range(9):
            place(who.opponent, when+1, i, table)

            for cell in range(9):
            empty = [(None, None) for _ in range(9)]
            place(firstplayer, 0, cell, empty)





            share|improve this answer

























              Your Answer






              StackExchange.ifUsing("editor", function () {
              StackExchange.using("externalEditor", function () {
              StackExchange.using("snippets", function () {
              StackExchange.snippets.init();
              });
              });
              }, "code-snippets");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "1"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53437620%2frecursively-generate-every-tic-tac-toe-game-in-python%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              3 Answers
              3






              active

              oldest

              votes








              3 Answers
              3






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              2














              If I understand your question correctly this should do, however this is not recursion -



              import itertools
              [zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]


              The code first generates a board (9 0's or 1's) -



              itertools.product([0, 1], repeat=9)


              and then add the index data to it.



              I recommend having a look in itertools






              share|improve this answer
























              • This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

                – handras
                Nov 23 '18 at 6:46











              • Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

                – handras
                Nov 23 '18 at 7:10











              • It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

                – Tom Ron
                Nov 23 '18 at 10:53











              • But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

                – handras
                Nov 23 '18 at 11:29






              • 1





                It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

                – גלעד ברקן
                Nov 24 '18 at 16:02


















              2














              If I understand your question correctly this should do, however this is not recursion -



              import itertools
              [zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]


              The code first generates a board (9 0's or 1's) -



              itertools.product([0, 1], repeat=9)


              and then add the index data to it.



              I recommend having a look in itertools






              share|improve this answer
























              • This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

                – handras
                Nov 23 '18 at 6:46











              • Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

                – handras
                Nov 23 '18 at 7:10











              • It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

                – Tom Ron
                Nov 23 '18 at 10:53











              • But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

                – handras
                Nov 23 '18 at 11:29






              • 1





                It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

                – גלעד ברקן
                Nov 24 '18 at 16:02
















              2












              2








              2







              If I understand your question correctly this should do, however this is not recursion -



              import itertools
              [zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]


              The code first generates a board (9 0's or 1's) -



              itertools.product([0, 1], repeat=9)


              and then add the index data to it.



              I recommend having a look in itertools






              share|improve this answer













              If I understand your question correctly this should do, however this is not recursion -



              import itertools
              [zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]


              The code first generates a board (9 0's or 1's) -



              itertools.product([0, 1], repeat=9)


              and then add the index data to it.



              I recommend having a look in itertools







              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered Nov 22 '18 at 20:37









              Tom RonTom Ron

              1,305819




              1,305819













              • This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

                – handras
                Nov 23 '18 at 6:46











              • Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

                – handras
                Nov 23 '18 at 7:10











              • It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

                – Tom Ron
                Nov 23 '18 at 10:53











              • But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

                – handras
                Nov 23 '18 at 11:29






              • 1





                It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

                – גלעד ברקן
                Nov 24 '18 at 16:02





















              • This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

                – handras
                Nov 23 '18 at 6:46











              • Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

                – handras
                Nov 23 '18 at 7:10











              • It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

                – Tom Ron
                Nov 23 '18 at 10:53











              • But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

                – handras
                Nov 23 '18 at 11:29






              • 1





                It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

                – גלעד ברקן
                Nov 24 '18 at 16:02



















              This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

              – handras
              Nov 23 '18 at 6:46





              This is not good, since it contains many invalid entries. For example the very first entry is [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8)].

              – handras
              Nov 23 '18 at 6:46













              Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

              – handras
              Nov 23 '18 at 7:10





              Also, it only includes games in wich the cells are filled sequentially. So it misses a lot of valid games in which e.g. the first player start in the middle.

              – handras
              Nov 23 '18 at 7:10













              It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

              – Tom Ron
              Nov 23 '18 at 10:53





              It contains all possible entries - len([zip(p, range(0, 9)) for p in itertools.product([0, 1], repeat=9)]) = 512=2^9.

              – Tom Ron
              Nov 23 '18 at 10:53













              But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

              – handras
              Nov 23 '18 at 11:29





              But 512 is not all the possible entries. You need to take into account which cell was filled first, second, ... last. That means a factor of 9!. Here is a representation of a valid game: [(0,8), (1,7), (0,6), (1,5), (0,4), (1,3), (0,2), (1,0), (0,0)] (note that 0 and 1 alternating in filling cells). Can you find it in your list of 512? It's not there... Furthermore you did not address the fact that your code will yield incorrect entries.

              – handras
              Nov 23 '18 at 11:29




              1




              1





              It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

              – גלעד ברקן
              Nov 24 '18 at 16:02







              It looks like you may have misunderstood the question. 2^9 will give us all combinations of 9 zeros and ones. Tic-tac-toe games are a significantly smaller subset of that and the OP's game representation also includes a number in each cell's data for "when it [the move] was placed."

              – גלעד ברקן
              Nov 24 '18 at 16:02















              0














              This is fun. Here's a method that plays the game, branching off each possible move (or at any rate, that's the intention).



              Although my preference is usually to concat and return a pure result, to allow for an early exit and inspection, this recursion accumulates in a global variable.



              import copy
              import json
              import time

              s = set()
              rs =

              def f():
              """
              111
              111000
              111000000
              1001001
              10010010
              100100100
              1010100
              100010001
              """
              wins = [0007,0070,0700,0111,0222,0444,0124,0421]
              def winner(board):
              # check xs or os individual board for a win
              for i in wins:
              if not (i ^ (board & i)):
              return True
              return False

              # xs board, os board, move-number, game
              def g(xs, os, move, result):
              # allow for early exit
              global rs
              if (len(rs) > 20000):
              return

              # base case, win or draw
              if winner(xs) or winner(os) or move == 9:
              #print "{0:b}".format(xs)
              #print "{0:b}".format(os)
              #print (result, xs, os)
              #print

              # confirm we're not duplicating results
              enc = json.dumps(result)
              if enc in s:
              print "Duplicate!"
              print result
              s.add(enc)

              # accumulate results
              rs.append((result, xs, os))
              return

              board = xs | os

              for i in xrange(9):
              # candidate move
              m = 1 << i

              # valid move
              if not (m & board):
              _result = copy.deepcopy(result)

              # 'O' plays on odd numbered moves
              if move & 1:
              _result[i] = [1, move]
              g(xs, os | m, move + 1, _result)

              # 'X' plays on even numbered moves
              else:
              _result[i] = [0, move]
              g(xs | m, os, move + 1, _result)

              # start the recursion
              g(0, 0, 0, [[-1, -1]] * 9)

              start_time = time.time()
              f()
              print("--- %s seconds ---" % (time.time() - start_time))


              Output:



              """
              rs[2002]

              => ([[0, 0], [1, 1], [-1, -1],
              [-1, -1], [1, 5], [0, 2],
              [0, 4], [1, 3], [-1, -1]], 97, 146)

              x--
              ---
              ---

              xo-
              ---
              ---

              xo-
              --x
              ---

              xo-
              --x
              -o-

              xo-
              --x
              xo-

              xo-
              -ox
              xo-
              """





              share|improve this answer




























                0














                This is fun. Here's a method that plays the game, branching off each possible move (or at any rate, that's the intention).



                Although my preference is usually to concat and return a pure result, to allow for an early exit and inspection, this recursion accumulates in a global variable.



                import copy
                import json
                import time

                s = set()
                rs =

                def f():
                """
                111
                111000
                111000000
                1001001
                10010010
                100100100
                1010100
                100010001
                """
                wins = [0007,0070,0700,0111,0222,0444,0124,0421]
                def winner(board):
                # check xs or os individual board for a win
                for i in wins:
                if not (i ^ (board & i)):
                return True
                return False

                # xs board, os board, move-number, game
                def g(xs, os, move, result):
                # allow for early exit
                global rs
                if (len(rs) > 20000):
                return

                # base case, win or draw
                if winner(xs) or winner(os) or move == 9:
                #print "{0:b}".format(xs)
                #print "{0:b}".format(os)
                #print (result, xs, os)
                #print

                # confirm we're not duplicating results
                enc = json.dumps(result)
                if enc in s:
                print "Duplicate!"
                print result
                s.add(enc)

                # accumulate results
                rs.append((result, xs, os))
                return

                board = xs | os

                for i in xrange(9):
                # candidate move
                m = 1 << i

                # valid move
                if not (m & board):
                _result = copy.deepcopy(result)

                # 'O' plays on odd numbered moves
                if move & 1:
                _result[i] = [1, move]
                g(xs, os | m, move + 1, _result)

                # 'X' plays on even numbered moves
                else:
                _result[i] = [0, move]
                g(xs | m, os, move + 1, _result)

                # start the recursion
                g(0, 0, 0, [[-1, -1]] * 9)

                start_time = time.time()
                f()
                print("--- %s seconds ---" % (time.time() - start_time))


                Output:



                """
                rs[2002]

                => ([[0, 0], [1, 1], [-1, -1],
                [-1, -1], [1, 5], [0, 2],
                [0, 4], [1, 3], [-1, -1]], 97, 146)

                x--
                ---
                ---

                xo-
                ---
                ---

                xo-
                --x
                ---

                xo-
                --x
                -o-

                xo-
                --x
                xo-

                xo-
                -ox
                xo-
                """





                share|improve this answer


























                  0












                  0








                  0







                  This is fun. Here's a method that plays the game, branching off each possible move (or at any rate, that's the intention).



                  Although my preference is usually to concat and return a pure result, to allow for an early exit and inspection, this recursion accumulates in a global variable.



                  import copy
                  import json
                  import time

                  s = set()
                  rs =

                  def f():
                  """
                  111
                  111000
                  111000000
                  1001001
                  10010010
                  100100100
                  1010100
                  100010001
                  """
                  wins = [0007,0070,0700,0111,0222,0444,0124,0421]
                  def winner(board):
                  # check xs or os individual board for a win
                  for i in wins:
                  if not (i ^ (board & i)):
                  return True
                  return False

                  # xs board, os board, move-number, game
                  def g(xs, os, move, result):
                  # allow for early exit
                  global rs
                  if (len(rs) > 20000):
                  return

                  # base case, win or draw
                  if winner(xs) or winner(os) or move == 9:
                  #print "{0:b}".format(xs)
                  #print "{0:b}".format(os)
                  #print (result, xs, os)
                  #print

                  # confirm we're not duplicating results
                  enc = json.dumps(result)
                  if enc in s:
                  print "Duplicate!"
                  print result
                  s.add(enc)

                  # accumulate results
                  rs.append((result, xs, os))
                  return

                  board = xs | os

                  for i in xrange(9):
                  # candidate move
                  m = 1 << i

                  # valid move
                  if not (m & board):
                  _result = copy.deepcopy(result)

                  # 'O' plays on odd numbered moves
                  if move & 1:
                  _result[i] = [1, move]
                  g(xs, os | m, move + 1, _result)

                  # 'X' plays on even numbered moves
                  else:
                  _result[i] = [0, move]
                  g(xs | m, os, move + 1, _result)

                  # start the recursion
                  g(0, 0, 0, [[-1, -1]] * 9)

                  start_time = time.time()
                  f()
                  print("--- %s seconds ---" % (time.time() - start_time))


                  Output:



                  """
                  rs[2002]

                  => ([[0, 0], [1, 1], [-1, -1],
                  [-1, -1], [1, 5], [0, 2],
                  [0, 4], [1, 3], [-1, -1]], 97, 146)

                  x--
                  ---
                  ---

                  xo-
                  ---
                  ---

                  xo-
                  --x
                  ---

                  xo-
                  --x
                  -o-

                  xo-
                  --x
                  xo-

                  xo-
                  -ox
                  xo-
                  """





                  share|improve this answer













                  This is fun. Here's a method that plays the game, branching off each possible move (or at any rate, that's the intention).



                  Although my preference is usually to concat and return a pure result, to allow for an early exit and inspection, this recursion accumulates in a global variable.



                  import copy
                  import json
                  import time

                  s = set()
                  rs =

                  def f():
                  """
                  111
                  111000
                  111000000
                  1001001
                  10010010
                  100100100
                  1010100
                  100010001
                  """
                  wins = [0007,0070,0700,0111,0222,0444,0124,0421]
                  def winner(board):
                  # check xs or os individual board for a win
                  for i in wins:
                  if not (i ^ (board & i)):
                  return True
                  return False

                  # xs board, os board, move-number, game
                  def g(xs, os, move, result):
                  # allow for early exit
                  global rs
                  if (len(rs) > 20000):
                  return

                  # base case, win or draw
                  if winner(xs) or winner(os) or move == 9:
                  #print "{0:b}".format(xs)
                  #print "{0:b}".format(os)
                  #print (result, xs, os)
                  #print

                  # confirm we're not duplicating results
                  enc = json.dumps(result)
                  if enc in s:
                  print "Duplicate!"
                  print result
                  s.add(enc)

                  # accumulate results
                  rs.append((result, xs, os))
                  return

                  board = xs | os

                  for i in xrange(9):
                  # candidate move
                  m = 1 << i

                  # valid move
                  if not (m & board):
                  _result = copy.deepcopy(result)

                  # 'O' plays on odd numbered moves
                  if move & 1:
                  _result[i] = [1, move]
                  g(xs, os | m, move + 1, _result)

                  # 'X' plays on even numbered moves
                  else:
                  _result[i] = [0, move]
                  g(xs | m, os, move + 1, _result)

                  # start the recursion
                  g(0, 0, 0, [[-1, -1]] * 9)

                  start_time = time.time()
                  f()
                  print("--- %s seconds ---" % (time.time() - start_time))


                  Output:



                  """
                  rs[2002]

                  => ([[0, 0], [1, 1], [-1, -1],
                  [-1, -1], [1, 5], [0, 2],
                  [0, 4], [1, 3], [-1, -1]], 97, 146)

                  x--
                  ---
                  ---

                  xo-
                  ---
                  ---

                  xo-
                  --x
                  ---

                  xo-
                  --x
                  -o-

                  xo-
                  --x
                  xo-

                  xo-
                  -ox
                  xo-
                  """






                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered Nov 24 '18 at 12:55









                  גלעד ברקןגלעד ברקן

                  12.4k21441




                  12.4k21441























                      0














                      I recommend you watch this video on youtube. The professor teaches really nicely about recursion. I think it will benefit for you more, then getting a working code. He uses sudoku as an example, but both games are just 2D arrays.



                      If you watched the video, you will know how to modify this example to better suit your needs.
                      A pseudo code:



                      def place(who, when, where, table):
                      if (None, None) not in table: # the table is full
                      print(table)
                      return

                      if table[where] not (None, None): # this cell is already marked
                      return

                      table[where] (who, when) # can place our mark on the cell
                      # make the recursive calls
                      for i in range(9):
                      place(who.opponent, when+1, i, table)

                      for cell in range(9):
                      empty = [(None, None) for _ in range(9)]
                      place(firstplayer, 0, cell, empty)





                      share|improve this answer






























                        0














                        I recommend you watch this video on youtube. The professor teaches really nicely about recursion. I think it will benefit for you more, then getting a working code. He uses sudoku as an example, but both games are just 2D arrays.



                        If you watched the video, you will know how to modify this example to better suit your needs.
                        A pseudo code:



                        def place(who, when, where, table):
                        if (None, None) not in table: # the table is full
                        print(table)
                        return

                        if table[where] not (None, None): # this cell is already marked
                        return

                        table[where] (who, when) # can place our mark on the cell
                        # make the recursive calls
                        for i in range(9):
                        place(who.opponent, when+1, i, table)

                        for cell in range(9):
                        empty = [(None, None) for _ in range(9)]
                        place(firstplayer, 0, cell, empty)





                        share|improve this answer




























                          0












                          0








                          0







                          I recommend you watch this video on youtube. The professor teaches really nicely about recursion. I think it will benefit for you more, then getting a working code. He uses sudoku as an example, but both games are just 2D arrays.



                          If you watched the video, you will know how to modify this example to better suit your needs.
                          A pseudo code:



                          def place(who, when, where, table):
                          if (None, None) not in table: # the table is full
                          print(table)
                          return

                          if table[where] not (None, None): # this cell is already marked
                          return

                          table[where] (who, when) # can place our mark on the cell
                          # make the recursive calls
                          for i in range(9):
                          place(who.opponent, when+1, i, table)

                          for cell in range(9):
                          empty = [(None, None) for _ in range(9)]
                          place(firstplayer, 0, cell, empty)





                          share|improve this answer















                          I recommend you watch this video on youtube. The professor teaches really nicely about recursion. I think it will benefit for you more, then getting a working code. He uses sudoku as an example, but both games are just 2D arrays.



                          If you watched the video, you will know how to modify this example to better suit your needs.
                          A pseudo code:



                          def place(who, when, where, table):
                          if (None, None) not in table: # the table is full
                          print(table)
                          return

                          if table[where] not (None, None): # this cell is already marked
                          return

                          table[where] (who, when) # can place our mark on the cell
                          # make the recursive calls
                          for i in range(9):
                          place(who.opponent, when+1, i, table)

                          for cell in range(9):
                          empty = [(None, None) for _ in range(9)]
                          place(firstplayer, 0, cell, empty)






                          share|improve this answer














                          share|improve this answer



                          share|improve this answer








                          edited Nov 26 '18 at 21:32

























                          answered Nov 22 '18 at 20:32









                          handrashandras

                          419115




                          419115






























                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to Stack Overflow!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53437620%2frecursively-generate-every-tic-tac-toe-game-in-python%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              404 Error Contact Form 7 ajax form submitting

                              How to know if a Active Directory user can login interactively

                              TypeError: fit_transform() missing 1 required positional argument: 'X'