ILP Part 78 — Tic-Tac-Toe – Random IT Utensils

This is the seventieth eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the Tic-Tac-Toe riddle.

We have a board with some circles and crosses. We need to fill it with more of these so that no 2 by 2 square has four same characters, and we can separate circles from crosses (each of them create a closed shape).

First part is simple. For separation we need to build a simple path of edges going from top to bottom.

First, the regular model:

public class Point{
	public IVariable Up {get;set;}
	public IVariable Down {get;set;}
	public IVariable Left {get;set;}
	public IVariable Right {get;set;}
	public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }
	public IVariable Identifier {get;set;}	
	public IVariable LowerNeighbourCount {get;set;}
	public List<IVariable> Neighbours {get; set;}
}

public class Point{

public IVariable Up {get;set;}

public IVariable Down {get;set;}

public IVariable Left {get;set;}

public IVariable Right {get;set;}

public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } }

public IVariable Identifier {get;set;}

public IVariable LowerNeighbourCount {get;set;}

public List<IVariable> Neighbours {get; set;}

}

As always, we have edges for directions, and an identifier which we’re going to propagate through the network.

Now the solution:

var board = new int [][]{
	new int[]{0,0,0,0,0,0,0,0,2,0},
	new int[]{0,0,0,0,0,1,2,0,0,0},
	new int[]{0,0,0,1,0,2,0,0,0,0},
	new int[]{0,1,0,0,0,0,0,1,0,0},
	new int[]{0,0,0,1,0,0,0,0,0,0},
	new int[]{0,0,0,0,0,0,0,0,2,0},
	new int[]{0,0,0,0,0,0,2,0,0,0},
	new int[]{0,0,0,0,1,0,0,2,2,0},
	new int[]{0,0,1,1,0,0,0,0,0,0},
	new int[]{0,1,0,0,0,0,0,0,0,0},
};
int height = board.Length;
int width = board[0].Length;

var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

Console.WriteLine("Initialize board");
for(int row=0;row<height;++row){
	for(int column=0;column<width;++column){
		if(board[row][column] > 0){
			fields[row][column].Set<Equal>(solver.FromConstant(board[row][column] == 1 ? 0 : 1));
		}
	}
}

Console.WriteLine("Disallow four equal");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		solver.Operation<Addition>(
			fields[row][column],
			fields[row+1][column],
			fields[row][column+1],
			fields[row+1][column+1]
		).Set<GreaterOrEqual>(solver.FromConstant(1)).Set<LessOrEqual>(solver.FromConstant(3));
	}
}

Console.WriteLine("Create path");		
var points = Enumerable.Range(0, height-1).Select(r => Enumerable.Range(0, width-1).Select(c => new Point(){
	Up = solver.CreateAnonymous(Domain.BinaryInteger),
	Down = solver.CreateAnonymous(Domain.BinaryInteger),
	Left = solver.CreateAnonymous(Domain.BinaryInteger),
	Right = solver.CreateAnonymous(Domain.BinaryInteger),
	Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger),
	Neighbours = new List<IVariable>()
}).ToArray()).ToArray();

Console.WriteLine("Make neighbours see the path the same way");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		if(column < width - 2) points[row][column].Right.Set<Equal>(points[row][column+1].Left);
		if(row < height - 2) points[row][column].Down.Set<Equal>(points[row+1][column].Up);
	}
}

Console.WriteLine("Ban forks");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		var sum = solver.Operation<Addition>(points[row][column].AllDirections);
		sum.Set<LessOrEqual>(solver.FromConstant(2));
		sum.Operation<Subtraction>(solver.FromConstant(1)).Operation<AbsoluteValue>().Set<Equal>(solver.FromConstant(1));
	}
}

Console.WriteLine("Make one entry at the top and one at the bottom");
solver.Operation<Addition>(points[0].Select(p => p.Up).ToArray()).Set<Equal>(solver.FromConstant(1));
solver.Operation<Addition>(points[height - 2].Select(p => p.Down).ToArray()).Set<Equal>(solver.FromConstant(1));

