sudoku.c
3.77 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
88
89
90
91
92
93
94
95
96
97
98
99
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
/*
* sudoku.c
*
* Created on: 23/08/2014
* Author: pedro
*
* 9*9 Sudoku Puzzle:
* All rows, columns, and the 9 disjoint inner squares (3*3 each) cannot contain repeated values
*/
#include "sudoku.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "../config.h"
#include "../constraints/all_different.h"
#include "../split.h"
#include "../variables.h"
#define _ 0 // sudoku empty square
// solved in filter phase
int sudoku_filter[9][9] = { { 4, 1, _, 2, 7, _, 8, _, 5 }, { _, 8, 5, 1, 4, 6, _, 9, 7 }, { _, 7, _, 5, 8, _, _, 4, _ }, { 9, 2, 7, 4, 5, 1, 3, 8, 6 },
{ 5, 3, 8, 6, 9, 7, 4, 1, 2 }, { 1, 6, 4, 3, 2, 8, 7, 5, 9 }, { 8, 5, 2, 7, _, 4, 9, _, _ }, { _, 9, _, 8, _, 2, 5, 7, 4 }, { 7, 4, _, 9, 6, 5, _, 2, 8 } };
// 3 solutions, easy
int sudoku_simple[9][9] = { { 4, 1, _, 2, 7, _, 8, _, 5 }, { _, 8, _, _, 4, 6, _, 9, 7 }, { _, 7, _, 5, 8, _, _, 4, _ }, { 9, 2, _, 4, _, 1, _, 8, 6 },
{ 5, _, 8, _, _, 7, 4, _, 2 }, { 1, _, _, 3, _, 8, _, 5, 9 }, { 8, _, _, 7, _, _, 9, _, _ }, { _, 9, _, _, _, 2, 5, 7, 4 }, { 7, 4, _, 9, _, 5, _, 2, 8 } };
// one solution, medium difficulty
int sudoku_gentle[9][9] = { { _, _, 8, 2, _, 5, _, _, _ }, { _, _, _, _, _, _, _, 9, 6 }, { 2, _, _, 6, 1, _, _, 8, _ }, { 1, 2, _, _, _, 3, _, _, 9 },
{ 3, _, _, _, 5, _, _, _, 7 }, { 8, _, _, 1, _,
_, _, 2, 4 }, { _, 4, _, _, 8, 7, _, _, 1 }, { 7, 3, _, _, _, _, _, _, _ }, { _, _, _, 3, _, 4, 7, _, _ } };
// one solution, hard
int sudoku_hard[9][9] = { { _, 2, _, _, _, 6, 3, _, _ }, { _, _, _, _, 8, _, _, _, 9 }, { 1, _, 6, _, _, _, 4, _, _ }, { 7, _, _, _, 9, _, _, _, _ }, { _, 3, _, 5, _, 7, _, 4, _ },
{ _, _, _, _, 4, _,
_, _, 8 }, { _, _, 8, _, _, _, 2, _, 1 }, { 2, _, _, _, 6, _, _, _, _ }, { _, _, 9, 1, _, _, _, 5, _ } };
// no solutions
int sudoku_unsolvable[9][9] = { { 1, _, _, 9, _, 7, _, _, 3 }, { _, 8, _, _, _, _, _, 7, _ }, { _, _, 9, _, _, _, 6, _, _ }, { _, _, 7, 2, _, 9, 4, _, _ }, { 4, 1, _, _, _, _, _,
9, 5 }, { _, _, 8, 5,
_, 4, 3, _, _ }, { _, _, 3, _, _, _, 7, _, _ }, { _, 5, _, _, _, _, _, 4, _ }, { 2, _, _, 8, _, 6, _, _, 1 } };
/*
* Solve one of the above sudoku puzzles
*/
void run_sudoku(int* csp_dims) {
int n = csp_dims[0];
int (*sudoku)[9] = sudoku_hard;
unsigned int vs_id[9][9];
unsigned int c_vs_itr;
unsigned long result;
int aux = n / 3;
int i, j, k, l, m, p;
// vector with the ID of the variables constrained by all the constraints
unsigned int c_vs[9];
// Create the CSP variables
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (sudoku[i][j] == _) {
vs_id[i][j] = v_new_range(0, (unsigned int)n - 1, true);
} else {
vs_id[i][j] = v_new_range((unsigned int)sudoku[i][j] - 1, (unsigned int)sudoku[i][j] - 1, false);
}
}
}
// horizontal lines all_diff constraints
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c_vs[j] = vs_id[i][j];
}
c_all_different(c_vs, (unsigned int)n);
}
// vertical lines all_diff constraints
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c_vs[j] = vs_id[j][i];
}
c_all_different(c_vs, (unsigned int)n);
}
// squares all_diff constraints
for (l = 0; l < n; l += aux) {
k = 0;
for (m = 0; m < aux; m++) {
p = 0;
c_vs_itr = 0;
for (i = l; i < aux + l; i++) {
for (j = k; j < k + aux; j++) {
c_vs[c_vs_itr++] = vs_id[i][j];
p++;
}
}
c_all_different(c_vs, (unsigned int)n);
k += 3;
}
}
if (FINDING_ONE_SOLUTION) {
printf("\nFinding one solution for Sudoku.\n");
} else {
printf("\nCounting all the solutions for Sudoku.\n");
}
// Solve the CSP
result = solve_CSP();
if (FINDING_ONE_SOLUTION && result == 1) {
printf("Solution:\n");
for (i = 0; i < 9; i++) {
vs_print_single_val(vs_id[i], 9, 1);
printf("\n");
}
} else {
printf("%lu solution(s) found\n", result);
}
}