sudognu Code

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

#include <stdio.h>
#include "sudoku.h"
/*
 ******************************************************************************/
int forcing_chain(t_sudoku *sudoku, int verbosity, int *fcl) {
	
	int size = sudoku->size;
	int r, c, cc, row, col, cand, c0, c1, elim[NUM_ET], ret, eofc0, eofc1;
	int minr, minc, mincand, minfcl, minrv, minstartr, minstartc;
	int fcrow, fccol, fccand, fclen, fcrv, fcstartr, fcstartc;
	int depth;
	status minstat, fcstat;
	char estr[512];
	t_sudoku sudokuc0, sudokuc1;
	
	t_field diffgridc0[SIZE2][SIZE2];
	t_field diffgridc1[SIZE2][SIZE2];
	t_field intgrid[SIZE2][SIZE2];

	extern int dfcs[];

	// minfcl is minimum length of forcing chain, minrv is return value
	// of this function
	minfcl = size*size;
	minrv = 0;
	
	// allowed techniques during forcing chain: .-dDbBtTqQ
	depth = 1;
	while ( (depth < (NUM_ET-1))
			&& (       (dfcs[depth] == et_hs)
					|| (dfcs[depth] == et_s)
					|| (dfcs[depth] == et_hd)
					|| (dfcs[depth] == et_d)
					|| (dfcs[depth] == et_l)
					|| (dfcs[depth] == et_b)
					|| (dfcs[depth] == et_ht)
					|| (dfcs[depth] == et_t)
					|| (dfcs[depth] == et_hq)
					|| (dfcs[depth] == et_q) ) ) {
		depth++;
	}
	depth--;
	
	
	// loop over all cells with only two candidates
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if (sudoku->grid[r][c].ncand == 2) {
				
				// copy grid twice
				copy_sudoku(*sudoku,&sudokuc0);
				copy_sudoku(*sudoku,&sudokuc1);
				
				// put candidates into copied grids
				cc = 0;
				while ((cc < size) && (sudoku->grid[r][c].cand[cc] == 0)) cc++;
				c0 = cc;
				sudokuc0.grid[r][c].value = sudoku->grid[r][c].cand[cc];
				sudokuc0.grid[r][c].stat = stat_guess;
				remove_candidates(&sudokuc0,r,c);

				cc++;
				while ((cc < size) && (sudoku->grid[r][c].cand[cc] == 0)) cc++;
				c1 = cc;
				sudokuc1.grid[r][c].value = sudoku->grid[r][c].cand[cc];
				sudokuc1.grid[r][c].stat = stat_guess;
				remove_candidates(&sudokuc1,r,c);

				// continue elimination until there is a corresponding cell value or
				// until end of forcing chain
				fclen = eofc0 = eofc1 = fcrv = 0;				
				do {
					// fill in hidden single or single
					if ((eofc0 == 0) && (apply_solution_technique1(&sudokuc0,elim,depth,0,stdout) <= 0)) {
						ret = check_sudoku(sudokuc0);
						if (ret == 0) {
							// end of sudoku: row r, col c, cand c0+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c0+1;
							fcstat = stat_guess; // have to include this cell for uniqueness check
							fcrv = 1;
							eofc0 = eofc1 = 1;
						} else if (ret < 0) {
							// contradiction: row r, col c, cand c1+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c1+1;
							fcstat = stat_fchain;
							fcrv = 2;
							eofc0 = eofc1 = 1;
						} else {
							// end of this part of forcing chain
							eofc0 = 1;
						}
					}
					if ((eofc1 == 0) && (apply_solution_technique1(&sudokuc1,elim,depth,0,stdout) <= 0)) {
						ret = check_sudoku(sudokuc1);
						if (ret == 0) {
							// end of sudoku: row r, col c, cand c1+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c1+1;
							fcstat = stat_guess; // have to include this cell for uniqueness check
							fcrv = 1;
							eofc0 = eofc1 = 1;
						} else if (ret < 0) {
							// contradiction: row r, col c, cand c0+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c0+1;
							fcstat = stat_fchain;
							fcrv = 2;
							eofc0 = eofc1 = 1;
						} else {
							// end of forcing chain: check gridc0 and gridc1 for new common cells
							eofc1 = 1;
						}
					}
					// increment length of forcing chain
					fclen++;

					// now look for new common values in gridc0 and gridc1
					if ((eofc0 == 0) || (eofc1 == 0)) {
						diff_grid(sudoku->grid,sudokuc0.grid,diffgridc0,size);
						diff_grid(sudoku->grid,sudokuc1.grid,diffgridc1,size);
						intersect_grid_no_cands(diffgridc0,diffgridc1,intgrid,size);
						intgrid[r][c].cand[c0] = 0;
						intgrid[r][c].cand[c1] = 0;
						intgrid[r][c].value = 0;
						intgrid[r][c].stat = stat_free;
						for (row=0; row<size; row++) {
							for (col=0; col<size; col++) {
								if ((cand = intgrid[row][col].value) != 0) {
									// forcing chain successful, end of loop
									fcrow = row;
									fccol = col;
									fccand = cand;
									fcstat = stat_fchain;
									fcstartr = r;
									fcstartc = c;
									fcrv = 3;
									eofc0 = eofc1 = 1;
								}
							}
						}
					}
				} while ((eofc0 == 0) || (eofc1 == 0));
				
				// if current forcing chain length is smaller than the ones before ...
				if ((fcrv > 0) && (fclen < minfcl)) {
					minr = fcrow;
					minc = fccol;
					minfcl = fclen;
					mincand = fccand;
					minstat = fcstat;
					minstartr = fcstartr;
					minstartc = fcstartc;
					minrv = fcrv;
				}
			}
			// look for next cell with 2 candidates			
		}
	}
	
	// if there is a forcing chain, put its result into grid
	if (minfcl < size*size) {
		sudoku->grid[minr][minc].value = mincand;
		sudoku->grid[minr][minc].stat = minstat;
		remove_candidates(sudoku,minr,minc);
		*fcl = minfcl;
		switch (minrv) {
			case 1:
				snprintf(estr,511,"e  r%dc%d, (%d) forcing chain of length %d to end",minr+1,minc+1,mincand,minfcl);
				break;
			case 2:
				snprintf(estr,511,"f  r%dc%d, (%d) forcing chain of length %d to contradiction",minr+1,minc+1,mincand,minfcl);
				break;
			case 3:
				snprintf(estr,511,"F  forcing chain of length %d starting at r%dc%d to common value (%d) at r%dc%d",minfcl,minstartr+1,minstartc+1,mincand,minr+1,minc+1);
				break;
		}
		estr[511] = '\0';
		fprint_explain(estr,*sudoku,verbosity);
		sudoku->rating += 4 * minfcl;
	}
	
	return(minrv);
}

