8
\$\begingroup\$

This will be somewhat larger than many Code Review posts.
In a recent CR thread, an invitation was extended for me to post my DIY Sudoku solver.
For the fun of it, here we are... I'm buzzing with excitement.

  • This has been written for my antiquated C++ compiler, but is really a C Windows Console app.
    (The old compiler allowed variables to be defined close to use, rather than grouped after any open brace.)
  • Comments are sparse and variable & function names terse. This was a "one coder" project.
  • A few "global" variables (the internal "game model" of 9x9 cells, for instance) obviate the need for passing app specific parameters that do not change.
  • The coder (me) did not use const and other language guard rails as piecewise, incremental development and frequent testing seemed to preclude the necessity.
  • Optimal speed was not an objective.
  • "Overview analysis" of the state of the game for different solving stategies varied for some advanced strategies purely for the interest of trying different approaches.
  • Some Sudokus are specifically "set" as "X-Factor" games.
    The file of games can have rows (1 game/row) that indicate "this game should invoke X-Factor analysis".
  • The penultimate strategy coded ("X-chaining" aka Xchn()) is only partially developed.
    The analysis for this and other off-the-wall strategies rely on a form of trial-and-error tantamount to Brute Force.
    "What's the point?", I asked myself!
    The final strategy is Brute Force, with visible backtracking if required.
  • Game progress is logged to "./___Played.lst" for review.
    Copy/paste of a partially solved game as a game to be played speeds development of a strategy; effectively a form of "Fast Forward to here".
  • There is a primitive vestigial print debugging facility left in the code.
    Messages can be displayed below the Sudoku grid for development of algorithms.
    Not sophisticated, but functional.

One wants to use a wide screen monitor with a full sized console ('terminal') window to run the solver.

The solver begins by showing the number of games available. Enter a value to start the solver solving that game.

The solver has 10 "speeds" (its current "Pace".)
Initially the Pace is 5.
1 is slowest, 9 is PDQ, and 0 is just do it!
+ and - increase and decrease the Pace by 1.

The space bar or 'Return' pauses the solver until a second press of either key resumes the solver.

Lowercase 's' toggles "stepping mode".
At certain points while updating the display, "stepping on" automatically engages "Pause" for the user to consider the solving being performed.

When a strategy more advanced than the two "easy" strategies is applied, and some candidates can be eliminated, the solver engages its throttle (reduced Pace) for the user to appreciate what's occurring.
Upon completion of this cell, Pace is reset to 5 and solving continues.

The escape key resets the game to its initial state awaiting user selection of a game to be solved.


This hobby development began a few years ago (2015) after learning that the Singapore PM, trained as an engineer, had made public his Sudoku Solver code (7 year old Github posting following international news event in May, 2015). That turned out to be only marginally better than a basic Brute Force Solver. The game was on!

The code is presented "as is" for those who have the time and interest. I will try to answer legitimate questions, but caution the reader that documentation is the code itself and this Code Review posting only.

Any/all commentary is welcome. Suggestions to decorate the code with modern C enhancements such as restrict, etc. are also welcome for enlightenment of those readers contemplating adopting/adapting this code for their own experimentation.

I suggest decreasing any modern compiler's sensitivity to current C standards and warning levels.
This code does compile and the executable does run after using my antiquated compiler.

Have fun!


Before presenting the code, here are some "games" to demonstrate the layout of the source data.
(Currently hardwired filename: "./_Puzzles.lst"):

# _Puzzles.lst - collection of various Sudokus
#
# Leading pipe '|' is an available game
# Leading hash '#' is a commented line
# Leading 'X' is a game designed to be solved as an "X-Factor" game
# Digits, empties and segments should be self-evident
# Intervening pipes are ignored
# Beyond 81 digits or dots are ignored; suitable for game specific comments
|.98..4..6|.7..6....|6.29.....||9....6.21|...4.8...|56.1....9||.....74.2|....1..5.|2..5..68.|,simple
|...1.....|8...652..|...47...8||359.27.6.|.4.....5.|.2.54.793||9...16...|..428...7|.....4...|,simple
|5...9..6.|...5..1.7|..4..1.9.||..14.765.|.........|.381.57..||.4.3..5..|1.7..4...|.2..7...4|,simple
|.........|9.46.7...|.768.41..||3.97.1.8.|..8...3..|.5.3.87.2||..75.261.|...4.32.8|.........|,HdnPair
|.........|231.9....|.65..31..||..8924...|1...5...6|...1367..||..93..57.|....1.843|.........|,HdnTrpl
|3.......5|.56.34.7.|9..1..32.||19..7....|..54231..|....1..57||.63..9..2|.1.56.73.|7.......9|,simple,x-wing
|34129....|2..83.9..|9....6...||.9......3|.75...19.|6......5.||...7....2|..9.62..8|....41569|,x-wing after HdnPair
|3....7.85|..68..9..|.87.5.3..||.....58.3|....2....|6.49.....||..3.8.41.|..9..27..|72.3....9|,x-wing after Pair-Pair-Trpl
|.41..7.8.|.5.8.49..|..7...3..||1....5..3|....2....|6..9....7||..3...4..|..95.2.3.|.2.3..56.|,x-wing after Pairs-Trpls-Ptrs
|7...8.4..|6..3.1...|..8.5...1||5..6..2..|3...1...8|..6..3..5||1...7.8..|...2.8..4|..5.6...3|,Y-Wing after HBox
|.....7.21|...6.8...|....5..86||93.7..4..|..6.4.5..|..4..9.63||67..3....|...1.6...|14.9.....|,many strategies
|..47....9|96...84..|......3.2||...4....7|.5.897.4.|7....6...||4.2......|..91...86|6....97..|,swordfish with many other strategies
|....4.316|...8...5.|51...6..8||9......47|.31...69.|46......5||1..3...74|.7...5...|352.7....|,swordfish I'll be damned!
|.......5.|.5.9..3..|3..754..8||..8.4.6..|17..2..45|..5.7.2..||5..867..4|..9..5.8.|.6.......|,simple then BRUTE FORCE
|.369..4..|79..6...2|..4...16.||..34...1.|...3.8...|.4...76..||.15...8..|4...7..91|..7..924.|,multicolor,BRUT after HdnQuad

This line is too short, so is ignored. A "comment".

Same as previous game, but "disabled" to demonstrate "switching off" a game
#.369..4..|79..6...2|..4...16.||..34...1.|...3.8...|.4...76..||.15...8..|4...7..91|..7..924.|,multicolor,BRUT after HdnQuad

# Following is an X-Factor Sudoku. (leading char is 'X')
# Source: https://puzzlemadness.co.uk/xsudoku/medium "Simple X-Factor" for 2024.05.26
# Notice '0' or '.' are equivalent.
# "STEP" in "game comment" causes solver to begin in "stepping mode".
# Type 's' to toggle "stepping mode" on/off.
# Solver will 'bump-off' candidates on diagonals as well as usual row/col/sqr

X000000070|000700003|240003901||900000004|000010600|000630009||003007210|005006390|721000050|,X-Factor,STEP

# Below is solution as "X-Factor" puzzle.
#368941572|159762843|247583961||936875124|874219635|512634789||693457218|485126397|721398456|
                        **         *   *    ** *      *  * *      **                   **
#368491572|159762843|247853961||936275184|872914635|514638729||693547218|485126397|721389456|
# Above is solution as "normal" Sudoku (Brute Forced with this Solver).
# Notice: when not-defined as X-Factor, puzzles can have multiple solutions

And the 4 header files interspersed with 4 code files

// main.h
#ifndef MAIN_H
#define MAIN_H

// value and a bitfield of possible values
// And offsets to its siblings in its row, col and square.

typedef struct cell {
    int row, col, sqr;
    int valu;       // 0 is 'unknown', else 1 - 9
    int bits;       // 9 flag bits of possible values
    int nBit;       // count of remaining possible values
    cell *nxt[3];   // next cell in each dimension
    cell *nxtUnk;   // circular linked list of unsolved cells
    char id[ 4+1 ]; // id = "[rc]" like "[A1]" or "[I7]"
} Cell;

enum {
    eNxtR,  // +1, +1, +1, ..., (+1 - 9)
    eNxtC,  // +9, +9, +9, ..., (+9 - 81)
    eNxtS   // +1, +1, (+1 - 3 + 9), ..., (-2 - 18)
};

#ifdef MAIN_SRC
#define GLOBAL
#else
#define GLOBAL extern
#endif

GLOBAL Cell *modlTL; // Top Left cell of grid
GLOBAL Cell *unkBase;
GLOBAL int toSolve;
GLOBAL int stepping;
GLOBAL int modeXfct;

//#define unsigned char uint8_t;

Cell *getHunt( int n );
Cell *rc2cell( const int r, const int c );
Cell *ind2cell( const int ind );
int cell2ind( Cell *p );

#endif
// main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>

#define  MAIN_SRC
#include "main.h"
#include "display.h"
#include "solve.h"
#include "helper.h"

static const char *fname = "_Puzzles.lst";
static Cell modl[9][9];

Cell *rc2cell( const int r, const int c ) {
    return &modl[ r ][ c ];
}

Cell *ind2cell( const int ind ) {
    return &modl[ ind / 9 ][ ind % 9 ];
}

int cell2ind( Cell *p ) {
    return p->row * 9 + p->col;
}

Cell *getHunt( int n ) {
//  A - -|- - -|- - -   cells A-I do not share any "unit"
//  - - -|B - -|- - -
//  - - -|- - -|C - -
//  -----------------
//  - D -|- - -|- - -
//  - - -|- E -|- - -
//  - - -|- - -|- F -
//  -----------------
//  - - G|- - -|- - -
//  - - -|- - H|- - -
//  - - -|- - -|- - I
    return n < 9 ? rc2cell( n, "036147258"[n] - '0' ) : NULL; // col translated instead of modulo calc
}

