Month
Month
Welcome to the CSIG, a Special Interest Group of the ACGNJ. This will be a "Members Night". Members are encouraged to bring in C++ questions, problems, and even programs to be discussed by the entire group. Additionally, we will have a review of topics covered during the last few months. Most of the programs previously presented used the latest C++ compiler in Microsoft's Visual Studio. There are a number of ways to refer to this compiler and code. Here's what Wikipedia says:
The Common Language Infrastructure (CLI) is an open specification developed by Microsoft that describes the executable code and runtime environment that form the core of the Microsoft .NET Framework. The specification defines an environment that allows multiple high-level languages to be used on different computer platforms without being rewritten for specific architectures.
| Microsoft .Net Framework 2.0, etc. |
| C++ 7.0, etc. |
| .Net 2.0, etc. |
| CLI |
| Common Language Infrastructure |
| Managed |
So bring in your Questions, Snippits and Programs for discussion.
/************************************************************************************/
/* */
/* Author: Bill DuPree */
/* Name: sudoku_engine.c */
/* Language: C */
/* Inception: Feb. 25, 2006 */
/* Copyright (C) August 17, 2008, All rights reserved. */
/* */
/* This is a program that solves Su Doku (aka Sudoku, Number Place, etc.) puzzles */
/* primarily using deductive logic. It will only resort to trial-and-error and */
/* backtracking approaches upon exhausting all of its deductive moves. */
/* */
/* Puzzles must be of the standard 9x9 variety using the (ASCII) characters '1' */
/* through '9' for the puzzle solution set. Puzzles should be submitted as 81 */
/* character strings which, when read left-to-right will fill a 9x9 Sudoku grid */
/* from left-to-right and top-to-bottom. In the puzzle specification, the */
/* characters 1 - 9 represent the puzzle "givens" or clues. Any other non-blank */
/* character represents an unsolved cell. */
/* */
/* The puzzle solving algorithm is "home grown." I did not borrow any of the usual */
/* techniques from the literature, e.g. Donald Knuth's "Dancing Links." Instead */
/* I rolled my own from scratch. As such, its performance can only be blamed */
/* on yours truly. Still, I feel it is quite fast. On a 333 MHz Pentium II Linux */
/* box it solves typical medium force puzzles in approximately 1100 microseconds or */
/* about 900 puzzles per second, give or take. On an Athlon 64 4000+ (2.4 GHz */
/* San Diego core) it solves about 8000 puzzles per sec. */
/* */
/* DESCRIPTION OF ALGORITHM: */
/* */
/* The puzzle algorithm initially assumes every unsolved cell can assume every */
/* possible value. It then uses the placement of the givens to refine the choices */
/* available to each cell. This is the markup phase. */
/* */
/* After markup completes, the algorithm then looks for "singleton" cells with */
/* values that, due to constraints imposed by the row, column, or 3x3 box, may */
/* only assume one possible value. Once these cells are assigned values, the */
/* algorithm returns to the markup phase to apply these changes to the remaining */
/* candidate solutions. The markup/singleton phases alternate until either no more */
/* changes occur, or the puzzle is solved. I call the markup/singleton elimination */
/* loop the "Simple Solver" because in a majority of cases it solves the puzzle. */
/* */
/* If the simple solver portion of the algorithm doesn't produce a solution, then */
/* more advanced deductive rules are applied. I've implemented two additional rules */
/* as part of the deductive puzzle solver. The first is "naked/hidden" subset */
/* elimination wherein a row/column/box is scanned for N number of cells with N */
/* matching candidate solutions. If such subsets are found in the row, column, or */
/* box, then the candidates values from the subset may be eliminated from all other */
/* unsolved cells within the row, column, or box, respectively. */
/* */
/* The second advanced deductive rule scans boxes looking for candidate values that */
/* exclusively align themselves along rows or columns within the boxes, aka */
/* chutes. If candidate values are found aligning within a set of N chutes aligned */
/* within N boxes, then those candidates may be eliminated from aligned chutes */
/* in boxes outside of the set of N boxes. */
/* */
/* Note that each of the advanced deductive rules calls all preceeding rules, in */
/* order, if that advanced rule has effected a change in puzzle markup. */
/* */
/* Finally, if no solution is found after iteratively applying all deductive rules, */
/* then we begin trial-and-error using recursion for backtracking. A working copy */
/* is created from our puzzle, and using this copy the first cell with the */
/* smallest number of candidate solutions is chosen. One of the solutions values is */
/* assigned to that cell, and the solver algorithm is called using this working */
/* copy as its starting point. Eventually, either a solution, or an impasse is */
/* reached. */
/* */
/* If we reach an impasse, the recursion unwinds and the next trial solution is */
/* attempted. If a solution is found (at any point) the values for the solution are */
/* added to a list. Again, so long as we are examining all possibilities, the */
/* recursion unwinds so that the next trial may be attempted. It is in this manner */
/* that puzzles with multiple solutions are enumerated. */
/* */
/* Note that it is certainly possible to add to the list of applied deductive */
/* rules. The techniques known as "X-Wing" and "Swordfish" come to mind. On the */
/* other hand, adding these additional rules will, in all likelihood, slow the */
/* solver down by adding to the computational burden while producing very few */
/* results. */
/* */
/* PUZZLE SCORING */
/* */
/* A word about puzzle scoring, i.e. rating a puzzle's difficulty, is in order. */
/* Rating Sudoku puzzles is a rather subjective thing, and thus it is difficult to */
/* develop an objective puzzle rating system. I, however, have attempted */
/* this feat (several times with varying degrees of success ;-) and I think the */
/* heuristics I've developed closely track the relative difficulty of solving a */
/* puzzle. */
/* */
/* The following is a brief rundown of how it works. The initial puzzle markup is */
/* a "free" operation, i.e. no points are scored for the first markup pass. I feel */
/* this is appropriate because a person solving a puzzle will always have to do */
/* their own eyeballing and scanning of the puzzle. Subsequent passes are */
/* scored at one point per candidate eliminated because these passes indicate */
/* that more deductive work is required. Secondly, the "reward" for solving a cell */
/* is set to one point, and as long as the solution does not require bifurcation, */
/* i.e. trial-and-error or recursion, then this level of reward remains unchanged. */
/* Also, puzzle "bottlenecks," wherein there are very few singletons (three or */
/* less) available after a round of deduction, are scored using the the formula: */
/* */
/* (20 * unsolved_cells_before_pass) / (solved_cells * (solved_this_pass + 1)) + 1 */
/* */
/* Other bottleneck penalties are assessed for the various deductive techniques */
/* applied during the solving process. They are computed as follows: */
/* */
/* Tuple elimination bottlenecks occur if such an elimination occurred but there */
/* were fewer than four changes to the puzzle markup. These are scored as: */
/* */
/* 20 - 5 * number_of_markup_changes */
/* */
/* Box-line alignment bottlenecks occur if this rule was successfully applied but */
/* there were fewer than three changes to markup. These are scored as: */
/* */
/* 15 - 5 * number_of_markup_changes */
/* */
/* In addition, box-line rules assess a penalty of five points per application, */
/* and naked tuple eliminations use the following calculation for their penalty: */
/* */
/* 10 + 2 * (5 - abs(5 - number_of_members_in_tuple)) */
/* */
/* The reason for such a calculation is that naked tuples form disjoint subsets */
/* with hidden tuples. Thus when the number of members in a naked subset is low, */
/* the difficulty is low. As the number increases so does the relative difficulty */
/* of finding the naked subset. However, for larger values of membership (five or */
/* better) it turns out that what we are really detecting are smaller and smaller */
/* hidden subsets, thus the penalty decreases. */
/* */
/* If a trial-and-error approach is called for, then the "reward" is set to the */
/* recursive depth times ten. Trial solutions are also penalized by a weighting */
/* factor that is computed as follows: */
/* */
/* unsolved_cells * trial_depth * trial_depth * alternatives_to_be_tried * 5 */
/* */
/* (I've seen a pathological puzzles require 16 or more levels of recursion score */
/* hundreds thousands of points using this scoring system!) */
/* */
/* And that brings me to this topic: What do all these points mean? */
/* */
/* Well, who knows? This is subjective, and the weighting system I've chosen */
/* for point scoring is is largely arbitrary and is derived from my own set of */
/* heuristics. But based upon feedback from a number of individuals, a rough scale */
/* of subjective difficulty plays out as follows: */
/* */
/* DEGREE OF DIFFICULTY | SCORE */
/* -------------------------+------------------------------------------ */
/* TRIVIAL | 80 points or less */
/* EASY | 81 - 125 points */
/* MEDIUM | 126 - 250 points */
/* HARD | 251 - 350 points */
/* VERY HARD | 351 - 760 points */
/* DIABOLICAL | 761 and up */
/* */
/* Experience shows that the hardest of the VERY HARD puzzles may require a small */
/* amount trial-and-error (bifurcation), and the DIABOLICAL puzzles will likely */
/* require more than one level of trial-and-error, so why waste your time? */
/* These are best left to masochists, savants and automated solvers. YMMV. */
/* */
/* LICENSE: */
/* */
/* This program is free software; you can redistribute it and/or modify */
/* it under the terms of the GNU General Public License as published by */
/* the Free Software Foundation; either version 2 of the License, or */
/* (at your option) any later version. */
/* */
/* This program is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
/* GNU General Public License for more details. */
/* */
/* You should have received a copy of the GNU General Public License */
/* along with this program; if not, write to the Free Software */
/* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
/* */
/* CONTACT: */
/* */
/* Email: bdupree@techfinesse.com */
/* Post: Bill DuPree, 609 Wenonah Ave, Oak Park, IL 60304 USA */
/* */
/************************************************************************************/
/* */
/* CHANGE LOG: */
/* */
/* Rev. Date Init. Description */
/* -------------------------------------------------------------------------------- */
/* 1.00 2006-02-25 WD Initial version. */
/* 1.01 2006-03-13 WD Fixed return code calc. Added signon message. */
/* 1.10 2006-03-20 WD Added explain option, add'l speed optimizations */
/* 1.11 2006-03-23 WD More simple speed optimizations, cleanup, bug fixes */
/* 1.20 2008-08-17 WD Fix early recursion. Rewrite markup, subset and */
/* box-line interaction. Add bottleneck detection and */
/* other scoring enhancements. Allow linkage to */
/* sudoku_engine as a reusable object module. */
/* (Thanks to Giuseppe Matarazzo for his suggestions.) */
/* */
/************************************************************************************/