Backtracking/Rat Maze

[dlesnoff]

Repository commit

fbad85d

Python version (python --version)

Python 3.10.9

Dependencies version (pip freeze)

alabaster @ file:///home/ktietz/src/ci/alabaster_1611921544520/work
arrow @ file:///croot/arrow_1676588132104/work
astroid @ file:///croot/astroid_1676904296642/work
asttokens @ file:///opt/conda/conda-bld/asttokens_1646925590279/work
atomicwrites==1.4.0
attrs @ file:///croot/attrs_1668696182826/work
autopep8 @ file:///opt/conda/conda-bld/autopep8_1650463822033/work
Babel @ file:///croot/babel_1671781930836/work
backcall @ file:///home/ktietz/src/ci/backcall_1611930011877/work
beautifulsoup4 @ file:///croot/beautifulsoup4-split_1680589949093/work
binaryornot @ file:///tmp/build/80754af9/binaryornot_1617751525010/work
black @ file:///croot/black_1680737249031/work
bleach @ file:///opt/conda/conda-bld/bleach_1641577558959/work
boltons @ file:///croot/boltons_1677628692245/work
brotlipy==0.7.0
certifi @ file:///croot/certifi_1671487769961/work/certifi
cffi @ file:///croot/cffi_1670423208954/work
chardet @ file:///home/builder/ci_310/chardet_1640804867535/work
charset-normalizer @ file:///tmp/build/80754af9/charset-normalizer_1630003229654/work
click @ file:///tmp/build/80754af9/click_1646056706450/work
cloudpickle @ file:///tmp/build/80754af9/cloudpickle_1632508026186/work
colorama @ file:///croot/colorama_1672386526460/work
comm @ file:///croot/comm_1671231121260/work
conda==23.3.1
conda-content-trust @ file:///tmp/abs_5952f1c8-355c-4855-ad2e-538535021ba5h26t22e5/croots/recipe/conda-content-trust_1658126371814/work
conda-package-handling @ file:///croot/conda-package-handling_1672865015732/work
conda_package_streaming @ file:///croot/conda-package-streaming_1670508151586/work
cookiecutter @ file:///opt/conda/conda-bld/cookiecutter_1649151442564/work
cryptography @ file:///croot/cryptography_1677533068310/work
debugpy @ file:///home/builder/ci_310/debugpy_1640789504635/work
decorator @ file:///opt/conda/conda-bld/decorator_1643638310831/work
defusedxml @ file:///tmp/build/80754af9/defusedxml_1615228127516/work
diff-match-patch @ file:///Users/ktietz/demo/mc3/conda-bld/diff-match-patch_1630511840874/work
dill @ file:///croot/dill_1667919592856/work
docstring-to-markdown @ file:///croot/docstring-to-markdown_1673447639232/work
docutils @ file:///opt/conda/conda-bld/docutils_1657175430858/work
entrypoints @ file:///tmp/build/80754af9/entrypoints_1649908313000/work
executing @ file:///opt/conda/conda-bld/executing_1646925071911/work
fastjsonschema @ file:///opt/conda/conda-bld/python-fastjsonschema_1661371079312/work
flake8 @ file:///croot/flake8_1674581792275/work
flit_core @ file:///croot/flit-core_1679397103445/work/source/flit_core
idna @ file:///croot/idna_1666125576474/work
imagesize @ file:///opt/conda/conda-bld/imagesize_1657179498843/work
importlib-metadata @ file:///croot/importlib-metadata_1678997070253/work
inflection==0.5.1
intervaltree @ file:///Users/ktietz/demo/mc3/conda-bld/intervaltree_1630511889664/work
ipykernel @ file:///croot/ipykernel_1671488378391/work
ipython @ file:///croot/ipython_1680701871216/work
ipython-genutils @ file:///tmp/build/80754af9/ipython_genutils_1606773439826/work
isort @ file:///tmp/build/80754af9/isort_1628603791788/work
jaraco.classes @ file:///tmp/build/80754af9/jaraco.classes_1620983179379/work
jedi @ file:///tmp/build/80754af9/jedi_1644315229345/work
jeepney @ file:///tmp/build/80754af9/jeepney_1627537048313/work
jellyfish @ file:///tmp/build/80754af9/jellyfish_1647944422765/work
Jinja2 @ file:///croot/jinja2_1666908132255/work
jinja2-time @ file:///opt/conda/conda-bld/jinja2-time_1649251842261/work
jsonpatch @ file:///tmp/build/80754af9/jsonpatch_1615747632069/work
jsonpointer==2.1
jsonschema @ file:///croot/jsonschema_1676558650973/work
jupyter_client @ file:///croot/jupyter_client_1676329080601/work
jupyter_core @ file:///croot/jupyter_core_1679906564508/work
jupyterlab-pygments @ file:///tmp/build/80754af9/jupyterlab_pygments_1601490720602/work
keyring @ file:///croot/keyring_1678999217139/work
lazy-object-proxy @ file:///home/builder/ci_310/lazy-object-proxy_1640791307593/work
lxml @ file:///opt/conda/conda-bld/lxml_1657545139709/work
MarkupSafe @ file:///opt/conda/conda-bld/markupsafe_1654597864307/work
matplotlib-inline @ file:///opt/conda/conda-bld/matplotlib-inline_1662014470464/work
mccabe @ file:///opt/conda/conda-bld/mccabe_1644221741721/work
mistune @ file:///home/builder/ci_310/mistune_1640791641754/work
more-itertools @ file:///tmp/build/80754af9/more-itertools_1637733554872/work
mypy-extensions==0.4.3
nbclient @ file:///tmp/build/80754af9/nbclient_1650290238894/work
nbconvert @ file:///croot/nbconvert_1668450669124/work
nbformat @ file:///croot/nbformat_1670352325207/work
nest-asyncio @ file:///croot/nest-asyncio_1672387112409/work
numpydoc @ file:///croot/numpydoc_1668085905352/work
packaging @ file:///croot/packaging_1678965309396/work
pandocfilters @ file:///opt/conda/conda-bld/pandocfilters_1643405455980/work
parso @ file:///opt/conda/conda-bld/parso_1641458642106/work
pathspec @ file:///croot/pathspec_1674681560568/work
pexpect @ file:///tmp/build/80754af9/pexpect_1605563209008/work
pickleshare @ file:///tmp/build/80754af9/pickleshare_1606932040724/work
pip==22.3.1
platformdirs @ file:///opt/conda/conda-bld/platformdirs_1662711380096/work
pluggy @ file:///tmp/build/80754af9/pluggy_1648024709248/work
ply==3.11
poyo @ file:///tmp/build/80754af9/poyo_1617751526755/work
prompt-toolkit @ file:///croot/prompt-toolkit_1672387306916/work
psutil @ file:///opt/conda/conda-bld/psutil_1656431268089/work
ptyprocess @ file:///tmp/build/80754af9/ptyprocess_1609355006118/work/dist/ptyprocess-0.7.0-py2.py3-none-any.whl
pure-eval @ file:///opt/conda/conda-bld/pure_eval_1646925070566/work
pycodestyle @ file:///croot/pycodestyle_1674267221883/work
pycosat @ file:///croot/pycosat_1666805502580/work
pycparser @ file:///tmp/build/80754af9/pycparser_1636541352034/work
pydocstyle @ file:///croot/pydocstyle_1675221668445/work
pyflakes @ file:///croot/pyflakes_1674165128613/work
Pygments @ file:///opt/conda/conda-bld/pygments_1644249106324/work
pylint @ file:///croot/pylint_1676919896363/work
pylint-venv @ file:///croot/pylint-venv_1673990127282/work
pyls-spyder==0.4.0
pyOpenSSL @ file:///croot/pyopenssl_1677607685877/work
PyQt5-sip==12.11.0
pyrsistent @ file:///home/builder/ci_310/pyrsistent_1640807196327/work
PySocks @ file:///home/builder/ci_310/pysocks_1640793678128/work
python-dateutil @ file:///tmp/build/80754af9/python-dateutil_1626374649649/work
python-lsp-black @ file:///opt/conda/conda-bld/python-lsp-black_1661852031497/work
python-lsp-jsonrpc==1.0.0
python-lsp-server @ file:///croot/python-lsp-server_1677296760843/work
python-slugify @ file:///tmp/build/80754af9/python-slugify_1620405669636/work
pytoolconfig @ file:///croot/pytoolconfig_1676315026871/work
pytz @ file:///croot/pytz_1671697431263/work
pyxdg @ file:///tmp/build/80754af9/pyxdg_1603822279816/work
PyYAML @ file:///croot/pyyaml_1670514731622/work
pyzmq @ file:///opt/conda/conda-bld/pyzmq_1657724186960/work
QDarkStyle @ file:///tmp/build/80754af9/qdarkstyle_1617386714626/work
qstylizer @ file:///croot/qstylizer_1674008522553/work/dist/qstylizer-0.2.2-py2.py3-none-any.whl
QtAwesome @ file:///croot/qtawesome_1674008680358/work
qtconsole @ file:///croot/qtconsole_1674008428467/work
QtPy @ file:///opt/conda/conda-bld/qtpy_1662014892439/work
requests @ file:///croot/requests_1678709721434/work
rope @ file:///croot/rope_1676675015455/work
Rtree @ file:///croot/rtree_1675157851263/work
ruamel.yaml @ file:///croot/ruamel.yaml_1666304550667/work
ruamel.yaml.clib @ file:///croot/ruamel.yaml.clib_1666302247304/work
SecretStorage @ file:///croot/secretstorage_1678709481048/work
setuptools==68.0.0
sip @ file:///tmp/abs_44cd77b_pu/croots/recipe/sip_1659012365470/work
six @ file:///tmp/build/80754af9/six_1644875935023/work
snowballstemmer @ file:///tmp/build/80754af9/snowballstemmer_1637937080595/work
sortedcontainers @ file:///tmp/build/80754af9/sortedcontainers_1623949099177/work
soupsieve @ file:///croot/soupsieve_1680518478486/work
Sphinx @ file:///opt/conda/conda-bld/sphinx_1657784123546/work
sphinxcontrib-applehelp @ file:///home/ktietz/src/ci/sphinxcontrib-applehelp_1611920841464/work
sphinxcontrib-devhelp @ file:///home/ktietz/src/ci/sphinxcontrib-devhelp_1611920923094/work
sphinxcontrib-htmlhelp @ file:///tmp/build/80754af9/sphinxcontrib-htmlhelp_1623945626792/work
sphinxcontrib-jsmath @ file:///home/ktietz/src/ci/sphinxcontrib-jsmath_1611920942228/work
sphinxcontrib-qthelp @ file:///home/ktietz/src/ci/sphinxcontrib-qthelp_1611921055322/work
sphinxcontrib-serializinghtml @ file:///tmp/build/80754af9/sphinxcontrib-serializinghtml_1624451540180/work
spyder @ file:///croot/spyder_1678296151130/work
spyder-kernels @ file:///croot/spyder-kernels_1678120593941/work
stack-data @ file:///opt/conda/conda-bld/stack_data_1646927590127/work
text-unidecode @ file:///Users/ktietz/demo/mc3/conda-bld/text-unidecode_1629401354553/work
textdistance @ file:///tmp/build/80754af9/textdistance_1612461398012/work
three-merge @ file:///tmp/build/80754af9/three-merge_1607553261110/work
tinycss2 @ file:///croot/tinycss2_1668168815555/work
toml @ file:///tmp/build/80754af9/toml_1616166611790/work
tomli @ file:///opt/conda/conda-bld/tomli_1657175507142/work
tomlkit @ file:///tmp/abs_56_0lnnq5x/croots/recipe/tomlkit_1658946880479/work
toolz @ file:///croot/toolz_1667464077321/work
tornado @ file:///opt/conda/conda-bld/tornado_1662061693373/work
tqdm @ file:///croot/tqdm_1679561862951/work
traitlets @ file:///croot/traitlets_1671143879854/work
typing_extensions @ file:///croot/typing_extensions_1669924550328/work
ujson @ file:///opt/conda/conda-bld/ujson_1657544923770/work
Unidecode @ file:///tmp/build/80754af9/unidecode_1614712377438/work
urllib3 @ file:///croot/urllib3_1680254681959/work
watchdog @ file:///home/builder/ci_310/watchdog_1640811339391/work
wcwidth @ file:///Users/ktietz/demo/mc3/conda-bld/wcwidth_1629357192024/work
webencodings==0.5.1
whatthepatch @ file:///opt/conda/conda-bld/whatthepatch_1661795988879/work
wheel==0.40.0
wrapt @ file:///tmp/abs_c335821b-6e43-4504-9816-b1a52d3d3e1eel6uae8l/croots/recipe/wrapt_1657814400492/work
wurlitzer @ file:///home/builder/ci_310/wurlitzer_1640796026694/work
yapf @ file:///tmp/build/80754af9/yapf_1615749224965/work
zipp @ file:///croot/zipp_1672387121353/work
zstandard @ file:///croot/zstandard_1677013143055/work