static void initModl( void ) {
    memset( modl, 0, sizeof modl );
    // standard initialization for each cell
    for( int r = 0; r < 9; r++ )
        for ( int c = 0; c < 9; c++ ) {
            Cell *p = assignVBN( rc2cell( r, c ), 0, 0777, 9 ); // Set 9 bits
            sprintf( p->id, "[%c%c]", r + 'A', c + '1' );

            p->row = r;
            p->col = c;
            p->sqr = r/3*3 + c/3;

            int i = 1; // to set next in sqr
            if( c == 2 || c == 5 || c == 8 ) {
                i += -3 + 9; // -3 cols AND +1 row
                if( ( r == 2 || r == 5 || r == 8 ) )
                    i += -3 * 9; // -3 rows to point to first in sqr
            }

            p->nxt[ eNxtR ] = p + (c < 8 ? 1 : 8*-1); // +1 OR  -8 horizontal
            p->nxt[ eNxtC ] = p + (r < 8 ? 9 : 8*-9); // +9 OR -72 vertical
            p->nxt[ eNxtS ] = p + i;
            p->nxtUnk = p + 1;
        }

    unkBase = modlTL = rc2cell( 8, 8 )->nxtUnk = rc2cell( 0, 0 );   // shrinking ring of linked cells
    toSolve = 9*9;
}

static void loadModl( char *cp ) {
//  hold( HLD_tmpQuick ); // fixme
    hold( HLD_standard ); // fixme

    stepping = 0;
    modeXfct = ( *cp == 'X' ); // set BEFORE looping to assign values

    for( int i = 0; i < 9*9; cp++ )
        if( '1' <= *cp && *cp <= '9' )
            assign( rc2cell( i/9, i%9 ), *cp - '0' ), i++;
        else i += (*cp == '.' || *cp == '0'); // NB: any other character is simply ignored

    stepping = strstr( cp, "STEP" ) != NULL; // set AFTER completing loops

    // always begin with most TL unassigned cell
    for( unkBase = modlTL; toSolve && unkBase->nBit == 0; ) unkBase = unkBase->nxtUnk;
    hold( HLD_standard );
}

static int select( int nPuzls ) {
    int n = 0;
    char buf[ 32 ];
    cursor( 1 );
    do {
        say( "\f" );
        printf( "%d available.  Select: ", nPuzls );
        if( fgets( buf, sizeof buf, stdin ) == 0 ) break;
    } while( ( n = strtol( buf, NULL, 0 ) ) < 0 || nPuzls < n );
    cursor( 0 );
    return n;
}

static int segment( char *cp, char **arr[] ) {
    char **lst = NULL;
    int i = 0;
    for( ; ( cp = strtok( cp, "\r\n" ) ) != NULL; cp = NULL )
        if( ( *cp == '|' || *cp == 'X' ) && strlen( cp ) >= 81 ) {
            char **tmp = (char **)realloc( lst, (i + 1) * sizeof *tmp );
            if( tmp == NULL ) fatal( "realloc failure" );
            (lst = tmp)[ i++ ] = cp;
        }
    if( i ) *arr = lst;
    return i;
}

GLOBAL jmp_buf envbuf;

int main( int ac, char *av[] ) {
    ac = ac; av = av;
//  if( ac < 2 ) fatal( "Usage: %s <puzzle file>", av[0] );

    char **arr, *buf = loadFile( fname );
    int n, nPuzl = segment( buf, &arr );
    if( !nPuzl )
        fatal( "No puzzles found in '%s'", fname );

    setjmp( envbuf );
    while( ( n = select( nPuzl ) ) != 0 ) {
        dispGrid();
        initModl();
        loadModl( arr[ n - 1 ] );
        solve();
    }
    free( arr );
    free( buf );

    return 0;
}
// helper.h
#ifndef HELPER_H
#define HELPER_H

void debug( char *fmt, ... );
void fatal( char *fmt, ... );
char *loadFile( const char *fname );
int hold( int h );
void pause( void );
void clearKbrd( void );

enum {
    HLD_precapture, // must be zero
    HLD_cell2cell,
    HLD_sustain,
    HLD_standard,
    HLD_tmpQuick,
    HLD_none,
    HLD_throttleON,
    HLD_throttleOFF,
    HLD_longPause,
    HLD_paceValue,
};

#endif
// helper.cpp
#include <stdio.h>
#include <stdarg.h>
#include <setjmp.h>
#include <sys/stat.h>

#include <Windows.h> // Sleep()
#include <conio.h> // _kbhit(), _getch()

#include "main.h"
#include "display.h"
#include "helper.h"

void debug( char *fmt, ... ) {
    static int row = 39;

    if( !fmt[0] ) { dispDebugErase( row = 39 ); return; }

    printf( "\033[%d;1H" "\033[0;0m", row++ );

    va_list ap;
    va_start( ap, fmt );
    vprintf( fmt, ap );
    va_end( ap );

    pause();
}

void fatal( char *fmt, ... ) {
    va_list ap;
    va_start(ap, fmt);
    vfprintf( stderr, fmt, ap );
    va_end( ap );

    fprintf( stderr, "\nPress Enter to terminate\n" );
    getchar();
    exit( EXIT_FAILURE );
}

// load file contents (plus '\0') to heap memory
char *loadFile( const char *fname ) {
    struct stat finfo;
    if( stat( fname, &finfo ) != 0 )
        fatal( "stat('%s') failed\n", fname );

    FILE *fp;
    if( ( fp = fopen( fname, "rb" ) ) == NULL )
        fatal( "fopen('%s') failed\n", fname );

    char *buf;
    if( ( buf = (char*)malloc( finfo.st_size + 1) ) == NULL )
        fatal( "malloc( %u ) failed\n", finfo.st_size + 1 );

    if( fread( buf, sizeof buf[0], finfo.st_size, fp ) != (size_t)finfo.st_size )
        fatal( "fread('%s') incomplete\n", fname );

    fclose( fp );

    buf[ finfo.st_size ] = '\0';

    return buf;
}

void pause( void ) {
    say( "\r%s%-12s", clrStr( CLR_Pause ), "   Paused" );
    for( int c; !_kbhit() || ( ( c = _getch() ) != ' ' && c != '\r' ); ) Sleep( 100 );
    say( "\r%s%-12s", clrStr( CLR_Normal ), "" );
}

void clearKbrd( void ) {
    while( _kbhit() ) _getch(); // clear pending keyboard input
}

extern jmp_buf envbuf;

int hold( int h ) {
    int hold[][3] = {
        {      0,     0,      0,    }, // 0 => as fast as possible
        {   1250,   400,    800,    }, // 1 - slow
        {   1100,   350,    700,    }, // 2
        {    950,   300,    600,    }, // 3
        {    800,   250,    500,    }, // 4
        {    650,   200,    400,    }, // 5 - start up
        {    450,   150,    300,    }, // 6
        {    300,   100,    200,    }, // 7
        {    150,    50,    100,    }, // 8
        {      0,     0,    100,    }, // 9 - zippy
        //     |      |       |
        //     |      |       +-HLD_sustain
        //     |      +-HLD_cell2cell
        //     +-HLD_precapture
    };

    const int paceStd = 5, paceThrottle = 2;
    static int pace = paceStd;

    switch( h ) {
        case HLD_longPause:
            if( stepping ) { pause(); break; }
            h = HLD_precapture;
            /* FALLTHROUGH */

        case HLD_precapture:
        case HLD_cell2cell:
        case HLD_sustain:
            Sleep( hold[ pace ][ h ] );
            break;

        case HLD_standard:
            dispPace( pace = paceStd );
            break;

        case HLD_tmpQuick:
            dispPace( pace = 0 );
            break;

        case HLD_none: break;

        case HLD_throttleON:
            dispSpcl( SPCL_throtON );
            dispPace( pace = paceThrottle );
            break;

        case HLD_throttleOFF:
            Sleep( hold[ pace = paceStd ][ HLD_sustain ] ); // Note: "sustain"
            dispSpcl( SPCL_throtOFF );
            dispPace( pace );
            break;

        case HLD_paceValue:
            return pace;
    }

    /*
     * and now, poll the keyboard for something new
     */

    enum {
        K_ESC = 27,
//      K_F1 = 315, K_F2 = 316, K_F3 = 317,
//      K_F4 = 318, K_F5 = 319, K_F6 = 320,
//      K_F7 = 321, K_F8 = 322, K_F9 = 323,
//      K_FA = 324, // "F10"
//      K_ARROW_UP = 328,
//      K_ARROW_LL = 331,
//      K_ARROW_RT = 333,
//      K_ARROW_DN = 336,
    };

    while( _kbhit() ) {
        int keycode = _getch();
        if( keycode == 0 || keycode == 224 )
            keycode = 256 + _getch(); // extended keys (eg. F10) add 256

        switch( keycode ) {
            case K_ESC: longjmp( envbuf, 1 ); break;

            case '0':
            case '1': case '2': case '3':
            case '4': case '5': case '6':
            case '7': case '8': case '9':
                pace = keycode - '0';
                break;

            case 's':
                say( "Step %s", (stepping = !stepping) ? "On" : "Off" );
                break;

            case '\r':
            case ' ': pause(); break;

            case '-': if( pace > 1 ) pace--; break;
            case '+': if( pace < 9 ) pace++; break;

            default:
                say( "Keycode: %d '%c'", keycode, ' ' <= keycode && keycode < 127 ? keycode : '?' );
                break;
        }
        dispPace( pace );
    }
    return 0;
}
// display.h
#ifndef DISPLAY_H
#define DISPLAY_H

enum {
    CLR_WhtOnBlk,
    CLR_BlkOnBlk,
    CLR_BlkOnGrn,
    CLR_BlkOnYlw,
    CLR_BlkOnPnk,
    CLR_BlkOnGry,

    CLR_Normal = CLR_WhtOnBlk,
    CLR_Puzl = CLR_BlkOnGrn,
    CLR_Keep = CLR_BlkOnGrn,
    CLR_Elim = CLR_BlkOnYlw,
    CLR_Erase = CLR_BlkOnBlk,

