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();
        }
    }
}



[StrmCkr]

Tk delete code: Show

Code: Select all

released under GNU licensing Strmckr Jan9 2026
package sudoku.testingItems;

import static sudoku.HelpingTools.Tools.Flist;
import static sudoku.HelpingTools.Tools.Slist;
import static sudoku.HelpingTools.Tools.comboset2;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.IntStream;

import sudoku.DataStorage.SBRCGrid;
import sudoku.HelpingTools.SetOps;
import sudoku.HelpingTools.SudokuTemplateGenerator;
import sudoku.HelpingTools.ToStringUtils;
import sudoku.HelpingTools.Tools;
import sudoku.Solvingtech.SolvingTechnique;
import sudoku.gui.TemplateGridViewer;
import sudoku.match.TechniqueMatch;
import sudoku.solvingtechClassifier.Technique;

public enum Templating implements SolvingTechnique {

    TECHNIQUE;

    private static final BitSet DUPLICATES_A = SetOps.fromInts(9, 10, 17, 30, 31, 35, 42, 43, 44);
    private static final BitSet DUPLICATES_B = SetOps.fromInts(45, 109, 128);
    private static final BitSet DUPLICATES_C = SetOps.fromInts(0, 1, 2, 3, 4, 5, 6, 7, 8);

    @SuppressWarnings("unchecked")
    public static List<SudokuTemplateGenerator.Template>[] templatesByDigit = new ArrayList[9];

    public static BitSet[][] DigitTemplates = new BitSet[9][81];

    private static final int MIN_HS = 1, MAX_HS = 4;
    private static final int MIN_NS = 1, MAX_NS = 4;
    private static final int TKMin = 1, TKMax = 4;

    @Override
    public Map<Technique, List<TechniqueMatch>> search(SBRCGrid sbrc) {

        ConcurrentHashMap<Integer, List<SudokuTemplateGenerator.Template>> resultMap = computeDigitTemplatesParallel(sbrc);
        storeDigitResults(resultMap);

        buildDigitTemplateIndex(sbrc);

        printTemplatesByDigitWithCells();

        TemplateGridViewer.showMultiDigitTemplateGrid(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 }, DigitTemplates, templatesByDigit);

        long t0 = System.nanoTime();
        POMexe(sbrc);
        double ms = (System.nanoTime() - t0) / 1_000_000.0;
        System.err.print(" POM:  (" + ms + "ms): ");