/*
 ******************************************************************************/
/*
int forcing_chain2(t_sudoku *sudoku, int verbosity, int *fcl) {
	
	int size = sudoku->size;
	int r, c, cc, row, col, cand, c0, c1, elim[NUM_ET], ret, eofc0, eofc1;
	int minr, minc, mincand, minfcl, minrv, minstartr, minstartc;
	int fcrow, fccol, fccand, fclen, fcrv, fcstartr, fcstartc;
	status minstat, fcstat;
	char estr[512];
	t_sudoku sudokuc0, sudokuc1;
	
	t_field diffgridc0[SIZE2][SIZE2];
	t_field diffgridc1[SIZE2][SIZE2];
	t_field intgrid[SIZE2][SIZE2];

	// set minfcl to number of fields
	minfcl = size*size;
	minrv = 0;
	
	// loop over all cells with only two candidates
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if (sudoku->grid[r][c].ncand == 2) {
				
				// copy grid twice
				copy_sudoku(*sudoku,&sudokuc0);
				copy_sudoku(*sudoku,&sudokuc1);
				
				// put candidates into copied grids
				cc = 0;
				while ((cc < size) && (sudoku->grid[r][c].cand[cc] == 0)) cc++;
				c0 = cc;
				sudokuc0.grid[r][c].value = sudoku->grid[r][c].cand[cc];
				sudokuc0.grid[r][c].stat = stat_guess;
				remove_candidates(&sudokuc0,r,c);

				cc++;
				while ((cc < size) && (sudoku->grid[r][c].cand[cc] == 0)) cc++;
				c1 = cc;
				sudokuc1.grid[r][c].value = sudoku->grid[r][c].cand[cc];
				sudokuc1.grid[r][c].stat = stat_guess;
				remove_candidates(&sudokuc1,r,c);

				// continue elimination until there is a corresponding cell value or
				// until end of forcing chain
				fclen = eofc0 = eofc1 = fcrv = 0;
				do {
					// fill in hidden single or single
					if ((eofc0 == 0) && (apply_solution_technique1(&sudokuc0,elim,et_s,0,stdout) <= 0)) {
						ret = check_sudoku(sudokuc0);
						if (ret == 0) {
							// end of sudoku: row r, col c, cand c0+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c0+1;
							fcstat = stat_guess; // have to include this cell for uniqueness check
							fcrv = 1;
							eofc0 = eofc1 = 1;
						} else if (ret < 0) {
							// contradiction: row r, col c, cand c1+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c1+1;
							fcstat = stat_fchain;
							fcrv = 2;
							eofc0 = eofc1 = 1;
						} else {
							// end of this part of forcing chain
							eofc0 = 1;
						}
					}
					if ((eofc1 == 0) && (apply_solution_technique1(&sudokuc1,elim,et_s,0,stdout) <= 0)) {
						ret = check_sudoku(sudokuc1);
						if (ret == 0) {
							// end of sudoku: row r, col c, cand c1+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c1+1;
							fcstat = stat_guess; // have to include this cell for uniqueness check
							fcrv = 1;
							eofc0 = eofc1 = 1;
						} else if (ret < 0) {
							// contradiction: row r, col c, cand c0+1, end of loop
							fcrow = r;
							fccol = c;
							fccand = c0+1;
							fcstat = stat_fchain;
							fcrv = 2;
							eofc0 = eofc1 = 1;
						} else {
							// end of forcing chain: check gridc0 and gridc1 for new common cells
							eofc1 = 1;
						}
					}
					// increment length of forcing chain
					fclen++;

					// now look for new common values in gridc0 and gridc1
					if ((eofc0 == 0) || (eofc1 == 0)) {
						diff_grid(sudoku->grid,sudokuc0.grid,diffgridc0,size);
						diff_grid(sudoku->grid,sudokuc1.grid,diffgridc1,size);
						intersect_grid_no_cands(diffgridc0,diffgridc1,intgrid,size);
						intgrid[r][c].cand[c0] = 0;
						intgrid[r][c].cand[c1] = 0;
						intgrid[r][c].value = 0;
						intgrid[r][c].stat = stat_free;
						for (row=0; row<size; row++) {
							for (col=0; col<size; col++) {
								if ((cand = intgrid[row][col].value) != 0) {
									// forcing chain successful, end of loop
									fcrow = row;
									fccol = col;
									fccand = cand;
									fcstat = stat_fchain;
									fcstartr = r;
									fcstartc = c;
									fcrv = 3;
									eofc0 = eofc1 = 1;
								}
							}
						}
					}
				} while ((eofc0 == 0) || (eofc1 == 0));
				
				// if current forcing chain length is smaller than the ones before ...
				if ((fcrv > 0) && (fclen < minfcl)) {
					minr = fcrow;
					minc = fccol;
					minfcl = fclen;
					mincand = fccand;
					minstat = fcstat;
					minstartr = fcstartr;
					minstartc = fcstartc;
					minrv = fcrv;
				}
			}
			// look for next cell with 2 candidates			
		}
	}
	
	// if there is a forcing chain, put its result into grid
	if (minfcl < size*size) {
		sudoku->grid[minr][minc].value = mincand;
		sudoku->grid[minr][minc].stat = minstat;
		remove_candidates(sudoku,minr,minc);
		*fcl = minfcl;
		switch (minrv) {
			case 1:
				snprintf(estr,511,"e  r%dc%d, (%d) forcing chain of length %d to end",minr+1,minc+1,mincand,minfcl);
				break;
			case 2:
				snprintf(estr,511,"f  r%dc%d, (%d) forcing chain of length %d to contradiction",minr+1,minc+1,mincand,minfcl);
				break;
			case 3:
				snprintf(estr,511,"F  forcing chain of length %d starting at r%dc%d to common value (%d) at r%dc%d",minfcl,minstartr+1,minstartc+1,mincand,minr+1,minc+1);
				break;
		}
		estr[511] = '\0';
		fprint_explain(estr,*sudoku,verbosity);
		sudoku->rating += 4 * minfcl;
	}
	
	return(minrv);
}
*/
/*
 ******************************************************************************/
/*
int forcing_chain1(t_field grid[SIZE*SIZE][SIZE*SIZE], int size, int verbosity, int *fcl) {
	int r, c, cc, c0, c1, elim[NUM_ET], ret0, ret1, nnc, fcl0, fcl1;
	t_field gridc0[SIZE*SIZE][SIZE*SIZE], gridc1[SIZE*SIZE][SIZE*SIZE];
	t_field diffgridc0[SIZE*SIZE][SIZE*SIZE], diffgridc1[SIZE*SIZE][SIZE*SIZE];
	t_field intgrid[SIZE*SIZE][SIZE*SIZE], mergegrid[SIZE*SIZE][SIZE*SIZE];

	// loop over all cells with only two candidates
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if (grid[r][c].ncand == 2) {
				
				// copy grid twice
				copy_grid(grid, gridc0, size);
				copy_grid(grid, gridc1, size);
				
				// put candidates into copied grids
				cc = 0;
				while ((cc < size) && (grid[r][c].cand[cc] == 0)) cc++;
				c0 = cc;
				gridc0[r][c].value = grid[r][c].cand[cc];
				gridc0[r][c].stat = stat_guess;
				remove_cands(gridc0,SIZE*SIZE,r,c);

				cc++;
				while ((cc < size) && (grid[r][c].cand[cc] == 0)) cc++;
				c1 = cc;
				gridc1[r][c].value = grid[r][c].cand[cc];
				gridc1[r][c].stat = stat_guess;
				remove_cands(gridc1,SIZE*SIZE,r,c);

				// continue elimination
				fcl0 = fcl1 = *fcl = 0;
				while (apply_solution_technique(gridc0,size,elim,et_s,0,stdout) > 0) fcl0++;
				ret0 = check_grid(gridc0,size);
				while (apply_solution_technique(gridc1,size,elim,et_s,0,stdout) > 0) fcl1++;
				ret1 = check_grid(gridc1,size);
				*fcl = fcl0 > fcl1 ? fcl0 : fcl1;

				// if forcing chain reaches end or if there's a contratiction for one
				// of the candidates we know the value for the starting cell of the
				// forcing chain
				if ((ret0 == 0) || (ret1 < 0)) {
					grid[r][c].value = c0+1;
					grid[r][c].stat = stat_guess;
					remove_cands(grid,SIZE*SIZE,r,c);
					if (ret0 == 0) {
						if (verbosity > 9) printf("e  r%dc%d, (%d) forcing chain of length %d to end\n",r+1,c+1,c0+1,*fcl);
						return(1);
					} else {
						if (verbosity > 9) printf("f  r%dc%d, (%d) forcing chain of length %d to contradiction\n",r+1,c+1,c0+1,*fcl);
						return(2);
					}
				}
				if ((ret0 < 0) || (ret1 == 0)) {
					grid[r][c].value = c1+1;
					grid[r][c].stat = stat_guess;
					remove_cands(grid,SIZE*SIZE,r,c);
					if (ret1 == 0) {
						if (verbosity > 9) printf("e  r%dc%d, (%d) forcing chain of length %d to end\n",r+1,c+1,c1+1,*fcl);
						return(1);
					}
					else {
						if (verbosity > 9) printf("f  r%dc%d, (%d) forcing chain of length %d to contradiction\n",r+1,c+1,c1+1,*fcl);
						return(2);
					}
				}

				// now look for common values in gridc0 and gridc1
				diff_grid(grid,gridc0,diffgridc0,size);
				diff_grid(grid,gridc1,diffgridc1,size);
				intersect_grid_no_cands(diffgridc0,diffgridc1,intgrid,size);
				intgrid[r][c].cand[c0] = 0;
				intgrid[r][c].cand[c1] = 0;
				intgrid[r][c].value = 0;
				intgrid[r][c].stat = stat_free;
				nnc = num_non_null_cells(intgrid,size);
				if (nnc > 0) {
					merge_grid(grid,intgrid,mergegrid,size);
					copy_grid(mergegrid,grid,size);
					if (verbosity > 9) printf("F  r%dc%d, (%d) forcing chain of length %d - %d common value(s)\n",r+1,c+1,c1+1,nnc,*fcl);
					return(3);
				}
			}
		}
	}
	return(0);
}
*/

