The New Sudoku Players' Forum

[SunnieShine2]

Hello everyone!

I'm new here. I wonder how to generate a puzzle using a pattern that I just set. I just implemented one, but the speed is too slow... I found that a program called NP-Generator can generate about this, and was effective. I just took a look for that prorgam source code, but I couldn't understand the backing algorithm.

I want to learn for such generation algorithm. Could you please help me? Thank you!

[P.O.]

hi SunnieShine2, you might find some ideas there:
http://programmers.enjoysudoku.com/www.setbb.com/sudoku/viewforum8d2f.html?f=2&mforum=sudoku

[Serg]

Hi, SunnieShine2!
Do you want to generate some valid puzzles, having given pattern, or generate all such puzzles? If you want to find just some (not all) puzzles, the simplest way to do it - random puzzles generation. In any way it's better to make check - is your pattern subset of some known invalid pattern? If it is subset of known invalid pattern, it cannot have valid puzzles.

Generation of all possible valid puzzles (having given pattern) is complicated task, because such process is too slow w/o complications.

Serg

[SunnieShine2]

hi SunnieShine2, you might find some ideas there:
http://programmers.enjoysudoku.com/www.setbb.com/sudoku/viewforum8d2f.html?f=2&mforum=sudoku

Thanks for your reply! I'll visit this page to learn!

[SunnieShine2]

Hi, SunnieShine2!
Do you want to generate some valid puzzles, having given pattern, or generate all such puzzles? If you want to find just some (not all) puzzles, the simplest way to do it - random puzzles generation. In any way it's better to make check - is your pattern subset of some known invalid pattern? If it is subset of known invalid pattern, it cannot have valid puzzles.

Generation of all possible valid puzzles (having given pattern) is complicated task, because such process is too slow w/o complications.

Serg

Thanks! I just want to generate one randomly, not all possible grids. However I don't know which details I should do extra checks, so the performance seems to be not good. I want to learn more information about the checking such details.

[Serg]

Hi, SunnieShine2!
Please, post an example of pattern you analyze. I could advice you something for particular pattern.

Serg

[champagne]

Hello everyone!

I'm new here. I wonder how to generate a puzzle using a pattern that I just set. I just implemented one, but the speed is too slow... I found that a program called NP-Generator can generate about this, and was effective. I just took a look for that prorgam source code, but I couldn't understand the backing algorithm.

I want to learn for such generation algorithm. Could you please help me? Thank you!

This was the basis for the "pattern game", a popular active topic here for many years.

AFAIK, most players used mainly a vicinity search around seeds.
The game started with a valid puzzle for the pattern, but one easy way to add seeds on my side was to expand the pattern with a symmetry of givens (the pattern had always at last one symmetry)

[SunnieShine2]

Hi, SunnieShine2!
Please, post an example of pattern you analyze. I could advice you something for particular pattern.

Serg

Hello. Here's my example to be tested:

Code: Select all

r1c5, r2c46, r3c37, r4c28, r5c159, r6c14569, r7c23578, r8c5, r9c456


How can I dive into this pattern?

The source code:

Hidden Text: Show

Code: Select all

public readonly ref struct PatternBasedPuzzleGenerator(
    [PrimaryConstructorParameter(MemberKinds.Field)] ref readonly CellMap seedPattern,
    Digit missingDigit = -1
)
{
    public Grid Generate(IProgress<GeneratorProgress>? progress = null, CancellationToken cancellationToken = default)
    {
        var resultGrid = Grid.Undefined;
        try
        {
            var (playground, count, cellsOrdered) = (Grid.Empty, 0, OrderCellsViaConnectionComplexity());
            GenerateCore(cellsOrdered, ref playground, ref resultGrid, 0, ref count, progress, cancellationToken);
        }
        catch (OperationCanceledException)
        {
        }
        catch
        {
            throw;
        }

        return resultGrid;
    }

    private void GenerateCore(
        Cell[] patternCellsSorted,
        ref Grid playground,
        ref Grid resultGrid,
        int i,
        ref int count,
        IProgress<GeneratorProgress>? progress,
        CancellationToken cancellationToken
    )
    {
        if (i == patternCellsSorted.Length)
        {
            if (playground.FixedGrid is { Uniqueness: Uniqueness.Unique } result)
            {
                resultGrid = result;
                throw new OperationCanceledException("Finished.");
            }

            progress?.Report(new(count++));
            return;
        }

        var cell = patternCellsSorted[i];
        var digitsMask = playground.GetCandidates(cell);
        var digits = ((Mask)(missingDigit != -1 ? digitsMask & (Mask)~(1 << missingDigit) : digitsMask)).GetAllSets();
        var indexArray = Digits[..digits.Length];
        Random.Shared.Shuffle(indexArray);
        foreach (var randomizedIndex in indexArray)
        {
            playground.ReplaceDigit(cell, digits[randomizedIndex]);

            if (playground.FixedGrid.Uniqueness == Uniqueness.Bad)
            {
                playground.SetDigit(cell, -1);
                continue;
            }

            cancellationToken.ThrowIfCancellationRequested();

            GenerateCore(patternCellsSorted, ref playground, ref resultGrid, i + 1, ref count, progress, cancellationToken);
        }

        playground.SetDigit(cell, -1);
    }

    private Cell[] OrderCellsViaConnectionComplexity()
    {
        var (isOrdered, result) = ((CellMap)[], new Cell[_seedPattern.Count]);
        for (var index = 0; index < _seedPattern.Count; index++)
        {
            var (maxRating, best) = (0, -1);
            for (var i = 0; i < 81; i++)
            {
                if (!_seedPattern.Contains(i) || isOrdered.Contains(i))
                {
                    continue;
                }

                var rating = 0;
                for (var j = 0; j < 81; j++)
                {
                    if (!_seedPattern.Contains(j) || i == j)
                    {
                        continue;
                    }

                    if (i.ToHouseIndex(HouseType.Block) == j.ToHouseIndex(HouseType.Block)
                        || i.ToHouseIndex(HouseType.Row) == j.ToHouseIndex(HouseType.Row)
                        || i.ToHouseIndex(HouseType.Column) == j.ToHouseIndex(HouseType.Column))
                    {
                        rating += isOrdered.Contains(j) ? 10000 : 100;
                    }

                    if (!isOrdered.Contains(j)
                        && (i.ToBandIndex() == j.ToBandIndex() || i.ToTowerIndex() == j.ToTowerIndex())
                        && i.ToHouseIndex(HouseType.Block) == j.ToHouseIndex(HouseType.Block))
                    {
                        rating++;
                    }
                }

                if (maxRating < rating)
                {
                    (maxRating, best) = (rating, i);
                }
            }

            (_, result[index]) = (isOrdered.Add(best), best);
        }

        return result;
    }
}


