SO业务编排>> sudoku>> 返回
项目作者： stronka

项目描述 ：
A heuristic based sudoku solver
高级语言： Python
项目地址: git://github.com/stronka/sudoku.git
创建时间： 2021-05-24T14:36:47Z
项目社区：https://github.com/stronka/sudoku
开源协议：GNU General Public License v3.0
下载


sudoku

A heuristic based sudoku solver

This is a simple python sudoku solver. It employs heuristic based approach for solving sudoku.
Heuristics may be implemented and configured independently in a plugin manner.

Installation

  1. python -m pip install git+git://github.com/stronka/sudoku.git

Usage

You can use sudoku from commandline. Currently it is possible to read input sudoku from a json file.

Basic usage :

  1. python -m sudoku -o path/to/file.json

Input file should look like this:

  1. {
  2.   "sudoku": [
  3.     [0, 0, 2,    0, 0, 0,   0, 0, 8],
  4.     [0, 5, 0,    0, 0, 0,   7, 0, 0],
  5.     [4, 0, 0,    0, 0, 1,   6, 3, 0],
  7.     [0, 0, 0,    4, 0, 0,   3, 7, 2],
  8.     [0, 0, 0,    9, 0, 3,   0, 0, 0],
  9.     [1, 2, 3,    0, 0, 6,   0, 0, 0],
  11.     [0, 8, 9,    5, 0, 0,   0, 0, 4],
  12.     [0, 0, 5,    0, 0, 0,   0, 9, 0],
  13.     [2, 0, 0,    0, 0, 0,   5, 0, 0]
  14.   ]
  15. }

Solver can be served to provide REST endpoint /sudoku/solve:

  1. python -m sudoku --serve

Example call using cURL:

  1. curl -X POST -H "Content-Type: application/json" -d @input.json http://localhost:5000/sudoku/solve

Please note that server mode is still work in progress.

For more help on CLI:

  1. python -m sudoku -h

You can also use solver in your own code:

  1. from sudoku.logic import solve_sudoku
  2. import numpy
  5. data = numpy.array([...])
  6. result = solve_sudoku(data)

Solution querying:

You can query the solution for explanation on given cells or number:

  1. $ python -m sudoku -io --query "cell == (0, 1) or (cell[1] == 1 and \"1\" in action)" sudoku92.json
  2. Input sudoku:
  3. array([[2, 0, 9, 0, 0, 0, 8, 0, 6],
  4.        [0, 0, 5, 1, 0, 4, 3, 0, 0],
  5.        [0, 0, 6, 0, 0, 0, 5, 0, 0],
  6.        [3, 0, 0, 7, 0, 5, 0, 0, 4],
  7.        [0, 0, 0, 4, 0, 6, 0, 0, 0],
  8.        [5, 0, 0, 2, 0, 9, 0, 0, 3],
  9.        [0, 0, 3, 0, 0, 0, 9, 0, 0],
  10.        [0, 0, 1, 3, 0, 7, 4, 0, 0],
  11.        [9, 0, 2, 0, 0, 0, 7, 0, 5]])
  12. Solution:
  13. array([[2, 1, 9, 5, 7, 3, 8, 4, 6],
  14.        [8, 7, 5, 1, 6, 4, 3, 2, 9],
  15.        [4, 3, 6, 9, 2, 8, 5, 1, 7],
  16.        [3, 2, 8, 7, 1, 5, 6, 9, 4],
  17.        [1, 9, 7, 4, 3, 6, 2, 5, 8],
  18.        [5, 6, 4, 2, 8, 9, 1, 7, 3],
  19.        [7, 4, 3, 8, 5, 2, 9, 6, 1],
  20.        [6, 5, 1, 3, 9, 7, 4, 8, 2],
  21.        [9, 8, 2, 6, 4, 1, 7, 3, 5]])
  22. Solution query result:
  23. [{'action': 'Remove: 2', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 2 present in cell (0, 0)'},
  24.  {'action': 'Remove: 9', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 9 present in cell (0, 2)'},
  25.  {'action': 'Remove: 8', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 8 present in cell (0, 6)'},
  26.  {'action': 'Remove: 6', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 6 present in cell (0, 8)'},
  27.  {'action': 'Remove: 5', 'cell': (0, 1), 'reason': 'Candidate elimination: present in box. Number 5 present in cell (1, 2)'},
  28.  {'action': 'Remove: 1', 'cell': (1, 1), 'reason': 'Candidate elimination: present in row. Number 1 present in cell (1, 3)'},
  29.  {'action': 'Remove: 1', 'cell': (7, 1), 'reason': 'Candidate elimination: present in row. Number 1 present in cell (7, 2)'},
  30.  {'action': 'Remove: 1', 'cell': (6, 1), 'reason': 'Candidate elimination: present in box. Number 1 present in cell (7, 2)'},
  31.  {'action': 'Remove: 1', 'cell': (8, 1), 'reason': 'Candidate elimination: present in box. Number 1 present in cell (7, 2)'},
  32.  {'action': 'Remove: 1', 'cell': (3, 1), 'reason': 'Annotated pairs: (9, 2) pair in cells (3, 1) and (4, 1)'},
  33.  {'action': 'Remove: 1', 'cell': (4, 1), 'reason': 'Annotated pairs: (9, 2) pair in cells (3, 1) and (4, 1)'},
  34.  {'action': 'Remove: 3', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 3 present in cell (0, 5)'},
  35.  {'action': 'Remove 1', 'cell': (2, 1), 'reason': 'Last position in row: Cell (2, 1) is last possible location for number 3'},
  36.  {'action': 'Remove: 7', 'cell': (0, 1), 'reason': 'Candidate elimination: present in row. Number 7 present in cell (0, 4)'},
  37.  {'action': 'Remove: 1', 'cell': (5, 1), 'reason': 'Candidate elimination: present in box. Number 1 present in cell (4, 0)'},
  38.  {'action': 'Remove 4', 'cell': (0, 1), 'reason': 'Last position in column: Cell (0, 1) is last possible location for number 1'},
  39.  {'action': 'Fill: 1', 'cell': (0, 1), 'reason': 'Number 1 is the last possible candidate in cell (0, 1)'}]

Example queries with explanation:

Get solution for cell 0, 0 (top left):

  1. python -m sudoku --query "cell == (0, 0)" resources/sudoku.json

Get solution for cells 0, 0 and cell 8, 8 (bottom right):

  1. python -m sudoku --query "cell == (0, 0) or cell == (8, 8)" resources/sudoku.json

All actions on number one:

  1. python -m sudoku --query "\"1\" in action" resources/sudoku.json

All actions performed by elimination heuristic:

  1. python -m sudoku --query "\"elimination\" in reason" resources/sudoku.json

Querying in your own python code:

  1. import numpy
  2. from pprint import pprint
  4. from sudoku.logic import solve_sudoku
  5. from sudoku.logic.meta.solution_log import SolutionLog
  8. data = numpy.array([...])
  9. solution = SolutionLog()
  10. result = solve_sudoku(data, solution)
  12. pprint(solution.where.query("cell == (0, 0").get_steps())
  14. complex_query = solution\
  15.     .where\
  16.     .query('cell == (1, 1)')\
  17.     .query('"elimination" in reason')\
  18.     .query('"1" in action or "2" in action')
  20. pprint(complex_query.get_steps())

TODO:

  • Make solver configurable

In the future

  • Add web API