Expected behavior

>>> maze = [[1, 0, 1, 0, 0],
...         [1, 1, 1, 1, 1],
...         [0, 1, 0, 1, 0],
...         [1, 1, 0, 1, 1],
...         [0, 1, 1, 0, 1]]
>>> solve_maze(maze)
([1, 0, 0, 0, 0]
[1, 1, 1, 1, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 1, 1]
[0, 0, 0, 0, 1], 1)

Or changing the documentation according to the current examples.

Actual behavior

Documentation is unclear.
« In this problem we have some n by n matrix, a start point and an end point.
We want to go from the start to the end. In this matrix zeroes represent walls
and ones paths we can use. »
But from the examples (reproducible with calls to the solver function):
>>> maze = [[0, 1, 0, 1, 1],
... [0, 0, 0, 0, 0],
... [1, 0, 1, 0, 1],
... [0, 0, 1, 0, 0],
... [1, 0, 0, 1, 0]]
>>> solve_maze(maze)
[1, 0, 0, 0, 0]
[1, 1, 1, 1, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 1, 1]
[0, 0, 0, 0, 1]

Walls seem to be represented with ones, and valid paths seem to be represented with 0s.
Additionally, the documentation does not describe the output. It seems that the solution returned is the contiguous path given by the 1s.

Nothing is said on the number of the solutions.