/*
 ******************************************************************************/
void copy_fields(t_field grid0[SIZE2][SIZE2], t_field grid1[SIZE2][SIZE2], int size) {
	
	int r, c, cc;
	
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			for (cc=0; cc<size; cc++) grid1[r][c].cand[cc] = grid0[r][c].cand[cc];
			grid1[r][c].ncand = grid0[r][c].ncand;
			grid1[r][c].value = grid0[r][c].value;
			grid1[r][c].stat = grid0[r][c].stat;
		}
	}
}

/* sets values and candidates to zero
 ******************************************************************************/
void grid_to_zero(t_field grid[SIZE2][SIZE2], int size) {
	
	int i, j, k;
	
	for (i=0; i<size; i++) {
		for (j=0; j<size; j++) {
			grid[i][j].value = 0;
			for (k=0; k<size; k++) grid[i][j].cand[k] = 0;
			grid[i][j].ncand = 0;
			grid[i][j].stat = stat_free;
		}
	}
}



/* for finding the differences of 2 grids (forced chain).
 * grid0 is before forced chain, grid1 is with guess for initial cell of 
 * forced chain and subsequent modifications of values and candidates
 ******************************************************************************/
void diff_grid(t_field grid0[SIZE2][SIZE2], t_field grid1[SIZE2][SIZE2], t_field egrid[SIZE2][SIZE2], int size) {
	
	int r, c, cc;
	
	grid_to_zero(egrid,size);
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			for (cc=0; cc<size; cc++) {
				if (grid0[r][c].cand[cc] != grid1[r][c].cand[cc]) {
					egrid[r][c].cand[cc] = grid0[r][c].cand[cc] + grid1[r][c].cand[cc];
				}
			}
			if (grid0[r][c].value != grid1[r][c].value) {
				egrid[r][c].value = grid0[r][c].value + grid1[r][c].value;
			}
		}
	}
}

