path: root/solve.c

#include <stdio.h>
#include <string.h>

#include "debug.h"
#include "update.h"
#include "cell.h"
#include "display.h"

/*
 * For all unsolved cells on the board, solve them if they have been marked as
 * impossible to be 8/9 values
 */
int solve_row_col(struct cell (*b)[9][9])
{
	int change_count = 0;
	int x = 0;
	int y = 0;
	int i = 0;
	int val = 0;
	int total = 0;

	for (y = 0; y < 9; y++)
	{
		total = 0;
		for (x = 0; x < 9; x++)
		{
			if ((*b)[x][y].val != 0)
				continue;

			for (i = 0; i < 9; i++)
			{
				if ((*b)[x][y].not[i])
				{
					total++;
				} else {
					val = i + 1;
				}
			}
			if (total == 8) {
				printf("%c%c must be %d because it is the only missing value in its row or column\n", NAME_CELL(x,y), val);
				DEBUG_LOG("ROW/COL: (%d,%d) must be %d\n", x, y, val);
				(*b)[x][y].val = val;
				change_count++;
			}
		}
	}
	return change_count;
}


/*
 * FIXME rename - cell != cell
 * For all unsolved cells on the board, solve them if they are the only place
 * left in their local 3x3 that a value missing from that 3x3 could fit
 */
int not_to_val_cell(struct cell (*b)[9][9])
{
	int change_count = 0;
	int cx = 0;
	int cy = 0;
	int x = 0;
	int y = 0;
	int n = 0;
	int potentials = 0;
	int okx, oky;
	struct cell *c;

	/* refactor this crap */
	for (cy = 0; cy < 9; cy += 3)
	{
		for (cx = 0; cx < 9; cx += 3)
		{
			/* for each val that has to be in cell */
			for (n = 1; n <= 9; n++)
			{
				for (y = 0; y < 3; y++)
				{
					for (x = 0; x < 3; x++)
					{
						c = &(*b)[cx+x][cy+y];
						if (c->val == n)
						{
							potentials = 0;
							y = 3;
							break;
						}
						if (c->val)
							continue;

						if (c->not[n-1] == 0)
						{
							potentials++;
							okx = x;
							oky = y;
						}
					}
				}
				if (potentials == 1)
				{
					DEBUG_LOG("CELL: (%d,%d) must be %d\n", cx + okx, cy + oky, n);
					printf("%c%c must be %d because it can't be anything else\n",
						NAME_CELL(cx+okx, cy+oky), n);
					(*b)[cx+okx][cy+oky].val = n;
					potentials = 0;
					change_count++;
				} else if(potentials) {
					DEBUG_LOG("CELL: (%d,%d) could be one of %d\n", cx + okx, cy + oky, potentials);
					int k = 0;
					for (k = 0; k < 9; k++) {
						if (!(*b)[cx+okx][cy+oky].not[k]) {
							DEBUG_LOG("   %d", k+1);
						}
					}
					DEBUG_LOG("\n\n");
				}
			}
		}
	}
	return change_count;
}


/* For the numbers 1-9 not filled into a cell, fill in those which have only
 * one place they can go */
int cell_fill_certainties(struct cell (*b)[9][9], int cx, int cy)
{
	int change_count = 0;
	int will_take_count = 0;
	int will_take_x = 0;
	int will_take_y = 0;
//	struct cell *will_take = NULL;
	int val = 0;
	int cell_has[9] = {0};
	int x,y;

	/* Translate cell-based index to tile-based */
	cx *= 3;
	cy *= 3;

	/* First: walk the cell and find which values it has */
	for (x = cx; x < cx + 3; x++) {
		for (y = cy; y < cy + 3; y++) {
			val = (*b)[x][y].val;
			if (val) {
				DEBUG_LOG("CELL_CERT: Cell (%d,%d) has %d\n", cx/3, cy/3, val);
				cell_has[val - 1] = 1;
			}
		}
	}

	/* Second: For all missing values, see if only one tile will take it.
	 * If only one will have it, put it in */
	for (val = 0; val < 9; val++) {

		will_take_count = 0;

		/* Does the cell lack the value? */
		if (!cell_has[val]) {

			DEBUG_LOG("Try to solve for %d\n", val + 1);

			/* Walk the cell and find which tile(s) will take it */
			for (x = cx; x < cx + 3; x++) {
				for (y = cy; y < cy + 3; y++) {
					if ((*b)[x][y].val) {
						continue;
					}
					if ((*b)[x][y].not[val] == 0) {
						will_take_count++;
						will_take_x = x;
						will_take_y = y;
					}
				}
			}
			DEBUG_LOG("will_take_count is %d\n", will_take_count);
			/* Don't make indeterminate choices here*/
			if (will_take_count == 1) {
				printf("%c%c must be %d because it is the only place in its 3x3 this will fit\n",
					NAME_CELL(will_take_x, will_take_y),
					val + 1);
				(*b)[will_take_x][will_take_y].val = val + 1;
				change_count++;
			}
		}
	}
	return change_count;
}

int cells_fill_certainties(struct cell (*b)[9][9])
{
	int change_count = 0;
	int x, y;

	for (x = 0; x < 3; x++) {
		for (y = 0; y < 3; y++) {
			change_count += cell_fill_certainties(b, x, y);
		}
	}
	return change_count;
}

/*
 * Check if every cell on a board is filled.
 * Returns -1 isf the board is not fully
 * Returns 0 if the board is filled
 */
int board_is_filled(struct cell (*b)[9][9])
{
	int x = 0;
	int y = 0;

	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			if ((*b)[x][y].val == 0) {
				return -1;
			}
		}
	}
	return 0;
}

/*
 * Check if all of the rows on are correctly solved on a board
 * Returns 0 for all rows correctly solved
 */
int board_rows_are_solved(struct cell (*b)[9][9])
{
	int row_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	for (y = 0; y < 9; y++) {
		memset(row_has, 0, sizeof(row_has));
		for (x = 0; x < 9; x++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (row_has[val - 1]) {
				DEBUG_LOG("Invalid board: Row %d duplicate %d\n", y, val);
				return -1;
			}
			row_has[val - 1] = 1;
		}
	}

	return 0;
}

/*
 * Check if all of the columns on are correctly solved on a board
 * Returns 0 for all columns correctly solved
 */
int board_cols_are_solved(struct cell (*b)[9][9])
{
	int col_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	for (x = 0; x < 9; x++) {
		memset(col_has, 0, sizeof(col_has));
		for (y = 0; y < 9; y++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (col_has[val - 1]) {
				DEBUG_LOG("Invalid board: Column %d duplicate %d\n", x, val);
				return -1;
			}
			col_has[val - 1] = 1;
		}
	}

	return 0;
}

/*
 * Check if one of the nine 3x3 blocks is correctly solved on a board
 * Returns 0 for a correctly solved 3x3
 */
int board_3_is_solved(struct cell (*b)[9][9], int cx, int cy)
{
	int col_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	cx *= 3;
	cy *= 3;

	for (x = cx; x < cx + 3; x++) {
		for (y = cy; y < cy + 3; y++) {
			val = (*b)[x][y].val;
			if (val == 0) {
				return -1;
			}
			if (col_has[val - 1]) {
				DEBUG_LOG("Invalid board: 3x3 %d duplicate %d\n", x, val);
				return -1;
			}
			col_has[val - 1