        TemplateGridViewer.showMultiDigitTemplateGrid(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 }, DigitTemplates, templatesByDigit);

        return Map.of(Technique.PATTERN_OVERLAY_METHOD, List.of());
    }

    // -------------------------------------------------------------------------
    // TEMPLATE COLLECTION //
    // -------------------------------------------------------------------------
    // -------------------------------------------------------------------------
    private ConcurrentHashMap<Integer, List<SudokuTemplateGenerator.Template>> computeDigitTemplatesParallel(SBRCGrid sbrc) {

        ConcurrentHashMap<Integer, List<SudokuTemplateGenerator.Template>> map = new ConcurrentHashMap<>();

        IntStream.range(0, 9).parallel().forEach(digit -> {
            try {
                BitSet digitMask = SetOps.union(
                        sbrc.digitcell[digit],
                        sbrc.SolvedCellByDigit[digit]);

                List<SudokuTemplateGenerator.Template> validTemplates = SudokuTemplateGenerator.templates.parallelStream()
                        .filter(t -> SetOps.isSubsetOf(t.cells, digitMask))
                        .map(t -> {
                            t.digit = digit; // ⭐ KEY FIX
                            return t;
                        })
                        .toList();

                map.put(digit, validTemplates);

            } catch (Throwable t) {
                t.printStackTrace();
                map.put(digit, List.of());
            }
        });

        return map;
    }

    private void storeDigitResults(ConcurrentHashMap<Integer, List<SudokuTemplateGenerator.Template>> map) {
        for (int d = 0; d < 9; d++) {
            templatesByDigit[d] = new ArrayList<>(map.getOrDefault(d, List.of()));
        }
    }

    public static void buildDigitTemplateIndex(SBRCGrid sbrc) {
        for (int d = 0; d < 9; d++) {
            List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
            if (tlist == null || tlist.isEmpty()) {
                for (int c = 0; c < 81; c++)
                    DigitTemplates[d][c] = new BitSet();
                continue;
            }
            for (int c = 0; c < 81; c++)
                DigitTemplates[d][c] = new BitSet();
            for (SudokuTemplateGenerator.Template tpl : tlist) {
                BitSet templateCells = SetOps.intersection(sbrc.digitcell[d], tpl.cells);
                for (int cell = templateCells.nextSetBit(0); cell >= 0; cell = templateCells.nextSetBit(cell + 1)) {
                    DigitTemplates[d][cell].set(tpl.id);
                }
            }
        }
    }

    // ============================================================================
    // POM CYCLICAL EXECUTION
    // ============================================================================
    private static void POMexe(SBRCGrid sbrc) {

        printTemplateCountsByDigit();
        printRemainingDigitsByRow();

        boolean changed;
        do {
            changed = false;

            if (computeOmissions(sbrc, true)) {
                changed = true;

                printTemplateCountsByDigit();
                printRemainingDigitsByRow();
                continue;
            }

            if (findHiddenSubsetsTemplateSpace(sbrc, true)) {
                changed = true;
                printTemplateCountsByDigit();
                printRemainingDigitsByRow();
                continue;
            }

            if (findNakedSubsetsTemplateSpace(sbrc, true)) {
                changed = true;
                printTemplateCountsByDigit();
                printRemainingDigitsByRow();
                continue;
            }

            if (findTKDelete(sbrc, true)) {
                changed = true;
                printTemplateCountsByDigit();
                printRemainingDigitsByRow();
                continue;
            }

        } while (changed);
    }

    private static void printTemplateCountsByDigit() {
        int total = 0;
        for (int d = 0; d < templatesByDigit.length; d++) {
            List<SudokuTemplateGenerator.Template> list = templatesByDigit[d];
            int count = (list == null) ? 0 : list.size();
            total += count;
            System.out.println("Digit " + (d + 1) + ": " + count + " templates");
        }
        System.out.println("Total templates remaining: " + total);
    }

    private static void printTemplatesByDigitWithCells() {
        for (int d = 0; d < templatesByDigit.length; d++) {
            List<SudokuTemplateGenerator.Template> list = templatesByDigit[d];
            if (list == null || list.isEmpty()) {
                System.out.println("Digit " + (d + 1) + ": no templates");
                continue;
            }

            System.out.println("Digit " + (d + 1) + " (" + list.size() + " templates):");

            for (SudokuTemplateGenerator.Template tpl : list) {
                System.out.print("  Template " + tpl.id + " cells: ");
                printCellBitSet(tpl.cells);
            }
        }
    }

    private static void printRemainingDigitsByRow() {
        @SuppressWarnings("unchecked")
        List<Integer>[] digitsPerCell = new ArrayList[81];
        for (int i = 0; i < 81; i++) {
            digitsPerCell[i] = new ArrayList<>();
        }

        // Collect allowed digits per cell
        for (int d = 0; d < templatesByDigit.length; d++) {
            List<SudokuTemplateGenerator.Template> templates = templatesByDigit[d];
            if (templates == null || templates.isEmpty())
                continue;

            int digit = d + 1;

            for (SudokuTemplateGenerator.Template tpl : templates) {
                for (int cell = tpl.cells.nextSetBit(0); cell >= 0; cell = tpl.cells.nextSetBit(cell + 1)) {

                    if (!digitsPerCell[cell].contains(digit)) {
                        digitsPerCell[cell].add(digit);
                    }
                }
            }
        }

        // Print as 9 rows × 9 columns
        for (int row = 0; row < 9; row++) {
            System.out.print("Row " + (row + 1) + ": ");

            for (int col = 0; col < 9; col++) {
                int cell = row * 9 + col;
                System.out.printf("%-9s", digitsPerCell[cell]);
            }

            System.out.println();
        }
    }

    private static void printCellBitSet(BitSet cells) {
        StringBuilder sb = new StringBuilder("[");
        boolean first = true;
        for (int cell = cells.nextSetBit(0); cell >= 0; cell = cells.nextSetBit(cell + 1)) {
            if (!first)
                sb.append(", ");
            sb.append(cell);
            first = false;
        }
        sb.append("]");
        System.out.println(sb);
    }

    // ------------------------------------------------------------------------- //
    // OMISSIONS : cells not used by any template for digit n //
    // -------------------------------------------------------------------------
    private static boolean computeOmissions(SBRCGrid sbrc, boolean applyIfFound) {
        boolean anyRemoved = false;

        for (int d = 0; d < 9; d++) {
            List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
            BitSet digitCells = sbrc.digitcell[d];
            if (tlist == null || tlist.isEmpty() || digitCells.isEmpty())
                continue;

            // Step 1: build a mask of all cells actually used by templates of this digit
            BitSet usedCells = new BitSet(81);
            for (SudokuTemplateGenerator.Template tpl : tlist) {
                usedCells.or(tpl.cells);
            }

            // Step 2: find cells in grid that are candidates but not used in any template
            BitSet omissions = (BitSet) digitCells.clone();
            omissions.andNot(usedCells);

            if (omissions.isEmpty())
                continue; // nothing to remove

            // Step 3: remove templates that touch any omitted cell
            BitSet toDelete = new BitSet();
            for (SudokuTemplateGenerator.Template tpl : tlist) {
                BitSet overlap = (BitSet) tpl.cells.clone();
                overlap.and(omissions);
                if (!overlap.isEmpty())
                    toDelete.set(tpl.id);
            }

            if (!toDelete.isEmpty()) {
                System.out.println("POM omissions for digit " + (d + 1) +
                        " => cells " + ToStringUtils.cellGroupToString(omissions) +
                        " | delete templates " + toDelete);
                if (applyIfFound)
                    anyRemoved |= applyTemplateEliminations(Map.of(d, toDelete), sbrc);
            }
        }

        return anyRemoved;
    }

    // ------------------------------------------------------------------------- //
    // INCLUSIONS + CROSS-DIGIT EXCLUSIONS cell appears in all templates for digit n
    // hidden single //
    // depreciated incorperated into hidden subsets
    // -------------------------------------------------------------------------
    private static boolean computeInclusionsHidden(SBRCGrid sbrc, boolean applyIfFound) {
        boolean anyRemoved = false;
        Map<Integer, BitSet> eliminations = new ConcurrentHashMap<>();

        for (int d = 0; d < 9; d++) {
            List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
            if (tlist == null || tlist.isEmpty())
                continue;

            int templateCount = tlist.size();
            BitSet inclusion = new BitSet();
            for (int cell = sbrc.digitcell[d].nextSetBit(0); cell >= 0; cell = sbrc.digitcell[d].nextSetBit(cell + 1)) {
                if (DigitTemplates[d][cell].cardinality() == templateCount)
                    inclusion.set(cell);
            }

            if (inclusion.isEmpty())
                continue;

            // System.out.println("POM inclusions for digit " + (d + 1) + ": " +
            // ToStringUtils.cellGroupToString(inclusion));

            for (int cell = inclusion.nextSetBit(0); cell >= 0; cell = inclusion.nextSetBit(cell + 1)) {
                BitSet otherDigits = SetOps.exclude(d, sbrc.pm[cell]);
                for (int d2 = otherDigits.nextSetBit(0); d2 >= 0; d2 = otherDigits.nextSetBit(d2 + 1)) {
                    BitSet toDelete = new BitSet();
                    for (SudokuTemplateGenerator.Template tpl : templatesByDigit[d2]) {
                        if (tpl.cells.get(cell))
                            toDelete.set(tpl.id);
                    }

                    // Only merge and print if there’s actually something to delete
                    if (!toDelete.isEmpty()) {
                        eliminations.merge(d2, toDelete, (oldBs, newBs) -> {
                            oldBs.or(newBs);
                            return oldBs;
                        });
                        // System.out.println(" → delete templates " + toDelete + " from digit " + (d2 +
                        // 1));
                    }
                }
            }
            // Only print if eliminations exist
            if (!eliminations.isEmpty()) {
                System.out.println("POM inclusions for digit " + (d + 1) + " (hidden single(s)): " + ToStringUtils.cellGroupToString(inclusion));
                for (Map.Entry<Integer, BitSet> e : eliminations.entrySet()) {
                    int d2 = e.getKey();
                    BitSet toDelete = e.getValue();
                    System.out.println("    → delete templates " + toDelete + " from digit " + (d2 + 1));
                }
            }
        }

        if (!eliminations.isEmpty() && applyIfFound)
            anyRemoved = applyTemplateEliminations(eliminations, sbrc);

        return anyRemoved;
    }

    // ------------------------------------------------------------------------- //
    // exclusion
    // naked single - digit x appears in one cell with activce templates
    // depreciated incorperated into naked subsets
    // -------------------------------------------------------------------------

    private static boolean computeExclusionsNaked(SBRCGrid sbrc, boolean applyIfFound) {
        boolean anyRemoved = false;
        Map<Integer, BitSet> eliminations = new ConcurrentHashMap<>();

        for (int cell = 0; cell < 81; cell++) {
            int activeDigit = -1;
            boolean validCell = true;
            for (int d = 0; d < 9; d++) {
                BitSet dt = DigitTemplates[d][cell];
                if (dt != null && !dt.isEmpty()) {
                    if (activeDigit == -1)
                        activeDigit = d;
                    else {
                        validCell = false;
                        break;
                    }
                }
            }
            if (!validCell || activeDigit < 0)
                continue;

            BitSet activeTemplates = (BitSet) DigitTemplates[activeDigit][cell].clone();
            List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[activeDigit];

            BitSet toDelete = new BitSet();
            for (SudokuTemplateGenerator.Template tpl : tlist) {
                if (!activeTemplates.get(tpl.id))
                    toDelete.set(tpl.id);
            }

            if (!toDelete.isEmpty())
                eliminations.put(activeDigit, toDelete);
        }

        if (!eliminations.isEmpty()) {
            for (Map.Entry<Integer, BitSet> e : eliminations.entrySet()) {
                int d = e.getKey();
                BitSet toDelete = e.getValue();

                System.out.println("POM exclusions for digit " + (d + 1) + " (naked single) -> delete templates:");
                for (int id = toDelete.nextSetBit(0); id >= 0; id = toDelete.nextSetBit(id + 1)) {
                    System.out.println("    → delete template " + id + " from digit " + (d + 1));
                }
            }
        }

        if (!eliminations.isEmpty() && applyIfFound) {
            anyRemoved = applyTemplateEliminations(eliminations, sbrc);
        }

        return anyRemoved;
    }

    // -------------------------------------------------------------------------
    // Hidden Subset support (sizes 1..4)
    // -------------------------------------------------------------------------

    private static boolean findHiddenSubsetsTemplateSpace(SBRCGrid sbrc, boolean applyIfFound) {
        boolean active = false;
        for (int n = MIN_HS; n <= MAX_HS; n++) {
            active = findHiddenSubsets_TemplateSpace(sbrc, n, applyIfFound);
            if (active) {
                return active;
            }
        }
        return active;
    }

    private static boolean findHiddenSubsets_TemplateSpace(SBRCGrid sbrc, int n, boolean applyIfFound) {
        boolean active = false;

        int subsetSize = n - 1; // matches Tools.comboset2 indexing
        int start = Tools.Slist[subsetSize];
        int end = Tools.Flist[subsetSize];

        Map<Integer, BitSet> allEliminations = new HashMap<>();

        for (int idx = start; idx <= end; idx++) {
            BitSet digitCombo = Tools.comboset2[idx]; // precomputed n-1 digit combos

            // skip if any digit in this combo has no templates
            boolean missingTemplates = false;
            for (int d = digitCombo.nextSetBit(0); d >= 0; d = digitCombo.nextSetBit(d + 1)) {
                List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
                if (tlist == null || tlist.isEmpty()) {
                    missingTemplates = true;
                    break;
                }
            }
            if (missingTemplates)
                continue;

            for (int sec = 0; sec < 27; sec++) {
                for (int k = Tools.Slist[subsetSize]; k <= Tools.Flist[subsetSize]; k++) {
                    if (boxEnforcer(sec, subsetSize, k))
                        continue;

                    BitSet cells = Tools.combosetS[sec][k];
                    if (cells == null || cells.isEmpty())
                        continue;

                    // check that all digits in subset cover all templates in these cells
                    boolean coversAll = true;
                    for (int d = digitCombo.nextSetBit(0); d >= 0; d = digitCombo.nextSetBit(d + 1)) {
                        BitSet union = new BitSet();
                        for (int c = cells.nextSetBit(0); c >= 0; c = cells.nextSetBit(c + 1)) {
                            BitSet dt = DigitTemplates[d][c];
                            if (dt != null)
                                union.or(dt);
                        }
                        if (union.cardinality() != templatesByDigit[d].size()) {
                            coversAll = false;
                            break;
                        }
                    }
                    if (!coversAll)
                        continue;

                    // collect eliminations for digits not in subset
                    Map<Integer, BitSet> eliminations = new HashMap<>();
                    for (int c = cells.nextSetBit(0); c >= 0; c = cells.nextSetBit(c + 1)) {
                        for (int d = 0; d < 9; d++) {
                            if (digitCombo.get(d))
                                continue;

                            BitSet cellTemplates = DigitTemplates[d][c];
                            if (cellTemplates == null || cellTemplates.isEmpty())
                                continue;

                            eliminations.computeIfAbsent(d, x -> new BitSet()).or(cellTemplates);
                        }
                    }

                    if (!eliminations.isEmpty()) {
                        System.out.println("HIDDEN-SUBSET: digits=" + ToStringUtils.getDigits(digitCombo) +
                                " cells=" + ToStringUtils.cellGroupToString(cells) +
                                " sector=" + sec + " size=" + n);
                        for (var e : eliminations.entrySet()) {
                            System.out.println("  -> eliminate digit " + (e.getKey() + 1) + " templates=" + e.getValue());
                        }

                        for (var e : eliminations.entrySet()) {
                            allEliminations.merge(e.getKey(), e.getValue(), (a, b) -> {
                                BitSet merged = (BitSet) a.clone();
                                merged.or(b);
                                return merged;
                            });
                        }

                    }
                }
            }
        }

        if (applyIfFound && !allEliminations.isEmpty()) {
            active = applyTemplateEliminations(allEliminations, sbrc);
        }

        return active;
    }

    // -------------------------------------------------------------------------
    // Naked Subset support (sizes 1..4)
    // -------------------------------------------------------------------------
    private static boolean findNakedSubsetsTemplateSpace(SBRCGrid sbrc, boolean applyIfFound) {
        boolean active = false;
        for (int n = MIN_NS; n <= MAX_NS; n++) {
            active = findNakedSubsets_TemplateSpace(sbrc, n, applyIfFound);
            if (active)
                return active;
        }
        return active;
    }

    private static boolean findNakedSubsets_TemplateSpace(SBRCGrid sbrc, int n, boolean applyIfFound) {
        boolean active = false;

        int subsetSize = n - 1; // matches Tools.comboset2 indexing
        int start = Tools.Slist[subsetSize];
        int end = Tools.Flist[subsetSize];

        Map<Integer, BitSet> allEliminations = new HashMap<>();

        for (int idx = start; idx <= end; idx++) {
            BitSet digitCombo = Tools.comboset2[idx]; // precomputed n-1 digit combos

            // skip if any digit in combo has no templates
            boolean missingTemplates = false;
            for (int d = digitCombo.nextSetBit(0); d >= 0; d = digitCombo.nextSetBit(d + 1)) {
                List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
                if (tlist == null || tlist.isEmpty()) {
                    missingTemplates = true;
                    break;
                }
            }
            if (missingTemplates)
                continue;

            BitSet subsetMask = (BitSet) digitCombo.clone();

            for (int sec = 0; sec < 27; sec++) {
                for (int k = Tools.Slist[subsetSize]; k <= Tools.Flist[subsetSize]; k++) {
                    if (boxEnforcer(sec, subsetSize, k))
                        continue;

                    BitSet cells = Tools.combosetS[sec][k];
                    if (cells == null || cells.isEmpty())
                        continue;

                    // verify all cells only contain digits in the subset
                    boolean validCells = true;
                    for (int c = cells.nextSetBit(0); c >= 0; c = cells.nextSetBit(c + 1)) {
                        BitSet activeDigits = new BitSet();
                        for (int d = 0; d < 9; d++) {
                            if (DigitTemplates[d][c] != null && !DigitTemplates[d][c].isEmpty())
                                activeDigits.set(d);
                        }

                        BitSet subsetInCell = (BitSet) activeDigits.clone();
                        subsetInCell.and(subsetMask);
                        if (subsetInCell.isEmpty()) {
                            validCells = false;
                            break;
                        }

                        BitSet otherDigits = (BitSet) activeDigits.clone();
                        otherDigits.andNot(subsetMask);
                        if (!otherDigits.isEmpty()) {
                            validCells = false;
                            break;
                        }
                    }
                    if (!validCells)
                        continue;

                    // compute which templates of each digit in subset appear in these cells
                    Map<Integer, BitSet> usedInCells = new HashMap<>();
                    for (int d = subsetMask.nextSetBit(0); d >= 0; d = subsetMask.nextSetBit(d + 1)) {
                        BitSet union = new BitSet();
                        for (int c = cells.nextSetBit(0); c >= 0; c = cells.nextSetBit(c + 1)) {
                            BitSet dt = DigitTemplates[d][c];
                            if (dt != null)
                                union.or(dt);
                        }
                        usedInCells.put(d, union);
                    }

                    // compute eliminations: templates outside the union of usedInCells
                    Map<Integer, BitSet> eliminations = new HashMap<>();
                    for (int d = subsetMask.nextSetBit(0); d >= 0; d = subsetMask.nextSetBit(d + 1)) {
                        List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
                        if (tlist == null || tlist.isEmpty())
                            continue;

                        BitSet full = new BitSet();
                        for (SudokuTemplateGenerator.Template tpl : tlist)
                            full.set(tpl.id);

                        BitSet outside = (BitSet) full.clone();
                        outside.andNot(usedInCells.get(d));
                        if (!outside.isEmpty())
                            eliminations.put(d, outside);
                    }

                    if (!eliminations.isEmpty()) {
                        System.out.println("NAKED-SUBSET: digits=" + ToStringUtils.getDigits(subsetMask) +
                                " cells=" + ToStringUtils.cellGroupToString(cells) +
                                " sector=" + sec + " size=" + n);
                        for (var e : eliminations.entrySet()) {
                            System.out.println("  -> eliminate digit " + (e.getKey() + 1) + " templates=" + e.getValue());
                        }

                        for (var e : eliminations.entrySet()) {
                            allEliminations.merge(e.getKey(), e.getValue(), (a, b) -> {
                                BitSet merged = (BitSet) a.clone();
                                merged.or(b);
                                return merged;
                            });
                        }
                    }
                }
            }
        }

        if (applyIfFound && !allEliminations.isEmpty()) {
            active = applyTemplateEliminations(allEliminations, sbrc);
        }

        return active;
    }

    // ============================================================================
    // TRUE TEMPLATE[K] DELETE (T2–T6) — UNIVERSAL EXTENSION VERSION
    // ============================================================================
    private static boolean findTKDelete(SBRCGrid sbrc, boolean applyIfFound) {
        for (int k = TKMin; k <= TKMax; k++) {
            if (applyTkDelete(sbrc, k, applyIfFound))
                return true;
        }
        return false;
    }

    // ============================================================================
    private static boolean applyTkDelete(SBRCGrid sbrc, int k, boolean applyIfFound) {

        boolean anyRemoved = false;
        Map<Integer, BitSet> eliminations = new HashMap<>();

        int subsetSize = k - 1;
        int start = Slist[subsetSize];
        int finish = Flist[subsetSize];

        for (int dA = 0; dA < 9; dA++) {

            List<SudokuTemplateGenerator.Template> baseList = templatesByDigit[dA];
            if (baseList == null || baseList.isEmpty())
                continue;

            for (SudokuTemplateGenerator.Template tA : baseList) {

                BitSet occupiedBase = tA.cells;

                for (int idx = start; idx <= finish; idx++) {

                    BitSet mask = comboset2[idx];

                    // must not include base digit
                    if (mask.get(dA))
                        continue;

                    List<List<SudokuTemplateGenerator.Template>> lists = new ArrayList<>(subsetSize);
                    boolean dead = false;

                    for (int d = mask.nextSetBit(0); d >= 0; d = mask.nextSetBit(d + 1)) {
                        List<SudokuTemplateGenerator.Template> lst = templatesByDigit[d];
                        if (lst == null || lst.isEmpty()) {
                            dead = true;
                            break;
                        }
                        lists.add(lst);
                    }

                    if (dead)
                        continue;

                    // prune hard
                    lists.sort(Comparator.comparingInt(List::size));

                    BitSet occupied = (BitSet) occupiedBase.clone();

                    // NEW: include chosen digits for universal extension check
                    BitSet chosenDigits = (BitSet) mask.clone();
                    chosenDigits.set(dA);

                    if (!existsCompatibleSet(lists, occupied, 0, chosenDigits)) {

                        eliminations
                                .computeIfAbsent(dA, x -> new BitSet())
                                .set(tA.id);

                        System.out.print(
                                "T" + (k + 1) + "-delete: digit " + (dA + 1) +
                                        " template " + tA.id +
                                        " cannot form Template[" + (k + 1) + "] with digits {");

                        System.out.print(dA + 1);
                        for (int d = mask.nextSetBit(0); d >= 0; d = mask.nextSetBit(d + 1))
                            System.out.print("," + (d + 1));
                        System.out.println("}");

                        break;
                    }
                }
            }
        }

        if (!eliminations.isEmpty() && applyIfFound) {
            anyRemoved = applyTemplateEliminations(eliminations, sbrc);
        }

        return anyRemoved;
    }

    // ============================================================================
    private static boolean existsCompatibleSet(
            List<List<SudokuTemplateGenerator.Template>> lists,
            BitSet occupied,
            int idx,
            BitSet chosenDigits) {

        if (idx == lists.size()) {
            // TK node fully built → check universal extension
            return universallyExtendableNode(occupied, chosenDigits);

        }

        for (SudokuTemplateGenerator.Template tpl : lists.get(idx)) {
            if (!occupied.intersects(tpl.cells)) {
                BitSet newOccupied = (BitSet) occupied.clone();
                newOccupied.or(tpl.cells);
                if (existsCompatibleSet(lists, newOccupied, idx + 1, chosenDigits))
                    return true;

            }
        }
        return false;
    }

    private static boolean universallyExtendableNode(
            BitSet occupied, BitSet chosenDigits) {

        // Collect remaining digits
        List<Integer> remaining = new ArrayList<>();
        for (int d = 0; d < 9; d++) {
            if (!chosenDigits.get(d)) {
                remaining.add(d);
            }
        }

        // ---- 1. Single-digit check
        for (int x : remaining) {
            List<SudokuTemplateGenerator.Template> lx = templatesByDigit[x];
            if (lx == null || lx.isEmpty())
                return false;

            boolean ok = false;
            for (var tx : lx) {
                if (!occupied.intersects(tx.cells)) {
                    ok = true;
                    break;
                }
            }
            if (!ok)
                return false;
        }

        // ---- 2. Pairwise check
        for (int i = 0; i < remaining.size(); i++) {
            int x = remaining.get(i);
            var lx = templatesByDigit[x];

            for (int j = i + 1; j < remaining.size(); j++) {
                int y = remaining.get(j);
                var ly = templatesByDigit[y];

                boolean pairOk = false;
                for (var tx : lx) {
                    if (occupied.intersects(tx.cells))
                        continue;

                    for (var ty : ly) {
                        if (occupied.intersects(ty.cells))
                            continue;

                        if (!tx.cells.intersects(ty.cells)) {
                            pairOk = true;
                            break;
                        }
                    }
                    if (pairOk)
                        break;
                }

                if (!pairOk)
                    return false;
            }
        }

        // ---- 3. Triple check {x, y, z}
        for (int i = 0; i < remaining.size(); i++) {
            int x = remaining.get(i);
            var lx = templatesByDigit[x];

            for (int j = i + 1; j < remaining.size(); j++) {
                int y = remaining.get(j);
                var ly = templatesByDigit[y];

                for (int k = j + 1; k < remaining.size(); k++) {
                    int z = remaining.get(k);
                    var lz = templatesByDigit[z];

                    boolean tripleOk = false;

                    for (var tx : lx) {
                        if (occupied.intersects(tx.cells))
                            continue;

                        for (var ty : ly) {
                            if (occupied.intersects(ty.cells))
                                continue;
                            if (tx.cells.intersects(ty.cells))
                                continue;

                            for (var tz : lz) {
                                if (occupied.intersects(tz.cells))
                                    continue;

                                if (!tx.cells.intersects(tz.cells)
                                        && !ty.cells.intersects(tz.cells)) {
                                    tripleOk = true;
                                    break;
                                }
                            }
                            if (tripleOk)
                                break;
                        }
                        if (tripleOk)
                            break;
                    }

                    if (!tripleOk)
                        return false; // {x,y,z} cannot be jointly extended
                }
            }
        }

        return true;
    }

    // -------------------------------------------------------------------------
    // elimiantion application tool
    // -------------------------------------------------------------------------
    private static Boolean applyTemplateEliminations(Map<Integer, BitSet> eliminations, SBRCGrid sbrc) {
        boolean anyRemoved = false;
        for (Map.Entry<Integer, BitSet> e : eliminations.entrySet()) {
            int d = e.getKey();
            BitSet toRemoveIdx = e.getValue();
            List<SudokuTemplateGenerator.Template> tlist = templatesByDigit[d];
            if (tlist == null || tlist.isEmpty())
                continue;
            List<SudokuTemplateGenerator.Template> newList = new ArrayList<>();
            for (SudokuTemplateGenerator.Template tpl : tlist) {
                if (!toRemoveIdx.get(tpl.id))
                    newList.add(tpl);
                else {
                    // System.out.println(" (applied) removed template " + tpl.id + " for digit " +
                    // (d + 1));
                    anyRemoved = true;
                }
            }
            templatesByDigit[d] = newList;

            // rebuild DigitTemplates
            for (int c = 0; c < 81; c++)
                DigitTemplates[d][c] = new BitSet();
            for (SudokuTemplateGenerator.Template tpl : newList) {
                BitSet cells = SetOps.intersection(sbrc.digitcell[d], tpl.cells);
                for (int cell = cells.nextSetBit(0); cell >= 0; cell = cells.nextSetBit(cell + 1))
                    DigitTemplates[d][cell].set(tpl.id);
            }
        }
        return anyRemoved;
    }

    private static boolean boxEnforcer(int sector, int positionSize, int PowerSetIndex) {
        if (sector >= 18)
            return false;
        if (positionSize == 0 && DUPLICATES_C.get(PowerSetIndex))
            return true;
        if (positionSize == 1 && DUPLICATES_A.get(PowerSetIndex))
            return true;
        if (positionSize == 2 && DUPLICATES_B.get(PowerSetIndex))
            return true;
        return false;
    }

}