    CLR_Pause    = CLR_BlkOnGry,
    CLR_Throttle = CLR_BlkOnYlw,

    SPCL_throtON    = (0x01<<1)|1,
    SPCL_throtOFF   = (0x01<<1)|0,
};

char *clrStr( int clr );

char v2ch( int v );

void dispGrid( void );
void dispCell( Cell *p, int v, int clr, int hld );
void dispExam( Cell *p, int v, int clr );

void say( char *fmt, ... );
void cursor( int ONoff );
void dispPace( int pace );
void dispSpcl( int slct );

void dispDebugErase( int r );

#endif
// display.cpp
#include <stdio.h>
#include <string.h>
#include <stdarg.h>

#include "main.h"
#include "solve.h"
#include "helper.h"
#include "display.h"

static enum {
    PuzlTL_r = 3, PuzlTL_c =   4,   // puzl board TL
    PossTL_r = 3, PossTL_c =  44,   // poss board TL
     SayTL_r = 3,  SayTL_c = 101    // "say" TL
};

char v2ch( int v ) { return " 123456789"[ v ]; }

char *clrStr( const int clr ) {
    static char *cstr[] = {
        "\033[0;0m",    // wht on blk - CLR_WhtOnBlk
        "\033[40;30m",  // blk on blk - CLR_BlkOnBlk
        "\033[102;30m", // blk on grn - CLR_BlkOnGrn
        "\033[103;30m", // blk on ylw - CLR_BlkOnYlw
        "\033[105;30m", // blk on pnk - CLR_BlkOnPnk
        "\033[47;30m",  // blk on gry - CLR_BlkOnGry
        "\033[106;30m", // blk on blu
    };

    return cstr[ clr ];
}

static void printAt( int r, int c, int clr, char *str ) {
    printf( "\033[%d;%dH%s%s", r, c, clrStr( clr ), str );
}

static char *fillBuf( char *buf, int ch, int wid, int cw, int c1, int c2 ) {
    memset( buf, ch, wid );
    buf[1*cw+0] = buf[2*cw+1] =
    buf[4*cw+3] = buf[5*cw+4] =
    buf[7*cw+6] = buf[8*cw+7] = c1;
    buf[3*cw+2] = buf[6*cw+5] = c2;
    return buf;
}

void dispGrid( void ) {
    enum {
        V1 = 0263, // single vertical
        V2 = 0272, // double vertical
        H1 = 0304, // single horizontal
        H2 = 0315, // double horizontal
        J1 = 0305, // single junction
        J2 = 0316, // double junction

        clr = CLR_Normal
    };

    { /* standard small grid on the left */
        const int cw = 3;
        const int wid = (cw+1+cw+1+cw) + 1 + (cw+1+cw+1+cw) + 1 + (cw+1+cw+1+cw);
        char buf[ wid + 1 ] = { 0 };
        int r = PuzlTL_r;
        int c = PuzlTL_c;

        for( size_t i = 1; i <= 9; i++ ) {
            printAt( r++, c, clr, fillBuf( buf, ' ', wid, cw, V1, V2 ) );

            if( i == 3 || i == 6 )
                printAt( r++, c, clr, fillBuf( buf, H2, wid, cw, H2, J2 ) );
            else if( i < 9 )
                printAt( r++, c, clr, fillBuf( buf, H1, wid, cw, J1, V2 ) );
        }
    }
    { /* large grid of possibles in the middle */
        const int cw = 5;
        const int wid = (cw+1+cw+1+cw) + 1 + (cw+1+cw+1+cw) + 1 + (cw+1+cw+1+cw);
        char buf[ wid + 1 ] = { 0 };
        int r = PossTL_r;
        int c = PossTL_c;

        for( size_t band = 0; band < 3; band++ ) { // 3 Sudoku "bands"
            for( size_t bandRow = 1; bandRow <= 9; bandRow++ ) { // each Sudoku "band" is 9 rows high
                fillBuf( buf, ' ', wid, cw, V1, V2 );

                for( size_t n = 0; n < 9; n++ ) // 9 horizontal "cells" per row
                    memcpy( &buf[n*6], "1 2 3 4 5 6 7 8 9" + ((bandRow-1) % 3)*6, 5 );

                printAt( r++, c, clr, buf );

                if( bandRow == 3 || bandRow == 6 )
                    printAt( r++, c, clr,  fillBuf( buf, H1, wid, cw, H1, J2 ) );
            }
            if( band < 2 ) // "band" separater
                printAt( r++, c, clr , (char*)memset( buf, 0376, wid ) ); // half height blob
        }
    }
}

void dispCell( Cell *p, int v, int clr, int hld ) {
    int r = PuzlTL_r + p->row*2;
    int c = PuzlTL_c + p->col*4;

    char str[] = "   "; str[1] = v2ch( v );
    printAt( r, c, clr, str );

    if( clr == CLR_Normal ) { // blank out the exam grid cell
        r = PossTL_r + p->row*(3+1);
        c = PossTL_c + p->col*(5+1);
#if 0
        for( int i = 0; i < 3; i++ )
            printAt( r++, c, clr, "     " );
#else
#       define REWIND "\033[5D\033[1B" // 5x left + 1x down
        printAt( r, c, clr, "     " REWIND  "     " REWIND  "     " );
#endif
    }
    hold( hld );
}

void dispExam( Cell *p, int v, int clr ) {
    int r = PossTL_r + p->row*(3+1) + ((v-1)/3);
    int c = PossTL_c + p->col*(5+1) + (((v-1)%3) * 2);

    char str[] = " "; str[0] = v2ch( v );
    printAt( r, c, clr, str );
    hold( HLD_cell2cell );
}

void cursor( int ONoff ) {
    printf( "\033[?25%c", "lh"[ ONoff ] );
}

void say( char *fmt, ... ) {
    static int r = 0, c = 0;
    const int maxVert = 35;
    const int colWide = 27;

    if( fmt[0] == '\f' ) {
        printAt( r = 0, c = 0, CLR_Normal, "\033[J" ); // cursor home & erase screen
        return;
    }
    int adv = 1;
    if( fmt[0] == '\r' ) adv = 0, fmt++;
    if( fmt[0] == '+' ) r++, fmt++; // blank row

    if( r == maxVert ) r = 0, c += 1; // next column

    printAt( SayTL_r + r, SayTL_c + (c * colWide), CLR_Normal, "" );

    r += adv;

    va_list ap;
    va_start( ap, fmt );
    vprintf( fmt, ap );
    va_end( ap );
}

void dispPace( int pace ) {
    char str[] = "pace = ?"; str[7] = v2ch( pace );
    printAt( 23, 13, CLR_Normal, str );
}

void dispSpcl( int slct ) {
    struct {
        char *str;
        int clr;
    } modes[] = {
        { "            ", CLR_Normal, },
        { "  Throttle  ", CLR_Throttle, },
    }, *p = modes;

    if( slct & 1 ) p += b2v( slct>>1 );
    printAt( 24 + b2v( slct>>1 ), 15, p->clr, p->str );
}

void dispDebugErase( int r ) {
    printAt( r, 1, CLR_Normal, "\033[0J" );
}
// solve.h
#ifndef SOLVE_H
#define SOLVE_H

int b2v( int b );
Cell *assignVBN( Cell *p, int v, int b, int n );
void assign( Cell *p, int v );
void solve( void );

#endif

And the big one (a bit of a behemoth!)

// solve.cpp
#include <stdio.h>

#include "main.h"
#include "display.h"
#include "solve.h"
#include "helper.h"

static int bits[] = { 0000, 0001, 0002, 0004, 0010, 0020, 0040, 0100, 0200, 0400 };

static int v2b( int v ) {
    return bits[ v ];
}

int b2v( int bit ) {
    int v = 1;
    while( !( bit & bits[v] ) ) v++;
    return v;
}

static int bitCnt( int x ) { // Kernighan's bit count
    int n = 0;
    while( x ) n++, x &= x - 1;
    return n;
}

static void onceMult( int bits, int *once, int *mult ) {
    *mult |= *once & bits; // gate thru ONLY multiple occurences
    *once |= bits; // bits seen at least once
}

static int getLoBit( int *bits ) {
    int bl =  *bits & (-*bits); // lowest set bit
    *bits &= ~(bl);
    return bl;
}

#define SameR( p, q ) ( (p)->row == (q)->row )
#define SameC( p, q ) ( (p)->col == (q)->col )
#define SameS( p, q ) ( (p)->sqr == (q)->sqr )

static int addOnce( Cell **pKnwn, Cell *p ) {
    while( *pKnwn ) if( *pKnwn++ == p ) return 0;
    *pKnwn = p;
    return 1;
}

static void loseBit( Cell *p, int bit ) {
    dispExam( p, b2v( bit ), CLR_Erase );
    p->bits &= ~bit;
    p->nBit--;
}

static int sameUnit( Cell *p, Cell *px ) {
    if( SameR( px, p ) || SameC( px, p ) || SameS( px, p ) ) return 1;
    return modeXfct &&
        (   px->row == px->col && p->row == p->col // both on downward slope TL to BR
         || px->row + px->col == 8 && p->row + p->col == 8 ); // both on upward slope BL to TR
}

typedef unsigned long cellbit_t;

static cellbit_t encode( unsigned long keepElim, Cell *p, int b ) {
    return (keepElim << 16) | (cell2ind( p ) << 9) | ( b );
}

static Cell *decode( const cellbit_t cb, int *keepElim, int *b ) {
    *b = cb & 0777;
    *keepElim = (cb >> 16);
    return ind2cell( (cb >> 9) & 0x7F );
}

enum { Sngls, PairTrpl, YWng, Hidn };

