Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimised Solver for Sudoku #13

Open
potatochick2020 opened this issue Oct 10, 2022 · 5 comments
Open

Optimised Solver for Sudoku #13

potatochick2020 opened this issue Oct 10, 2022 · 5 comments

Comments

@potatochick2020
Copy link
Owner

    By looking at the code of the sudoku class, there are two parts generator and a solver.

I propose that we make TWO separate issues for each one, and add a generator with specific difficulty.

Regarding the solver, there are better algorithms than Backtracking, I have two candidates in my mind Dancing Links algorithm and the Rule-based Algorithm, both of them are faster than the backtracking.

This Medium article explains and Implements the Dancing Links Algorithm, and this Paper explains the Rule-based algorithm.

By looking at the two proposed algorithms it would take time to read the papers and deciding wich one to implement and as I'm still a student contributing on my weekend so, I'll do my best to make the pull request by the end of friday.

If there's another algorithm in your mind please let me know.

Originally posted by @MMostafa-Hub in #3 (comment)

@potatochick2020
Copy link
Owner Author

@MMostafa-Hub I am a student too, this is a really good thing that you could observe there is a part of optimised solution.

You could decide which algorithm to use.

@MMostafa-Hub
Copy link
Contributor

For the time being, I don't have the time to read both articles with attention to detail and decide which one to use, but It will be done on Friday.
so by Friday, I'll implement

  1. new SudokuSolution()
  2. try to optimize isValid(), isPlacable(), isComplete()

Is this ok with you?

@potatochick2020
Copy link
Owner Author

Sorry for my late reply.
Sure, let's say next Monday? No rush at all.

@MMostafa-Hub
Copy link
Contributor

Ok, the pull request will be ready on Monday

@MMostafa-Hub
Copy link
Contributor

Can I get assigned to the issue, so that i can start working on it?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants