Effiziente Programme WS 2010/11

Gruppe 111

rev03
rev04
rev05
rev06
rev07
rev08
rev09
rev10
rev11
rev12
rev16
rev21
rev23
rev24
rev27
rev28
rev31

final result

Präsentation

Ausgangslage

Sudoku Solver v1.2, http://www.techfinesse.com/game/sudoku_solver.php
2660 LOC

standard 9x9 Sudokus
werden von links nach rechts als Strings der Länge 1 dargestellt
andere non-blank Zeichen sind leere Zellen

Präsentation mit Profiling für die verschiedenen Revisionen ist hier zu finden.

Bsp:
.........8..3.5..2..6...9...4.5.6.8.7.1...4.9...9.1...97..6...5..3...1...........

papiex -e PAPI_TOT_CYC -e PAPI_TOT_INS -e PAPI_BR_MSP -e PAPI_FP_OPS ./sudoku_solver -f input.txt -o output.txt -G

(gcc -O)
Cycles 3,31373e+08
Instructions Completed 3,61562e+08
Mispredicted Branches 8,64681e+06

rev03

Variablen aus den folgenden Funktionen wurden entfernt

explain_solve_cell
explain_markup_impasse
explain_singleton
explain_given
explain_vector_elim
explain_vector_impasse

 
      /*************************************************************/
 
      static void explain_markup_elim(Grid *g, int chgd, int clue)
 
      {
-
      	int chgd_row, chgd_col, clue_row, clue_col;
 
              char buf[32];
-
              chgd_row = map[chgd].row+1;
-
              chgd_col = map[chgd].col+1;
-
              clue_row = map[clue].row+1;
-
              clue_col = map[clue].col+1;
 
              explain_indent(solnfile);
 
              fprintf(solnfile, "Candidate %s removed from row %d, col %d because of cell at row %d, col %d\n",
-
                      clues(g->cell[clue], buf), chgd_row, chgd_col, clue_row, clue_col);
+
                      clues(g->cell[clue], buf), (map[chgd].row+1), (map[chgd].col+1), (map[clue].row+1), (map[clue].col+1));
 
      }
 
      /*****************************************/

rev04

init_grid - entfernen bzw in cvt_to_grid integrieren

 
      #endif
-
      /*****************************************************/
-
      /* Initialize a grid to an empty state.              */
-
      /* At the start, all cells can have any value        */
-
      /* so set all 9 lower order bits in each cell.       */
-
      /* In effect, the 9x9 grid now has markup that       */
-
      /* specifies that each cell can assume any value     */
-
      /* of 1 through 9.                                   */
-
      /*****************************************************/
-
      static void init_grid(Grid *g)
-
      {
-
      	int i;
-
              for (i = 0; i < PUZZLE_CELLS; i++) {
-
      		g->cell[i] = 0x01ff;
-
                      g->cellflags[i] = UNSOLVED;
-
              }
-
              g->exposed = 0;
-
              g->givens = 0;
-
              g->inc = 0;
-
              g->maxlvl = 1;
-
              g->score = 0;
-
              g->solncount = 0;
-
              g->reward = 1;
-
              g->next = NULL;
-
              g->tail = 0;
-
              EXPLAIN_MARKUP;
-
      }
 
      /*****************************************************/
 
      /* Convert a puzzle from the input format,           */
 
      /* i.e. a string of 81 non-blank characters          */
 
      static int cvt_to_grid(Grid *g, const char *game)
 
      {
 
      	int i;
+
      		g->exposed = 0;
+
              g->givens = 0;
+
              g->inc = 0;
+
              g->maxlvl = 1;
+
              g->score = 0;
+
              g->solncount = 0;
+
              g->reward = 1;
+
              g->next = NULL;
+
              g->tail = 0;
+
              EXPLAIN_MARKUP;
-
              init_grid(g);
 
              for (i = 0; i < PUZZLE_CELLS && game[i]; i++) {
 
              	if (is_given(game[i])) {
 
      			/* warning -- ASCII charset assumed */
 
                              g->solved[g->exposed++] = i;
 
                              EXPLAIN_GIVEN(i, game[i]);
 
                      }
+
      			else
+
      			{
+
      				g->cell[i] = 0x01ff;
+
                      g->cellflags[i] = UNSOLVED;
+
      			}
 
              }
 
              return i;

rev05

validate - variablen entfernen/zusammenfassen (boxmask, rowmask, colmask)
schleifen zusammenlegen

	4		5
971		971
972	static int validate(const Grid *g, int verbose)	972	static int validate(const Grid *g, int verbose)
973	{	973	{
974	int i, j, bc, boxmask, rowmask, colmask, flag = 1;	974	int i, j, bc, mask, flag = 1;
975	char buf[32];	975	char buf[32];
976		976
977	/* Sanity check */	977	/* Sanity check */
...		...
984	flag = 0;	984	flag = 0;
985	} else return 0;	985	} else return 0;
986	}	986	}
987	}	987	}
988		988
989	/* Check rows */	989	/* Check rows */
990	for (i = 0; i < PUZZLE_DIM; i++) {	990	for (i = 0; i < PUZZLE_DIM; i++) {
991	for (rowmask = j = 0; j < PUZZLE_DIM; j++) {	991	for (mask = j = 0; j < PUZZLE_DIM; j++) {
992	if (bitcount(g->cell[row[i][j]]) == 1) rowmask \|= g->cell[row[i][j]];	992	if (bitcount(g->cell[row[i][j]]) == 1) mask \|= g->cell[row[i][j]];
993	}	993	}
994	if (rowmask != 0x01ff) {	994	if (mask != 0x01ff) {
995	if (verbose) {	995	if (verbose) {
996	fprintf(rejects, "Row %d is not solved for %s.\n", 1+i, clues(~rowmask, buf)); fflush(rejects);	996	fprintf(rejects, "Row %d is not solved for %s.\n", 1+i, clues(~mask, buf)); fflush(rejects);
997	flag = 0;	997	flag = 0;
998	} else return 0;	998	} else return 0;
999	}	999	}
1000	}
1001		1000
1002	/* Check columns */	1001	/* Check columns */
1003	for (i = 0; i < PUZZLE_DIM; i++) {	1002	for (mask = j = 0; j < PUZZLE_DIM; j++) {
1004	for (colmask = j = 0; j < PUZZLE_DIM; j++) {	1003
1005		1004
1006		1005
1007		1006
1008		1007
1009		1008
1010		1009
1011	} else return 0;	1010	}
1012	}
1013	}
1014		1011
1015	/* Check 3x3 boxes */	1012	/* Check 3x3 boxes */
1016	for (i = 0; i < PUZZLE_DIM; i++) {	1013	for (mask = j = 0; j < PUZZLE_DIM; j++) {
1017	for (boxmask = j = 0; j < PUZZLE_DIM; j++) {	1014	if (bitcount(g->cell[box[i][j]]) == 1) mask \|= g->cell[box[i][j]];
1018	if (bitcount(g->cell[box[i][j]]) == 1) boxmask \|= g->cell[box[i][j]];	1015	}
1019	}	1016
1020	if (boxmask != 0x01ff) {	1017
1021	if (verbose) {	1018
1022	fprintf(rejects, "Box %d is not solved for %s.\n", 1+i, clues(~boxmask, buf)); fflush(rejects);	1019
1023	flag = 0;	1020
1024	} else return 0;	1021
1025	}	1022
1026	}
1027		1023
1028	return flag;	1024
		1025	return flag;
1029	}	1026	}
1030		1027
1031	/********************************************************************************/	1028	/********************************************************************************/

rev06

static int mark_cells(Grid *g)
(before != cell) durch ^ ersetzen

	5		6
1061	g->cell[ndx] = cell;	1061	g->cell[ndx] = cell;
1062		1062
1063	/* Did the cell change value? */	1063	/* Did the cell change value? */
1064	if (before != cell) {	1064	if (before ^ cell) {
1065		1065
1066	chgflag \|= CHANGE; /* Flag that puzzle markup was changed */	1066	chgflag \|= CHANGE; /* Flag that puzzle markup was changed */
1067	g->score += g->inc; /* More work means higher scoring */	1067	g->score += g->inc; /* More work means higher scoring */

rev07

eliminate_singles - 3 schleifen durch 1 sersetzen

 
              /* Do rows (horizontal chutes) */
 
              for (i = 0; i < PUZZLE_DIM; i++) {
 
              	found |= find_singletons(g, row[i], "row");
-
              }
-
              /* Do columns (vertical chutes) */
+
      			  /* Do columns (vertical chutes) */
-
              for (i = 0; i < PUZZLE_DIM; i++) {
+
      			found |= find_singletons(g, col[i], "column");
-
              	found |= find_singletons(g, col[i], "column");
-
              }
-
              /* Do boxes */
+
      			/* Do boxes */
-
              for (i = 0; i < PUZZLE_DIM; i++) {
+
      			found |= find_singletons(g, box[i], "box");
-
              	found |= find_singletons(g, box[i], "box");
 
              }
 
              return found;

rev08

eliminate_singles - loop unrolling

	7		8
1161		1161
1162	static int eliminate_singles(Grid *g)	1162	static int eliminate_singles(Grid *g)
1163	{	1163	{
1164	int i, found = NOCHANGE;	1164	int found = NOCHANGE;
1165		1165
1166	/* Do rows (horizontal chutes) */	1166	/* Do rows (horizontal chutes) */
1167	for (i = 0; i < PUZZLE_DIM; i++) {	1167	found \|= find_singletons(g, row[0], "row");
1168	found \|= find_singletons(g, row[i], "row");	1168	found \|= find_singletons(g, row[1], "row");
		1169	found \|= find_singletons(g, row[2], "row");
		1170	found \|= find_singletons(g, row[3], "row");
		1171	found \|= find_singletons(g, row[4], "row");
		1172	found \|= find_singletons(g, row[5], "row");
		1173	found \|= find_singletons(g, row[6], "row");
		1174	found \|= find_singletons(g, row[7], "row");
		1175	found \|= find_singletons(g, row[8], "row");
1169		1176
1170	/* Do columns (vertical chutes) */	1177	/* Do columns (vertical chutes) */
1171	found \|= find_singletons(g, col[i], "column");	1178	found \|= find_singletons(g, col[0], "column");
		1179	found \|= find_singletons(g, col[1], "column");
		1180	found \|= find_singletons(g, col[2], "column");
		1181	found \|= find_singletons(g, col[3], "column");
		1182	found \|= find_singletons(g, col[4], "column");
		1183	found \|= find_singletons(g, col[5], "column");
		1184	found \|= find_singletons(g, col[6], "column");
		1185	found \|= find_singletons(g, col[7], "column");
		1186	found \|= find_singletons(g, col[8], "column");
1172		1187
1173	/* Do boxes */	1188	/* Do boxes */
1174	found \|= find_singletons(g, box[i], "box");	1189	found \|= find_singletons(g, box[0], "box");
1175	}	1190	found \|= find_singletons(g, box[1], "box");
		1191	found \|= find_singletons(g, box[2], "box");
		1192	found \|= find_singletons(g, box[3], "box");
		1193	found \|= find_singletons(g, box[4], "box");
		1194	found \|= find_singletons(g, box[5], "box");
		1195	found \|= find_singletons(g, box[6], "box");
		1196	found \|= find_singletons(g, box[7], "box");
		1197	found \|= find_singletons(g, box[8], "box");
1176		1198
1177	return found;	1199	return found;
1178	}	1200	}

rev09

chute_elimination - rc == NOCHANGE durch !rc ändern

8		9
1482	g->pass_mods = 0;	1482	g->pass_mods = 0;
1483		1483
1484	/* For each digit... */	1484	/* For each digit... */
1485	for (i = 0; i < PUZZLE_DIM && rc == NOCHANGE; i++) {	1485	for (i = 0; i < PUZZLE_DIM && !rc; i++) {
1486	rc \|= box_row_chute_elim(g, i);	1486	rc \|= box_row_chute_elim(g, i);
1487	}	1487	}
1488		1488
1489	if (rc == NOCHANGE) for (i = 0; i < PUZZLE_DIM && rc == NOCHANGE; i++) {	1489	if (rc == NOCHANGE) for (i = 0; i < PUZZLE_DIM && !rc; i++) {
1490	rc \|= box_col_chute_elim(g, i);	1490	rc \|= box_col_chute_elim(g, i);
1491	}	1491	}
1492		1492

rev10

naked_tuple_elimination - loop unrolling

 
      static int naked_tuple_elimination(Grid *g)
 
      {
-
      	int i, rc = NOCHANGE;
+
      	int rc = NOCHANGE;
 
              g->pass_mods = 0;
 
              /* Eliminate subsets from rows */
-
              for (i = 0; i < PUZZLE_DIM; i++) {
+
      		rc |= elim_naked_tuples(g, row[0], "row", 0);
-
              	rc |= elim_naked_tuples(g, row[i], "row", i);
+
      		rc |= elim_naked_tuples(g, row[1], "row", 1);
-
              }
+
      		rc |= elim_naked_tuples(g, row[2], "row", 2);
+
      		rc |= elim_naked_tuples(g, row[3], "row", 3);
+
      		rc |= elim_naked_tuples(g, row[4], "row", 4);
+
      		rc |= elim_naked_tuples(g, row[5], "row", 5);
+
      		rc |= elim_naked_tuples(g, row[6], "row", 6);
+
      		rc |= elim_naked_tuples(g, row[7], "row", 7);
+
      		rc |= elim_naked_tuples(g, row[8], "row", 8);
 
              /* Eliminate subsets from columns */
-
              for (i = 0; i < PUZZLE_DIM; i++) {
+
              rc |= elim_naked_tuples(g, col[0], "column", 0);
-
              	rc |= elim_naked_tuples(g, col[i], "column", i);
+
              rc |= elim_naked_tuples(g, col[1], "column", 1);
-
              }
+
      		rc |= elim_naked_tuples(g, col[2], "column", 2);
+
      		rc |= elim_naked_tuples(g, col[3], "column", 3);
+
      		rc |= elim_naked_tuples(g, col[4], "column", 4);
+
      		rc |= elim_naked_tuples(g, col[5], "column", 5);
+
      		rc |= elim_naked_tuples(g, col[6], "column", 6);
+
      		rc |= elim_naked_tuples(g, col[7], "column", 7);
+
      		rc |= elim_naked_tuples(g, col[8], "column", 8);
 
              /* Eliminate subsets from boxes */
-
              for (i = 0; i < PUZZLE_DIM; i++) {
+
              rc |= elim_naked_tuples(g, box[0], "box", 0);
-
              	rc |= elim_naked_tuples(g, box[i], "box", i);
+
      		rc |= elim_naked_tuples(g, box[1], "box", 1);
-
              }
+
      		rc |= elim_naked_tuples(g, box[2], "box", 2);
+
      		rc |= elim_naked_tuples(g, box[3], "box", 3);
+
      		rc |= elim_naked_tuples(g, box[4], "box", 4);
+
      		rc |= elim_naked_tuples(g, box[5], "box", 5);
+
      		rc |= elim_naked_tuples(g, box[6], "box", 6);
+
      		rc |= elim_naked_tuples(g, box[7], "box", 7);
+
      		rc |= elim_naked_tuples(g, box[8], "box", 8);
 
              /* score penalty for puzzle bottlenecks */
 
      	if (g->pass_mods && g->pass_mods < 4) {
 
                      g->score += 20 - (5 * g->pass_mods);;

rev11

find_singletons: loop elimination, variable reduction

	10		11
1102		1102
1103	static int find_singletons(Grid g, int const vector, char *vdesc)	1103	static int find_singletons(Grid g, int const vector, char *vdesc)
1104	{	1104	{
1105	int i, j, mask, hist[PUZZLE_DIM], value[PUZZLE_DIM], found = NOCHANGE;	1105	int i, j, mask, hist, value, found = NOCHANGE;
1106		1106
1107	/* We are going to create a histogram of cell candidate values */	1107	/* We are going to create a histogram of cell candidate values */
1108	/* for the specified cell vector (row/column/box). */	1108	/* for the specified cell vector (row/column/box). */
1109	/* First set all buckets to zero. */	1109	/* First set all buckets to zero. */
1110	memset(hist, 0, sizeof(hist[0])*PUZZLE_DIM);	1110	// memset(hist, 0, sizeof(hist[0])*PUZZLE_DIM);
1111		1111
1112	/* For each possible candidate value... */	1112	/* For each possible candidate value... */
1113	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {	1113	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {
1114		1114
		1115	hist = 0;
1115	/* For each cell in the vector... */	1116	/* For each cell in the vector... */
1116	for (j = 0; j < PUZZLE_DIM; j++) {	1117	for (j = 0; j < PUZZLE_DIM; j++) {
1117		1118
1118	/* If the cell may possibly assume this value... */	1119	/* If the cell may possibly assume this value... */
1119	if (g->cell[vector[j]] & mask) {	1120	if (g->cell[vector[j]] & mask) {
1120		1121
1121	if (++hist[i] > 1) break; /* Bump bucket in histogram */	1122	if (++hist > 1) break; /* Bump bucket in histogram */
1122	value[i] = vector[j]; /* Save the cell coordinate */	1123	value = vector[j]; /* Save the cell coordinate */
1123	}	1124	}
1124	}	1125	}
1125		1126
1126	mask <<= 1;	1127	/* If the bucket == 1 and the cell is not already solved, */
1127	}	1128	/* then the cell has a unique solution specified by "mask" */
1128		1129	if (hist == 1 && g->cellflags[value] == UNSOLVED) {
1129	/* Examine each bucket in the histogram... */
1130	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {
1131
1132	/* If the bucket == 1 and the cell is not already solved, */
1133	/* then the cell has a unique solution specified by "mask" */
1134	if (hist[i] == 1 && g->cellflags[value[i]] == UNSOLVED) {
1135
1136	found = CHANGE; /* Indicate that markup has been changed */	1130	found = CHANGE; /* Indicate that markup has been changed */
1137	g->cell[value[i]] = mask; /* Assign solution value to cell */	1131	g->cell[value] = mask; /* Assign solution value to cell */
1138	g->cellflags[value[i]] = SOLVED; /* Mark cell as solved */	1132	g->cellflags[value] = SOLVED; /* Mark cell as solved */
1139	g->score += g->reward; /* Bump puzzle score */	1133	g->score += g->reward; /* Bump puzzle score */
1140	g->pass_mods += 1;	1134	g->pass_mods += 1;
1141	g->solved[g->exposed++] = value[i];	1135	g->solved[g->exposed++] = value;
1142	EXPLAIN_SINGLETON(g, value[i], mask, vdesc);	1136	EXPLAIN_SINGLETON(g, value, mask, vdesc);
1143	}	1137	}
1144		1138
1145	mask <<= 1; /* Get next candidate value */	1139	mask <<= 1;
1146	}	1140	}
1147		1141
		1142
1148	return found;	1143	return found;
1149	}	1144	}
1150		1145

rev12

added counter for remaining values per row/box/column to reduce find_singletons-loops

	11		12
865	g->reward = 1;	865	g->reward = 1;
866	g->next = NULL;	866	g->next = NULL;
867	g->tail = 0;	867	g->tail = 0;
		868	g->rowValuesLeft[0] = 0x01ff;
		869	g->rowValuesLeft[1] = 0x01ff;
		870	g->rowValuesLeft[2] = 0x01ff;
		871	g->rowValuesLeft[3] = 0x01ff;
		872	g->rowValuesLeft[4] = 0x01ff;
		873	g->rowValuesLeft[5] = 0x01ff;
		874	g->rowValuesLeft[6] = 0x01ff;
		875	g->rowValuesLeft[7] = 0x01ff;
		876	g->rowValuesLeft[8] = 0x01ff;
		877	g->columnValuesLeft[0] = 0x01ff;
		878	g->columnValuesLeft[1] = 0x01ff;
		879	g->columnValuesLeft[2] = 0x01ff;
		880	g->columnValuesLeft[3] = 0x01ff;
		881	g->columnValuesLeft[4] = 0x01ff;
		882	g->columnValuesLeft[5] = 0x01ff;
		883	g->columnValuesLeft[6] = 0x01ff;
		884	g->columnValuesLeft[7] = 0x01ff;
		885	g->columnValuesLeft[8] = 0x01ff;
		886	g->boxValuesLeft[0] = 0x01ff;
		887	g->boxValuesLeft[1] = 0x01ff;
		888	g->boxValuesLeft[2] = 0x01ff;
		889	g->boxValuesLeft[3] = 0x01ff;
		890	g->boxValuesLeft[4] = 0x01ff;
		891	g->boxValuesLeft[5] = 0x01ff;
		892	g->boxValuesLeft[6] = 0x01ff;
		893	g->boxValuesLeft[7] = 0x01ff;
		894	g->boxValuesLeft[8] = 0x01ff;
868	EXPLAIN_MARKUP;	895	EXPLAIN_MARKUP;
869		896
870	for (i = 0; i < PUZZLE_CELLS && game[i]; i++) {	897	for (i = 0; i < PUZZLE_CELLS && game[i]; i++) {
...		...
875	g->givens += 1;	902	g->givens += 1;
876	g->solved[g->exposed++] = i;	903	g->solved[g->exposed++] = i;
877	EXPLAIN_GIVEN(i, game[i]);	904	EXPLAIN_GIVEN(i, game[i]);
		905
		906	g->rowValuesLeft[map[i].row] ^= g->cell[i];
		907	g->columnValuesLeft[map[i].col] ^= g->cell[i];
		908	g->boxValuesLeft[map[i].box] ^= g->cell[i];
878	}	909	}
879	else	910	else
880	{	911	{
...		...
1080	g->pass_mods += 1;	1111	g->pass_mods += 1;
1081	g->solved[g->exposed++] = ndx;	1112	g->solved[g->exposed++] = ndx;
1082	EXPLAIN_MARKUP_SOLVE(g, ndx);	1113	EXPLAIN_MARKUP_SOLVE(g, ndx);
		1114
		1115	//neu - ValeusLedt
		1116	g->rowValuesLeft[map[ndx].row] ^= cell;
		1117	g->columnValuesLeft[map[ndx].col] ^= cell;
		1118	g->boxValuesLeft[map[ndx].box] ^= cell;
1083	}	1119	}
1084	}	1120	}
1085	}	1121	}
...		...
1100	/* CHANGE - Markup was modified. */	1136	/* CHANGE - Markup was modified. */
1101	/*******************************************************************/	1137	/*******************************************************************/
1102		1138
1103	static int find_singletons(Grid g, int const vector, char *vdesc)	1139	static int find_singletons(Grid g, int const vector, char *vdesc, int valuesLeft)
1104	{	1140	{
1105	int i, j, mask, hist, value, found = NOCHANGE;	1141	int i, j, mask, hist, value, found = NOCHANGE;
1106		1142
...		...
1112	/* For each possible candidate value... */	1148	/* For each possible candidate value... */
1113	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {	1149	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {
1114		1150
		1151	if(!(mask & valuesLeft))
		1152	continue;
		1153
1115	hist = 0;	1154	hist = 0;
1116	/* For each cell in the vector... */	1155	/* For each cell in the vector... */
1117	for (j = 0; j < PUZZLE_DIM; j++) {	1156	for (j = 0; j < PUZZLE_DIM; j++) {
...		...
1134	g->pass_mods += 1;	1173	g->pass_mods += 1;
1135	g->solved[g->exposed++] = value;	1174	g->solved[g->exposed++] = value;
1136	EXPLAIN_SINGLETON(g, value, mask, vdesc);	1175	EXPLAIN_SINGLETON(g, value, mask, vdesc);
		1176
		1177	//neu - ValeusLedt
		1178	g->rowValuesLeft[map[i].row] ^= mask;
		1179	g->columnValuesLeft[map[i].col] ^= mask;
		1180	g->boxValuesLeft[map[i].box] ^= mask;
1137	}	1181	}
1138		1182
1139	mask <<= 1;	1183	mask <<= 1;
...		...
1159	int found = NOCHANGE;	1203	int found = NOCHANGE;
1160		1204
1161	/* Do rows (horizontal chutes) */	1205	/* Do rows (horizontal chutes) */
1162	found \|= find_singletons(g, row[0], "row");	1206	found \|= find_singletons(g, row[0], "row", g->rowValuesLeft[0]);
1163	found \|= find_singletons(g, row[1], "row");	1207	found \|= find_singletons(g, row[1], "row", g->rowValuesLeft[1]);
1164	found \|= find_singletons(g, row[2], "row");	1208	found \|= find_singletons(g, row[2], "row", g->rowValuesLeft[2]);
1165	found \|= find_singletons(g, row[3], "row");	1209	found \|= find_singletons(g, row[3], "row", g->rowValuesLeft[3]);
1166	found \|= find_singletons(g, row[4], "row");	1210	found \|= find_singletons(g, row[4], "row", g->rowValuesLeft[4]);
1167	found \|= find_singletons(g, row[5], "row");	1211	found \|= find_singletons(g, row[5], "row", g->rowValuesLeft[5]);
1168	found \|= find_singletons(g, row[6], "row");	1212	found \|= find_singletons(g, row[6], "row", g->rowValuesLeft[6]);
1169	found \|= find_singletons(g, row[7], "row");	1213	found \|= find_singletons(g, row[7], "row", g->rowValuesLeft[7]);
1170	found \|= find_singletons(g, row[8], "row");	1214	found \|= find_singletons(g, row[8], "row", g->rowValuesLeft[8]);
1171		1215
1172	/* Do columns (vertical chutes) */	1216	/* Do columns (vertical chutes) */
1173	found \|= find_singletons(g, col[0], "column");	1217	found \|= find_singletons(g, col[0], "column", g->columnValuesLeft[0]);
1174	found \|= find_singletons(g, col[1], "column");	1218	found \|= find_singletons(g, col[1], "column", g->columnValuesLeft[1]);
1175	found \|= find_singletons(g, col[2], "column");	1219	found \|= find_singletons(g, col[2], "column", g->columnValuesLeft[2]);
1176	found \|= find_singletons(g, col[3], "column");	1220	found \|= find_singletons(g, col[3], "column", g->columnValuesLeft[3]);
1177	found \|= find_singletons(g, col[4], "column");	1221	found \|= find_singletons(g, col[4], "column", g->columnValuesLeft[4]);
1178	found \|= find_singletons(g, col[5], "column");	1222	found \|= find_singletons(g, col[5], "column", g->columnValuesLeft[5]);
1179	found \|= find_singletons(g, col[6], "column");	1223	found \|= find_singletons(g, col[6], "column", g->columnValuesLeft[6]);
1180	found \|= find_singletons(g, col[7], "column");	1224	found \|= find_singletons(g, col[7], "column", g->columnValuesLeft[7]);
1181	found \|= find_singletons(g, col[8], "column");	1225	found \|= find_singletons(g, col[8], "column", g->columnValuesLeft[8]);
1182		1226
1183	/* Do boxes */	1227	/* Do boxes */
1184	found \|= find_singletons(g, box[0], "box");	1228	found \|= find_singletons(g, box[0], "box", g->boxValuesLeft[0]);
1185	found \|= find_singletons(g, box[1], "box");	1229	found \|= find_singletons(g, box[1], "box", g->boxValuesLeft[0]);
1186	found \|= find_singletons(g, box[2], "box");	1230	found \|= find_singletons(g, box[2], "box", g->boxValuesLeft[0]);
1187	found \|= find_singletons(g, box[3], "box");	1231	found \|= find_singletons(g, box[3], "box", g->boxValuesLeft[0]);
1188	found \|= find_singletons(g, box[4], "box");	1232	found \|= find_singletons(g, box[4], "box", g->boxValuesLeft[0]);
1189	found \|= find_singletons(g, box[5], "box");	1233	found \|= find_singletons(g, box[5], "box", g->boxValuesLeft[0]);
1190	found \|= find_singletons(g, box[6], "box");	1234	found \|= find_singletons(g, box[6], "box", g->boxValuesLeft[0]);
1191	found \|= find_singletons(g, box[7], "box");	1235	found \|= find_singletons(g, box[7], "box", g->boxValuesLeft[0]);
1192	found \|= find_singletons(g, box[8], "box");	1236	found \|= find_singletons(g, box[8], "box", g->boxValuesLeft[0]);
1193		1237
1194	return found;	1238	return found;
1195	}	1239	}
...		...
1336	EXPLAIN_VECTOR_ELIM("row", box_row_mask, c, num, box_tuple);	1380	EXPLAIN_VECTOR_ELIM("row", box_row_mask, c, num, box_tuple);
1337	if (bitcount(g->cell[c]) == 1) {	1381	if (bitcount(g->cell[c]) == 1) {
1338	g->cellflags[c] = SOLVED;	1382	g->cellflags[c] = SOLVED;
1339	g->score += g->reward + 5;	1383	g->score += g->reward + 5;
1340	g->solved[g->exposed++] = c;	1384	g->solved[g->exposed++] = c;
1341	EXPLAIN_VECTOR_SOLVE(g, c);	1385	EXPLAIN_VECTOR_SOLVE(g, c);
1342	return CHANGE;	1386
		1387	//neu - ValeusLedt
		1388	g->rowValuesLeft[map[c].row] ^= g->cell[c];
		1389	g->columnValuesLeft[map[c].col] ^= g->cell[c];
		1390	g->boxValuesLeft[map[c].box] ^= g->cell[c];
		1391
		1392	return CHANGE;
1343	}	1393	}
1344	}	1394	}
1345	}	1395	}
...		...
1440	g->score += g->reward + 5;	1490	g->score += g->reward + 5;
1441	g->solved[g->exposed++] = c;	1491	g->solved[g->exposed++] = c;
1442	EXPLAIN_VECTOR_SOLVE(g, c);	1492	EXPLAIN_VECTOR_SOLVE(g, c);
		1493
		1494	//neu - ValeusLedt
		1495	g->rowValuesLeft[map[c].row] ^= g->cell[c];
		1496	g->columnValuesLeft[map[c].col] ^= g->cell[c];
		1497	g->boxValuesLeft[map[c].box] ^= g->cell[c];
		1498
1443	return CHANGE;	1499	return CHANGE;
1444	}	1500	}
1445	}	1501	}
...		...
1583	g->score += g->reward;	1639	g->score += g->reward;
1584	g->solved[g->exposed++] = c;	1640	g->solved[g->exposed++] = c;
1585	EXPLAIN_TUPLE_SOLVE(g, c);	1641	EXPLAIN_TUPLE_SOLVE(g, c);
		1642
		1643	//neu - ValeusLedt
		1644	g->rowValuesLeft[map[ndx].row] ^= g->cell[c];
		1645	g->columnValuesLeft[map[ndx].col] ^= g->cell[c];
		1646	g->boxValuesLeft[map[ndx].box] ^= g->cell[c];
		1647
1586	}	1648	}
1587	}	1649	}
1588	}	1650	}
...		...
1725		1787
1726	/* Try one of the possible candidates for this cell */	1788	/* Try one of the possible candidates for this cell */
1727	mygrid.cell[c] = mask;	1789	mygrid.cell[c] = mask;
1728	mygrid.cellflags[c] = SOLVED;	1790	mygrid.cellflags[c] = SOLVED;
1729	mygrid.solved[mygrid.exposed++] = c;	1791	mygrid.solved[mygrid.exposed++] = c;
1730		1792
		1793	//neu - ValeusLedt
		1794	g->rowValuesLeft[map[c].row] ^= mask;
		1795	g->columnValuesLeft[map[c].col] ^= mask;
		1796	g->boxValuesLeft[map[c].box] ^= mask;
		1797
1731	EXPLAIN_CURRENT_MARKUP(&mygrid);	1798	EXPLAIN_CURRENT_MARKUP(&mygrid);
1732	flag = rsolve(&mygrid); /* Recurse with working copy of puzzle */	1799	flag = rsolve(&mygrid); /* Recurse with working copy of puzzle */
1733		1800

 
              short tail, givens, exposed, maxlvl, inc, reward;
 
              unsigned int score, solncount, pass_mods;
 
              struct grd *next;
+
      		int rowValuesLeft[PUZZLE_DIM];
+
      		int columnValuesLeft[PUZZLE_DIM];
+
      		int boxValuesLeft[PUZZLE_DIM];
 
      } Grid;
 
      /********************************************************/

rev16

removed variable i in find_singletons and replaced by mask comparison

 
      static int find_singletons(Grid *g, int const *vector, char *vdesc, short valuesLeft)
 
      {
-
      	int i, j, mask, hist, value, found = NOCHANGE;
+
      	int j, mask, hist, value, found = NOCHANGE;
 
      	/* We are going to create a histogram of cell candidate values */
 
              /* for the specified cell vector (row/column/box).             */
 
            //  memset(hist, 0, sizeof(hist[0])*PUZZLE_DIM);
 
      	/* For each possible candidate value... */
-
      	for (mask = 1, i = 0; i < PUZZLE_DIM; i++) {
+
      	for (mask = 1; !(mask & (1 << PUZZLE_DIM)); mask <<= 1) {
 
      		if(!(mask & valuesLeft))
 
      			continue;
 
      					g->columnValuesLeft[map[value].col] &= ~mask;
 
      					g->boxValuesLeft[map[value].box] &= ~mask;
 
                      }
-
                      mask <<= 1;
 
              }

rev21

Schleifen am Anfang der Funktionen box_col_chute_elim und box_row_chute_elim rückwärts zählen

rev23

One more down-count of for loop

	22		23
1220		1220
1221	hist = 0;	1221	hist = 0;
1222	/* For each cell in the vector... */	1222	/* For each cell in the vector... */
1223	for (j = 0; j < PUZZLE_DIM; j++) {	1223	for (j = PUZZLE_DIM - 1; j >= 0 ; j--) {
1224		1224
1225	/* If the cell may possibly assume this value... */	1225	/* If the cell may possibly assume this value... */
1226	if (g->cell[vector[j]] & mask) {	1226	if (g->cell[vector[j]] & mask) {

rev24

	23		24
1518	box_tuple = 1 << (b+k); /* include box in subset */	1518	box_tuple = 1 << (b+k); /* include box in subset */
1519	box_col_mask = boxmask[b+k];	1519	box_col_mask = boxmask[b+k];
1520		1520
1521	if (i - 1) for (t = 0; t < PUZZLE_DIM; t += PUZZLE_ORDER) { /* find other boxes in the subset, if any */	1521	if (i - 1) for (t = PUZZLE_DIM -1 ; t >= 0 ; t -= PUZZLE_ORDER) { /* find other boxes in the subset, if any */
1522		1522
1523	if (t != k && box_col_mask == boxmask[b+t]) { /* did we find one? */	1523	if (t != k && box_col_mask == boxmask[b+t]) { /* did we find one? */
1524	box_tuple \|= 1 << (b+t);	1524	box_tuple \|= 1 << (b+t);

rev27

	26		27
1068		1068
1069	static int validate(const Grid *g, int verbose)	1069	static int validate(const Grid *g, int verbose)
1070	{	1070	{
1071	int i, j, bc, mask, flag = 1;	1071	int i, j, bc, mask1, mask2, mask3, flag = 1;
1072	char buf[32];	1072	char buf[32];
1073		1073
1074	/* Sanity check */	1074	/* Sanity check */
...		...
1084	}	1084	}
1085		1085
1086	/* Check rows */	1086	/* Check rows */
1087	for (i = 0; i < PUZZLE_DIM; i++) {	1087	for (i = 0; i < PUZZLE_DIM; i++) {
1088	for (mask = j = 0; j < PUZZLE_DIM; j++) {
1089	if (bitcount(g->cell[row[i][j]]) == 1) mask \|= g->cell[row[i][j]];
1090	}
1091	if (mask != 0x01ff) {
1092	if (verbose) {
1093	fprintf(rejects, "Row %d is not solved for %s.\n", 1+i, clues(~mask, buf)); fflush(rejects);
1094	flag = 0;
1095	} else return 0;
1096	}
1097		1088
1098	/* Check columns */	1089	for (mask1 = mask2 = mask3 = j = 0; j < PUZZLE_DIM; j++) {
1099	for (mask = j = 0; j < PUZZLE_DIM; j++) {	1090	if (bitcount(g->cell[row[i][j]]) == 1) {
1100	if (bitcount(g->cell[col[i][j]]) == 1) mask \|= g->cell[col[i][j]];	1091	mask1 \|= g->cell[row[i][j]];
1101	}	1092	mask2 \|= g->cell[col[i][j]];
1102	if (mask != 0x01ff) {	1093	mask3 \|= g->cell[col[i][j]];
1103	if (verbose) {	1094	}
1104	fprintf(rejects, "Column %d is not solved for %s.\n", 1+i, clues(~mask, buf)); fflush(rejects);	1095	}
1105	flag = 0;
1106	} else return 0;
1107	}
1108		1096
1109	/* Check 3x3 boxes */	1097	if (mask1 != 0x01ff) {
1110	for (mask = j = 0; j < PUZZLE_DIM; j++) {	1098	if (verbose) {
1111	if (bitcount(g->cell[box[i][j]]) == 1) mask \|= g->cell[box[i][j]];	1099	fprintf(rejects, "Row %d is not solved for %s.\n", 1 + i,
1112	}	1100	clues(~mask1, buf));
1113	if (mask != 0x01ff) {	1101	fflush(rejects);
1114	if (verbose) {	1102	flag = 0;
1115	fprintf(rejects, "Box %d is not solved for %s.\n", 1+i, clues(~mask, buf)); fflush(rejects);	1103	} else
1116	flag = 0;	1104	return 0;
1117	} else return 0;	1105	}
1118	}	1106
		1107	/* Check columns */
		1108	if (mask2 != 0x01ff) {
		1109	if (verbose) {
		1110	fprintf(rejects, "Column %d is not solved for %s.\n", 1 + i,
		1111	clues(~mask2, buf));
		1112	fflush(rejects);
		1113	flag = 0;
		1114	} else
		1115	return 0;
		1116	}
		1117
		1118	/* Check 3x3 boxes */
		1119	if (mask3 != 0x01ff) {
		1120	if (verbose) {
		1121	fprintf(rejects, "Box %d is not solved for %s.\n", 1 + i,
		1122	clues(~mask3, buf));
		1123	fflush(rejects);
		1124	flag = 0;
		1125	} else
		1126	return 0;
		1127	}
1119	}	1128	}
1120		1129
1121		1130

rev28

Downcount in for in rsolv (min value finder).

	27		28
1834	memcpy(&mygrid, g, sizeof(Grid)); /* Make working copy of puzzle */	1834	memcpy(&mygrid, g, sizeof(Grid)); /* Make working copy of puzzle */
1835		1835
1836	/* Find the first cell with the smallest number of alternatives */	1836	/* Find the first cell with the smallest number of alternatives */
1837	for (c = -1, j = 0, min = PUZZLE_DIM, i = 0; i < PUZZLE_CELLS; i++) {	1837	for (c = -1, j = 0, min = PUZZLE_DIM, i = PUZZLE_CELLS - 1; i >= 0; i--) {
1838	if (mygrid.cellflags[i] == UNSOLVED) {	1838	if (mygrid.cellflags[i] == UNSOLVED) {
1839	j = bitcount(mygrid.cell[i]);	1839	j = bitcount(mygrid.cell[i]);
1840	if (j < min) {	1840	if (j < min) {

rev31

uncomment naked tuple elimination

static int rsolve(Grid *g)
{
    int i, j, min, c, mask, flag = NOCHANGE;
        Grid mygrid;

        /* Keep track of recursive depth */
        lvl += 1;
        if (lvl > g->maxlvl) g->maxlvl = lvl;

        /* Attempt a simple solution */
        while (simple_solver(g) != IMPASSE && g->exposed < PUZZLE_CELLS) {

                /* Eliminate clues aligned along chutes within boxes from */
        /* cells exterior to the box that are in those chutes     */
                if ((flag = chute_elimination(g)) == CHANGE) {
            EXPLAIN_CURRENT_MARKUP(g);
            continue;
        }

                /* Check if impasse or solution */
                if (flag == IMPASSE || g->exposed >= PUZZLE_CELLS) break;

        /* Eliminate tuples */
                if ((flag = naked_tuple_elimination(g)) == CHANGE) {
            EXPLAIN_CURRENT_MARKUP(g);
            continue;
        }

                /* Check if impasse or solution */
                if (flag == IMPASSE || g->exposed >= PUZZLE_CELLS) break;

                g->reward = lvl * 10;        /* Bump reward as we are about to start trial-and-error soutions */

                /* Attempt a trial solution */
            memcpy(&mygrid, g, sizeof(Grid));    /* Make working copy of puzzle */

Final Result

Vergleich mit Ausgangsversion (gcc -O)
Cycles    -64,58 %
Instructions Completed    -53,99 %
Mispredicted Branches    -77,14 %

Vergleich mit Ausgangsversion (gcc -O3)
Cycles    -47,75 %
Instructions Completed    -39,02 %
Mispredicted Branches    -59,61 %