static void elim( int typ, int n, Cell *wrk[], int bits[] ) {
    cellbit_t cb[ (9*4) + 1 ] = { 0 };

    int i = 0, w = 0;
    switch( typ ) {
        case Sngls: 
            for( ; wrk[i]; i++ )
                if( wrk[i]->bits & bits[0] )
                    cb[ w++ ] = encode( (i < n) ? 1 : 0, wrk[i], bits[0] );
            break;
        case PairTrpl:
            for( ; wrk[i]; i++ )
                for( int bi = n; bi--; )
                    if( wrk[i]->bits & bits[bi] )
                        cb[ w++ ] = encode( (i < n) ? 1 : 0, wrk[i], bits[bi] );
            break;
        case YWng:
            for( ; i < 3; i++ )
                for( int b, bb = wrk[i]->bits; ( b = getLoBit( &bb ) ) != 0; )
                    cb[ w++ ] = encode( 1, wrk[i], b );
            cb[ w++ ] = encode( 0, wrk[i], bits[0] );
            break;
        case Hidn:
            for( ; i < n; i++ )
                for( int b, bb = bits[0]; ( b = getLoBit( &bb ) ) != 0; )
                    if( wrk[i]->bits & b )
                        cb[ w++ ] = encode( 1, wrk[i], b );

            for( i = 0; i < n; i++ )
                for( int b, bb = (wrk[i]->bits & ~bits[0]); ( b = getLoBit( &bb ) ) != 0; )
                //  if( 1 ) // for code structure
                        cb[ w++ ] = encode( 0, wrk[i], b );
            break;
    }
    hold( HLD_throttleON );

    int ke, b;
    for( i = 0; cb[ i ]; i++ ) {
        Cell *p = decode( cb[ i ], &ke, &b );
        dispExam( p, b2v( b ), ke ? CLR_Keep : CLR_Elim );
    }
    hold( HLD_longPause );

    while( i-- ) {
        Cell *p = decode( cb[ i ], &ke, &b );
        if( ke )
            dispExam( p, b2v(b), CLR_Normal );
        else
            loseBit( p, b );
    }

    hold( HLD_throttleOFF );
}

void assign( Cell *p, int v ) {
    Cell *wrk[ 5*9 ] = { 0 };

    if( hold( HLD_paceValue ) ) {
        dispCell( p, v, CLR_Puzl, HLD_precapture );
        dispExam( p, v, CLR_Keep );
        hold( HLD_longPause );
    }

    assignVBN( p, v, 0, 0 );

    int bit = v2b( v ), i = 0;
    Cell *px = p;
    do { if( (px->bits & bit) && sameUnit( px, p ) ) wrk[i++] = px; } while( ( px = px->nxtUnk ) != p );

    if( hold( HLD_paceValue ) ) {
        for( i = 0; wrk[i]; i++ )
            dispExam( wrk[i], v, CLR_Elim );
        hold( HLD_sustain );
    }

    for( i = 0; wrk[i]; i++ )
        loseBit( wrk[i], bit );

    dispCell( p, v, CLR_Normal, HLD_sustain );

    // Drop this cell OUT of the ring...
    for( i = --toSolve; i--; ) p = p->nxtUnk;
    unkBase = p->nxtUnk = p->nxtUnk->nxtUnk;
}

/* * * * */

static int lone( void ) {  // find "sole candidate"
    Cell *p = unkBase;

    do { if( p->nBit == 1 ) break; } while( ( p = p->nxtUnk ) != unkBase );

    if( p->nBit != 1 ) return 0;

    int bv = b2v( p->bits );
    say( "%s %d Lone", p->id, bv );
    assign( p, bv );

    // minimize jumps by favouring same sqr, then same col, then same row
    for( int dim = 3; dim--; )
        for( Cell *px = p->nxt[ dim ]; px != p; px = px->nxt[ dim ] )
            if( px->nBit == 1 ) { unkBase = px; return 1; }

    return 1;
}

/* * * * */

static int uniq( void ) { // find only instance in row/col/sqr
    for( int hnt = 0; hnt < 9; hnt++ ) {
        Cell *px = getHunt( hnt ), *p = px; // hunting origins
        for( int dim = 0; dim < 3; dim++ ) { // three dimensions (row, col, sqr)
            int occ1 = 0, occX = 0, bit;
            do { onceMult( p->bits, &occ1, &occX ); } while( ( p = p->nxt[ dim ] ) != px );
            occ1 &= ~occX;

            if( occ1 ) {
#if 1 // a single Unique in a "unit" assigns immediately
                int bv = b2v( bit = getLoBit( &occ1 ) );

                while( !(p->bits & bit) ) p = p->nxt[ dim ]; // find cell with that bit
                assignVBN( p, bv, bit, 1 ); // force it...

                say( "%s %d Unique (%s)", p->id, bv, "row\0col\0sqr" + dim * (3+1) );
                assign( p, bv );
#else // Several uniques in a "unit" can found, their extraneous bits turned off, and "lone()" cleans up afterward
                while( ( bit = getLoBit( &occ1 ) ) != 0 ) {
                    while( !(p->bits & bit) ) p = p->nxt[ dim ]; // find cell with that bit
                    say( "%s %d Unique (%s)", p->id, b2v( bit ), "row\0col\0sqr" + dim * (3+1) );
                    elim( Hidn, 1, &p, &bit );
                }
#endif
                return 1;
            }
        }
    }
    return 0;
}

/* * * * */

static int nptqTry( int n, Cell *p1, Cell *p2, Cell *p3 ) {
    Cell *wrk[ 2*9 ] = { p1, p2, p3 }; // row or col or sqr or row+sqr or col+sqr only

    int bits = p1->bits | p2->bits | wrk[n-1]->bits; // 2 => 0,1,1  3 => 0,1,2
    if( bitCnt( bits ) != n ) return 0; // must be from the same bits (only) involved

    int dim = 0;
         if( SameR( p1, p2 ) && ( n < 3 || SameR( p1, p3 ) ) ) dim = eNxtR;
    else if( SameC( p1, p2 ) && ( n < 3 || SameC( p1, p3 ) ) ) dim = eNxtC;
    else if( SameS( p1, p2 ) && ( n < 3 || SameS( p1, p3 ) ) ) dim = eNxtS;
    else return 0; // must share at least one dimension

    for( Cell *p = p1->nxt[ dim ]; p != p1; p = p->nxt[ dim ] )
        if( p->bits & bits )
            addOnce( wrk, p ); // add to list if not there already

    if( !wrk[n] ) return 0; // nothing added

    int b[3] = { 0 }, v[3] = { 0 };

    v[0] = b2v( b[0] = getLoBit( &bits ) );
    v[1] = b2v( b[1] = getLoBit( &bits ) );

    if( n == 2 )
        say( "%s%s %d %d Pair", wrk[0]->id, wrk[1]->id, v[0], v[1] );
    else { // n == 3
        v[2] = b2v( b[2] = bits );
        say( "%s%s%s %d %d %d Trpl", wrk[0]->id, wrk[1]->id, wrk[2]->id, v[0], v[1], v[2] );
    }
    elim( PairTrpl, n, wrk, b );
    return 1;
}

static int nptq( void ) {
    int rval = 0;
    Cell *arr[ 81 - 17 + 1 ] = { 0 }, *p = unkBase; // gather list of cells with only 2 or 3 candidates

    int i = 0;
    do { if( p->nBit <= 3 ) arr[i++] = p; } while( ( p = p->nxtUnk ) != unkBase );

    for( int i0 = 0; arr[i0]; i0++ )
        for( int i1 = i0+1; arr[i1]; i1++ ) {
            rval |= nptqTry( 2, arr[i0], arr[i1], NULL );
            for( int i2 = i1+1; arr[i2]; i2++ )
                rval |= nptqTry( 3, arr[i0], arr[i1], arr[i2] );
        }

    return rval;
}

/* * * * */

static int pntr( void ) {
    int rval = 0; // pessimism

    // tabulate occurences of each bit in each of the 9 squares
    int tab[9][9] = { 0 }, bit, bits;
    Cell *p = unkBase;
    do {
        if( p->nBit ) {
            bits = p->bits;
            while( ( bit = getLoBit( &bits ) ) != 0 )
                tab[ p->sqr ][ b2v( bit ) - 1 ]++;
        }
    } while( (p = p->nxtUnk) != unkBase );

    // Go through the tabulation looking for a bit that occurs only twice or thrice in a square
    for( int v = 1; v <= 9; v++ ) {
        for( int sqrInd = 0; sqrInd < 9; sqrInd++ ) {
            int i, j, cnt = tab[ sqrInd ][ v-1 ];
            if( cnt != 2 && cnt != 3 ) continue; // shortcut

            bit = v2b( v ); // now have the bit

            // revisit that square getting ptrs to its 2 or 3 cells that have that bit set
            Cell *wrk[ 81 - 17 + 1 ] = { 0 }, *p = getHunt( sqrInd ); // worklist
            for( i = 0, j = 0; i < 9; i++, p = p->nxt[ eNxtS ] )
                if( p->bits & bit )
                    wrk[ j++ ] = p;

            // those 2 or 3 cells MUST be in the same row or the same column
            int useNxt = -1;

                 if( SameR( wrk[0], wrk[1] ) && ( cnt == 2 || SameR( wrk[0], wrk[2] ) ) ) useNxt = eNxtR;
            else if( SameC( wrk[0], wrk[1] ) && ( cnt == 2 || SameC( wrk[0], wrk[2] ) ) ) useNxt = eNxtC;

            if( useNxt == -1 ) continue; // rejected

            // if this pair/trio in same row, check sqrs horizontally for possible victims
            // if this pair/trio in same col, check sqrs vertically   for possible victims

            p = wrk[0]; // begin with a known "keeper"
            for( i = 0; i < 9; i++, p = p->nxt[ useNxt ] )
                if( p->bits & bit /* && p->sqr != wrk[0]->sqr */ ) // ToDo: is this right?
                    addOnce( wrk, p );

            if( !wrk[cnt] ) continue; // didn't find any possible victims so move on to try for another

            // check that the square of any possible victim has other occurences so that victim(s) can be eliminated
            int okay = false; // pessimism
            for( i = cnt; !okay && wrk[i]; i++ ) {
                p = wrk[i];
                for( j = 0; !okay && j < 9; j++, p = p->nxt[ eNxtS ] )
                    if( p->bits & bit && ( ( useNxt == eNxtR && !SameR( p, wrk[i] ) ) || !SameC( p, wrk[i] ) ) )
                        okay = true;
            }

            if( okay ) {
                // now have work list for eliminations
                say( "%s%s%s %d Pointing", wrk[0]->id, wrk[1]->id, cnt == 3 ? wrk[2]->id : "", v );
                elim( Sngls, cnt, wrk, &bit );
                rval = 1;
                break;
            }
        }
    }
    return rval;
}

/* * * * */

static int hidDoIt( int n, Cell *wrk[], int bits ) {
    int v[4] = { 0 }, bRem = bits;

    v[0] = b2v( getLoBit( &bRem ) ); // extract values (1-9) of this pair/triplet/quad of bits
    v[1] = b2v( getLoBit( &bRem ) );

    // chatty
    if( n == 2 )
        say( "%s%s %d %d HdnPair", wrk[0]->id, wrk[1]->id, v[0], v[1] );
    else if( n == 3 ) {
        v[2] = b2v( bRem );
        say( "%s%s%s %d %d %d HdnTrpl", wrk[0]->id, wrk[1]->id, wrk[2]->id, v[0], v[1], v[2] );
    }
    else if( n == 4 ) {
        v[2] = b2v( getLoBit( &bRem ) );
        v[3] = b2v( bRem );
        say( "%s%s%s%s %d %d %d %d HdnQuad", wrk[0]->id, wrk[1]->id, wrk[2]->id, wrk[3]->id, v[0], v[1], v[2], v[3] );
    }
    elim( Hidn, n, wrk, &bits );
    return 1;
}

static int hidSrchDo( int n, Cell *lst[], int bits ) {
    int cnt = 0, rval = 0, clearable = 0;
    Cell *wrk[9+1] = { 0 };
    for( int i = 0, k = 0; lst[i]; i++ ) {
        if( bitCnt( lst[i]->bits & bits ) > 1 ) {
            wrk[k++] = lst[i];
            clearable |= ( lst[i]->bits & ~bits ); // Are there bits that can be erased?
        } else if( lst[i]->bits & bits ) // not exclusive?
            return 0;
    }

    if( wrk[n] == NULL && clearable ) { // not too many, not too few
        hidDoIt( n, wrk, bits );
        rval = 1;
    }
    return rval;
}

static int hptq( void ) { // Try to find 2 (or 3 (or 4) ) cells with exclusive bits
    int h = 0, rval = 0;

    for( Cell *p; ( p = getHunt( h ) ) != NULL; h++ ) // visit each of the 9 squares
        for( int dim = 0; dim < 3; dim++ ) { // check each unit (row/col/sqr) involved with this cell
            Cell *wrk[9+1] = { 0 }, *px = p;
            int i = 0, bits = 0;
            do { if( px->bits ) wrk[ i++ ] = px; bits |= px->bits; } while( ( px = px->nxt[dim] ) != p );

            for( int i0 = bits; (i = getLoBit( &i0 )) != 0; ) { // first of 2 or 3 or 4 bits
                for( int j, j0 = i0; (j = getLoBit( &j0 )) != 0; ) { // and a second bit
                    rval |= hidSrchDo( 2, wrk, ( i | j ) );
                    for( int k, k0 = j0; (k = getLoBit( &k0 )) != 0; ) { // and a third
                        rval |= hidSrchDo( 3, wrk, ( i | j | k ) );
                        for( int m, m0 = k0; (m = getLoBit( &m0 )) != 0; ) { // and a fourth
                            rval |= hidSrchDo( 4, wrk, ( i | j | k | m ) );
                        }
                    }
                }
            }
        }

    return rval;
}

/* * * * */

static int bxlnExec( int dim ) {
    int rval = 0;   // pessimism
    int bands[3][9] = { 0 }, maj, min;  // Horz or Vert, 3 bands each, 9 cells in each dimension.

    for( maj = 0; maj < 9; maj++ ) {
        Cell *p = dim ? rc2cell( 0, maj ) : rc2cell( maj, 0 );
        int *pBand = &bands[ maj / 3 ][0];
        for( min = 0; min < 9; min++, p = p->nxt[ dim ] )
            *pBand++ |= p->bits;
    }

#if 0
    debug( "" ); // erase debugging region
    for( maj = 0; maj < 3; maj++ ) {
        char buf[256] = { 0 }, *at = buf;
        at += sprintf( at, "%c Chute %d - ", "VH"[dim], maj );
        for( min = 0; min < 9; min++ ) {
            for( int v = 0; v < 9; v++ )
                *at++ = v2ch( bands[ maj ][ min ] & (1<<v) ? v+1 : 0 );
            *at++ = ' '; *at++ = '/'; *at++ = ' ';
        }
        debug( buf );
    }
#endif
    const int others[][2] = { {1,2},{0,2},{0,1},  {4,5},{3,5},{3,4},  {7,8},{6,8},{6,7} };

    for( min = 0; min < 9; min++ ) { // across each col (horizontal) or row (vertical )
        // filter for bits seen in only ONE square of this col/row
        // If same bit appears in another square that has alternatives, clear those that share this col/row
        int seen1 = 0, seenX = 0, bit;
        for( maj = 0; maj < 3; maj++ )
            onceMult( bands[ maj ][ min ], &seen1, &seenX );
        seen1 &= ~seenX;

        while( ( bit = getLoBit( &seen1 ) ) != 0 ) // iterative isolation of lowest value bit(s)
            for( maj = 0; maj < 3; maj++ ) // check all bands
                if( bands[ maj ][ min ] & bit ) // band has a bit seen only once
                    if( ( bands[ maj ][ others[min][0] ] & bit ) // one or both other bands too?
                    ||  ( bands[ maj ][ others[min][1] ] & bit ) ) {
                        // prep to traverse all cells of col/row of the band
                        Cell *p = (dim == eNxtR) ? rc2cell( maj * 3, min ) : rc2cell( min, maj * 3 );
                        Cell *arr[ 9 + 1 ] = { 0 };
                        int i = 0, n = 0;
                        for( i = 0; i < 9; i++ )
                            if( ( p = p->nxt[ eNxtS ] )->bits & bit )
                                if( dim == eNxtR && p->col != min
                                ||  dim == eNxtC && p->row != min ) {
                                    addOnce( arr, p );
                                    n++;
                                }

                        if( arr[0] ) {
                            int m = n;
                            char buf[32] = { 0 }, *at = buf;
                            p = arr[0];
                            for( i = 0; i < 9; i++ )
                                if( ( p = p->nxt[ eNxtS ] )->bits & bit )
                                    if( addOnce( arr, p ) )
                                        m++, at += sprintf( at, "%s", p->id );

                            for( int l = 0, r = m - 1; l < r; l++, r-- ) // flip the array
                                p = arr[l], arr[l] = arr[r], arr[r] = p;

                            say( "%s %d %c-Box/Line", buf, b2v( bit ), "VH"[dim] );
                            elim( Sngls, m - n, arr, &bit );
                            rval = 1;
                        }
                    }
    }
    return rval;
}

static int bxln( void ) {
    return bxlnExec( eNxtR ) ? 1 : bxlnExec( eNxtC );
}

/* * * * */

typedef struct { int cnt[9]; int field[9]; } pop_t;

static int xwngExec( Cell *arr[], int bit, pop_t *xp, int vctmDir ) {
    for( int x0 = 0; x0 < 9; x0++ )
        if( xp->cnt[x0] == 2 ) // only want units with two bits
            for( int y0 = x0+1; y0 < 9; y0++ )
                if( xp->field[y0] == xp->field[x0] ) { // match 2 bits exact! now have other unit
                    int bits = xp->field[x0];
                    int x1 = b2v( getLoBit( &bits ) ) - 1;
                    int x2 = b2v( bits ) - 1;

                    Cell *wrk[ 20 ] = { 0 }; // assign four cells to worklist
                    if( vctmDir == eNxtC ) {
                        wrk[ 0 ] = rc2cell( x0, x1 );
                        wrk[ 1 ] = rc2cell( x0, x2 );
                        wrk[ 2 ] = rc2cell( y0, x1 );
                        wrk[ 3 ] = rc2cell( y0, x2 );
                    } else{
                        wrk[ 0 ] = rc2cell( x1, x0 );
                        wrk[ 1 ] = rc2cell( x2, x0 );
                        wrk[ 2 ] = rc2cell( x1, y0 );
                        wrk[ 3 ] = rc2cell( x2, y0 );
                    }

                    for( int i = 0; i <= 3; i += 3 ) {
                        Cell *p = wrk[i];
                        do {
                            if( p->bits & bit ) addOnce( wrk, p );
                        } while( ( p = p->nxt[ vctmDir ] ) != wrk[i] );
                    }

                    if( wrk[4] ) {
                        say( "%s%s%s%s %d X-Wing", wrk[0]->id, wrk[1]->id, wrk[2]->id, wrk[3]->id, b2v( bit ) );
                        elim( Sngls, 4, wrk, &bit );
                        return 1;
                    }
                }

    return 0;
}

/* * * * */