[StrmCkr]

my results for Tungsten Rod

Code: Select all

000000007020400060100000500090002040000800600600900000005003000030080020700004001

with a max depth of "T6" reached currently. run time: POM: (18489.4348ms): {higher time with all the write to screen functions to paste in here}

Code: Select all

 .---------.---------.---------.
| 8  5  4 | 3  6  9 | 2  1  7 |
| 3  2  7 | 4  5  1 | 9  6  8 |
| 1  6  9 | 2  7  8 | 5  3  4 |
:---------+---------+---------:
| 5  9  8 | 6  1  2 | 7  4  3 |
| 4  1  2 | 8  3  7 | 6  5  9 |
| 6  7  3 | 9  4  5 | 1  8  2 |
:---------+---------+---------:
| 2  4  5 | 1  9  3 | 8  7  6 |
| 9  3  1 | 7  8  6 | 4  2  5 |
| 7  8  6 | 5  2  4 | 3  9  1 |
'---------'---------'---------'

amended {old build reached T6}

[P.O.]

hi StrmCkr,
My solution to Tungsten Rod is similar to yours; I have the same number of templates at puzzle initialization and I need combinations of size 6 to obtain the solution.

Hidden Text: Show

Code: Select all

POMethod TPlimit: 10 / checkVT: NIL / CheckCombsEarly: NIL

