The New Sudoku Players' Forum

[coloin]

hi P.O.
please could you explain what went on in this thread templates as patterns
It wasnt at all clear what the difference of opinion was ...ie 6 vv 3 in Tungsten Rod !! between the various schools...

[P.O.]

hi Coloin
in any resolution state the possible templates are recovered and the combinations made, this operation alone allows to eliminate templates, those that no longer appear in any combination, and it is powerful enough, increasing the size of the combinations from 2 to 3, from 3 to 4 etc. to solve all the puzzles
Denis's implementation doesn't just do that, an excerpt from a comment of the code posted on his github page
- "When a template[2] is deleted, all the templates[3] that extend it must be deleted."
- "When a template[3] is deleted, all the templates[4] that extend it must be deleted."
i've done an analysis of what i understand about his implementation here

[StrmCkr]

Java code for working template 46656 list generator.

Template Generator: Show

Code: Select all

 
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class SudokuTemplateGenerator {

    // Peers for each cell (row, col, box)
    static BitSet[] peer = new BitSet[81];

    public static List<BitSet> templates = new ArrayList<>();
    static BitSet setStuff = new BitSet();
    static BitSet[] cellSetStuff = new BitSet[81];

    public static void main(String[] args) {
        System.out.println("Initializing peer sets...");
        initPeers();

        System.out.println("Generating templates...");
        Templates();

        System.out.println("Done. Total templates = " + templates.size());
        printTemplates(templates);
    }

    /** Build peer list (row, column, box peers). */
    static void initPeers() {
        for (int i = 0; i < 81; i++) {
            peer[i] = new BitSet(81);

            int r = i / 9;
            int c = i % 9;

            // Row peers
            for (int cc = 0; cc < 9; cc++) {
                if (cc != c)
                    peer[i].set(r * 9 + cc);
            }

            // Column peers
            for (int rr = 0; rr < 9; rr++) {
                if (rr != r)
                    peer[i].set(rr * 9 + c);
            }

            // Box peers
            int br = (r / 3) * 3;
            int bc = (c / 3) * 3;
            for (int rr = br; rr < br + 3; rr++) {
                for (int cc = bc; cc < bc + 3; cc++) {
                    int cell = rr * 9 + cc;
                    if (cell != i)
                        peer[i].set(cell);
                }
            }
        }
    }

    /** Generate all templates. */
    public static void Templates() {
        templates.clear();

        setStuff = new BitSet();
        for (int c = 0; c < 81; c++) {
            cellSetStuff[c] = new BitSet();
        }
        generateTemplates(new int[9], 0, new BitSet());
    }

    /** Recursive template builder. */
    static void generateTemplates(int[] chosen, int row, BitSet used) {
        if (row == 9) {
            BitSet template = new BitSet(81);
            for (int r = 0; r < 9; r++)
                template.set(chosen[r]);

            int templateId = templates.size();
            templates.add(template);

            setStuff.set(templateId);
            for (int cell = template.nextSetBit(0); cell >= 0; cell = template.nextSetBit(cell + 1)) {
                cellSetStuff[cell].set(templateId);
            }
            return;
        }

        int rowStart = row * 9;
        for (int col = 0; col < 9; col++) {
            int cell = rowStart + col;
            if (!used.get(cell)) {
                BitSet nextUsed = union(include(cell, used), peer[cell]);
                chosen[row] = cell;
                generateTemplates(chosen, row + 1, nextUsed);
            }
        }
    }

    /** Utility: include a bit. */
    static BitSet include(int bit, BitSet bs) {
        BitSet copy = (BitSet) bs.clone();
        copy.set(bit);
        return copy;
    }

    /** Utility: union two bitsets. */
    static BitSet union(BitSet a, BitSet b) {
        BitSet c = (BitSet) a.clone();
        c.or(b);
        return c;
    }

    /** Print all templates. */
    public static void printTemplates(List<BitSet> templates) {
        System.out.println("templates: " + templates.size());
        for (int id = 0; id < templates.size(); id++) {
            BitSet t = templates.get(id);
            System.out.print("Template " + id + ": ");
            for (int cell = t.nextSetBit(0); cell >= 0; cell = t.nextSetBit(cell + 1)) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}