latin_squares.c
1.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
* latin_squares.c
*
* Created on: 12/04/2017
* Author: pedro
*
* https://www.cril.univ-artois.fr/~lecoutre/benchmarks.html#
*
* Pandiagonal Latin Square problem:
* All rows and columns of a matrix must contain different values (taken from 0 to n-1).
*
*/
#include "latin_squares.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "../config.h"
#include "../constraints/fake_all_different.h"
#include "../split.h"
#include "../variables.h"
/*
* Solve an instance of Latin Square problem with N values
*/
void run_latin_squares(int* csp_dims) {
int n = csp_dims[0];
unsigned long result;
int i, j;
// vector with the IDs of all the variables
unsigned int** vs_id = malloc((unsigned int)n * 2 * sizeof(unsigned int*));
for (i = 0; i < n * 2; i++) {
vs_id[i] = malloc((unsigned int)n * 2 * sizeof(unsigned int));
}
unsigned int* c_vs_id = malloc((unsigned int)n * sizeof(unsigned int));
// Create all the variables
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
vs_id[i][j] = v_new_range(0, (unsigned int)n - 1, true);
}
}
// horizontal lines all_diff constraints
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c_vs_id[j] = vs_id[i][j];
}
c_fake_all_different(c_vs_id, (unsigned int)n);
}
// vertical lines all_diff constraints
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c_vs_id[j] = vs_id[j][i];
}
c_fake_all_different(c_vs_id, (unsigned int)n);
}
if (FINDING_ONE_SOLUTION) {
printf("\nFinding one solution for Latin Squares with %u numbers.\n", n);
} else {
printf("\nCounting all the solutions for Latin Squares with %u numbers.\n", n);
}
// Solve the CSP
result = solve_CSP();
if (FINDING_ONE_SOLUTION && result == 1) {
printf("Solution:\n");
for (i = 0; i < n; i++) {
vs_print_single_val(vs_id[i], (unsigned int)n, 1);
printf("\n");
}
} else {
printf("%lu solution(s) found\n", result);
}
for (i = 0; i < n * 2; i++) {
free(vs_id[i]);
}
free(vs_id);
free(c_vs_id);
}