........7.2.4...6.1.....5...9...2.4....8..6..6..9.......5..3....3..8..2.7....4..1
#VT: (42 10 113 24 42 28 57 144 88)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL

34589   4568    34689   12356   123569  15689   123489  1389    7               
3589    2       3789    4       13579   15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     23489           
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
253 candidates. 21 values.

----- after TPinit -----
----- Combs2 -----
----- Combs3 -----

34589   4568    34689   12356   123569  15689   123489  1389    7               
3589    2       3789    4       13579   15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     23489           
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
253 candidates. 21 values.

----- SetVC -----
#VT: (30 10 75 24 42 28 55 97 56)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: (7) NIL (7 27) NIL NIL NIL NIL (7 27) (7 27)
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

34589   4568    34689   12356   123569  15689   24      1389    7               
3589    2       3789    4       13579   15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     24               
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
246 candidates. 21 values.

----- SetVC -----
#VT: (30 10 74 24 34 28 52 96 56)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----
----- Combs5 -----

34589   4568    34689   12356   123569  15689   24      1389    7               
3589    2       3789    4       13579   15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     24               
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
246 candidates. 21 values.

----- SetVC -----
#VT: (27 10 53 24 32 28 46 84 51)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL (14) NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----
----- Combs5 -----

34589   4568    34689   12356   123569  15689   24      1389    7               
3589    2       3789    4       1579    15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     24               
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
245 candidates. 21 values.

