Argthtjtr

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])

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

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-

"""

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)