sudognu Code

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

#include "sudoku.h"
#include <stdio.h>

/*
 ******************************************************************************/
int two_color(t_sudoku *sudoku, int doElim, int verbosity) {
	int i, j;
	int cc, ncellrow, ncellcol, ncellblk;
	int rrow[2], crow[2], rcol[2], ccol[2], rblk[2], cblk[2], row, col, *r, *c;
	int ret;
	int nelim, tcand, scand, ncolor;
	t_sudoku s1, s2;
	char estr[512];

	/* number of two-color elimination possibilities */
	ncolor = 0;
	
	/* find row, column, block where there are only to cells c1 and c2 with a
	 * given candidate cc */
	for (cc=0; cc<SIZE2; cc++) {
		/* i is block, row, or col */
		for (i=0; i<SIZE2; i++) {
			ncellrow = ncellblk = ncellcol = 0;
			/* j is cell within block, row, or col */
			for (j=0; j<SIZE2; j++) {
				/* row */
				if (sudoku->grid[i][j].cand[cc] != 0) {
					if (ncellrow < 2) {
						rrow[ncellrow] = i;
						crow[ncellrow] = j;
					}
					ncellrow++;
				}
				/* col */
				if (sudoku->grid[j][i].cand[cc] != 0) {
					if (ncellcol < 2) {
						rcol[ncellcol] = j;
						ccol[ncellcol] = i;
					}
					ncellcol++;
				}
				/* blk */
				col = (i / SIZE) * SIZE + (j / SIZE);
				row = (i % SIZE) * SIZE + (j % SIZE);
				if (sudoku->grid[row][col].cand[cc] != 0) {
					if (ncellblk < 2) {
						rblk[ncellblk] = row;
						cblk[ncellblk] = col;
					}
					ncellblk++;
				}
			}
		}
		if (ncellrow == 2) {
			r = rrow;
			c = crow;
		} else if (ncellcol == 2) {
			r = rcol;
			c = ccol;
		} else if (ncellblk == 2) {
			r = rblk;
			c = cblk;
		} else {
			goto next;  /* with next candidate - no cells c1, c2 found */
		}

		/* copy sudoku twice to s1 and s2. insert candidate cc into c1 in s1
		 * and into c2 in s2 and use hidden single technique to eliminate cc
		 * in s1 and s2 far as possible */
		copy_sudoku(*sudoku,&s1);
		insert_val(&s1,r[0],c[0],cc,stat_colortmp);
		ret = hsinglecc(&s1,cc);
		

		if (ret < 0) { /* contradiction --> put cc into c2 of orig. sudoku */
			if (doElim == 1) {
				insert_val(sudoku,r[1],c[1],cc,stat_2color);
				snprintf(estr,511,"c  r%dc%d, (%d) 2-color contradiction",
						r[1]+1,c[1]+1,cc+1);
				fprint_explain(estr,*sudoku,verbosity);
				return(1);
			}
		}

		copy_sudoku(*sudoku,&s2);
		insert_val(&s2,r[1],c[1],cc,stat_colortmp);
		ret = hsinglecc(&s2,cc);

		if (ret < 0) { /* contradiction --> put cc into c1 of orig. sudoku */
			if (doElim == 1) {
				insert_val(sudoku,r[0],c[0],cc,stat_2color);
				snprintf(estr,511,"c  r%dc%d, (%d) 2-color contradiction",
						r[0]+1,c[0]+1,cc+1);
				fprint_explain(estr,*sudoku,verbosity);
				return(1);
			}
		}

		/* if there are rows / columns / blocks that have new solved cells in both
		 * sudokus and more than two cells with the given candidate cc, those extra
		 * candidates can be eliminated */
		nelim = 0;

		/* check rows */
		for (i=0; i<SIZE2; i++) {
			tcand = scand = 0;
			for (j=0; j<SIZE2; j++) {
				if (s1.grid[i][j].stat == stat_colortmp) tcand++;
				if (s2.grid[i][j].stat == stat_colortmp) tcand++;
				if (sudoku->grid[i][j].cand[cc] != 0)    scand++;
			}
			if ((tcand == 2) && (scand > 2)) {
				/* eliminate candidates */
				for (j=0; j<SIZE2; j++) {
					if ((sudoku->grid[i][j].cand[cc] != 0)
							&& (s1.grid[i][j].stat != stat_colortmp)
							&& (s2.grid[i][j].stat != stat_colortmp)) {
						/* candidate cc can be eliminated here */
						if (doElim == 1) {
							sudoku->grid[i][j].cand[cc] = 0;
							sudoku->grid[i][j].ncand -= 1;
						}
						nelim++;
					}
				}
			}
		}
		
		/* check columns */
		for (j=0; j<SIZE2; j++) {
			tcand = scand = 0;
			for (i=0; i<SIZE2; i++) {
				if (s1.grid[i][j].stat == stat_colortmp) tcand++;
				if (s2.grid[i][j].stat == stat_colortmp) tcand++;
				if (sudoku->grid[i][j].cand[cc] != 0)  scand++;
			}
			
			if ((tcand == 2) && (scand > 2)) {
				for (i=0; i<SIZE2; i++) {
					if ((sudoku->grid[i][j].cand[cc] != 0)
							&& (s1.grid[i][j].stat != stat_colortmp)
							&& (s2.grid[i][j].stat != stat_colortmp)) {
						if (doElim == 1) {
							sudoku->grid[i][j].cand[cc] = 0;
							sudoku->grid[i][j].ncand -= 1;
						}
						nelim++;
					}
				}
			}
		}

		/* check blocks */
		for (i=0; i<SIZE2; i++) {
			tcand = scand = 0;
			for (j=0; j<SIZE2; j++) {
				col = (i / SIZE) * SIZE + (j / SIZE);
				row = (i % SIZE) * SIZE + (j % SIZE);
				if (s1.grid[row][col].stat == stat_colortmp) tcand++;
				if (s2.grid[row][col].stat == stat_colortmp) tcand++;
				if (sudoku->grid[row][col].cand[cc] != 0)  scand++;
			}
			if ((tcand == 2) && (scand > 2)) {
				for (j=0; j<SIZE2; j++) {
					col = (i / SIZE) * SIZE + (j / SIZE);
					row = (i % SIZE) * SIZE + (j % SIZE);
					if ((sudoku->grid[row][col].cand[cc] != 0)
							&& (s1.grid[row][col].stat != stat_colortmp)
							&& (s2.grid[row][col].stat != stat_colortmp)) {
						if (doElim == 1) {
							sudoku->grid[row][col].cand[cc] = 0;
							sudoku->grid[row][col].ncand -= 1;
						}
						nelim++;
					}
				}
			}
		}

		/* return after 1st successful color elimination candidate */
		if (nelim > 0) {
			ncolor++;
			if (doElim == 1) {
				snprintf(estr,511,"c  r%dc%d, r%dc%d, (%d) 2-color elimination, -%d candidates",
					r[0]+1,c[0]+1,r[1]+1,c[1]+1,cc+1,nelim);
				fprint_explain(estr,*sudoku,verbosity);
				return ncolor;
			}
		}
		next: ;
	}
	
	return ncolor;
}