Skip to main content

Sudoku generator and solver with a step-by-step guidance

Project description

Build Status Coverage Status Checked with mypy PyPI Package latest release PyPI Wheel Supported versions GPLv3 License

Sudoku generator and solver with a step-by-step guidance

Installation

pip install dokusan

Quickstart

Sudoku Solvers

Step-by-step solver

This solver tries to solve sudoku using human-like strategies. Currently following techniques are supported:

  • Naked/Hidden singles
  • Naked Pairs/Triplets
  • Locked Candidate
  • XY-Wing
  • Unique Rectangle

For example to see all techniques that sudoku has:

from dokusan import solvers
from dokusan.boards import BoxSize, Sudoku


sudoku = Sudoku.from_list(
    [
        [0, 0, 0, 0, 9, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 2, 3, 0, 0],
        [0, 0, 7, 0, 0, 1, 8, 2, 5],
        [6, 0, 4, 0, 3, 8, 9, 0, 0],
        [8, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 9, 0, 0, 0, 0, 0, 8],
        [1, 7, 0, 0, 0, 0, 6, 0, 0],
        [9, 0, 0, 0, 1, 0, 7, 4, 3],
        [4, 0, 3, 0, 6, 0, 0, 0, 1],
    ],
    box_size=BoxSize(3, 3),
)

{step.combination.name for step in solvers.steps(sudoku)}

Backtracking-based solver

This solver is based on backtracking algorithm, however slightly modified to work fast

from dokusan import solvers, renderers
from dokusan.boards import BoxSize, Sudoku


sudoku = Sudoku.from_list(
    [
        [0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 3, 0, 8, 5],
        [0, 0, 1, 0, 2, 0, 0, 0, 0],
        [0, 0, 0, 5, 0, 7, 0, 0, 0],
        [0, 0, 4, 0, 0, 0, 1, 0, 0],
        [0, 9, 0, 0, 0, 0, 0, 0, 0],
        [5, 0, 0, 0, 0, 0, 0, 7, 3],
        [0, 0, 2, 0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 4, 0, 0, 0, 9],
    ],
    box_size=BoxSize(3, 3),
)

solution = solvers.backtrack(sudoku)
print(renderers.colorful(solution))

Sudoku Generator

Generator algorithm is mainly based on article by Daniel Beer. The average time to generate Sudoku with rank of 150 is 700ms.

To generate a new sudoku:

from dokusan import generators, renderers


sudoku = generators.random_sudoku(avg_rank=150)
print(renderers.colorful(sudoku))

Ranking and Sudoku difficulty

avg_rank option roughly defines the difficulty of the sudoku. Sudoku with rank lower than 100 contains only naked/hidden singles. Sudoku with rank greater than 150 contains Naked Subsets/Locked Candidate/XY Wing/etc…, however this is not always guaranteed.

For higher ranks it is also not guaranteed that generated Sudoku rank will be higher than provided avg_rank, so to ensure sudoku has desired rank one can do the following:

from dokusan import generators, stats


avg_rank = 450
while stats.rank(sudoku := generators.random_sudoku(avg_rank)) < avg_rank:
    continue

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for dokusan, version 0.1.0a6
Filename, size File type Python version Upload date Hashes
Filename, size dokusan-0.1.0a6-py3-none-any.whl (22.6 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size dokusan-0.1.0a6.tar.gz (22.1 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page