[SunnieShine2]

Hello everyone!

I'm new here. I wonder how to generate a puzzle using a pattern that I just set. I just implemented one, but the speed is too slow... I found that a program called NP-Generator can generate about this, and was effective. I just took a look for that prorgam source code, but I couldn't understand the backing algorithm.

I want to learn for such generation algorithm. Could you please help me? Thank you!

This was the basis for the "pattern game", a popular active topic here for many years.

AFAIK, most players used mainly a vicinity search around seeds.
The game started with a valid puzzle for the pattern, but one easy way to add seeds on my side was to expand the pattern with a symmetry of givens (the pattern had always at last one symmetry)

Hi! I just took a look for that threads. Such patterns are really amazing!

However I used my application to generate puzzles based on such patterns, a puzzle may be generated very slow... I want to optimize my implementation but I have no ideas on this.

[m_b_metcalf]

How can I dive into this pattern?

This was produced by the simplest method: generate a solution grid and check whether the pattern corresponds to a valid puzzle (unique solution). For that you need a solver.

Code: Select all

  . . . . 9 . . . .
 . . . 1 . 2 . . .
 . . 4 . . . 3 . .
 . 1 . . . . . 4 .
 3 . . . 8 . . . 9
 2 . . 3 7 4 . . 8
 . 7 5 . 4 . 6 9 .
 . . . . 5 . . . .
 . . . 8 1 6 . . .

There are more, quite sophisticated, methods.

Regards,

Mike

[1to9only]

Hello everyone!

I'm new here. I wonder how to generate a puzzle using a pattern that I just set. I just implemented one, but the speed is too slow... I found that a program called NP-Generator can generate about this, and was effective. I just took a look for that prorgam source code, but I couldn't understand the backing algorithm.

I want to learn for such generation algorithm. Could you please help me? Thank you!

See this thread: http://forum.enjoysudoku.com/it-s-raining-get-the-umbrella-puzzle-solved-t35075.html

[Serg]

Hi, SunnieShine2!
Clue cells can be assigned to random candidate digits. Example below (valid puzzle) was found by less than 1 second.

Code: Select all

. . . . 7 . . . .
. . . 4 . 1 . . .
. . 3 . . . 2 . .
. 9 . . . . . 8 .
1 . . . 9 . . . 4
4 . . 1 5 3 . . 9
. 2 8 . 4 . 6 5 .
. . . . 8 . . . .
. . . 7 1 5 . . .

Serg

P.S. I used home-made program written in C. It calls JCZSolver - very fast Sudoku solver. If you want to speed up puzzles generation you probably should use C or C++ and embed into your program really fast solver.

[SunnieShine2]

Hi, SunnieShine2!
Clue cells can be assigned to random candidate digits. Example below (valid puzzle) was found by less than 1 second.

Code: Select all

. . . . 7 . . . .
. . . 4 . 1 . . .
. . 3 . . . 2 . .
. 9 . . . . . 8 .
1 . . . 9 . . . 4
4 . . 1 5 3 . . 9
. 2 8 . 4 . 6 5 .
. . . . 8 . . . .
. . . 7 1 5 . . .

Serg

P.S. I used home-made program written in C. It calls JCZSolver - very fast Sudoku solver. If you want to speed up puzzles generation you probably should use C or C++ and embed into your program really fast solver.

Hi! It seems that my solver is not good Many thanks! I'll adjust my backing solver logic to speed up.