static int swrdExec( Cell *lst[], int bit, pop_t xp[], int vctmDir ) {
#define CNTGOOD( N ) ( xp->cnt[N] == 2 || xp->cnt[N] == 3 )
#define ALIGNED( M, N ) (xp->field[M] & xp->field[N] )

    int x[3] = { 0 };
    for( x[0] = 0; x[0] < 9; x[0]++ )
        if( CNTGOOD( x[0] ) )
            for( x[1] = x[0]+1; x[1] < 9; x[1]++ )
                if( CNTGOOD( x[1] ) && ALIGNED( x[1], x[0] ) )
                    for( x[2] = x[1]+1; x[2] < 9; x[2]++ )
                        if( CNTGOOD( x[2] ) && ( ALIGNED( x[2], x[0] ) || ALIGNED( x[2], x[1] ) ) ) {
                            // Now to extract 9 Cell ptrs from this
                            // x[0 - 2] are the "base" values -- deterimine 3 "cover" values as y[0 - 2]
                            int bits = xp->field[x[0]] | xp->field[x[1]] | xp->field[x[2]]; // all 3, or more, now here

                            if( bitCnt( bits ) != 3 ) continue; // Oops, too many

                            int y[3] = { 0 };
                            y[0] = b2v( getLoBit( &bits ) ) - 1; // translate bits' positions to values 0-8 for use as indices
                            y[1] = b2v( getLoBit( &bits ) ) - 1;
                            y[2] = b2v( getLoBit( &bits ) ) - 1;

                            Cell *wrk[ 9 + 18 + 5 ] = { 0 }; // the 9 "target" cells + headroom
                            for( int c = 0; c < 9; c++ ) {
                                int xx = ( vctmDir == eNxtC ) ? x[ c/3 ] : y[ c/3 ];
                                int yy = ( vctmDir == eNxtC ) ? y[ c%3 ] : x[ c%3 ];
                                wrk[c] = rc2cell( xx, yy );
                            }

                            for( int q = 0; q < 9; q += (3+1)) // use [0], [4] and [8] as start point
                                for( Cell *p = wrk[q]; ( p = p->nxt[ vctmDir ] ) != wrk[q]; ) // traverse seeking eliminations
                                    if( p->bits & bit )
                                        addOnce( wrk, p );

                            if( wrk[9] ) {
                                say( "%s%s%s %d S-Fish (%c)", lst[0]->id, lst[4]->id, lst[8]->id, b2v( bit ), "HV"[ vctmDir ] );
                                elim( Sngls, 9, wrk, &bit );
                                return 1;
                            }
                        }
    return 0;
}

/* * * * * * * * * * * * */

static int xwng_swrd( int (*fnc)( Cell *lst[], int bit, pop_t *p, int vctmDir ) ) { // used by two functions
    Cell *px = unkBase;

    for( unsigned bit = v2b( 9 ); bit; bit >>= 1 ) { // Try all values from 9 to 1.

        Cell *lst[ 81 - 17 + 1 ] = { 0 }, *p = px; // gather list of cells with this bit unresolved
        int i = 0;
        do {
            if( p->bits & bit ) lst[ i++ ] = p;
        } while( ( p = p->nxtUnk ) != px );

        if( ( fnc == xwngExec && i > 4 ) || ( fnc == swrdExec && i > 6 ) ) { // minimum req'd for possibility of erasing a candidate

            pop_t x[2] = { 0 };
            for( i = 0; lst[i]; i++ ) {
                int r = lst[i]->row, c = lst[i]->col;
                x[0].cnt[r]++; x[0].field[r] |= v2b( c + 1 );
                x[1].cnt[c]++; x[1].field[c] |= v2b( r + 1 );
            }

            for( int vh = 0; vh < 2; vh++ )
                if( fnc( lst, bit, &x[  vh ], vh == 0 ? eNxtC : eNxtR ) )
                    return 1;
        }
    }

    return 0;
}

static int xwng( void ) { return xwng_swrd( xwngExec ); }
static int swrd( void ) { return xwng_swrd( swrdExec ); }

/* * * * */

static int ywng( void ) {
    int rval = 0;
    int w = 0;
    Cell *arr[ 81 - 17 + 1 ] = { 0 }, *p = unkBase; // gather list of cells with only 2 candidates

    do { if( p->nBit == 2 ) arr[w++] = p; } while( ( p = p->nxtUnk ) != unkBase );

    for( int x = 0; arr[x]; x++ ) { // check each possibility as being a "corner" cell; the "pivot" cell
        int xb2 = arr[x]->bits, xbh = xb2, xbl = getLoBit( &xbh ); // the two "corner" bits under investigation

        for( int y = 0; arr[y]; y++ ) { // look for one of two "pincers"
            const int yb2 = arr[y]->bits;
            if( !(yb2 & xb2) || !(yb2 ^ xb2) )
                continue; // skip if nothing or too much in common

            for( int z = 0; arr[z]; z++ ) { // look for other of two "pincers"
                if( SameR( arr[y], arr[z] ) || SameC( arr[y], arr[z] ) || SameS( arr[y], arr[z] ) )
                    continue; // "pincers" must not be in the same "unit" (row/col/sqr)

                if( ( ( SameR( arr[x], arr[y] ) || SameR( arr[x], arr[z] ) )
                    + ( SameC( arr[x], arr[y] ) || SameC( arr[x], arr[z] ) )
                    + ( SameS( arr[x], arr[y] ) || SameS( arr[x], arr[z] ) ) ) != 2 )
                        continue; // must have only two dimensions in common

                const int zb2 = arr[z]->bits;
                if( !(zb2 & xb2) || !(zb2 & yb2) || !(zb2 ^ xb2) || !(zb2 ^ yb2) )
                    continue; // skip if nothing or too much in common

                if( (yb2 & xbh) && !(zb2 & xbl)
                ||  (yb2 & xbl) && !(zb2 & xbh) )
                    continue; // must be pair with candidate's alternate bits

                Cell *wrk[ 3 + 6 + 6 + 1 ] = { arr[x], arr[y], arr[z] }; // x, y & z under examination, plus extras
                int bit = yb2 & zb2, i = 3;
                if( SameR( wrk[0], wrk[1] ) && SameC( wrk[0], wrk[2] ) ) { // "box" (90deg) hoping for 1 bit to elim
                    p = modlTL + wrk[2]->row * 9 + wrk[1]->col;
                    if( p->bits & bit ) wrk[i] = p;

                } else
                if( SameR( wrk[0], wrk[2] ) && SameC( wrk[0], wrk[1] ) ) { // "box" (90deg) hoping for 1 bit to elim
                    p = modlTL + wrk[1]->row * 9 + wrk[2]->col;
                    if( p->bits & bit ) wrk[i] = p;

                } else { // "bent" possibility of up to 3 bits to eliminate
                    Cell *pSQ, *pRC;
                    if( SameS( wrk[0], wrk[1] ) )
                        pSQ = wrk[2], p = pRC = wrk[1];
                    else
                        pSQ = wrk[1], p = pRC = wrk[2];

                    if( !SameR( pSQ, wrk[0] ) && !SameC( pSQ, wrk[0] ) )
                        continue; // must be colinear with "corner" cell

                    int nxt = ( SameC( wrk[0], pSQ ) ) ? eNxtC : eNxtR;
                    do {
                        if( SameS( p, pSQ ) && (p->bits & bit) )
                            wrk[i++] = p;
                    } while( (p = p->nxt[nxt]) != pRC );
                }

                if( wrk[3] ) {
                    say( "%s%s%s Y-Wing", wrk[0]->id, wrk[1]->id, wrk[2]->id );
                    elim( YWng, 3, wrk, &bit );
                    return 1;
                }
            }
        }
    }
    return rval;
}

/* * * * */

static int xchn( void ) {
    say( "xchn()" );

    // one preliminary scan of all bits to avoid wasting loops when no 4's or 7's, for ex, to be found
    int b, all = 0;
    Cell *px;
    px = unkBase; do { all |= px->bits; } while( ( px = px->nxtUnk ) != unkBase );

    // deal with bits in ascending order
    while( ( b = getLoBit( &all ) ) != 0 ) {
        // make a worklist of all cells having this candidate
        int i, n = 0;
        Cell *wrk[81] = { 0 }, *px = unkBase;
        do { if( px->bits & b ) wrk[n++] = px; } while( ( px = px->nxtUnk ) != unkBase );

        // too few instances are worthless here
        if( n < 5 ) continue;

        say( "%d %d", b2v( b ), n );

        //hold( HLD_throttleON );
        for( i = 0; wrk[ i ]; i++ )
            dispExam( wrk[ i ], b2v( b ), CLR_Keep );
        pause(); //hold( HLD_longPause );
        while( i-- )
            dispExam( wrk[ i ], b2v( b ), CLR_Normal );
        //hold( HLD_throttleOFF );
    }
    return 0;
}

/* * * * */

static Cell *brutNext( int *bits ) { // search for cell with lowest possibles
    int nMin = 9 + 1; // outlandishly high initially
    int bMin = 0;
    Cell *pMin = NULL;

    for( Cell *p = modlTL; p < modlTL + 81; p++ )
        if( !p->valu ) {
            int i = 0; // gather bits from siblings in three dimensions
            for( int dim = 3; dim--; )
                for( Cell *pd = p->nxt[ dim ]; pd != p; pd = pd->nxt[ dim ] )
                    i |= v2b( pd->valu );
            i = (~i)&0777; // form candidate bits by inverting and masking

            int nPoss = bitCnt( i );
            if( nPoss < nMin ) {
                nMin = nPoss;
                bMin = i;
                pMin = p;
            }
            if( nPoss == 1 ) break;
        }

    *bits = bMin;
    return pMin;
}

static int brutExec( int *pCnt ) { // solve by brute force (recursive)
    *pCnt += 1;

    int bits = 0;
    Cell *p = brutNext( &bits ); // ToDo: Halt if puzzle is unsolvable

    if( !p ) { toSolve = 0; return 1; } // no empty cells

    for( int num = 1; bits; bits >>= 1, num++ )
        if( bits & 1 ) { // try each candidate
            dispCell( p, p->valu = num, CLR_Puzl, HLD_sustain );
            if( brutExec( pCnt ) )
                return 1;
            dispCell( p, p->valu = 0, CLR_Normal, HLD_sustain );
        }

    return 0;
}

static int brut( void ) {
    int cnt = 0;
    hold( HLD_standard );
    say( "+revert to brute force" );
    say( "%d remain: ", toSolve );
    pause(); // to reflect
    int rval = brutExec( &cnt );
    say( "Done = %d  Count = %d", rval, cnt );
    return rval;
}

