The New Sudoku Players' Forum

[PIsaacson]

Civiliza,

If you review the following thread http://www.setbb.com/phpbb/viewtopic.php?t=1824, there are 3 separate brute force solvers with source code that you can download in order to determine which may best fit your needs. I have the most experience with Brian Turner's bb_sudoku_solve code and that's the one I elected to use, but I've also downloaded Dobrichev's fsss and Jason Lion's JSolve code. All three are very fast compared to using DLX, and they can really speed up the process of determining whether or not a puzzle still has a single valid solution after eliminating a given.

Cheers,
Paul

[daj95376]

Quite awhile back, I converted a "C" backtracking solver program by gsf into an embedded backtracking solver where you pass it a character array containing the puzzle and it returns {0,1,2} for {none,one,multiple} solutions.

For comments on its speed vs DLX, see here.

If you are interested: (Note: you can not feed it a solved puzzle!)

Code: Select all

/*
 * Glenn Fowler
 * AT&T Research
 * 9x9 sudoku backtrack solver -- no dancing
 */

/* converted to an embedded solver by Danny A. Jones */

#define N1              3
#define N2              9
#define N4              81

#include <mem.h>

#define SET(A,VALUE)    memset( A, VALUE, sizeof(A) )
#define ZERO(A)         SET( A, 0 )

#define MASK(g,i)       (g.rcb[cell_rcb[i][0]]&g.rcb[cell_rcb[i][1]]&g.rcb[cell_rcb[i][2]])
#define PROP(g,i,x)     (g.rcb[cell_rcb[i][0]]^=(x),g.rcb[cell_rcb[i][1]]^=(x),g.rcb[cell_rcb[i][2]]^=(x))
#define MOVE(g,i,x)     (g.cell[i]=(x),PROP(g,i,x))
#define UNDO(g,i,x)     (g.cell[i]=(0),PROP(g,i,x))

typedef struct Grid_s {  /* rcb  -> Row/Column/Block as bitmap of values
                            cell -> solution value   as bitmap of value  */

        unsigned    int     rcb[27], cell[N4];

} Grid_t;

static  const       char    name[] = ".123456789";  /* self-descriptive          */
static  unsigned    short   token [256];            /* bit-map     for [name []] */
static  unsigned    char    ident [512];            /* value       of  [token[]] */
static  unsigned    short   next  [512];            /* LSB         of        []  */
static  unsigned    char    cell_rcb[N4][N1];       /* rcb indices for  cell []  */

static              Grid_t  base;                   /* initial grid w/all rcb[] active */

static  const       int     BC_9[512] = {
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2,
            2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3,
            2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
            4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
            2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4,
            4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
            4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
            6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,
            3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,
            4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4,
            4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
            4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,
            5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7,
            6, 7, 7, 8, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4,
            4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4,
            4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4,
            3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5,
            5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6,
            4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
            6, 7, 6, 7, 7, 8, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
            4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
            6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 3, 4,
            4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6,
            5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 4, 5, 5, 6, 5, 6,
            6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8,
            6, 7, 7, 8, 7, 8, 8, 9 };



void    once_gsf( void ) {   /* called once at program initialization */

    int     i, j, k, n;

/*  ZERO( base     ); */    memset( &base, 0, sizeof( base ) );
    ZERO( cell_rcb );
    ZERO( ident    );
    ZERO( next     );
    ZERO( token    );

    token['.'] = token['0'] = token['X'] = token['_'] = 0x1ff;

    for (i = 1; i <= N2; i++)
    {
        ident[token[name[i]] = (1<<(i-1))] = i;
    }

    for (i = 0; i < 27; i++)
        base.rcb[i] = 0x1ff;

    for (i = 0; i < 512; i++) {
        k = 0;
        for (j = 1; j < 512; j <<= 1)
            if ((i & j) && !k++)
                next[i] = j;
    }

    for (k = i = 0; i < N2; i++) {
        n = 18 + ((i / N1) * N1);
        for (j = N2; j < 18; j++) {
            cell_rcb[k][0] = i;
            cell_rcb[k][1] = j;
            cell_rcb[k][2] = n + ((j / N1) % N1);
            k++;
        }
    }
}



typedef struct Try_s {   /* list of unresolved cells */

                    int     candidates, cell, free, guess, index;
} Try_t;


int     gsf( char * c_puzzle ) {

    int     i, j, k, m, n, x;
    int     depth, level, solutions;
    Grid_t  grid;
    Try_t   try[N4];

    ZERO( try );

    grid  = base;
    depth = level = solutions = 0;

    for ( i = 0 ; i < N4 ; i++ )
        if ((j = token[c_puzzle[i]]) == 0x1ff)
            try[depth++].free = i;
        else
            MOVE(grid, i, j);

    for (;;) {

        m = 10;

        for (k = level; k < depth; k++) {
            i = try[k].free;
            if (!(x = grid.cell[i] = MASK(grid, i))) {
                m = 11;
                break;
            }
            if (m > (n = BC_9[x])) {
                try[level+1].index      = k;
                try[level+1].candidates = x;
                if ((m = n) == 1)
                    break;
            }
        }

        if (m < 10) {
            k = try[level+1].index;
            try[level+1].cell = try[k].free;
            if (k != level) {
                j               = try[level].free;
                try[level].free = try[k    ].free;
                try[k    ].free = j;
            }
            level++;
        }
        else {
            if (m == 10) {
                if (solutions++) {
                    break;
                }
            }
            UNDO(grid, try[level].cell, try[level].guess);
        }

        while (!(x = next[try[level].candidates])) {
            if (!--level) {
                return ( solutions );
            }
            UNDO(grid, try[level].cell, try[level].guess);
        }

        try[level].candidates ^= x;
        try[level].guess       = x;

        MOVE(grid, try[level].cell, x);
    }

    return ( solutions );   /* {0,1,2} == {no,one,multiple} */
}
/*
__________________________________________________________________________________________________________
*/


[civiliza]

Hmm .. hinterlesting

I put DAJ's source code into it's own C file and called it in parallel to my current C++ algorithms, using the rule that a cell is removable if removing it still leads to a single solution.

In the middle stages it frequently detects non-removable cells that my own code reckons can be removed. At the end though it identified some removable cells using techniques my own code doesn't implement (Unique Rectangle Type 3, Turbot Fish, Bidirectional Cycle and Forcing Chain over two runs according to Sudoku Explainer).

When I added diagnostics showing what my code was "thinking" at the time, I saw a variety of methods, but a large number were my lowest rated "Sub Group Analysis" (pointing and claiming type techniques).

Blast - just checked my last batch mode run, and the first three puzzles were non-unique This despite several sucessful one off's.

I've clearly still got problems with my code. That said, as long as I disable my Unique Rectangle Type 1 code, I seem to create unique puzzles despite clashing with the backtracker.

Velly Hinterlesting

[civiliza]

I suspect that I have been getting away with clashing with the backtracker because the cell(s) affected were assigned a low difficulty rating and so not actually chosen.

I have decided on a hybrid method that only assigns a cell the "removable" status if both the backtracker and my existing code agree that it is removable.

Theoretically at least that should use the backtracker to ensure uniqueness while limiting the puzzle to methods that I personally can understand.

The only risk is of my code mistakenly identifying a UR Type 1 at the same time as the backtracker identifies a high order technique of which I have no knowledge. That said, I suspect my UR related problems are caused by the knock on effects of applying UR techniques on non-unique puzzles, so this should not be an issue.

We'll wait and see ...

[daj95376]

FYI: A common mistake when implementing UR Type 1 logic is to not restrict the cells to a band/stack.