sudognu Code

/*
 * This file is part of sudognu.
 *
 * Copyright (C) 2007 Jens Baaran, Germany.
 ******************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "sudoku.h"

/*
 ******************************************************************************/
int single(t_sudoku *sudoku, int doElim, int verbosity) {
	
	int size = sudoku->size;
	int r, c, cc, ns=0;
	char estr[512];
	
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if (sudoku->grid[r][c].ncand == 1) {
				if (doElim == 1) {
					for (cc=0; cc<size; cc++) {
						if (sudoku->grid[r][c].cand[cc] > 0) {
							sudoku->grid[r][c].value = sudoku->grid[r][c].cand[cc];
							if (sudoku->grid[r][c].stat == stat_free) sudoku->grid[r][c].stat  = stat_single;
							sprintf(estr,"-  r%dc%d, (%d) single",r+1,c+1,sudoku->grid[r][c].cand[cc]);
							remove_candidates(sudoku,r,c);
							fprint_explain(estr,*sudoku,verbosity);
							return(1);
						}
					}
				} else {
					ns++;
				}
			}
		}
	}
	if (doElim == 1)
		return(-1);
	else
		return(ns);
}

/*
 ******************************************************************************/
int tuple(t_sudoku *sudoku, int tuple, int doElim, int verbosity) {
	
	int size = sudoku->size;
	int r, c, br, bc, *cc, ntup = 0;
	int rowVals[SIZE2], colVals[SIZE2], blkVals[SIZE2];

	cc = (int *) malloc(sizeof(int)*size);
	for (c = 0; c < size; c++) cc[c] = 0;
	
	for (c = 0; c < size; c++) {
		for (r = 0; r < size; r++) {
			rowVals[r] = colVals[r] = blkVals[r] = 0;
		}
		for (r = 0; r < size; r++) {
			if (sudoku->grid[r][c].value != 0) colVals[sudoku->grid[r][c].value-1] = 1;
			if (sudoku->grid[c][r].value != 0) rowVals[sudoku->grid[c][r].value-1] = 1;
			br = (c / SIZE) * SIZE + (r / SIZE);
			bc = (c % SIZE) * SIZE + (r % SIZE);
			if (sudoku->grid[br][bc].value != 0) blkVals[sudoku->grid[br][bc].value-1] = 1;
		}
		for (cc[0] = 0; cc[0] < size-tuple+1; cc[0]++) {
			find_tuple(sudoku,tuple,1,c,cc,colVals,rowVals,blkVals,doElim,verbosity,&ntup);
			if ((doElim == 1) && (ntup > 0)) goto done;
		}
	}

	done:
	free(cc);
	return(ntup);
}

/*
 ******************************************************************************/
void find_tuple(
	t_sudoku *sudoku,
	int tuple, int itup, int c, int *cc,
	int colVals[SIZE2], int rowVals[SIZE2], int blkVals[SIZE2],
	int doElim, int verbosity,
	int *ntup) {

	int size = sudoku->size;
	int iqc, checkTuple;
	
	for (cc[itup] = cc[itup-1]+1; cc[itup] < size-tuple+itup+1; cc[itup]++) {
		if (itup+1 < tuple) {
			find_tuple(sudoku,tuple,itup+1,c,cc,colVals,rowVals,blkVals,doElim,verbosity,ntup);
		} else {
			// columns
			checkTuple = 1;
			for (iqc = 0; iqc < tuple; iqc++) if (colVals[cc[iqc]] != 0)
				checkTuple = 0;
			if (checkTuple == 1) {
				tuple_crb(sudoku,tuple,cc,c,'c',doElim,verbosity,ntup);
				if ((doElim == 1) && (*ntup > 0)) return;
			}
			// rows
			checkTuple = 1;
			for (iqc = 0; iqc < tuple; iqc++) if (rowVals[cc[iqc]] != 0)
				checkTuple = 0;
			if (checkTuple == 1) {
				tuple_crb(sudoku,tuple,cc,c,'r',doElim,verbosity,ntup);
				if ((doElim == 1) && (*ntup > 0)) return;
			}
			// blocks
			checkTuple = 1;
			for (iqc = 0; iqc < tuple; iqc++) if (blkVals[cc[iqc]] != 0)
				checkTuple = 0;
			if (checkTuple == 1) {
				tuple_crb(sudoku,tuple,cc,c,'b',doElim,verbosity,ntup);
				if ((doElim == 1) && (*ntup > 0)) return;
			}
		}
	}
}

