Share your work: March 2021

Note: Since the Topic hasn’t been created yet and I have work to share, I’m creating it and will reply with my work.

Use this thread to share your work for the month of March 2021.

The best way to structure your reply is to include:

  • What would you like to share?
  • Brief Summary
  • Link to your work
  • Learnings

Read the getting started post for more instructions:
https://jovian.ai/forum/t/share-your-work-getting-started/7166/2

1 Like
  • What would you like to share?
    Implementation of Dancing Links (Algorithm X) in Python

  • Brief Summary
    I’m preparing for my course project for Python Data Structures and Algorithms and need to select a problem to solve. I’ve decided on my problem being a Sudoku solver. I’ve already written a brute force solver, which works but can be very slow due to the O(n^m) complexity of the problem. Researching better algorithms lead me to Donald Knuth’s Algorithm X and Dancing Links. This work is an implementation of the algorithm and using it to solve a 2x2 Latin Square

  • Link to your work
    https://jovian.ai/fuzzyray/dancing-links

  • Learnings
    My biggest challenge with this implementation was learning how to build and represent the sparse matrix to define the problem. Most descriptions show how to implement the algorithm, but not how to define the problem. The actual implementation of the algorithm was a pretty forward translation of the pseudo code to Python.

  • Next Steps
    There is a Python implementation of Algorithm X that utilizes Python dictionaries instead of doubly linked lists: Algorithm X in 30 lines. Without copying/referencing the code, I would like to investigate and implement the algorithm with dictionaries.

1 Like