[Excergic]

hello i did not get this issue will you please explain what to do in this I want to contribute on this project

[457ayan]

def solve_maze(maze):
# Create a copy of the maze to avoid modifying the original maze
solved_maze = [row[:] for row in maze]

# Get the dimensions of the maze
rows = len(maze)
cols = len(maze[0])

# Define the starting and ending points
start = (0, 0)
end = (rows - 1, cols - 1)

# Call the recursive function to solve the maze
solve_maze_recursive(solved_maze, start, end)

# Return the solved maze and the path length
return solved_maze, solved_maze[end[0]][end[1]]

def solve_maze_recursive(maze, current, end):
# Check if the current position is out of bounds or a wall
if current[0] < 0 or current[0] >= len(maze) or current[1] < 0 or current[1] >= len(maze[0]) or maze[current[0]][current[1]] == 0:
return False

# Check if the current position is the end point
if current == end:
    maze[current[0]][current[1]] = 1
    return True

# Mark the current position as part of the path
maze[current[0]][current[1]] = 1

# Recursively explore all possible directions
if solve_maze_recursive(maze, (current[0] + 1, current[1]), end) or \
   solve_maze_recursive(maze, (current[0] - 1, current[1]), end) or \
   solve_maze_recursive(maze, (current[0], current[1] + 1), end) or \
   solve_maze_recursive(maze, (current[0], current[1] - 1), end):
    return True

