Skip to content

A Rubik's Cube solver implementation with optimal algorithms (e.g. DLS, IDS) in C++ ❓

License

Notifications You must be signed in to change notification settings

seyedsaleh/rubik2D-IDS

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Contributors Forks Stargazers Issues MIT License


In The Name Of God

rubik2D-IDS

A Rubik's Cube solver implementation with optimal algorithms (e.g. DLS, IDS) ❓
Explore the docs »

Report Bug & Request Feature

Table of Contents
  1. About The Project
  2. Parts
  3. Results
  4. License
  5. Refereces
  6. Contact
  7. Roadmap

About The Project

In this project, I have done two simple tasks: simulating and solving 2x2 Rubik's games! 😄

The game is made up of two parts, Graphics and Algorithms, in which the graphic demands the use of C++ and terminal, and for the Search Algorithm, the DLS algorithm (which is an uninformed search algorithm) and the IDS algorithm in Artificial Intelligence and Algorithms.

To start, you can just change the "Rubik-Surf-Color.csv" file which is the first color state of Rubik, and then run the main code to see the result!!

(back to top)

Built With

Major frameworks/libraries used to this project:

(back to top)

Parts

Algorithms

Depth Limited Search Algorithm (DLS Algorithm)

In AI we have 2 main methods of searching: Informed and Uninformed searching. In an Uninformed search, we don’t know how far or close are we to the goal, so with checking of reach a goal or not, we continue our move in all possible directions, but in Informed search, we know where our goal is and how far or close we are to the goal, so we define a heuristic which determines which move to choose.

The DLS search algorithm is one of the uninformed search methods in Artificial Intelligence so that the goal is not clear and we must reach the goal through uninformed moves of the target.

Every state of the agent (cube in this example) is called a node. Each of these nodes can produce a new node (they are called parent nodes which produce child nodes) by moving to its next state, so all possible modes are available. These newly made nodes would be a new parent node to new nodes that could be produced by them.

The DLS algorithm determines the depth to extend in various nodes and determines how deep the initial node goes. The final non-goal solution returns to the previous state that it can be checked. This algorithm is graphical as follows:

If the desired solution is reached, the algorithm will ignore the rest of the nodes returns the answer.The pseudo-code of this method (DLS) will be as the following.

DLS will equal Depth-First-Search (DFS) if we set depth to infinity.

Iterative Deepening Depth-First Search Algorithm (IDS Algorithm)

IDS is a graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDS, or more specifically IDDFS is optimal like breadth-first search but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

In this project, I have implemented both algorithms to find the optimal solutions.

Graphic

I named the surface colors as:

  1. Orange
  2. Green
  3. White
  4. Blue
  5. Red
  6. Yellow

For printing stuff, I stated the number of the cube and the round and movement.

The initial state of the cube is taken from the input as follows in the order of the number of surfaces mentioned above, the colors of surfaces is shown by numbers as 1 to 6. For example, for the following figure, the input would be as follows:

(back to top)

Result

Once you get the solution of Rubik's solver, the program display number of expanded nodes (procedure) and also displays the depth in which the program found the result (number of steps to achieve the answer).

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Refereces

[1] Russell, Stuart J. (Stuart Jonathan). Artificial Intelligence : a Modern Approach. Upper Saddle River, N.J. :Prentice Hall, 2010. (Chapter3 - Solving Problems by Searching)

(back to top)

Contact

Seyedmohammadsaleh Mirzatabatabaei - @seyedsaleh - [email protected]

Project Link: https://github.com/seyedsaleh/rubik2D-IDS

(back to top)

Roadmap

  • Simulating and solving 2x2 Rubik's games with DLS and IDS!
  • Bidirectional Search method and solve this question with it.
  • GUI implemented using Qt.

See the open issues for a full list of proposed features (and known issues).

(back to top)


About

A Rubik's Cube solver implementation with optimal algorithms (e.g. DLS, IDS) in C++ ❓

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published