https://github.com/konstin/sudoku-in-python-packaging

Skip to content

Navigation Menu

Toggle navigation
 
Sign in

  * Product
      +  
        GitHub Copilot
        Write better code with AI
      +  
        Security
        Find and fix vulnerabilities
      +  
        Actions
        Automate any workflow
      +  
        Codespaces
        Instant dev environments
      +  
        Issues
        Plan and track work
      +  
        Code Review
        Manage code changes
      +  
        Discussions
        Collaborate outside of code
      +  
        Code Search
        Find more, search less
    Explore
      + All features
      + Documentation
      + GitHub Skills
      + Blog
  * Solutions
    By company size
      + Enterprises
      + Small and medium teams
      + Startups
    By use case
      + DevSecOps
      + DevOps
      + CI/CD
      + View all use cases
    By industry
      + Healthcare
      + Financial services
      + Manufacturing
      + Government
      + View all industries
    View all solutions
  * Resources
    Topics
      + AI
      + DevOps
      + Security
      + Software Development
      + View all
    Explore
      + Learning Pathways
      + White papers, Ebooks, Webinars
      + Customer Stories
      + Partners
  * Open Source
      +  
        GitHub Sponsors
        Fund open source developers
      +  
        The ReadME Project
        GitHub community articles
    Repositories
      + Topics
      + Trending
      + Collections
  * Enterprise
      +  
        Enterprise platform
        AI-powered developer platform
    Available add-ons
      +  
        Advanced Security
        Enterprise-grade security features
      +  
        GitHub Copilot
        Enterprise-grade AI features
      +  
        Premium Support
        Enterprise-grade 24/7 support
  * Pricing

Search or jump to...

Search code, repositories, users, issues, pull requests...

Search
[                    ]
Clear

Search syntax tips

Provide feedback

We read every piece of feedback, and take your input very seriously.

[                    ] [ ] Include my email address so I can be
contacted
Cancel Submit feedback

Saved searches

Use saved searches to filter your results more quickly

Name [                    ] 
Query [                    ]

To see all available qualifiers, see our documentation.

Cancel Create saved search
Sign in
Sign up Reseting focus
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session. You switched accounts on another tab or window. Reload
to refresh your session. Dismiss alert
{{ message }}
konstin / sudoku-in-python-packaging Public

  * Notifications You must be signed in to change notification
    settings
  * Fork 0
  * Star 305

Sudoku solving in python packaging

305 stars 0 forks Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

  * Code
  * Issues 0
  * Pull requests 0
  * Actions
  * Projects 0
  * Security
  * Insights

Additional navigation options

  * Code
  * Issues
  * Pull requests
  * Actions
  * Projects
  * Security
  * Insights

konstin/sudoku-in-python-packaging

 main
BranchesTags
  
Go to file
Code

Folders and files

                                               Last commit    Last
         Name                    Name            message     commit
                                                              date
Latest commit

 

History

4 Commits
 
packages                packages                            
Readme.md               Readme.md                           
csv_to_requirements.py  csv_to_requirements.py              
generate_packages.py    generate_packages.py                
pyproject.toml          pyproject.toml                      
render_solution.py      render_solution.py                  
requirements.in         requirements.in                     
requirements.txt        requirements.txt                    
royle.csv               royle.csv                           
royle.in                royle.in                            
sudoku.csv              sudoku.csv                          
View all files

Repository files navigation

  * README

Sudoku in python packaging

 

Solve sudokus not in python, but in python packages.

Solving the versions of python package from your requirements is
NP-complete, in the worst case it runs exponentially slow. Sudokus
are also NP-complete, which means we can solve sudokus with python
packaging.

Each cell in the sudoku grid is a package sudoku_{x}_{y} (0 indexed),
and the version (1-9) is the value in the field, so you can write a
pyproject.toml and the installed packages are the solution.

[project]
name = "sudoku"
version = "1.0.0"
dependencies = [
    "sudoku_3_1 == 2",
    "sudoku_5_7 == 6",
    "sudoku_0_7 == 5"
    ...
]

Usage

 

You can write the sudoku as csv:

5,3,_,_,7,_,_,_,_
6,_,_,1,9,5,_,_,_
_,9,8,_,_,_,_,6,_
8,_,_,_,6,_,_,_,3
4,_,_,8,_,3,_,_,1
7,_,_,_,2,_,_,_,6
_,6,_,_,_,_,2,8,_
_,_,_,4,1,9,_,_,5
_,_,_,_,8,_,_,7,9

Convert it to requirements:

python csv_to_requirements.py sudoku.csv requirements.in

sudoku_0_0 == 5
sudoku_1_0 == 3
[...]
sudoku_7_8 == 7
sudoku_8_8 == 9

Solve it with your favourite package manager, e.g:

uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txt

or (slow)

pip-compile --find-links packages/ --no-annotate --no-header requirements.in -o requirements.txt

sudoku-0-0==5
sudoku-0-1==6
sudoku-0-2==1
sudoku-0-3==8
sudoku-0-4==4
[...]

Render the solution:

python render_solution.py requirements.txt

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

Or as a oneliner:

$ python csv_to_requirements.py royle.csv - | uv pip compile --find-links packages/ --no-annotate --no-header - | python render_solution.py -
Resolved 81 packages in 126ms
5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9

Benchmark

 

$ hyperfine --warmup 5 "uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in"
Benchmark 1: uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in
  Time (mean +- s):      29.7 ms +-   1.6 ms    [User: 29.9 ms, System: 21.0 ms]
  Range (min ... max):    27.5 ms ...  35.0 ms    97 runs

The walltime didn't vary much between the sudokus i tried.

While dependency resolution is NP-complete and their backing
algorithm is usually some form of SAT solver, in reality the problem
space is much smaller: packages usually depend on a single range of
another package, and that range usually increasing monotonically. You
almost never run into an exponential case, most resolution in python
can be done without even backtracking. The performance bottleneck is
instead fetching and parsing metadata, and for python specifically
building source distributions.

About

Sudoku solving in python packaging

Resources

Readme
Activity

Stars

305 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages 0

No packages published

Languages

  * Python 100.0%

Footer

 (c) 2024 GitHub, Inc.

Footer navigation

  * Terms
  * Privacy
  * Security
  * Status
  * Docs
  * Contact
  * Manage cookies
  * Do not share my personal information

You can't perform that action at this time.