----- SetVC -----
#VT: (27 10 53 24 32 28 45 84 51)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----
----- Combs5 -----
----- Combs6 -----

34589   4568    34689   12356   123569  15689   24      1389    7               
3589    2       3789    4       1579    15789   1389    6       389             
1       4678    346789  2367    23679   6789    5       389     24               
358     9       1378    13567   13567   2       1378    4       358             
2345    1457    12347   8       13457   157     6       13579   2359             
6       14578   123478  9       13457   157     12378   13578   2358             
2489    1468    5       1267    12679   3       4789    789     4689             
49      3       1469    1567    8       15679   479     2       4569             
7       68      2689    256     2569    4       389     3589    1               
245 candidates. 21 values.

----- SetVC -----
#VT: (14 10 25 17 4 12 9 36 23)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL (5 23 31) (20) (1 4 6 15 31 32 37 41 45 50 54 69 77) (23 58 67) (21 24 61) (20) (5 14)
----- EraseCC -----

----- Combs2 -----

3489    4568    34689   1236    1256    1689    24      1389    7               
3589    2       3789    4       157     1789    1389    6       389             
1       67      34689   2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
219 candidates. 21 values.

----- SetVC -----
#VT: (14 9 25 17 4 12 9 36 23)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----

3489    4568    34689   1236    1256    1689    24      1389    7               
3589    2       3789    4       157     1789    1389    6       389             
1       67      34689   2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
219 candidates. 21 values.