# If no path is found, backtrack and mark the current position as a dead end
maze[current[0]][current[1]] = 0
return False

[tianyizheng02]

@lets-cod Read the contributing guidelines:

If you are interested in resolving an open issue, simply make a pull request with your proposed fix. We do not assign issues in this repo so please do not ask for permission to work on an issue.

[tianyizheng02]

@amitaryansingh Read the contributing guidelines.

If you are interested in resolving an open issue, simply make a pull request with your proposed fix. We do not assign issues in this repo so please do not ask for permission to work on an issue.

[tianyizheng02]

@nrhitik Did you read my previous comment?

[dlesnoff]

hello i did not get this issue will you please explain what to do in this I want to contribute on this project

The documentation explains the opposite of the input given as a test example.
It swapped walls and open paths. In the current example, the ones correspond to walls and zeroes to open paths.
The documentation said the opposite: "In this matrix zeroes represent walls and ones paths we can use."
I offered to swap the zeroes and ones in the input as I found confusing that ones denote walls in the input and the path taken in the output.

@Muhammadummerr has opened a Pull Request that solves this issue.

I also proposed an enhancement, which is to count the number of potential solutions to the maze and to return this along one solution when it exists.

[Muhammadummerr]

hello i did not get this issue will you please explain what to do in this I want to contribute on this project

The documentation explains the opposite of the input given as a test example. It swapped walls and open paths. In the current example, the ones correspond to walls and zeroes to open paths. The documentation said the opposite: "In this matrix zeroes represent walls and ones paths we can use." I offered to swap the zeroes and ones in the input as I found confusing that ones denote walls in the input and the path taken in the output.

@Muhammadummerr has opened a Pull Request that solves this issue.

I also proposed an enhancement, which is to count the number of potential solutions to the maze and to return this along one solution when it exists.

Counting the number of possible solutions and returning one of them would not be a good idea. Returning the solution maze if one exists; otherwise, raising an exception would be better.

[dlesnoff]

@Muhammadummerr Counting the number of possible solutions and returning one of them would not be a good idea. Returning the solution maze if one exists; otherwise, raising an exception would be better.

Why? You made a general statement without justification.

Anyway, thanks for the work you made.

[Muhammadummerr]

@Muhammadummerr Counting the number of possible solutions and returning one of them would not be a good idea. Returning the solution maze if one exists; otherwise, raising an exception would be better.

Why? You made a general statement without justification.

Anyway, thanks for the work you made.

Sorry for the miscommunication from my side, but the issue is that if no solution exists, what would it return with 0 total paths in place of one possible solution? Another consideration is that we can create another algorithm that counts all possible paths from the source to the destination (which we will name 'possible_paths' instead of 'solve_maze').
Thanks for your appreciation.