blackorangebox
BAN USER>> we list the paths by using DFS
What is DFS?
look at my programmatic solution blow. it's almost the same you offered.
- blackorangebox December 04, 2010I created a programmatic solution for the case. It uses almost full tree of field combination and don't seem to sweet cause is't bruteforce.
package test;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
public class TicTacToe {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println("Game processing started.");
Level init = Level.getInitialLevel(true);
int c = init.getGamesCount();
System.out.println("\n---------------------------------------");
System.out.println("Games count for X-starter player = " + c);
System.out.println("Games count for both players = " + c * 2);
System.out.println("---------------------------------------");
System.out.println("Total field object created: "
+ Field.totalFieldsCount);
System.out.println("Total level object created: "
+ Level.totalLevelsCount);
System.out.println("Note: 9! is " + fact(9));
System.out.println("Total game processing time: "
+ (System.currentTimeMillis() - start) / 1000.0 + " s.");
}
static class Field {
static long totalFieldsCount = 0;
static int MAX_FIELD_CELLS = 9;
BitSet cells = new BitSet(MAX_FIELD_CELLS);
// true means cell is empty
BitSet emptyCells = new BitSet(MAX_FIELD_CELLS);
public Field() {
emptyCells.flip(0, MAX_FIELD_CELLS);
}
public Field(Field prevLevField) {
totalFieldsCount++;
cells = (BitSet) prevLevField.cells.clone();
emptyCells = (BitSet) prevLevField.emptyCells.clone();
}
public String getCellContentsForToString(int idx) {
if (emptyCells.get(idx)) {
return "_ ";
} else {
return cells.get(idx) ? "X " : "O ";
}
}
public String toString() {
StringBuilder buff = new StringBuilder();
buff.append(getCellContentsForToString(0));
buff.append(getCellContentsForToString(1));
buff.append(getCellContentsForToString(2));
buff.append("\n");
buff.append(getCellContentsForToString(3));
buff.append(getCellContentsForToString(4));
buff.append(getCellContentsForToString(5));
buff.append("\n");
buff.append(getCellContentsForToString(6));
buff.append(getCellContentsForToString(7));
buff.append(getCellContentsForToString(8));
buff.append("\n");
return buff.toString();
}
boolean putVal(int idx, boolean player) {
if (!emptyCells.get(idx)) {
throw new IllegalArgumentException(String.format(
"Cell with idx %s is not empty.", idx));
}
emptyCells.set(idx, false);
cells.set(idx, player);
return checkIsGameOver();
}
boolean makeMove(BitSet foreignEmptySections, boolean player) {
int clearIdx = foreignEmptySections.nextSetBit(0);
foreignEmptySections.set(clearIdx, false);
return putVal(clearIdx, player);
}
private boolean checkIsGameOver() {
if (getEmptySectionsCount() == 0) {
return true;
}
if (checkLineIsWinLine(0, 1, 2) || checkLineIsWinLine(3, 4, 5)
|| checkLineIsWinLine(6, 7, 8)
|| checkLineIsWinLine(0, 3, 6)
|| checkLineIsWinLine(1, 4, 7)
|| checkLineIsWinLine(2, 5, 8)
|| checkLineIsWinLine(0, 4, 8)
|| checkLineIsWinLine(2, 4, 6)) {
System.out.println(toString());
return true;
}
return false;
}
boolean checkLineIsWinLine(int i1, int i2, int i3) {
if (!emptyCells.get(i1) && !emptyCells.get(i2)
&& !emptyCells.get(i3)) {
if (cells.get(i1) && cells.get(i2) && cells.get(i3)) {
return true;
}
if (!cells.get(i1) && !cells.get(i2) && !cells.get(i3)) {
return true;
}
}
return false;
}
public int getEmptySectionsCount() {
return emptyCells.cardinality();
}
public BitSet getEmptyCells() {
return (BitSet) emptyCells.clone();
}
}
static class Level {
int levelDepth = 0;
List<Field> fields = new ArrayList<Field>(9);
boolean currentPlayer;
Field prevLevField;
public static Level getInitialLevel(boolean player) {
Field prevLevField = new Field();
return new Level(prevLevField, player, 0);
}
public int getGamesCount() {
return makeMove();
}
public static int totalLevelsCount = 0;
public Level(Field prevLevField, boolean currentPlayer, int levelDepth) {
totalLevelsCount++;
this.levelDepth = levelDepth;
this.currentPlayer = currentPlayer;
this.prevLevField = prevLevField;
int emptyCells = prevLevField.getEmptySectionsCount();
for (int i = 0; i < emptyCells; i++) {
fields.add(new Field(prevLevField));
}
}
int makeMove() {
// System.out.println("level depth = " + levelDepth);
BitSet prevLevFieldEmptyCells = prevLevField.getEmptyCells();
int gamesCounter = 0;
for (Field field : fields) {
// System.out.println(field);
boolean gameOver = field.makeMove(prevLevFieldEmptyCells,
currentPlayer);
// System.out.println(field);
if (gameOver) {
// System.out.print("0");
gamesCounter++;
continue;
}
Level nextLevel = new Level(field, !currentPlayer,
levelDepth + 1);
gamesCounter += nextLevel.makeMove();
}
return gamesCounter;
}
}
private static int fact(int in) {
if (in == 0) {
return 1;
}
return in * fact(--in);
}
}
output:
---------------------------------------
Games count for X-starter player = 255168
Games count for both players = 510336
---------------------------------------
Total field object created: 549945
Total level object created: 294778
Note: 9! is 362880
Total game processing time: 7.512 s.
For next 10 elements it's straightforward progression of pascal's triangle third line:
>>0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55,
And then pascal's progression fails:
>> 10=63, 11=69, 12=73, 13=75,
should be 66, 78 ..
that's ok, as of ".. answer is 2", distance is what we need
- blackorangebox December 08, 2010