Pedro Roque / PHACT_src

Blame view

src/csps/sudoku.c 3.77 KB
Edit Raw Normal View History
94b2b13d   Pedro Roque   PHACT source 
1
2
3
4
 
/*
 * sudoku.c
 *
 *  Created on: 23/08/2014
4d26a735   Pedro Roque   Increased recogni... 
5
 
 *      Author: pedro
94b2b13d   Pedro Roque   PHACT source 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
 *
 *      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
4d26a735   Pedro Roque   Increased recogni... 
25
26
 
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 } };
94b2b13d   Pedro Roque   PHACT source 
27
28
 

// 3 solutions, easy
4d26a735   Pedro Roque   Increased recogni... 
29
30
 
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 } };
94b2b13d   Pedro Roque   PHACT source 
31
32
 

// one solution, medium difficulty
4d26a735   Pedro Roque   Increased recogni... 
33
34
35
 
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, _, _ } };
94b2b13d   Pedro Roque   PHACT source 
36
37
 

// one solution, hard
4d26a735   Pedro Roque   Increased recogni... 
38
39
40
 
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, _ } };
94b2b13d   Pedro Roque   PHACT source 
41
42
 

// no solutions
4d26a735   Pedro Roque   Increased recogni... 
43
44
45
 
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 } };
94b2b13d   Pedro Roque   PHACT source 
46
47
48
49
 

/*
 * Solve one of the above sudoku puzzles
 */
4d26a735   Pedro Roque   Increased recogni... 
50
 
void run_sudoku(int* csp_dims) {
94b2b13d   Pedro Roque   PHACT source 
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
	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] == _) {
4d26a735   Pedro Roque   Increased recogni... 
66
 
				vs_id[i][j] = v_new_range(0, (unsigned int)n - 1, true);
94b2b13d   Pedro Roque   PHACT source 
67
 
			} else {
4d26a735   Pedro Roque   Increased recogni... 
68
 
				vs_id[i][j] = v_new_range((unsigned int)sudoku[i][j] - 1, (unsigned int)sudoku[i][j] - 1, false);
94b2b13d   Pedro Roque   PHACT source 
69
70
71
72
73
74
75
76
77
 
			}
		}
	}

	// horizontal lines all_diff constraints
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			c_vs[j] = vs_id[i][j];
		}
4d26a735   Pedro Roque   Increased recogni... 
78
 
		c_all_different(c_vs, (unsigned int)n);
94b2b13d   Pedro Roque   PHACT source 
79
80
81
82
83
84
85
 
	}

	// vertical lines all_diff constraints
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			c_vs[j] = vs_id[j][i];
		}
4d26a735   Pedro Roque   Increased recogni... 
86
 
		c_all_different(c_vs, (unsigned int)n);
94b2b13d   Pedro Roque   PHACT source 
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
	}

	// 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++;
				}
			}
4d26a735   Pedro Roque   Increased recogni... 
101
 
			c_all_different(c_vs, (unsigned int)n);
94b2b13d   Pedro Roque   PHACT source 
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
			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);
	}
}