Console.WriteLine("Make no entries to the left nor to the right");
solver.Operation<Addition>(Enumerable.Range(0, height - 1).Select(i => points[i][0].Left).ToArray()).Set<Equal>(solver.FromConstant(0));
solver.Operation<Addition>(Enumerable.Range(0, height - 1).Select(i => points[i][width - 2].Right).ToArray()).Set<Equal>(solver.FromConstant(0));

Console.WriteLine("Separate characters");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		points[row][column].Up.Operation<MaterialImplication>(fields[row][column].Operation<IsNotEqual>(fields[row][column+1])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Down.Operation<MaterialImplication>(fields[row+1][column].Operation<IsNotEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Left.Operation<MaterialImplication>(fields[row][column].Operation<IsNotEqual>(fields[row+1][column])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Right.Operation<MaterialImplication>(fields[row][column+1].Operation<IsNotEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));
		
		points[row][column].Up.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column].Operation<IsEqual>(fields[row][column+1])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Down.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row+1][column].Operation<IsEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Left.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column].Operation<IsEqual>(fields[row+1][column])).Set<Equal>(solver.FromConstant(1));
		points[row][column].Right.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column+1].Operation<IsEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));
	}
}

Console.WriteLine("Propagate identifiers");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();
		
		Point self = points[row][column];
		
		if(row > 0)neighbours.Add(Tuple.Create(points[row-1][column].Identifier, self.Up));
		if(row < height - 2)neighbours.Add(Tuple.Create(points[row+1][column].Identifier, self.Down));
		if(column > 0)neighbours.Add(Tuple.Create(points[row][column-1].Identifier, self.Left));
		if(column < width - 2)neighbours.Add(Tuple.Create(points[row][column+1].Identifier, self.Right));
		
		
		foreach(var n in neighbours){
			var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();
			
			n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}
		
		foreach(var n1 in neighbours){
			foreach(var n2 in neighbours){
				if(n1.Item1 == n2.Item1)continue;
				var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();
				n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));
			}
		}
	}
}

Console.WriteLine("Calculate lower neighbours");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		var result = solver.FromConstant(0);
		var self = points[row][column].Identifier;
		if(row > 0){
			result = result.Operation<Addition>(points[row][column].Up.Operation<Conjunction>(points[row-1][column].Identifier.Operation<IsLessThan>(self)));
			points[row][column].Neighbours.Add(points[row][column].Up);
		}
		if(row < height - 2){
			result = result.Operation<Addition>(points[row][column].Down.Operation<Conjunction>(points[row+1][column].Identifier.Operation<IsLessThan>(self)));
			points[row][column].Neighbours.Add(points[row][column].Down);
		}
		if(column > 0){
			result = result.Operation<Addition>(points[row][column].Left.Operation<Conjunction>(points[row][column-1].Identifier.Operation<IsLessThan>(self)));
			points[row][column].Neighbours.Add(points[row][column].Left);
		}
		if(column < width - 2){
			result = result.Operation<Addition>(points[row][column].Right.Operation<Conjunction>(points[row][column+1].Identifier.Operation<IsLessThan>(self)));
			points[row][column].Neighbours.Add(points[row][column].Right);
		}
		
		points[row][column].LowerNeighbourCount = result;
	}
}

Console.WriteLine("Make fields having correct number of neighbours");
for(int row=0;row<height-1;++row){
	for(int column=0;column<width-1;++column){
		if(row == 0){
			solver.Operation<Disjunction>(points[row][column].Neighbours.ToArray()).Operation<MaterialImplication>(points[row][column].LowerNeighbourCount.Operation<IsLessOrEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}else{
			solver.Operation<Disjunction>(points[row][column].Neighbours.ToArray()).Operation<MaterialImplication>(points[row][column].LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));
		}
	}
}
solver.Operation<Addition>(points[0].Select(p => p.LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(0))).ToArray()).Set<Equal>(solver.FromConstant(1));

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