/*
 ******************************************************************************/
void tuple_crb(t_sudoku *sudoku, int tuple, int *cc, int c, char ent, int doElim, int verbosity, int *ntup) {

	int size = sudoku->size;
	int r, iqc, row, col, nelim;
	int numTupleCells, numTupleCandsWithinCell, numTupleCellsWithOnlyTupleCands;
	int numElimCells;
	int rows[SIZE2], cols[SIZE2], tupCands[SIZE2];
	
	numTupleCells = numTupleCellsWithOnlyTupleCands = numElimCells = 0;
	for (r = 0; r < size; r++) {
		switch (ent) {
		case 'c':
			col=c; row=r; break;
		case 'r':
			col=r; row=c; break;
		case 'b':
			row = (c / SIZE) * SIZE + (r / SIZE);
			col = (c % SIZE) * SIZE + (r % SIZE);
			break;
		}
		numTupleCandsWithinCell = 0;
		for (iqc = 0; iqc < tuple; iqc++) {
			if (sudoku->grid[row][col].cand[cc[iqc]] != 0) {
				if (numTupleCandsWithinCell == 0) {
					numTupleCells++;
				}
				numTupleCandsWithinCell++;
			}
		}
		if (numTupleCandsWithinCell > 0) {
			if (sudoku->grid[row][col].ncand == numTupleCandsWithinCell) {
				numTupleCellsWithOnlyTupleCands++;
			} else {
				rows[numElimCells] = row;
				cols[numElimCells] = col;
				numElimCells++;
			}
		}
	}
	
	if ((numTupleCells > tuple)
		&& (numTupleCellsWithOnlyTupleCands == tuple)) {

		if (DEBUG) {
			fprintf(stderr,"[%c%d tuple(%d",ent,c+1,cc[0]+1);
			for(iqc = 1; iqc < tuple; iqc++) fprintf(stderr,",%d",cc[iqc]+1);
			fprintf(stderr,")]");
		}

		(*ntup)++;
		
		if (doElim == 1) {
			
			// eliminate
			for (r = 0; r < size; r++) tupCands[r] = 0;
			for (iqc=0; iqc<tuple; iqc++) tupCands[cc[iqc]] = 1;

			nelim = 0;
			for (iqc=0; iqc<numElimCells; iqc++) {
				for (r = 0; r < size; r++) {
					if ((tupCands[r] == 1) && (sudoku->grid[rows[iqc]][cols[iqc]].cand[r] != 0)) {
						nelim++;
						sudoku->grid[rows[iqc]][cols[iqc]].cand[r]  = 0;
						sudoku->grid[rows[iqc]][cols[iqc]].ncand   -= 1;
					}
				}
			}

			// output
			if (verbosity > 0) {
				char entstr[8], tupstr[20], estr[512];

				switch (ent) {
				case 'c':	strcpy(entstr,"column"); break;
				case 'r':	strcpy(entstr,"row");    break;
				case 'b':	strcpy(entstr,"block");  break;
				}

				switch (tuple) {
				case 2: strcpy(tupstr,"double");    break;
				case 3: strcpy(tupstr,"triple");    break;
				case 4: strcpy(tupstr,"quadruple"); break;
				}
			
				if (ent == 'b')
					sprintf(estr,"%c  %c%d%d, (%d",toupper(tupstr[0]),entstr[0],c/3+1,c%3+1,cc[0]+1);
				else
					sprintf(estr,"%c  %c%d, (%d",toupper(tupstr[0]),entstr[0],c+1,cc[0]+1);
				for (iqc=1; iqc<tuple; iqc++)
					sprintf(estr+strlen(estr)," %d",cc[iqc]+1);
				sprintf(estr+strlen(estr),") %s, -%d candidates",tupstr,nelim);
				fprint_explain(estr,*sudoku,verbosity);
			}

			// after elimination return
			return;
		}
	}
}