/* * * * */

Cell *assignVBN( Cell *p, int v, int b, int n ) {
    p->valu = v;
    p->bits = b;
    p->nBit = n;
    return p;
}

void solve( void ) {
    debug( "" ); // reset debug row counter

    if( modeXfct ) say( "X-Factor" );
    say( "%d to solve: ", toSolve ); // to reflect on the layout
    pause();

    char *cp = "___Played.lst";

    FILE *fp;
    if( ( fp = fopen( cp, "wb" ) ) == NULL )
        fatal( "fopen('%s') to write failed\n", cp );

    enum { Chek, Lone, Uniq, Nptq, Hptq, Pntr, BxLn, Xwng, Ywng, Swrd, Xchn, Brut, End };

    for( int state = Chek; state < End; ) {
        if( state == Chek ) {
            Cell *p = modlTL;
            fputc( '|', fp );
            for( int i = 0; i < 9*9; ) {
                fputc( ".123456789"[ p[ i ].valu ], fp );
                if( ++i < 81 ) {
                    if( i%(1*9) == 0 ) fputc( '|', fp );
                    if( i%(3*9) == 0 ) fputc( '|', fp );
                }
            }
            fputc( '|', fp );
            fputc( '\n', fp );
            fflush( fp );
        }

        switch( state++ ) {
            case Chek: if( !toSolve )   state = End;    break;
            case Lone: if( lone() ) state = Chek;   break;
            case Uniq: if( uniq() ) state = Chek;   break;
            case Nptq: if( nptq() ) state = Chek;   break;
            case Hptq: if( hptq() ) state = Chek;   break;
            case Pntr: if( pntr() ) state = Chek;   break;
            case BxLn: if( bxln() ) state = Chek;   break;
            case Xwng: if( xwng() ) state = Chek;   break;
            case Ywng: if( ywng() ) state = Chek;   break;
            case Swrd: if( swrd() ) state = Chek;   break;
            case Xchn: if( xchn() ) state = Chek;   break;
            case Brut:  brut();         state = End;    break;
        }
    }
    fclose( fp );

    say( "+%d unsolved", toSolve );
    pause();
}

Bzzzzzz went the fly...

\$\endgroup\$
10
  • 3
    \$\begingroup\$ "Suggestions to decorate the code with modern C enhancements such as restrict" ==> But restrict is older than some of these new languages today. :) \$\endgroup\$
    – Harith
    Commented May 25 at 10:08
  • 1
    \$\begingroup\$ Please don't edit the question after it has been answered. Normally the edit would have been rolled back, but I do not see any Answer Invalidation. \$\endgroup\$
    – pacmaninbw
    Commented May 26 at 12:28
  • \$\begingroup\$ @pacmaninbw Noted. Thank you... I thought it a minor addition to help all future readers. Addition was triggered by one segment of the answer from G. Sliepen that was based on a misunderstanding of the game... Conveniently 'G' has, moments earlier, removed that portion of their fine commentary... Thanks again. I'll bare that in mind if/when another issue arises... :-) \$\endgroup\$
    – Fe2O3
    Commented May 26 at 12:34
  • 1
    \$\begingroup\$ Are you familiar with Peter Norvig's solution to Sudoku? It's kind of barbaric, but works great. He suggests that you fill out the puzzle up to the point where some "trick" is required to solve any more cells, and at that point find a cell with the lowest number of possible candidate values and start guessing. Keep applying those "solve & guess" steps recursively until the puzzle is solved, or a contradiction is reached (at which point you backtrack to the last guess that still has unchecked candidates and pick a different value). \$\endgroup\$
    – Z4-tier
    Commented May 27 at 3:06
  • 1
    \$\begingroup\$ @Harith Sorry for the stress caused. I cannot speak to current versions or usage... This is the syntax I'd been using for many years -- started with C on UNIX back before Torvalds' voice broke -- and it still works with my "DevStudio '97" build system... :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 2 at 0:34

4 Answers 4

7
\$\begingroup\$

About your own points

  • This has been written for my antiquated C++ compiler, but is really a C Windows Console app. (The old compiler allowed variables to be defined close to use, rather than grouped after any open brace.)

C99 already allows variables to be declared anywhere in the code, so you should be able to compile it with a compliant C compiler made anywhere in the current millenium.

  • Comments are sparse and variable & function names terse. This was a "one coder" project.

Sparse comments are fine if the code itself is self-documenting enough. However, overly terse variable and function names are definitely not self-documenting. So I would recommend you go over them, make sure each name is concise and meaningful, and that the naming scheme you use is consistent.

A few "global" variables (the internal "game model" of 9x9 cells, for instance) obviate the need for passing app specific parameters that do not change.

If a variable really doesn't change, it's a constant, and then it's fine if you declare it as a static const variable. But modl is definitely changed at runtime. In general it's a good idea to put the mutable state in a struct and pass a pointer to it to the functions that need to access that state. Global variables are problematic since they prevent you from running multiple solvers in parallel, and in a larger project the chance that you get conflicts in the global namespace will increase.

  • The coder (me) did not use const and other language guard rails as piecewise, incremental development and frequent testing seemed to preclude the necessity.

Having multiple layers of defense against programming errors is not a bad thing. Are you really sure you were frequently testing all the possible corner cases? Language guard rails allow the compiler to detect bugs at compile time.

  • Optimal speed was not an objective.

That's fine. However, you also don't want to wait days for a single puzzle to be solved, so you do want to use algorithms that guarantee an acceptable time for solving them. So in general you do want to avoid using algorithms that are too naive and slow. You added several heuristics to speed up the algorithm, so that is great.

  • Game progress is logged to "./___Played.lst" for review. Copy/paste of a partially solved game as a game to be played speeds development of a strategy; effectively a form of "Fast Forward to here".

That's very nice! Too often I've seen long-running code not save intermediate results, and then any kind of issue that would cause the program to quit before finishing its tasks would cause all progress to be lost.

  • There is a primitive vestigial print debugging facility left in the code.

You would typically remove such debugging facilities before a review; it just adds to the noise, and if you still need it it probably means there are bugs left and the code wasn't ready for review.

I suggest decreasing any modern compiler's sensitivity to current C standards and warning levels. This code does compile and the executable does run after using my antiquated compiler.

We typically recommend moving to a more recent compiler, setting a recent C standard and turning on a reasonable set of warnings (for example, I'd recommend using -Wall -W -pedantic as a start for GCC and Clang). Then fix all the errors as well as all the warnings the compiler finds.

Currently hardwired filename: "./_Puzzles.lst"

Avoid hardcoding things where possible. Why not pass the filename on the command line? From the commented out line in main(), it seems like you had already planned that.

Consider using a curses library

Whenever you find yourself drawing things on the terminal, waiting for keys and redrawing again, and you are using platform-specific functions and hardcoding ANSI sequences, consider using a curses library instead. These provide a standard, platform-independent API for doing all that. There are curses library implementations for all major operating systems, including Windows.

Avoid setjmp()/longjmp() if possible

These functions break the normal structured flow of a program, and it's easy to leave things in a bad state (for example, you skip over code that frees previously allocated memory, or unlocks a mutex that was previously locked, and so on). Often you don't need them, with just a little more work you can just create a regular return path.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Terrific! Thank you. This was just the kind of comment I was hoping for. Readers/adopters now have a guide to some of the items they may wish to improve-upon. Two small points: my antique was cranking out EXEs while C99 was still in the womb... :-) 2) X-Factor games cannot be distinguished from 'normal' games except by their presentation (id'd as such when printed.) They can have multiple solutions. It is their being id'd as 'X-Factor' that leads to a unique solution... Again, my thanks for this appraisal and its suggestions. :-) \$\endgroup\$
    – Fe2O3
    Commented May 25 at 21:05
  • \$\begingroup\$ Re: "setjmp()/longjmp()" A flaw in this program that demonstrates your recommendation is that the "progress so-far FILE pointer" is left open when user uses ESC to reset the solver. Yech!! This has been a hobby project to play with blinky-flashy VT-100 UX and coding Sudoku strategies. Your recommendation is 100% correct and my code is an example of why you are right. Thank you for spotting that item... Cheers! :-) \$\endgroup\$
    – Fe2O3
    Commented May 25 at 23:33
  • 1
    \$\begingroup\$ Apparently I did not know about X-Factor sudokus... TIL :) \$\endgroup\$
    – G. Sliepen
    Commented May 26 at 12:23
  • \$\begingroup\$ It has only taken my old brain approx. four days to find the term. "X-Factor is META-data that describes a Sudoku and its solution"... Trivial, but salient. Again, Mr. Spider, my thanks for your time spent writing this answer... My visit here was less painful than I anticipated... Cheers! :-) \$\endgroup\$
    – Fe2O3
    Commented May 28 at 23:24
5
\$\begingroup\$

Suggestions to decorate the code with modern C enhancements such as restrict, etc. are also welcome

How about some C23 <stdbit.h> stuff? I couldn't find an official reference (it's that new, and yes that also probably means that you may not want to use it at all for compiler compatibility reasons), but here's a reference

For v2b you can use a shift, I'd generally recommend that over a table lookup. OK that wasn't C23 yet.

For b2v you can use stdc_trailing_zeros.

For bitCnt you can use stdc_count_ones.

\$\endgroup\$
3
  • \$\begingroup\$ GCC and Clang support a lot of new things already, but I do not think they have implemented <stdbit.h> yet. We'd have to wait some more. \$\endgroup\$
    – Harith
    Commented May 25 at 19:57
  • \$\begingroup\$ Much appreciation. :-) \$\endgroup\$
    – Fe2O3
    Commented May 25 at 21:07
  • 1
    \$\begingroup\$ user555045, "How about some C23 <stdbit.h> stuff? " --> C23 is not yet released. Although likely <stdbit.h> will exist in it, it is still TBD. \$\endgroup\$ Commented May 26 at 3:26
