/*
 * 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);
	}
}