morvanzhou / sudoku

A simple Sudoku generator and solver. 数独生成器和解题器

A Sudoku generator and solver

This is a Sudoku game written in python, default to use Wave Function Collapse method.

Install

pip install sudokum

Generation

A sudoku can be generated with a mask_rate. A full solution is generated when passing mask_rate=0.

import sudokum

g = sudokum.generate(mask_rate=0.7)
print(g)
"""
[[1 0 0 5 0 0 0 0 3]
 [0 3 7 0 0 1 0 0 4]
 [0 0 0 0 0 2 0 0 0]
 [0 0 0 0 9 4 0 0 0]
 [0 0 4 0 0 0 0 3 2]
 [0 0 0 3 2 5 0 0 0]
 [0 0 0 0 0 0 2 0 0]
 [7 4 0 0 0 0 0 0 0]
 [8 0 0 0 0 3 1 0 0]]
"""

To visualize the generating procedure, I have made a GUI for animating Wave Function Collapse in sudoku generation.

import sudokum

sudokum.display_wfc()

Or you can get you hand on it by running following code.

import sudokum

sudokum.display_wfc(human=True)

Solving

By using sudokum.solve() function, it tries to solve the puzzle.

import sudokum

g = sudokum.generate(mask_rate=0.7)
s = sudokum.solve(g)
print(s)
"""
[[1 2 8 5 4 7 6 9 3]
 [6 3 7 9 8 1 5 2 4]
 [4 9 5 6 3 2 7 1 8]
 [2 1 3 7 9 4 8 5 6]
 [5 7 4 1 6 8 9 3 2]
 [9 8 6 3 2 5 4 7 1]
 [3 5 1 4 7 6 2 8 9]
 [7 4 2 8 1 9 3 6 5]
 [8 6 9 2 5 3 1 4 7]]
"""

A solving max try number (default to 10) can set as following:

import sudokum

s = sudokum.solve(g, max_try=3)

Manually check solution

If you have your own solution, you can validate it by following function:

import sudokum

ok, position_of_problems = sudokum.check(g)

More Example

More use cases can be found in my test files.

sudoku's Issues

怎么运行？

The generator can produce invalid grids

Hi.

I was looking for a Python lib that would provide me with a sudoku grid generator,
and I tested yours.

The issue is that it can produces unsolvable grids.

Because :

• the grid is generated simply by applying a random mask, not ensuring it has a solution:
  https://github.com/MorvanZhou/sudoku/blob/master/sudoku.py#L25
• your check_solution function does not ensure there is a unique deductible solution.
  By setting the mask_rate to 0.9 the script generates unsolvable grids but still prints Checked: OK

I only wish to share share my findings.
It is very nice of you to share your code on GitHub, please do not take this as negative critiscim.

Kind regards

There is no license applied to the project

Please let us use your work for our own projects and choose an open source license :)
It's easy with GitHub!

License?

Hi!

I spent some time last night searching through the internet for code that will create a puzzle board. Yours is by FAR the best I've found. It's compact and it works without modification.

I have used your generate_puzzle function in my code and want to make sure that I'm abiding by your licensing wishes. Is it OK to include as part of my project's Demo Programs? My code is LGPL3.

I have included a link to your project in the header comments and would like to include a little more. If you have something you would like added specifically, please let me know.

Thank you for your hard work on this!

My PySimpleGUI project homepage:
http://www.PySimpleGUI.com

I'm including my application code below since it's so short.

It produces this window:

Clicking the Solve button at the moment simply fills in your solved puzzle. I'll add "score checking" at some point. The goal of Demo Programs is to show how to build the basics of programs. They are purposefully lacking in features as the goal is to help people build the framework as a starting point.

import PySimpleGUI as sg, random
import numpy as np

"""
    Sudoku Puzzle Demo
    
    How to easily generate a Sudoku puzzle window.  It can be done in ONE line of code.
    Code to generate a playable puzzle was supplied from:
    https://github.com/MorvanZhou/sudoku
    
    Copyright 2020 PySimpleGUI.com
    
"""
def generate_sudoku(mask_rate=0.5):
    while True:
        n = 9
        m = np.zeros((n, n), np.int)
        rg = np.arange(1, n + 1)
        m[0, :] = np.random.choice(rg, n, replace=False)
        try:
            for r in range(1, n):
                for c in range(n):
                    col_rest = np.setdiff1d(rg, m[:r, c])
                    row_rest = np.setdiff1d(rg, m[r, :c])
                    avb1 = np.intersect1d(col_rest, row_rest)
                    sub_r, sub_c = r//3, c//3
                    avb2 = np.setdiff1d(np.arange(0, n+1), m[sub_r*3:(sub_r+1)*3, sub_c*3:(sub_c+1)*3].ravel())
                    avb = np.intersect1d(avb1, avb2)
                    m[r, c] = np.random.choice(avb, size=1)
            break
        except ValueError:
            pass
    mm = m.copy()
    mm[np.random.choice([True, False], size=m.shape, p=[mask_rate, 1 - mask_rate])] = 0
    return mm, m


def main():
    puzzle, solution = generate_sudoku(mask_rate=0.7)

    window = sg.Window('Sudoku', [[sg.Frame('', [[sg.I(random.randint(1,9), justification='r', size=(3,1), key=(fr*3+r,fc*3+c)) for c in range(3)] for r in range(3)]) for fc in range(3)] for fr in range(3)] +[[sg.B('Solve')]], finalize=True)

    for r, row in enumerate(puzzle):
        for c, col in enumerate(row):
            window[r,c].update(puzzle[r][c] if puzzle[r][c] else '')

    while True:
        event, values = window.read()
        if event is None:
            break
        if event == 'Solve':
            for r, row in enumerate(solution):
                for c, col in enumerate(row):
                    window[r, c].update(solution[r][c] if solution[r][c] else '')

    window.close()

if __name__ == "__main__":
    main()