search

aimacode / aima-javascript

Javascript visualization of algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"
http://aimacode.github.io/aima-javascript/
MIT License
538 stars 216 forks source link

Add Visualization for 8-Queen Problem #134

Closed Dragneel7 closed 5 years ago

Dragneel7 commented 6 years ago

The 8-Queen problem is a excellent example that proves not only a good searching example but also as a an example in the list of problems solved using genetic algorithms. So maybe we can add it. I am note sure in which chapter should it go as it is mentioned in chapter3, 4, 6. @redblobgames what do you think?

Would like to work on it : Yes.

redblobgames commented 6 years ago

Sure, go for it. I think the 8-Queen problem is probably better for chapter 4 or 6. We have lots of search visualizations in chapter 3 already. We could use more visualizations of the techniques in chapter 4 and 6 :-)

Dragneel7 commented 6 years ago

I will start working on it.

Dragneel7 commented 6 years ago

@redblobgames Hi, I have decided to put this visualization in chapter 6 under subheading "Minimum-Conflict" in reference to the book.

Dragneel7 commented 6 years ago

@redblobgames Please review the PR. I have a bit of trouble in the code which i would like to clarify. Thanks.

anishaswain commented 6 years ago

Hello, I have worked on the 8-Queen problem which is hosted here. I went through all the suggestions and recommendations from @redblobgames and @samuelgoto from the docs and have come up with it. I agree with the previous contributors regarding the suggestion to let the user fiddle with the problem itself before presenting the solution to solve the problem. In the blog, we first present the user with a chessboard and ask to put 8 queens on the board without conflict. Whenever there is a conflict, we provide feedback through a red line showing which queens are in conflict. This will allow the user to understand the problem statement before jumping to the solution. Next, we abstract the problem by providing visual feedback as to which positions are no longer possible for queens, once a queen has been placed. This will allow the user to look at the problem with a different view. This is a build-up before presenting the backtracking search method to solve the problem. As the blog mentions, most of the users will try to randomly place queens and then change the positions of already placed queen once all the cells are finished. This will provide the user with necessary intuition regarding the algorithm. I have not completed the visualizations yet (backtracking search and some finishing touches). I will be glad if you could provide some feedback. I would like to include these visualizations in the project as PR. This also serves as a showcase for design skills as required by GSOC for aimacode-javascript. Please provide suggestions! Thanks in advance.

Dragneel7 commented 6 years ago

@Anisha1234 That is nice work. I have a suggestion for the min-conflict visualization. The algorithm starts by assigning random values and then minimizes the conflicts step by step. So you can start by random arrangement of 8 Queens and then the show the reader where the queen he selects(as you have done now).

samuelgoto commented 6 years ago

Can you kick off a design doc and send this to us in this thread? It is very hard for us to comment/collaborate/iterate on your design in the form of a HTML/JS/CSS prototype.

Start with a design doc (recommendation: use google docs and google diagrams in it) to lay out your narrative, bigger diagrams, get some feedback and when you have something solid you move on to a prototype.

Please follow this process.

anishaswain commented 6 years ago

Hello @samuelgoto, I have made the design document as per your recommendation and have shared the google doc with you. I understand your suggestion of having a design doc before moving on to a prototype but as I had already implemented some part of the visualization, so I tried to combine both prototypes images and google diagrams to explain the concept in the design doc. Thank You

redblobgames commented 5 years ago

Closing as this seems inactive