/* egrid gets values and candidates present in both  * grid0 AND grid1.
 * use this for comparing the difference grids (results of diff_grid)
 * for the 2 possibilities of 1 cell. if egrid is non-zero after this
 * operation, forced_chain was successful. only cell values are compared,
 * common eliminated candidates are not evaluated
 ******************************************************************************/
void intersect_grid_no_cands(t_field grid0[SIZE2][SIZE2], t_field grid1[SIZE2][SIZE2], t_field egrid[SIZE2][SIZE2], int size) {
	
	int r, c;
	
	grid_to_zero(egrid,size);
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if ((grid0[r][c].value == grid1[r][c].value) && (grid0[r][c].value != 0)){
				egrid[r][c].value = grid0[r][c].value;
				egrid[r][c].stat = stat_fchain;
			}
		}
	}
}

/* egrid gets values and candidates present in both  * grid0 AND grid1.
 * use this for comparing the difference grids (results of diff_grid)
 * for the 2 possibilities of 1 cell. if egrid is non-zero after this
 * operation, forced_chain was successful
 ******************************************************************************/
void intersect_grid_with_cands(t_field grid0[SIZE2][SIZE2], t_field grid1[SIZE2][SIZE2], t_field egrid[SIZE2][SIZE2], int size) {
	
	int r, c, cc;
	
	grid_to_zero(egrid,size);
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			for (cc=0; cc<size; cc++) {
				if ((grid0[r][c].cand[cc] == grid1[r][c].cand[cc])
						&& (grid0[r][c].value != cc+1)
						&& (grid1[r][c].value != cc+1)) {
					egrid[r][c].cand[cc] = grid0[r][c].cand[cc];
				}
			}
			if ((grid0[r][c].value == grid1[r][c].value) && (grid0[r][c].value != 0)){
				egrid[r][c].value = grid0[r][c].value;
				egrid[r][c].stat = stat_fchain;
			}
		}
	}
}

/* for merging correlations of a forced chain (grid0) into grid (grid1).
 * result of operation is stored in egrid.
 ******************************************************************************/
/*
void merge_grid(t_field grid0[SIZE*SIZE][SIZE*SIZE],
t_field grid1[SIZE*SIZE][SIZE*SIZE], t_field egrid[SIZE*SIZE][SIZE*SIZE], int size) {
	int r, c, cc;
	copy_grid(grid0,egrid,size);
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			if (grid1[r][c].value != 0) {
				egrid[r][c].value = grid1[r][c].value;
				for (cc=0; cc<size; cc++) egrid[r][c].cand[cc] = 0;
				egrid[r][c].ncand = 0;
				egrid[r][c].stat = grid1[r][c].stat;
				remove_cands(egrid,size,r,c);
			}
		}
	}
	for (r=0; r<size; r++) {
		for (c=0; c<size; c++) {
			for (cc=0; cc<size; cc++) {
				if ((grid1[r][c].cand[cc] != 0) && (egrid[r][c].cand[cc] != 0)) {
					egrid[r][c].cand[cc] = 0;
					egrid[r][c].ncand--;
				}
			}
		}
	}
}
*/