dxz

Name	dxz JSON
Version	0.0.6 JSON
	download
home_page	https://github.com/Thilo-J/dxz
Summary	An exact cover solver that returns all solutions for a given problem
upload_time	2023-10-22 15:16:39
maintainer
docs_url	None
author	Thilo Langensteiner
requires_python	>=3.7
license
keywords
VCS
bugtrack_url
requirements	No requirements were recorded.
Travis-CI	No Travis.
coveralls test coverage	No coveralls.

            # DXZ

dxz is a Python package that implements the dxz algorithm that is described in the paper [Dancing with Decision Diagrams: A Combined Approach to Exact Cover](https://ojs.aaai.org/index.php/AAAI/article/view/10662). The algorithms returns all solutions to a given exact cover problem.

## Installation

Use the package manager [pip](https://pip.pypa.io/en/stable/) to install dxz.

```bash
pip install dxz
```

## The Algorithm

dxz is an algorithm for solving an exact cover problem. It build a [zdd](https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram) that represents all solutions for a given problem. This module converts the zdd to to a list of lists of ints. Each list in the list represents one solution.

For more details about dxz read the paper [Dancing with Decision Diagrams: A Combined Approach to Exact Cover](https://ojs.aaai.org/index.php/AAAI/article/view/10662).

## Usage

```python
import dxz

rows = 8
columns = 5

# A flatten matrix of boolean values. Row 0 is 1,0,0,1,1 row 2 is 0,1,1,0,0 and so on.
matrix = [
    1,0,0,1,1, # 0
    0,1,1,0,0, # 1
    0,0,0,1,1, # 2
    0,1,0,1,0, # 3
    1,0,1,0,0, # 4
    0,0,0,0,1, # 5
    0,0,0,1,0, # 6
    1,0,0,0,0, # 7
]

# Get all solutions to the exact cover problem.
solutions = dxz.dxz_solve(rows, columns, matrix, 0)

print(solutions)
# [
#   [1,0],
#   [1,7,2],
#   [1,7,6,5],
#   [3,4,5]
# ]
# One solutions is row 1 and 2 another solution is row 1, 7 and 2.

# Get only the number of solutions
number_of_solutions = dxz.dxz_count(rows, columns, matrix)


# Get only 3 solutions.
solutions = dxz.dxz_solve(rows, columns, matrix, 3)

```

## Contributing

Pull requests are welcome. For major changes, please open an issue first
to discuss what you would like to change.

## License

[MIT](https://choosealicense.com/licenses/mit/)
            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/Thilo-J/dxz",
    "name": "dxz",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.7",
    "maintainer_email": "",
    "keywords": "",
    "author": "Thilo Langensteiner",
    "author_email": "thilo.j.la@gmail.com",
    "download_url": "https://files.pythonhosted.org/packages/dc/f5/049f7af622aae07d1f6efd57b7f76834853de4a74266b061ec689f2b2c3e/dxz-0.0.6.tar.gz",
    "platform": null,
    "description": "# DXZ\n\ndxz is a Python package that implements the dxz algorithm that is described in the paper [Dancing with Decision Diagrams: A Combined Approach to Exact Cover](https://ojs.aaai.org/index.php/AAAI/article/view/10662). The algorithms returns all solutions to a given exact cover problem.\n\n## Installation\n\nUse the package manager [pip](https://pip.pypa.io/en/stable/) to install dxz.\n\n```bash\npip install dxz\n```\n\n## The Algorithm\n\ndxz is an algorithm for solving an exact cover problem. It build a [zdd](https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram) that represents all solutions for a given problem. This module converts the zdd to to a list of lists of ints. Each list in the list represents one solution.\n\nFor more details about dxz read the paper [Dancing with Decision Diagrams: A Combined Approach to Exact Cover](https://ojs.aaai.org/index.php/AAAI/article/view/10662).\n\n## Usage\n\n```python\nimport dxz\n\nrows = 8\ncolumns = 5\n\n# A flatten matrix of boolean values. Row 0 is 1,0,0,1,1 row 2 is 0,1,1,0,0 and so on.\nmatrix = [\n    1,0,0,1,1, # 0\n    0,1,1,0,0, # 1\n    0,0,0,1,1, # 2\n    0,1,0,1,0, # 3\n    1,0,1,0,0, # 4\n    0,0,0,0,1, # 5\n    0,0,0,1,0, # 6\n    1,0,0,0,0, # 7\n]\n\n# Get all solutions to the exact cover problem.\nsolutions = dxz.dxz_solve(rows, columns, matrix, 0)\n\nprint(solutions)\n# [\n#   [1,0],\n#   [1,7,2],\n#   [1,7,6,5],\n#   [3,4,5]\n# ]\n# One solutions is row 1 and 2 another solution is row 1, 7 and 2.\n\n# Get only the number of solutions\nnumber_of_solutions = dxz.dxz_count(rows, columns, matrix)\n\n\n# Get only 3 solutions.\nsolutions = dxz.dxz_solve(rows, columns, matrix, 3)\n\n```\n\n## Contributing\n\nPull requests are welcome. For major changes, please open an issue first\nto discuss what you would like to change.\n\n## License\n\n[MIT](https://choosealicense.com/licenses/mit/)",
    "bugtrack_url": null,
    "license": "",
    "summary": "An exact cover solver that returns all solutions for a given problem",
    "version": "0.0.6",
    "project_urls": {
        "GitHub": "https://github.com/Thilo-J/dxz",
        "Homepage": "https://github.com/Thilo-J/dxz"
    },
    "split_keywords": [],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "dcf5049f7af622aae07d1f6efd57b7f76834853de4a74266b061ec689f2b2c3e",
                "md5": "f5861ccf2b49796e6d3751474b400c51",
                "sha256": "32d2e957f537c24ee8df54e0fd8cd6e8d62ea37a59ebfbfebb61b4c4c7782091"
            },
            "downloads": -1,
            "filename": "dxz-0.0.6.tar.gz",
            "has_sig": false,
            "md5_digest": "f5861ccf2b49796e6d3751474b400c51",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.7",
            "size": 7946,
            "upload_time": "2023-10-22T15:16:39",
            "upload_time_iso_8601": "2023-10-22T15:16:39.489515Z",
            "url": "https://files.pythonhosted.org/packages/dc/f5/049f7af622aae07d1f6efd57b7f76834853de4a74266b061ec689f2b2c3e/dxz-0.0.6.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2023-10-22 15:16:39",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "codeberg": false,
    "github_user": "Thilo-J",
    "github_project": "dxz",
    "travis_ci": false,
    "coveralls": false,
    "github_actions": false,
    "lcname": "dxz"
}