----- SetVC -----
#VT: (14 9 25 17 4 12 9 30 23)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    1256    1689    24      1389    7               
3589    2       3789    4       157     1789    1389    6       389             
1       67      34689   2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
219 candidates. 21 values.

----- SetVC -----
#VT: (14 8 23 15 4 11 9 26 21)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL (5) NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       3789    4       157     1789    1389    6       389             
1       67      34689   2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
218 candidates. 21 values.

----- SetVC -----
#VT: (14 8 21 15 4 11 9 25 18)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL (12)
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      34689   2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
217 candidates. 21 values.

----- SetVC -----
#VT: (14 8 21 15 4 11 9 23 18)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL (21) NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      3469    2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
216 candidates. 21 values.

----- SetVC -----
#VT: (14 8 20 15 4 11 9 23 17)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      3469    2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
216 candidates. 21 values.

----- SetVC -----
#VT: (14 8 19 15 4 11 9 23 17)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      3469    2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
216 candidates. 21 values.

----- SetVC -----
#VT: (14 8 19 15 4 11 9 23 16)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      3469    2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
216 candidates. 21 values.

----- SetVC -----
#VT: (14 8 19 15 4 10 9 23 16)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----
----- Combs4 -----
----- Combs5 -----

3489    4568    34689   1236    156     1689    24      1389    7               
3589    2       378     4       157     1789    1389    6       389             
1       67      3469    2367    279     689     5       389     24               
358     9       1378    167     1367    2       1378    4       358             
234     1457    12347   8       1347    157     6       13579   239             
6       14578   123478  9       1347    157     12378   13578   238             
2489    1468    5       127     12679   3       489     789     4689             
49      3       1469    157     8       1679    479     2       4569             
7       68      2689    256     269     4       389     3589    1               
216 candidates. 21 values.

----- SetVC -----
#VT: (10 4 7 7 4 9 8 11 7)
Cells: NIL NIL (79) (27) NIL NIL NIL NIL NIL
SetVC: ( n4r3c9   n3r9c7   n2r1c7 )

Candidates: (4 39 41 48 50 69) (45 48 59) (3 21 32 37 54) (66) NIL NIL (50) (2 3 16 55 80) (24 63 66 72)
EraseCC: ( n2r6c9 )
----- EraseCC -----

----- SetVC -----
#VT: (10 4 7 7 4 9 8 11 7)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----

3489   456    469    36     156    1689   2      1389   7               
3589   2      378    4      157    1789   19     6      389             
1      67     69     2367   279    68     5      389    4               
358    9      1378   167    167    2      178    4      358             
24     1457   2347   8      347    157    6      13579  39             
6      14578  3478   9      34     157    178    13578  2               
249    1468   5      127    1679   3      489    789    68             
49     3      16     157    8      679    479    2      56             
7      68     2689   256    269    4      3      59     1               
173 candidates. 25 values.

----- SetVC -----
#VT: (10 3 7 7 4 9 8 8 6)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL (56) (3)
----- EraseCC -----

----- Combs2 -----

3489   456    46     36     156    1689   2      1389   7               
3589   2      378    4      157    1789   19     6      389             
1      67     69     2367   279    68     5      389    4               
358    9      1378   167    167    2      178    4      358             
24     1457   2347   8      347    157    6      13579  39             
6      14578  3478   9      34     157    178    13578  2               
249    146    5      127    1679   3      489    789    68             
49     3      16     157    8      679    479    2      56             
7      68     2689   256    269    4      3      59     1               
171 candidates. 25 values.

----- SetVC -----
#VT: (10 3 7 7 4 9 8 6 5)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL (45)
SetVC: ( n9r5c9 )

Candidates: NIL NIL NIL NIL NIL NIL NIL (15) (61)
----- EraseCC -----

----- Combs2 -----

3489   456    46     36     156    1689   2      1389   7               
3589   2      378    4      157    179    19     6      38             
1      67     69     2367   279    68     5      389    4               
358    9      1378   167    167    2      178    4      358             
24     1457   2347   8      347    157    6      1357   9               
6      14578  3478   9      34     157    178    13578  2               
249    146    5      127    1679   3      48     789    68             
49     3      16     157    8      679    479    2      56             
7      68     2689   256    269    4      3      59     1               
165 candidates. 26 values.

----- SetVC -----
#VT: (10 3 5 7 4 9 8 6 5)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL (12 28) NIL NIL NIL NIL NIL NIL
----- EraseCC -----

----- Combs2 -----
----- Combs3 -----

3489   456    46     36     156    1689   2      1389   7               
3589   2      78     4      157    179    19     6      38             
1      67     69     2367   279    68     5      389    4               
58     9      1378   167    167    2      178    4      358             
24     1457   2347   8      347    157    6      1357   9               
6      14578  3478   9      34     157    178    13578  2               
249    146    5      127    1679   3      48     789    68             
49     3      16     157    8      679    479    2      56             
7      68     2689   256    269    4      3      59     1               
163 candidates. 26 values.

----- SetVC -----
#VT: (10 3 5 7 4 5 4 6 3)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL (2 4 59) (14 30 39 41 53 58) NIL (10 26)
EraseCC: ( n3r1c4   n3r3c8   n3r2c1   n5r2c5   n5r1c2   n5r4c1   n8r3c6   n8r1c1   n9r3c3   n7r2c3
           n8r2c9   n6r3c2   n3r4c9   n6r7c9   n5r8c9   n8r9c2   n9r9c8   n4r1c3   n1r1c8   n9r2c7
           n6r1c5   n9r1c6   n1r2c6   n2r9c5   n7r3c5   n1r4c5   n1r7c4   n9r7c5   n7r8c4   n6r8c6
           n4r8c7   n6r9c3   n5r9c4   n2r3c4   n8r4c3   n6r4c4   n7r4c7   n5r5c8   n3r6c3   n4r6c5
           n8r6c8   n4r7c2   n8r7c7   n7r7c8   n9r8c1   n1r8c3   n2r5c3   n3r5c5   n7r5c6   n5r6c6
           n1r6c7   n2r7c1   n4r5c1   n1r5c2   n7r6c2 )
8 5 4   3 6 9   2 1 7
3 2 7   4 5 1   9 6 8
1 6 9   2 7 8   5 3 4
5 9 8   6 1 2   7 4 3
4 1 2   8 3 7   6 5 9
6 7 3   9 4 5   1 8 2
2 4 5   1 9 3   8 7 6
9 3 1   7 8 6   4 2 5
7 8 6   5 2 4   3 9 1

(3 4 5 5 6 2 3 4 4 4 4 4 4 4 5 2 2 2 3)
puzzle in 6(1)-Template


[StrmCkr]

any idea what denis is doing different to get his "Tk score down to 4?" I cannot figure that out atm

how is my computation time of 18s

[P.O.]

Your time is excellent compared to mine.
Regarding Denis's implementation, here is the explanation I gave to Coloin.

[StrmCkr]

i really don't get what he did there, i cannot replicate what i am missing/overlooked to replicate it....

[P.O.]

