/*
 * Copyright (C) 2022 Camden Dixie O'Brien
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public
 * License along with this program.  If not, see
 * <https://www.gnu.org/licenses/>.
 */

#include "solve.h"
#include "lut.h"

#include <stdio.h>

static void setpval(struct sudoku *sud, unsigned i, uint16_t pval)
{
	unsigned val;
	for (val = 0; val < NDIGITS; ++val) {
		if (pval & 1) {
			update(sud, i, val);
			return;
		}
		pval >>= 1;
	}
}

int solve(struct sudoku *sud)
{
	unsigned n, i, j, val;
	int match;
	uint16_t valmask, pvals;

	for (n = 0;; ++n) {
		match = 0;

		for (i = 0; i < NCELLS; ++i) {
			if (DET(sud->cells[i]))
				continue;

			/*
			 * Check if there's only one possible value this cell
			 * can have.
			 */
			pvals = sud->cells[i] & PVALSMASK;
			for (val = 0; val < NDIGITS; ++val) {
				if (pvals & 1) {
					if (pvals == 1) {
						update(sud, i, val);
						match = 1;
						goto next_cell;
					}
					break;
				}
				pvals >>= 1;
			}

			/*
			 * Check if there's a possible value unique to this
			 * cell in its row.
			 */
			valmask = 0;
			for (j = 0; j < NGROUP; ++j)
				valmask |= sud->cells[rowidx_lut[i][j]];
			if ((pvals = sud->cells[i] & ~valmask)) {
				setpval(sud, i, pvals);
				match = 1;
				continue;
			}

			/*
			 * Check if there's a possible value unique to this
			 * cell in its column.
			 */
			valmask = 0;
			for (j = 0; j < NGROUP; ++j)
				valmask |= sud->cells[colidx_lut[i][j]];
			if ((pvals = sud->cells[i] & ~valmask)) {
				setpval(sud, i, pvals);
				match = 1;
				continue;
			}

			/*
			 * Check if there's a possible value unique to this
			 * cell in its segment.
			 */
			valmask = 0;
			for (j = 0; j < NGROUP; ++j)
				valmask |= sud->cells[segidx_lut[i][j]];
			if ((pvals = sud->cells[i] & ~valmask)) {
				setpval(sud, i, pvals);
				match = 1;
				continue;
			}

		next_cell:;
		}

		/* Exit if no matches. */
		if (!match)
			return n;
	}
}