grilops


Namegrilops JSON
Version 0.9.1 PyPI version JSON
download
home_pagehttps://github.com/obijywk/grilops
SummaryGRId LOgic Puzzle Solver
upload_time2021-01-14 02:21:48
maintainer
docs_urlNone
authorMatt Gruskin
requires_python>=3.6
licenseMIT
keywords
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # grilops

a GRId LOgic Puzzle Solver library, using Python 3 and
[z3](https://github.com/Z3Prover/z3).

This package contains a collection of libraries and helper functions that are
useful for solving and checking
[Nikoli](https://en.wikipedia.org/wiki/Nikoli_(publisher))-style logic puzzles
using z3.

To get a feel for how to use this package to model and solve puzzles, try
working through the [tutorial IPython
notebook](https://github.com/obijywk/grilops/blob/master/examples/tutorial.ipynb),
and refer to the
[examples](https://github.com/obijywk/grilops/tree/master/examples) and the
[API Documentation](https://obijywk.github.io/grilops/).

## Installation

grilops requires Python 3.6 or later.

To install grilops for use in your own programs:

```
$ pip3 install grilops
```

To install the source code (to run the examples and/or work with the code):

```
$ git clone https://github.com/obijywk/grilops.git
$ cd grilops
$ pip3 install -e .
```

## Basic Concepts and Usage

The `symbols`, `geometry`, and `grids` modules contain the core functionality
needed for modeling most puzzles. For convenience, their attributes can be
accessed directly from the top-level `grilops` module.

Symbols represent the marks that are determined and written into a grid by a
solver while solving a puzzle. For example, the symbol set of a
[Sudoku](https://en.wikipedia.org/wiki/Sudoku) puzzle would be the digits 1
through 9. The symbol set of a binary determination puzzle such as
[Nurikabe](https://en.wikipedia.org/wiki/Nurikabe_(puzzle)) could contain two
symbols, one representing a black cell and the other representing a white cell.

The geometry module defines Lattice classes that are used to manage the shapes
of grids and relationships between cells. Rectangular and hexagonal grids are
supported, as well as grids with empty spaces in them.

A symbol grid is used to keep track of the assignment of symbols to grid
cells. Generally, setting up a program to solve a puzzle using grilops involves:

* Constructing a symbol set
* Constructing a lattice for the grid
* Constructing a symbol grid in the shape of the lattice, limited to contain
  symbols from the symbol set
* Adding puzzle-specific constraints to cells in the symbol grid
* Checking for satisfying assignments of symbols to symbol grid cells

Grid cells are exposed as z3 constants, so built-in z3 operators can and should
be used when adding puzzle-specific constraints. In addition, grilops provides
several modules to help automate and abstract away the introduction of common
kinds of constraints.

### Loops

The `grilops.loops` module is helpful for adding constraints that ensure symbols
connect to form closed loops. Some examples of puzzle types for which this is
useful are [Masyu](https://en.wikipedia.org/wiki/Masyu) and
[Slitherlink](https://en.wikipedia.org/wiki/Slitherlink).

~~~~
$ python3 examples/masyu.py             $ python3 examples/slitherlink.py 
 ┌───┐┌──┐                              ┌──┐                              
┌┘ ┌─┘└─┐│                              │┌┐│ ┌┐                           
└─┐│┌──┐││                              └┘│└┐││                           
  │││┌─┘││                                │ └┘│                           
┌─┘└┘│ ┌┘│                                └┐  │                           
│┌──┐│ │┌┘                              ┌──┘┌┐│                           
││┌─┘└─┘└┐                              └───┘└┘                           
│││ ┌───┐│                                                                
└┘│ │┌──┘│                              Unique solution
  └─┘└───┘

Unique solution
~~~~

### Regions

The `grilops.regions` module is helpful for adding constraints that ensure
cells are grouped into orthogonally contiguous regions (polyominos) of variable
shapes and sizes. Some examples of puzzle types for which this is useful are
[Nurikabe](https://en.wikipedia.org/wiki/Nurikabe_(puzzle)) and
[Fillomino](https://en.wikipedia.org/wiki/Fillomino).

~~~~
$ python3 examples/nurikabe.py          $ python3 examples/fillomino.py 
2 █   ██ 2                              8 8 3 3 101010105               
███  █2███                              8 8 8 3 1010105 5               
█2█ 7█ █ █                              3 3 8 10104 4 4 5               
█ ██████ █                              1 3 8 3 102 2 4 5               
██ █  3█3█                              2 2 8 3 3 1 3 2 2               
 █2████3██                              6 6 2 2 1 3 3 1 3               
2██4 █  █                               6 4 4 4 2 2 1 3 3               
██  █████                               6 4 2 2 4 3 3 4 4               
█1███ 2█4                               6 6 4 4 4 1 3 4 4               

Unique solution                         Unique solution
~~~~

### Shapes

The `grilops.shapes` module is helpful for adding constraints that ensure
cells are grouped into orthogonally contiguous regions (polyominos) of fixed
shapes and sizes. Some examples of puzzle types for which this is useful are
[Battleship](https://en.wikipedia.org/wiki/Battleship_(puzzle)) and
[LITS](https://en.wikipedia.org/wiki/LITS).

~~~~
$ python3 examples/battleship.py        $ python3 examples/lits.py
     ▴                                        IIII
◂▪▸  ▪ •                                   SS  L  
     ▾                                   LSS   L I
◂▪▪▸   •                                 L IIIILLI
                                         LL   L  I
 ▴    ◂▸                                  TTT L  I
 ▾ ▴                                    SS T LL  T
   ▾ •                                   SSLL   TT
                                            L T  T
Unique solution                         IIIILTTT

                                        Unique solution
~~~~

### Sightlines

The `grilops.sightlines` module is helpful for adding constraints that ensure
properties hold along straight lines through the grid. These "sightlines" may
terminate before reaching the edge of the grid if certain conditions are met
(e.g. if a certain symbol, such as one representing a wall, is
encountered). Some examples of puzzle types for which this is useful are
[Akari](https://en.wikipedia.org/wiki/Light_Up_(puzzle)) and
[Skyscraper](https://www.puzzlemix.com/Skyscraper).

~~~~
$ python3 examples/akari.py             $ python3 examples/skyscraper.py 
█* █*    █                              23541                            
   *   █                                15432                            
*█*   █  *                              34215                            
 *█  █   █                              42153                            
   ███*                                 51324                            
   *███*                                                                 
█ * █* █*                               Unique solution
*  █*   █*
  █     * 
█ *   █* █

Unique solution
~~~~



            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/obijywk/grilops",
    "name": "grilops",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.6",
    "maintainer_email": "",
    "keywords": "",
    "author": "Matt Gruskin",
    "author_email": "matthew.gruskin@gmail.com",
    "download_url": "https://files.pythonhosted.org/packages/28/8c/b4506047e6ec04c39c4099c3e62013be078649c356a417ad76a5f549fd01/grilops-0.9.1.tar.gz",
    "platform": "",
    "description": "# grilops\n\na GRId LOgic Puzzle Solver library, using Python 3 and\n[z3](https://github.com/Z3Prover/z3).\n\nThis package contains a collection of libraries and helper functions that are\nuseful for solving and checking\n[Nikoli](https://en.wikipedia.org/wiki/Nikoli_(publisher))-style logic puzzles\nusing z3.\n\nTo get a feel for how to use this package to model and solve puzzles, try\nworking through the [tutorial IPython\nnotebook](https://github.com/obijywk/grilops/blob/master/examples/tutorial.ipynb),\nand refer to the\n[examples](https://github.com/obijywk/grilops/tree/master/examples) and the\n[API Documentation](https://obijywk.github.io/grilops/).\n\n## Installation\n\ngrilops requires Python 3.6 or later.\n\nTo install grilops for use in your own programs:\n\n```\n$ pip3 install grilops\n```\n\nTo install the source code (to run the examples and/or work with the code):\n\n```\n$ git clone https://github.com/obijywk/grilops.git\n$ cd grilops\n$ pip3 install -e .\n```\n\n## Basic Concepts and Usage\n\nThe `symbols`, `geometry`, and `grids` modules contain the core functionality\nneeded for modeling most puzzles. For convenience, their attributes can be\naccessed directly from the top-level `grilops` module.\n\nSymbols represent the marks that are determined and written into a grid by a\nsolver while solving a puzzle. For example, the symbol set of a\n[Sudoku](https://en.wikipedia.org/wiki/Sudoku) puzzle would be the digits 1\nthrough 9. The symbol set of a binary determination puzzle such as\n[Nurikabe](https://en.wikipedia.org/wiki/Nurikabe_(puzzle)) could contain two\nsymbols, one representing a black cell and the other representing a white cell.\n\nThe geometry module defines Lattice classes that are used to manage the shapes\nof grids and relationships between cells. Rectangular and hexagonal grids are\nsupported, as well as grids with empty spaces in them.\n\nA symbol grid is used to keep track of the assignment of symbols to grid\ncells. Generally, setting up a program to solve a puzzle using grilops involves:\n\n* Constructing a symbol set\n* Constructing a lattice for the grid\n* Constructing a symbol grid in the shape of the lattice, limited to contain\n  symbols from the symbol set\n* Adding puzzle-specific constraints to cells in the symbol grid\n* Checking for satisfying assignments of symbols to symbol grid cells\n\nGrid cells are exposed as z3 constants, so built-in z3 operators can and should\nbe used when adding puzzle-specific constraints. In addition, grilops provides\nseveral modules to help automate and abstract away the introduction of common\nkinds of constraints.\n\n### Loops\n\nThe `grilops.loops` module is helpful for adding constraints that ensure symbols\nconnect to form closed loops. Some examples of puzzle types for which this is\nuseful are [Masyu](https://en.wikipedia.org/wiki/Masyu) and\n[Slitherlink](https://en.wikipedia.org/wiki/Slitherlink).\n\n~~~~\n$ python3 examples/masyu.py             $ python3 examples/slitherlink.py \n \u250c\u2500\u2500\u2500\u2510\u250c\u2500\u2500\u2510                              \u250c\u2500\u2500\u2510                              \n\u250c\u2518 \u250c\u2500\u2518\u2514\u2500\u2510\u2502                              \u2502\u250c\u2510\u2502 \u250c\u2510                           \n\u2514\u2500\u2510\u2502\u250c\u2500\u2500\u2510\u2502\u2502                              \u2514\u2518\u2502\u2514\u2510\u2502\u2502                           \n  \u2502\u2502\u2502\u250c\u2500\u2518\u2502\u2502                                \u2502 \u2514\u2518\u2502                           \n\u250c\u2500\u2518\u2514\u2518\u2502 \u250c\u2518\u2502                                \u2514\u2510  \u2502                           \n\u2502\u250c\u2500\u2500\u2510\u2502 \u2502\u250c\u2518                              \u250c\u2500\u2500\u2518\u250c\u2510\u2502                           \n\u2502\u2502\u250c\u2500\u2518\u2514\u2500\u2518\u2514\u2510                              \u2514\u2500\u2500\u2500\u2518\u2514\u2518                           \n\u2502\u2502\u2502 \u250c\u2500\u2500\u2500\u2510\u2502                                                                \n\u2514\u2518\u2502 \u2502\u250c\u2500\u2500\u2518\u2502                              Unique solution\n  \u2514\u2500\u2518\u2514\u2500\u2500\u2500\u2518\n\nUnique solution\n~~~~\n\n### Regions\n\nThe `grilops.regions` module is helpful for adding constraints that ensure\ncells are grouped into orthogonally contiguous regions (polyominos) of variable\nshapes and sizes. Some examples of puzzle types for which this is useful are\n[Nurikabe](https://en.wikipedia.org/wiki/Nurikabe_(puzzle)) and\n[Fillomino](https://en.wikipedia.org/wiki/Fillomino).\n\n~~~~\n$ python3 examples/nurikabe.py          $ python3 examples/fillomino.py \n2 \u2588   \u2588\u2588 2                              8 8 3 3 101010105               \n\u2588\u2588\u2588  \u25882\u2588\u2588\u2588                              8 8 8 3 1010105 5               \n\u25882\u2588 7\u2588 \u2588 \u2588                              3 3 8 10104 4 4 5               \n\u2588 \u2588\u2588\u2588\u2588\u2588\u2588 \u2588                              1 3 8 3 102 2 4 5               \n\u2588\u2588 \u2588  3\u25883\u2588                              2 2 8 3 3 1 3 2 2               \n \u25882\u2588\u2588\u2588\u25883\u2588\u2588                              6 6 2 2 1 3 3 1 3               \n2\u2588\u25884 \u2588  \u2588                               6 4 4 4 2 2 1 3 3               \n\u2588\u2588  \u2588\u2588\u2588\u2588\u2588                               6 4 2 2 4 3 3 4 4               \n\u25881\u2588\u2588\u2588 2\u25884                               6 6 4 4 4 1 3 4 4               \n\nUnique solution                         Unique solution\n~~~~\n\n### Shapes\n\nThe `grilops.shapes` module is helpful for adding constraints that ensure\ncells are grouped into orthogonally contiguous regions (polyominos) of fixed\nshapes and sizes. Some examples of puzzle types for which this is useful are\n[Battleship](https://en.wikipedia.org/wiki/Battleship_(puzzle)) and\n[LITS](https://en.wikipedia.org/wiki/LITS).\n\n~~~~\n$ python3 examples/battleship.py        $ python3 examples/lits.py\n     \u25b4                                        IIII\n\u25c2\u25aa\u25b8  \u25aa \u2022                                   SS  L  \n     \u25be                                   LSS   L I\n\u25c2\u25aa\u25aa\u25b8   \u2022                                 L IIIILLI\n                                         LL   L  I\n \u25b4    \u25c2\u25b8                                  TTT L  I\n \u25be \u25b4                                    SS T LL  T\n   \u25be \u2022                                   SSLL   TT\n                                            L T  T\nUnique solution                         IIIILTTT\n\n                                        Unique solution\n~~~~\n\n### Sightlines\n\nThe `grilops.sightlines` module is helpful for adding constraints that ensure\nproperties hold along straight lines through the grid. These \"sightlines\" may\nterminate before reaching the edge of the grid if certain conditions are met\n(e.g. if a certain symbol, such as one representing a wall, is\nencountered). Some examples of puzzle types for which this is useful are\n[Akari](https://en.wikipedia.org/wiki/Light_Up_(puzzle)) and\n[Skyscraper](https://www.puzzlemix.com/Skyscraper).\n\n~~~~\n$ python3 examples/akari.py             $ python3 examples/skyscraper.py \n\u2588* \u2588*    \u2588                              23541                            \n   *   \u2588                                15432                            \n*\u2588*   \u2588  *                              34215                            \n *\u2588  \u2588   \u2588                              42153                            \n   \u2588\u2588\u2588*                                 51324                            \n   *\u2588\u2588\u2588*                                                                 \n\u2588 * \u2588* \u2588*                               Unique solution\n*  \u2588*   \u2588*\n  \u2588     * \n\u2588 *   \u2588* \u2588\n\nUnique solution\n~~~~\n\n\n",
    "bugtrack_url": null,
    "license": "MIT",
    "summary": "GRId LOgic Puzzle Solver",
    "version": "0.9.1",
    "split_keywords": [],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "ddf881cebc05824f397a4506f6e98bd3",
                "sha256": "94d37f2daec76ebff85a1e8d6bf0a44185760b86b3c268a67454e36e6dfb0ab9"
            },
            "downloads": -1,
            "filename": "grilops-0.9.1-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "ddf881cebc05824f397a4506f6e98bd3",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.6",
            "size": 25068,
            "upload_time": "2021-01-14T02:21:47",
            "upload_time_iso_8601": "2021-01-14T02:21:47.214906Z",
            "url": "https://files.pythonhosted.org/packages/6e/77/2a4d8d492140b9174f5792ea90cd4e36c38d32b3e74c5b03517a89c5bd98/grilops-0.9.1-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "d839e84703e9e15484c2486fee6f6554",
                "sha256": "b078394eadcabe6aaef1fc3c6d1c9c341214c778a812364ea79f2e5904365d5b"
            },
            "downloads": -1,
            "filename": "grilops-0.9.1.tar.gz",
            "has_sig": false,
            "md5_digest": "d839e84703e9e15484c2486fee6f6554",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.6",
            "size": 21925,
            "upload_time": "2021-01-14T02:21:48",
            "upload_time_iso_8601": "2021-01-14T02:21:48.193256Z",
            "url": "https://files.pythonhosted.org/packages/28/8c/b4506047e6ec04c39c4099c3e62013be078649c356a417ad76a5f549fd01/grilops-0.9.1.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2021-01-14 02:21:48",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "github_user": null,
    "github_project": "obijywk",
    "error": "Could not fetch GitHub repository",
    "lcname": "grilops"
}
        
Elapsed time: 0.20916s