ILP Part 61 – Sudomino – Random IT Utensils

This is the sixtieth first 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 Sudomino.

We have a Sudoku board filled with dominoes. Some fields are blocked. We need to assign numbers to dominoes in a way that numbers in each row/column are different.

Solution:

var solver = new CplexMilpSolver(23);

var board = @"aabbccdd
22eff6gh
i!e!j6gh
i4kkjl33
!4mm!l!n
oo!pqr6n
!sspqr61
ttuu!vv1".Split(' ');

var width = board[0].Length;
var height = board.Length;

Console.WriteLine("Create variables");
var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()).ToArray();

Console.WriteLine("Set ranges");
for(int row = 0; row < height; ++ row){
	for(int column = 0; column < width; ++ column){
		if(board[row][column] != '!'){
			solver.Set(ConstraintType.LessOrEqual, fields[row][column], solver.FromConstant(6));
			solver.Set(ConstraintType.GreaterOrEqual, fields[row][column], solver.FromConstant(1));
		}
		
		if(char.IsDigit(board[row][column])){
			solver.Set(ConstraintType.Equal, fields[row][column], solver.FromConstant(board[row][column] - '0'));
		}
	}
}

Console.WriteLine("Make dominoes");
for(int row = 0; row < height; ++ row){
	for(int column = 0; column < width; ++ column){
		if(char.IsLetter(board[row][column])){
			for(int row2 = 0; row2 < height;++row2){
				for(int column2=0;column2<width;++column2){
					if(board[row][column] == board[row2][column2]){
						solver.Set(ConstraintType.Equal, fields[row][column], fields[row2][column2]);
					}
				}
			}
		}
	}
}

Console.WriteLine("Set constraints for columns");
for(int row=0;row<height;++row){
	HashSet<char> visited = new HashSet<char>();
	List<IVariable> selected = new List<IVariable>();
	for(int column=0;column<width;++column){
		if(board[row][column] != '!' && !visited.Contains(board[row][column])){
			selected.Add(fields[row][column]);
			visited.Add(board[row][column]);
		}
	}
	
	solver.Set(CompositeConstraintType.AllDifferent, selected[0], selected.Skip(1).ToArray());
}

Console.WriteLine("Set constraints for rows");
for(int column=0;column<width;++column){
	HashSet<char> visited = new HashSet<char>();
	List<IVariable> selected = new List<IVariable>();
	for(int row=0;row<height;++row){
		if(board[row][column] != '!' && !visited.Contains(board[row][column])){
			selected.Add(fields[row][column]);
			visited.Add(board[row][column]);
		}
	}
	
	solver.Set(CompositeConstraintType.AllDifferent, selected[0], selected.Skip(1).ToArray());
}

solver.AddGoal("Goal", solver.FromConstant(0));
solver.Solve();

for(var row = 0; row < height;++row){
	for(var column = 0; column < width; ++ column){
		if(board[row][column] == '!'){
			Console.Write(" ");
		}else{
			Console.Write(solver.GetValue(fields[row][column]));
		}
	}
	Console.WriteLine();
}

var solver = new CplexMilpSolver(23);

var board = @"aabbccdd

22eff6gh

i!e!j6gh

i4kkjl33

!4mm!l!n

oo!pqr6n

!sspqr61

ttuu!vv1".Split(' ');

var width = board[0].Length;

var height = board.Length;

Console.WriteLine("Create variables");

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

Console.WriteLine("Set ranges");

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

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

if(board[row][column] != '!'){

solver.Set(ConstraintType.LessOrEqual, fields[row][column], solver.FromConstant(6));

solver.Set(ConstraintType.GreaterOrEqual, fields[row][column], solver.FromConstant(1));

}

if(char.IsDigit(board[row][column])){

solver.Set(ConstraintType.Equal, fields[row][column], solver.FromConstant(board[row][column] - '0'));

}

Console.WriteLine("Make dominoes");

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

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

if(char.IsLetter(board[row][column])){

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

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

if(board[row][column] == board[row2][column2]){

solver.Set(ConstraintType.Equal, fields[row][column], fields[row2][column2]);

}

Console.WriteLine("Set constraints for columns");

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

HashSet<char> visited = new HashSet<char>();

List<IVariable> selected = new List<IVariable>();

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

if(board[row][column] != '!' && !visited.Contains(board[row][column])){

selected.Add(fields[row][column]);

visited.Add(board[row][column]);

}

solver.Set(CompositeConstraintType.AllDifferent, selected[0], selected.Skip(1).ToArray());

}

Console.WriteLine("Set constraints for rows");

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

HashSet<char> visited = new HashSet<char>();

List<IVariable> selected = new List<IVariable>();

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

if(board[row][column] != '!' && !visited.Contains(board[row][column])){

selected.Add(fields[row][column]);

visited.Add(board[row][column]);

}

solver.Set(CompositeConstraintType.AllDifferent, selected[0], selected.Skip(1).ToArray());

}

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

solver.Solve();

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

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

if(board[row][column] == '!'){

Console.Write(" ");

}else{

Console.Write(solver.GetValue(fields[row][column]));

}

Console.WriteLine();

}

This one should be pretty obvious. Solution:

Solution