3
\$\begingroup\$

select is a reserved identifier:

sys/select.h defines the select(2) system call. You may wish to name your function something else.

Use GNU C's attributes if available:

As per the description:

format (archetype, string-index, first-to-check) The format attribute specifies that a function takes printf, scanf, strftime or strfmon style arguments which should be type-checked against a format string. For example, the declaration:

  extern int
  my_printf (void *my_object, const char *my_format, ...)
      __attribute__ ((format (printf, 2, 3)));

causes the compiler to check the arguments in calls to my_printf for consistency with the printf style format string argument my_format.

This is how their availability can be detected:

#if defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
    #define PRINTF_LIKE(...)    __attribute__((format (printf, __VA_ARGS_)))
#else
    #define PRINTF_LIKE(...)    /**/
#endif

I believe you can drop the double underscores after attribute, so __attribute instead of __attribute__. Though I acknowledge that the syntax appears grotesque. In C23, you can use:

[[gnu::format(printf, ...)]] // Prettier

If an implementation does not support the attribute, it shall ignore it. If an implementation does not recognize the syntax [[ ]], the program shall not compile. You can check if the attribute is available with:

#if defined(__STDC_VERSION__) && __STDC_VERSION__ > 201710L
    #define PRINTF_LIKE(...)    [[gnu::format(printf, __VA_ARGS__)]]
#elif defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
    #define PRINTF_LIKE(...)    __attribute__((format (printf, __VA_ARGS_)))
#else
    #define PRINTF_LIKE(...)    /**/
#endif
    // Define the attribute to expand to a single whitespace, or none.
#endif

Note that __VA_ARGS__ is C99.

These two functions can use the afore-mentioned function attribute:

void debug( char *fmt, ... );
void fatal( char *fmt, ... );

Talking about variadic functions, variadic functions no longer need a named argument before the ellipsis and the va_start macro no longer needs a second argument nor does it evaluate any argument after the first one if present in C23.

Aside: GNU C also has case ranges, which allows you to do:

case '0' ... '9':

instead of:

case '0':
    case '1': case '2': case '3':
    case '4': case '5': case '6':
    case '7': case '8': case '9':

This is a core GNU C language feature and is supported by most compilers that claim any level of GCC compatibility. GCC itself, as well as Clang, and third party tools emulating GNU C such as QAC, all support this feature.

It might (very likely) be in the next revision of the C Standard. The C committee is okay with it, at least according to the proposals in WG14's document log.

Use noreturn:

Since C11, code can use the _Noreturn keyword to specify that a function never returns (calls exit()/abort()). It can also be used through its convenience macro noreturn from <stdnoreturn.h>. Of course this has been deprecated in C23 and the [[noreturn]] attribute should be used.

#if defined(__STDC_VERSION__) && __STDC_VERSION__ > 201710L
    #define NORETURN    [[noreturn]]
#elif defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
    #define NORETURN    _Noreturn
#elif defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
    #define NORETURN    __attribute__ ((noreturn));
#else
    #define NORETURN    /**/

In your code, fatal() can make use of it.

Detect Windows before including its headers:

A simple:

#ifdef _WIN32    /* Defined in both 32-bit and 64-bit */
    #include <Windows.h>
    ...
#else
    #error // or include a POSIX header?

shalt suffice.

Oh, I see that it is a "Windows console app". I don't see much Windows specific in the code albeit. It should be fairly easy to port to it UNIX-like systems, if the author desires to of course.

StackOverflow answers have implementations of getch() for UNIX. You'd have to include <termios.h> and set the terminal to raw mode.

No need to cast the return value of malloc() and memcpy() etc. in C89 and above:

Assuming your antique compiler supports at least C89, the cast in the following code (and other places too):

char *buf;
if( ( buf = (char*)malloc( finfo.st_size + 1) ) == NULL )

can be safely elided. You are using size_t in the code, which is C99, so I am assuming that it does. But if it is to compile as C++ as well, they should stay.

If the following:

    if( ( fp = fopen( cp, "wb" ) ) == NULL )
        fatal( "fopen('%s') to write failed\n", cp );

would like to fail if the file already exists, code can use C11's "x" mode.

ISO POSIX Standard specifies that errno is set if fopen() returned a nullptr, unlike ISO C. Code can use:

FILE *const fp = (errno = 0, fopen(fname, "rb"));
errno ? 
    (void) fprintf(stderr, "Error: failed to open \"%s\": %s\n", fname, strerror(errno)) : 
    fatal("fopen('%s') failed\n", fname);

The cast to void is required because ISO C forbids conditional expr with only one void side. GCC complains about it with -pedantic-errors.

Use C99's designated initializers:

char *clrStr( const int clr ) {
    static char *cstr[] = {
        "\033[0;0m",    // wht on blk - CLR_WhtOnBlk
        "\033[40;30m",  // blk on blk - CLR_BlkOnBlk
        "\033[102;30m", // blk on grn - CLR_BlkOnGrn
        "\033[103;30m", // blk on ylw - CLR_BlkOnYlw
        "\033[105;30m", // blk on pnk - CLR_BlkOnPnk
        "\033[47;30m",  // blk on gry - CLR_BlkOnGry
        "\033[106;30m", // blk on blu
    };

    return cstr[ clr ];
}

can be rewritten as:

char *clrStr( const int clr ) {
    static char *cstr[] = {
        [CLR_WhtOnBlk] = "\033[0;0m", 
        [CLR_BlkOnBlk] = "\033[40;30m", 
        [CLR_BlkOnGrn] = "\033[102;30m",
        [CLR_BlkOnYlw] = "\033[103;30m",
        [CLR_BlkOnPnk] = "\033[105;30m",
        [CLR_BlkOnGry] = "\033[47;30m",
        "\033[106;30m", // blk on blu
    };

    return cstr[ clr ];
}

I did not find any CLR_BlkOnBlu, so I have not edited the last line. Now your code is self-documenting. No need of comments.

Though it is not clear to me why this is not an array of const char *s, or why the function returns a plain char *?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Great! Thank you for trying to drag me & my code into this century. :-) Still using "Dev Studio '97" that complies with C??. Not really concerned, as life took a turn after the DotCom bubble burst and Y2K drained coffers. Favouring .cpp to write C code because my ol' reliable's C compiler doesn't like variables defined anywhere by at the start of a block... black or blue is how I've felt sometimes codifying a strategy here: 'black (mood)' when things aren't right, turning to 'blue' realising my brain's not what it used to be... Cheers, and thanks again for your time covering these items. \$\endgroup\$
    – Fe2O3
    Commented Jun 2 at 0:18
  • \$\begingroup\$ Just brooding over lengthy qualifiers, et. al. I agree whole heartedly with enlisting the aid of the compiler to get it right! No arguments... They're almost the same, the func signatures of strstr() and strtok()... The const parameter(s) assure the coder/caller of what the func might play with and what doesn't change... However, if the coder uses strtok() where he should have used strstr(), all hope is lost; the compiler simply says, "Okay, boss!"... "Guard rails" allow one to do the wrong thing, but do it the right way. ... (I think I need a break from this stuff.) :-) \$\endgroup\$
    – Fe2O3
    Commented Jun 3 at 23:38
  • 1
    \$\begingroup\$ @Fe2O3 In that case, the programmer is to be blamed for not consulting the documentation. :) \$\endgroup\$
    – Harith
    Commented Jun 4 at 8:00
2
\$\begingroup\$

There have been a handful of VERY USEFUL responses to this question during the last week.
First, my thanks to those users for sharing their knowledge of current and future C code standards & practices.


Not addressed, so far, has been the logic of this app as being "fit for purpose". (It is still no more than a hobby project for personal use. This code, and its sparse documentation, is not intended to be distributed as a robust consumer-grade app suited for naive users.)

With renewed interest in this project, the code below FINALLY improves on one aspect that, until now, has never been written into the project: "verification of validity" of both an initial Sudoku challenge and the Solver's (possibly hallucinated) solution. This seeks to correct that shortfall.


First, static int v2b() (in solve.cpp) must lose its static-ness, and its prototype added to solve.h.

Then, the simple call to solve(); in main() is replaced with:

        verify() && (solve(),1) && verify();

to invoke verify() both before and after the Solver does its thing.
This catches Sudokus that have been manually but incorrectly entered into the compendium of puzzles. verify() performs a minimal verification, checking all "houses" of the Sudoku to ensure no illegal duplications of values 1 to 9 exist in any "houses".

And, here is the code of that function that extends the code of main.cpp:

static int verify( void ) {
    int okay = 1; // optimism

    for( int i = 0; i < 9; i++ ) {
        Cell *pStart = getHunt( i ); // check using the 9 unique "hunt" cells
        // examine the entire row/col/sqr from this start cell
        for( int dim = 0; dim < 3; dim++ ) {
            Cell *p = pStart;
            int bits = 0; // record assigned values "seen" as bit flags
            do {
                int bit = v2b( p->valu );
                if( bit & bits ) {
                    okay = 0; // report duplicate value in this dimension
                    char *dimStr = &"row\0col\0sqr\0"[dim * 4];
                    int houseInd = dim == 0 ? p->row : dim == 1 ? p->col : p->sqr;
                    say( "%s %d: too many %ds", dimStr, houseInd, p->valu );
                }
                bits |= bit;
            } while( ( p = p->nxt[ dim ] ) != pStart ); // traverse all 9 cells
        }
    }
    if( !okay ) pause(); // before clearing screen
    return okay;
}

I feel it is also the time to apologise for the scattered terminology used throughout the code that has been shaped over several years. Sudoku documentation (numerous websites) and YouTube tutorials ("masters of solving techniques") use a variety of terms to identify strategies or to refer to groups of cells leading one to perceive a "Tower of Babel" problem in the realm of Sudoku. Mea culpa...

As a coder, I would welcome comments or answers that address the presented code's logic.
Especially welcome would be improvements on what I will call "analysis heuristics". Thank you.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.