var board = new int [][]{

new int[]{0,0,0,0,0,0,0,0,2,0},

new int[]{0,0,0,0,0,1,2,0,0,0},

new int[]{0,0,0,1,0,2,0,0,0,0},

new int[]{0,1,0,0,0,0,0,1,0,0},

new int[]{0,0,0,1,0,0,0,0,0,0},

new int[]{0,0,0,0,0,0,0,0,2,0},

new int[]{0,0,0,0,0,0,2,0,0,0},

new int[]{0,0,0,0,1,0,0,2,2,0},

new int[]{0,0,1,1,0,0,0,0,0,0},

new int[]{0,1,0,0,0,0,0,0,0,0},

};

int height = board.Length;

int width = board[0].Length;

var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

Console.WriteLine("Initialize board");

for(int row=0;row<height;++row){

for(int column=0;column<width;++column){

if(board[row][column] > 0){

fields[row][column].Set<Equal>(solver.FromConstant(board[row][column] == 1 ? 0 : 1));

}

Console.WriteLine("Disallow four equal");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

solver.Operation<Addition>(

fields[row][column],

fields[row+1][column],

fields[row][column+1],

fields[row+1][column+1]

).Set<GreaterOrEqual>(solver.FromConstant(1)).Set<LessOrEqual>(solver.FromConstant(3));

}

Console.WriteLine("Create path");

var points = Enumerable.Range(0, height-1).Select(r => Enumerable.Range(0, width-1).Select(c => new Point(){

Up = solver.CreateAnonymous(Domain.BinaryInteger),

Down = solver.CreateAnonymous(Domain.BinaryInteger),

Left = solver.CreateAnonymous(Domain.BinaryInteger),

Right = solver.CreateAnonymous(Domain.BinaryInteger),

Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger),

Neighbours = new List<IVariable>()

}).ToArray()).ToArray();

Console.WriteLine("Make neighbours see the path the same way");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

if(column < width - 2) points[row][column].Right.Set<Equal>(points[row][column+1].Left);

if(row < height - 2) points[row][column].Down.Set<Equal>(points[row+1][column].Up);

}

Console.WriteLine("Ban forks");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

var sum = solver.Operation<Addition>(points[row][column].AllDirections);

sum.Set<LessOrEqual>(solver.FromConstant(2));

sum.Operation<Subtraction>(solver.FromConstant(1)).Operation<AbsoluteValue>().Set<Equal>(solver.FromConstant(1));

}

Console.WriteLine("Make one entry at the top and one at the bottom");

solver.Operation<Addition>(points[0].Select(p => p.Up).ToArray()).Set<Equal>(solver.FromConstant(1));

solver.Operation<Addition>(points[height - 2].Select(p => p.Down).ToArray()).Set<Equal>(solver.FromConstant(1));

Console.WriteLine("Make no entries to the left nor to the right");

solver.Operation<Addition>(Enumerable.Range(0, height - 1).Select(i => points[i][0].Left).ToArray()).Set<Equal>(solver.FromConstant(0));

solver.Operation<Addition>(Enumerable.Range(0, height - 1).Select(i => points[i][width - 2].Right).ToArray()).Set<Equal>(solver.FromConstant(0));

Console.WriteLine("Separate characters");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

points[row][column].Up.Operation<MaterialImplication>(fields[row][column].Operation<IsNotEqual>(fields[row][column+1])).Set<Equal>(solver.FromConstant(1));

points[row][column].Down.Operation<MaterialImplication>(fields[row+1][column].Operation<IsNotEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));

points[row][column].Left.Operation<MaterialImplication>(fields[row][column].Operation<IsNotEqual>(fields[row+1][column])).Set<Equal>(solver.FromConstant(1));

points[row][column].Right.Operation<MaterialImplication>(fields[row][column+1].Operation<IsNotEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));

points[row][column].Up.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column].Operation<IsEqual>(fields[row][column+1])).Set<Equal>(solver.FromConstant(1));

points[row][column].Down.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row+1][column].Operation<IsEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));

points[row][column].Left.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column].Operation<IsEqual>(fields[row+1][column])).Set<Equal>(solver.FromConstant(1));