I haven't replicated what Denis did; Blue seems to have a similar implementation to Denis's, as it appears to have the same results.
The fact is that it's possible to test the validity of templates and combinations within the context of the current possible templates.
For example, once the templates are retrieved, a template for value 1 is valid if it's compatible with at least one template for each of the other values.
Similarly for combinations, for example a combination (1 2) is valid if it is compatible with at least one template for each of the other values
Performing these kinds of checks can lead to more template eliminations and therefore more candidate eliminations or placements.
This reduces the template depth of a puzzle, but it's not my preferred method.
What I prefer is the purely combinatorial method, eliminating templates that don't appear in any of the combinations.

[rjamil]

Similarly for combinations, for example a combination (1 2) is valid if it is compatible with at least one template for each of the other values
Performing these kinds of checks can lead to more template eliminations and therefore more candidate eliminations or placements.
This reduces the template depth of a puzzle, but it's not my preferred method.

In my opinion, combination of (1 2) is not either equal to or same as the combination of (2 1).

In my limited knowledge, "combination of (1 2) is valid if it is compatible with at least one template for each of the other valies" is simply none other than that checking the combination of (1 2 3) (1 2 4) ... (1 2 9), without removing any intermediate templates.

Combination (1 2 3) means to check all valid templates of digit 1 against at least one of the digits 2 and 3 valid templates. similarly, (2 1 3) means to check all valid templates of digit 2 against at least one of the digits 1 and 3 valid templates, and so on.

Let for example, digit 1 valid templates are 10, digit 2 valid templates are 8 and digit 3 valid templates are 6. I check all templates of digit 1 templates compatible with digit 2 and 3 templates simultaneously/concurrently. I know that, if digit 1 template not compatible with all combinations of digits 2 and 3 templates then it is considered as invalid for all other combinations. But again, for simplicity, I check again in four digits combination, i.e., combination (1 2 3 4) (1 2 3 5) ... (1 2 3 9).

I admit that my way of doing is replicated work but simple one and without keep tracking individual digit valid templates. If I searched single digit valid templates with highly optimised 46,656 indexed templates efficiently then, it is easy to search multi digit valid templates too.

I have share what I understand the simpliest way to tackle the POM.

R. Jamil

[StrmCkr]

i built a 2nd version of my Template code to try to figure out how Denis' stuff.
this time i build a full table as a Tree :
Ti parent node -> child -> grand child -> great grand child ...
children represent K depth level

generalized T k delete rule 1:
for Each Ti at child depth k, it must have a representation for each combo-set size K that include Ti's digit
meaning at k =1 : there must be at least 1 representation, k=2 : 8, k=3:28, k=4: 56 and so on.
nCr = (8, k-1) combinations.

if there is < nCr combinations represented at depth K, then the Ti is excluded.

Code: Select all

.----------.-------------.---------.
| 3  8  6  | 79   27  29 | 1  4  5 |
| 7  4  5  | 6    8   1  | 9  2  3 |
| 2  9  1  | 3    4   5  | 6  7  8 |
:----------+-------------+---------:
| 1  5  38 | 78   37  4  | 2  9  6 |
| 4  2  39 | 19   13  6  | 8  5  7 |
| 6  7  89 | 589  25  29 | 4  3  1 |
:----------+-------------+---------:
| 8  1  7  | 2    9   3  | 5  6  4 |
| 9  6  4  | 15   15  7  | 3  8  2 |
| 5  3  2  | 4    6   8  | 7  1  9 |
'----------'-------------'---------'

At k level 4 the following occurs:
ELIMINATE Ti { digit=3, templateId=4437 } — seen 55 / 56
ELIMINATE Ti { digit=5, templateId=43865 } — seen 55 / 56
ELIMINATE Ti { digit=7, templateId=21156 } — seen 55 / 56
ELIMINATE Ti { digit=9, templateId=18644 } — seen 55 / 56
ELIMINATE Ti { digit=9, templateId=29024 } — seen 55 / 56

cross matched to my first draft of Tk delete at depth 4.
the missing representation :
T4-delete: digit 3 template 4437 cannot form Template[4] with digits {3,2,7,9}
T4-delete: digit 5 template 43865 cannot form Template[4] with digits {5,7,8,9}
T4-delete: digit 7 template 21156 cannot form Template[4] with digits {7,2,5,8}
T4-delete: digit 9 template 18644 cannot form Template[4] with digits {9,3,7,8}
T4-delete: digit 9 template 29024 cannot form Template[4] with digits {9,1,5,8}

referencing the printed copies of the 4437 tree - 2,3,7,9 is not represented confirming the 1 missing combination.

this rule is solid...now to figure out the other one....

[P.O.]

Code: Select all

my analysis of the puzzle:

3    8    6    79   27   29   1    4    5             
7    4    5    6    8    1    9    2    3             
2    9    1    3    4    5    6    7    8             
1    5    38   78   37   4    2    9    6             
4    2    39   19   13   6    8    5    7             
6    7    89   589  25   29   4    3    1             
8    1    7    2    9    3    5    6    4             
9    6    4    15   15   7    3    8    2             
5    3    2    4    6    8    7    1    9             
31 candidates. 66 values.

386...14574568192329134567815...429642...685767....431817293564964..7382532468719

the possible templates after initialization:

#VT: (2 2 2 1 2 1 2 2 3)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates: NIL NIL NIL NIL NIL NIL NIL NIL NIL

#1: ((7 15 21 28 41 54 56 67 80) (7 15 21 28 40 54 56 68 80))
#2: ((6 17 19 34 38 50 58 72 75) (5 17 19 34 38 51 58 72 75))
#3: ((1 18 22 32 39 53 60 70 74) (1 18 22 30 41 53 60 70 74))
#4: ((8 11 23 33 37 52 63 66 76))
#5: ((9 12 24 29 44 50 61 67 73) (9 12 24 29 44 49 61 68 73))
#6: ((3 13 25 36 42 46 62 65 77))
#7: ((5 10 26 31 45 47 57 69 79) (4 10 26 32 45 47 57 69 79))
#8: ((2 14 27 31 43 48 55 71 78) (2 14 27 30 43 49 55 71 78))
#9: ((6 16 20 35 40 48 59 64 81) (6 16 20 35 39 49 59 64 81) (4 16 20 35 39 51 59 64 81))

without performing any validity checks, I need combinations of size 4 to solve it
Any of these combinations: (2 5 7 8) (5 7 8 9) (3 7 8 9) (2 3 7 9) (1 5 8 9)

for example (1 5 8 9)
Combining the templates for these values gives 4 instances, which eliminates one template for 9 and consequently places n9r5c3, thus solving the puzzle

(1 5 8 9): 4 instances
.8.9..1.5..5.819...91..5..815.8...9...9.1.85...85.9..181..9.5..9..15..8.5....8.19
.8...91.5..5.819...91..5..815.8...9...91..85...895...181..9.5..9..51..8.5....8.19
.8.9..1.5..5.819...91..5..815.8...9...91..85...8.59..181..9.5..9..51..8.5....8.19
.8.9..1.5..5.819...91..5..8158....9...91..85....859..181..9.5..9..51..8.5....8.19

......1.......1.....1......1............1............1.1..........1............1.
......1.......1.....1......1...........1.............1.1...........1...........1.

........5..5...........5....5..............5.....5..........5.....5.....5........
........5..5...........5....5..............5....5...........5......5....5........

