Skip to content
Comparison between BFS and DFS in solving several real-world puzzle problems.
Python
Branch: master
Clone or download

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
mdres
LICENSE
README.md
grid_peg_solitaire_puzzle.py
mn_puzzle.py
puzzle.py
puzzle_tools.py
sudoku_puzzle.py
word_ladder_puzzle.py
words

README.md

BFS-DFS-puzzle-solving

Comparison between BFS and DFS in solving several real-world puzzle problems.

Getting Started

Prerequisites

  • Python 3.x
  • Terminal (in Unix) OR PowerShell (in Windows)

Download source code

# Change to HOME directory
$ cd ~

# Clone this repo and 'cd' into it
$ git clone https://github.com/jellycsc/BFS-DFS-puzzle-solving.git
$ cd BFS-DFS-puzzle-solving/

Solving Sudoku

Sudoku         Sudoku solution
Image source: https://en.wikipedia.org/wiki/Sudoku

$ python3 sudoku_puzzle.py

Solving Peg solitaire

Peg solitaire
Image source: http://www.gibell.net/pegsolitaire/diagonal/index.html

$ python3 grid_peg_solitaire_puzzle.py

Solving MN puzzle (15-puzzle)


Image source: https://en.wikipedia.org/wiki/15_puzzle

$ python3 mn_puzzle.py

Solving Word ladder

Word ladder         Word ladder solution
Image source: http://www.clarity-media.co.uk/aboutpuzzles/word-ladder-puzzle

$ python3 word_ladder_puzzle.py

Authors

Name GitHub Email
Chenjie Ni jellycsc nichenjie2013@gmail.com

Thoughts and future improvements

  • BFS and DFS are both uninformed search algorithms. BFS is capable of finding shortest path solution but it's not memory efficient. In contrast, DFS uses a lot less memory, but it's not guaranteed to find a solution if the depth of the search tree is infinite.
  • A* with clever heuristic will save your life.
  • Pacman in Stanford CS221

Contributing to this project

  1. Fork it GitHub forks
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -m 'Add some feature')
  4. Push to your feature branch (git push origin my-new-feature)
  5. Create a new Pull Request

Details are described here.

Bug Reporting GitHub issues

Please click issue button above↑ to report any issues related to this project
OR you can shoot an email to nichenjie2013@gmail.com

License

This project is licensed under the MIT License - see LICENSE file for more details.

You can’t perform that action at this time.