path: root/solve.c

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

#include "debug.h"
#include "update.h"
#include "cell.h"
#include "display.h"
#include "load.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 (CELL_IS_NOT((*b)[x][y].not, val))
				{
					total++;
				} else {
					val = i;
				}
			}
			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 (box) that a value missing from that box could fit
 */
int not_to_val_cell(struct cell (*b)[9][9])
{
	int change_count = 0;
	int bx = 0;
	int by = 0;
	int x = 0;
	int y = 0;
	int n = 0;
	int potentials = 0;
	int okx, oky;
	struct cell *c;

	/* refactor this crap */
	for (by = 0; by < 9; by += 3)
	{
		for (bx = 0; bx < 9; bx += 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)[bx+x][by+y];
						if (c->val == n)
						{
							potentials = 0;
							y = 3;
							break;
						}
						if (c->val)
							continue;

						if (!CELL_IS_NOT(c->not, n))
						{
							potentials++;
							okx = x;
							oky = y;
						}
					}
				}
				if (potentials == 1)
				{
					DEBUG_LOG("CELL: (%d,%d) must be %d\n", bx + okx, by + oky, n);
					printf("%c%c must be %d because it can't be anything else\n",
						NAME_CELL(bx+okx, by+oky), n);
					(*b)[bx+okx][by+oky].val = n;
					potentials = 0;
					change_count++;
				}
			}
		}
	}
	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 bx, int by)
{
	int change_count = 0;
	int will_take_count = 0;
	int will_take_x = 0;
	int will_take_y = 0;
	int val = 0;
	int cell_has = 0;
	int x,y;

	/* Translate cell-based index to tile-based */
	bx *= 3;
	by *= 3;

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

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

		will_take_count = 0;

		/* Does the cell lack the value? */
		if (!(cell_has & CELL_VALUE_MASK(val))) {

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

			/* Walk the cell and find which tile(s) will take it */
			for (x = bx; x < bx + 3; x++) {
				for (y = by; y < by + 3; y++) {
					if ((*b)[x][y].val) {
						continue;
					}
					if (!CELL_IS_NOT((*b)[x][y].not, val)) {
						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 box this will fit\n",
					NAME_CELL(will_take_x, will_take_y),
					val);
				(*b)[will_take_x][will_take_y].val = val;
				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 boxes is correctly solved on a board
 * Returns 0 for a correctly solved 3x3
 */
int board_box_is_solved(struct cell (*b)[9][9], int bx, int by)
{
	int col_has[9] = {0};
	int val = 0;
	int x = 0;
	int y = 0;

	bx *= 3;
	by *= 3;

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

	return 0;
}

/*
 * Check if all of the nine 3x3 boxes are correctly solved on a board
 * Returns 0 for correctly solved boxes
 */
int board_boxes_are_solved(struct cell (*b)[9][9])
{
	int ret = 0;
	int x = 0;
	int y = 0;
	for (x = 0; x < 3; x++) {
		for (y = 0; y < 3; y++) {
			ret = board_box_is_solved(b, x, y);
			if (ret)
				return ret;
		}
	}
	return ret;
}

/*
 * Check if a board is solved.
 * Returns 0 if the board is solved correctly
 */
int board_is_solved(struct cell (*b)[9][9])
{
	int ret = 0;
	ret = board_is_filled(b);
	if (ret)
		return ret;

	ret = board_rows_are_solved(b);
	if (ret)
		return ret;

	ret = board_cols_are_solved(b);
	if (ret)
		return ret;

	ret = board_boxes_are_solved(b);

	return ret;
}