.8...........8............8...8...........8....8......8...............8......8...
.8...........8............8..8............8.....8.....8...............8......8...

.....9.........9...9..............9...9.........9.........9....9................9
...9...........9...9..............9...9...........9.......9....9................9


#VT: (2 2 2 1 2 1 2 2 2)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL (39)
SetVC: ( n9r5c3   n1r5c4   n3r5c5   n8r6c3   n5r8c4   n1r8c5   n3r4c3   n7r4c5   n9r6c4   n2r6c6
         n7r1c4   n2r1c5   n9r1c6   n8r4c4   n5r6c5 )
3 8 6   7 2 9   1 4 5
7 4 5   6 8 1   9 2 3
2 9 1   3 4 5   6 7 8
1 5 3   8 7 4   2 9 6
4 2 9   1 3 6   8 5 7
6 7 8   9 5 2   4 3 1
8 1 7   2 9 3   5 6 4
9 6 4   5 1 7   3 8 2
5 3 2   4 6 8   7 1 9


with validity checks it is solved with combinations of size 2
Any of these combinations: (5 7) (2 3) (8 9) (5 9)

for example (5 9)
Combining the templates for these values gives 5 instances

(5 9): 5 instances
.....9..5..5...9...9...5....5.....9....9...5...9.5........9.5..9..5.....5.......9
.....9..5..5...9...9...5....5.....9...9....5....95........9.5..9..5.....5.......9
...9....5..5...9...9...5....5.....9...9....5.....59.......9.5..9..5.....5.......9
.....9..5..5...9...9...5....5.....9....9...5...95.........9.5..9...5....5.......9
...9....5..5...9...9...5....5.....9...9....5....5.9.......9.5..9...5....5.......9

After checking these instances, only 2 remain
.....9..5..5...9...9...5....5.....9...9....5....95........9.5..9..5.....5.......9
...9....5..5...9...9...5....5.....9...9....5....5.9.......9.5..9...5....5.......9

which eliminates one template for 9

#VT(2 2 2 1 2 1 2 2 2)

Checking the remaining templates leaves only one for each value

#VT(1 1 1 1 1 1 1 1 1)


(5 9): 1 instance
.....9..5..5...9...9...5....5.....9...9....5....95........9.5..9..5.....5.......9

........5..5...........5....5..............5.....5..........5.....5.....5........

.....9.........9...9..............9...9.........9.........9....9................9


#VT: (1 1 1 1 1 1 1 1 1)
Cells: (40 68) (5 51) (30 41) NIL (50 67) NIL (4 32) (31 48) (6 39 49)
SetVC: ( n7r1c4   n2r1c5   n9r1c6   n3r4c3   n8r4c4   n7r4c5   n9r5c3   n1r5c4   n3r5c5   n8r6c3
         n9r6c4   n5r6c5   n2r6c6   n5r8c4   n1r8c5 )
3 8 6   7 2 9   1 4 5
7 4 5   6 8 1   9 2 3
2 9 1   3 4 5   6 7 8
1 5 3   8 7 4   2 9 6
4 2 9   1 3 6   8 5 7
6 7 8   9 5 2   4 3 1
8 1 7   2 9 3   5 6 4
9 6 4   5 1 7   3 8 2
5 3 2   4 6 8   7 1 9


[StrmCkr]

with validity checks it is solved with combinations of size 2
Any of these combinations: (5 7) (2 3) (8 9) (5 9)

for example (5 9)
Combining the templates for these values gives 5 instances

(5 9): 5 instances
.....9..5..5...9...9...5....5.....9....9...5...9.5........9.5..9..5.....5.......9
.....9..5..5...9...9...5....5.....9...9....5....95........9.5..9..5.....5.......9
...9....5..5...9...9...5....5.....9...9....5.....59.......9.5..9..5.....5.......9
.....9..5..5...9...9...5....5.....9....9...5...95.........9.5..9...5....5.......9
...9....5..5...9...9...5....5.....9...9....5....5.9.......9.5..9...5....5.......9

After checking these instances, only 2 remain
.....9..5..5...9...9...5....5.....9...9....5....95........9.5..9..5.....5.......9
...9....5..5...9...9...5....5.....9...9....5....5.9.......9.5..9...5....5.......9

care to explain this in detail exactly what it is doing as "checks".

i have :
Level 2 digits=5,9 tplIds=[43865, 18644]
5:r1c9,r2c3,r3c6,r4c2,r5c8,r6c4,r7c7,r8c5,r9c1
9:r1c4,r2c7,r3c2,r4c8,r5c3,r6c6,r7c5,r8c1,r9c9

Level 2 digits=5,9 tplIds=[43865, 29024]
5:r1c9,r2c3,r3c6,r4c2,r5c8,r6c4,r7c7,r8c5,r9c1
9:r1c6,r2c7,r3c2,r4c8,r5c4,r6c3,r7c5,r8c1,r9c9

Level 2 digits=5,9 tplIds=[43871, 18644]
5:r1c9,r2c3,r3c6,r4c2,r5c8,r6c5,r7c7,r8c4,r9c1
9:r1c4,r2c7,r3c2,r4c8,r5c3,r6c6,r7c5,r8c1,r9c9

Level 2 digits=5,9 tplIds=[43871, 29006]
5:r1c9,r2c3,r3c6,r4c2,r5c8,r6c5,r7c7,r8c4,r9c1
9:r1c6,r2c7,r3c2,r4c8,r5c3,r6c4,r7c5,r8c1,r9c9

Level 2 digits=5,9 tplIds=[43871, 29024]
5:r1c9,r2c3,r3c6,r4c2,r5c8,r6c5,r7c7,r8c4,r9c1
9:r1c6,r2c7,r3c2,r4c8,r5c4,r6c3,r7c5,r8c1,r9c9

is this check the compatibility of size 2 combinations with all other size 2 combinations. { naturally makes a size 4} if they cannot its removed from the size 2 list. { guessing here}

[P.O.]

I'm checking the combinations with the current possible templates for each value.
To be part of the solution, an instance of the combination (5 9) must be compatible with at least one template for each value (1 2 3 4 6 7 8).
This is the case for only 2 of the instances.
consider the first (5 9) instance: .....9..5..5...9...9...5....5.....9....9...5...9.5........9.5..9..5.....5.......9
which corresponds to the cells: (6 9 12 16 20 24 29 35 40 44 48 50 59 61 64 67 73 81)
It is not compatible with either of the two templates for value 1.
it shares cell 67 with the first one and cell 40 with the second one, and therefore this instance (5 9) cannot form an instance (1 5 9)
The same verification applies to the other instances, resulting in the following:

(6 9 12 16 20 24 29 35 40 44 48 50 59 61 64 67 73 81) no compatible with value 1 67 / 40
(6 9 12 16 20 24 29 35 39 44 49 50 59 61 64 67 73 81) compatible with all values
(4 9 12 16 20 24 29 35 39 44 50 51 59 61 64 67 73 81) no compatible with value 2 50 / 51
(6 9 12 16 20 24 29 35 40 44 48 49 59 61 64 68 73 81) no compatible with value 8 48 / 49
(4 9 12 16 20 24 29 35 39 44 49 51 59 61 64 68 73 81) compatible with all values