Generate list of all possible unfinished tic-tac-toe positions in Java, considering symmetry

Question

Given that

• A board is possible if it could occur in a Tic-Tac-Toe game
• An empty board counts as a valid solution
• The board cannot be "finished" (i.e., neither side can have three pieces in a row)
• If two boards differ only by reflection or rotation, they are counted as the same position

How many such positions exist and how can I get an list of them. I tried this:

import java.util.ArrayList;
import java.util.Arrays;

public class Second {
static ArrayList<int[]> arr = new ArrayList<int[]>();
static int[] board = new int[9];

public static void main(String[] args) {
    for(int i = 0; i < 19683; ++i){
        int c = i;
        for (int j = 0; j < 9; ++j){
            board[j] = c%3;
            c /= 3;
        }  

        //Check for Xs and Os
        int diff = 0;
        for(int x : board){
            if(x==1){
                diff++;
            }else if(x==2){
                diff--;
            }
        }
        if(diff==0 || diff==1){
            add(board);
        }
    }   
    System.out.println(arr.size());
}

public static void add(int[] board){
    //If the board is won by either side
    if(isCompleted(board)){return;}

    //Get all possible arrangements
    int[] board1 = {board[6],board[7],board[8],   board[3],board[4],board[5],   board[0],board[1],board[2]};
    int[] board2 = {board[2],board[1],board[0],   board[5],board[4],board[3],   board[8],board[7],board[6]};
    int[] board3 = {board[8],board[5],board[2],   board[7],board[4],board[1],   board[6],board[3],board[0]};
    int[] board4 = {board[0],board[3],board[6],   board[1],board[4],board[7],   board[2],board[5],board[8]};
    int[] board5 = {board[2],board[5],board[8],   board[1],board[4],board[7],   board[0],board[3],board[6]};
    int[] board6 = {board[8],board[7],board[6],   board[5],board[4],board[3],   board[2],board[1],board[0]};
    int[] board7 = {board[6],board[3],board[0],   board[7],board[4],board[1],   board[8],board[5],board[2]};

    int[][] boards = {board1, board2, board3, board4, board5, board6, board7};

    //Find the smallest of the 8 possible arrangements
    int[] smallestBoard = board;
    for(int k=0; k<7; k++){
        if(isGreater(boards[k], smallestBoard)){
            smallestBoard = boards[k];
        }
    }

    for(int[] x : arr){
        if(Arrays.equals(x, smallestBoard)){
            return;
        }
    }
    arr.add(smallestBoard);     
}

public static boolean isCompleted(int[] board){
    int piece = 1;

    if(isAll(piece, new int[]{board[0], board[1], board[2]})){return true;}
    if(isAll(piece, new int[]{board[3], board[4], board[5]})){return true;}
    if(isAll(piece, new int[]{board[6], board[7], board[8]})){return true;}
    if(isAll(piece, new int[]{board[0], board[3], board[6]})){return true;}
    if(isAll(piece, new int[]{board[1], board[4], board[7]})){return true;}
    if(isAll(piece, new int[]{board[2], board[5], board[8]})){return true;}
    if(isAll(piece, new int[]{board[0], board[4], board[8]})){return true;}
    if(isAll(piece, new int[]{board[2], board[4], board[6]})){return true;}

    piece = 2;

    if(isAll(piece, new int[]{board[0], board[1], board[2]})){return true;}
    if(isAll(piece, new int[]{board[3], board[4], board[5]})){return true;}
    if(isAll(piece, new int[]{board[6], board[7], board[8]})){return true;}
    if(isAll(piece, new int[]{board[0], board[3], board[6]})){return true;}
    if(isAll(piece, new int[]{board[1], board[4], board[7]})){return true;}
    if(isAll(piece, new int[]{board[2], board[5], board[8]})){return true;}
    if(isAll(piece, new int[]{board[0], board[4], board[8]})){return true;}
    if(isAll(piece, new int[]{board[2], board[4], board[6]})){return true;}

    return false;
}

public static boolean isGreater(int[] first, int[] second){
    for(int j=0; j<9; j++){
        if(first[j]>second[j]){return true;}
        if(second[j]>first[j]){return false;}
    }
    return true;
}

public static boolean isAll(int value, int[] arr){
    for(int x : arr){
        if(x != value){
            return false;
        }
    }
    return true;
}

}

This gives a result of 628 possible positions. However, Michal Forišek's answer to a Quora question gives the answer of 630 positions, including three which I don't have. My program also outputs [2, 2, 2, 2, 2, 2, 2, 2, 2] as a valid positions, which it can't be.

Answer 1

The basic problem is that you never backtrack. You start with an empty board and make a linear-script set of nine moves, filling the board. There are no more possible moves, so the algorithm terminates, leaving arr holding only those nine positions, the squares occupied in order.

To get proper coverage, make board a dynamic variable, rather than a static attribute of the class. Pass it as a parameter to playThrough, so that each instance has its own copy. This isn't a space problem: your call stack has a max depth of 10.

Handling the board dynamically will let the run-time stack manage your backtracking (since each instance maintains its own partial-game state).

I do hope that you're braced for the volume of solutions; 9! isn't large by some standards, but your array of 9! integer arrays of size 9 is something to consider.