points[row][column].Right.Operation<BinaryNegation>().Operation<MaterialImplication>(fields[row][column+1].Operation<IsEqual>(fields[row+1][column+1])).Set<Equal>(solver.FromConstant(1));

}

Console.WriteLine("Propagate identifiers");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>();

Point self = points[row][column];

if(row > 0)neighbours.Add(Tuple.Create(points[row-1][column].Identifier, self.Up));

if(row < height - 2)neighbours.Add(Tuple.Create(points[row+1][column].Identifier, self.Down));

if(column > 0)neighbours.Add(Tuple.Create(points[row][column-1].Identifier, self.Left));

if(column < width - 2)neighbours.Add(Tuple.Create(points[row][column+1].Identifier, self.Right));

foreach(var n in neighbours){

var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>();

n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}

foreach(var n1 in neighbours){

foreach(var n2 in neighbours){

if(n1.Item1 == n2.Item1)continue;

var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>();

n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1));

}

Console.WriteLine("Calculate lower neighbours");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

var result = solver.FromConstant(0);

var self = points[row][column].Identifier;

if(row > 0){

result = result.Operation<Addition>(points[row][column].Up.Operation<Conjunction>(points[row-1][column].Identifier.Operation<IsLessThan>(self)));

points[row][column].Neighbours.Add(points[row][column].Up);

}

if(row < height - 2){

result = result.Operation<Addition>(points[row][column].Down.Operation<Conjunction>(points[row+1][column].Identifier.Operation<IsLessThan>(self)));

points[row][column].Neighbours.Add(points[row][column].Down);

}

if(column > 0){

result = result.Operation<Addition>(points[row][column].Left.Operation<Conjunction>(points[row][column-1].Identifier.Operation<IsLessThan>(self)));

points[row][column].Neighbours.Add(points[row][column].Left);

}

if(column < width - 2){

result = result.Operation<Addition>(points[row][column].Right.Operation<Conjunction>(points[row][column+1].Identifier.Operation<IsLessThan>(self)));

points[row][column].Neighbours.Add(points[row][column].Right);

}

points[row][column].LowerNeighbourCount = result;

}

Console.WriteLine("Make fields having correct number of neighbours");

for(int row=0;row<height-1;++row){

for(int column=0;column<width-1;++column){

if(row == 0){

solver.Operation<Disjunction>(points[row][column].Neighbours.ToArray()).Operation<MaterialImplication>(points[row][column].LowerNeighbourCount.Operation<IsLessOrEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}else{

solver.Operation<Disjunction>(points[row][column].Neighbours.ToArray()).Operation<MaterialImplication>(points[row][column].LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1));

}

solver.Operation<Addition>(points[0].Select(p => p.LowerNeighbourCount.Operation<IsEqual>(solver.FromConstant(0))).ToArray()).Set<Equal>(solver.FromConstant(1));

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

First, we define the input. 0 indicates empty field, 1 indicates circle, 2 indicates cross.

We define binary variables for each field indicating what we choose for given field. We then translate existing board in lines 18-25.

Next, we block squares to have the same characters. This is done in lines 27-37 where we make sure that sum is at least one and at most three. If there were four the same characters we’d end up with sum equal to zero or four.

Next, we start building the path. We create variables in lines 39-47, then we make sure neighbours see the same assignments (49-55), and then we ban forks (lines 57-64). Notice that we create crossing points only in the middle of the board, not on the edges. Then we want to make sure that path starts at the top and enters the bottom only once (lines 66-68) and doesn’t touch side edges (70-72).

Next, we want to separate characters. If two fields are separated by a path then they must have different characters (77-80), otherwise they must be the same (82-85).

Finally, we start building the BFS graph to make sure there is only one path. So we propagate identifiers (lines 89-116), and then calculate lower neighbours (lines 118-142) as always.

Finally, we need to make sure that fields in the middle have exactly one lower neighbour, and in the top row there is exactly one point with no lower neighbours. The point would have one edge going to the top (and touching top side of the board) and one other outgoing edge. Since there is no point above the point then the up edge will be ignored, effectively ending with one neighbour only.