Ask Question, Ask an Expert


Ask Computer Engineering Expert

For this assignment you will study and implement Korf’s algorithm for finding optimal solutions to random instances of Rubik’s Cube. Included with the assignment is a copy of Korf’s original paper. You should begin by reading the paper. Korf initially suggest using an iterative deepening version of A* (IDA*) with the heuristic. However, he points out that the inaccuracy of this heuristic results in too many nodes generated and therefore too much time to compute a solution. His answer to this problem is to precompute the heuristic for three components of the cube (corners, sides, sides) and store the values in a table. If these tables are small enough to be kept in memory, they can be referenced as part of the heuristic function. The assignment then breaks down into two steps:

1. Precompute the three tables for Korf’s heuristic and store the tables in a file. Be sure to choose a representation that is memory-efficient.

2. prepare a program that takes an arbitrary cube state as input and outputs an optimal solution move sequence. Your program should read in the tables that you precomputed, and use IDA* and Korf’s heuristic to find the solution.


For both input and output we will use the letters {R, O, Y, G, B, W} to represent the colors {Red, Orange, Yellow, Green, Blue, White}, respectively.


For input your program should take the name of a file that will contain an arbitrary cube state. The file will contain a specific two dimensional representation of the cube, using the letters above to describe each cube face. The structure of the two dimensional representation will be as follows:

1850_cube face.jpg

Sample Files
The goal state would be:                             A valid non-goal state would be:
RRR                                                                    GGW
RRR                                                                    RRG
RRR                                                                    RRG                                                              
GGGYYYBBB                                                   OWWGGOYYR
GGGYYYBBB                                                   OGOYYYRBR
GGGYYYBBB                                                   YYYRBGRWW
OOO                                                                  BOY
OOO                                                                  BOB
OOO                                                                  BOB
WWW                                                                OGO
WWW                                                                WWB
WWW                                                                WWB

All spaces should be ignored when reading the files. Note that the six center faces are always the same in any valid state.
Invalid States

Not all arrangements of the faces are reachable from the goal state. The first thing your program should do is check that the input state is valid. If not, the program should output a message indicating that the state is invalid and terminate.


Your program should output the optimal solution sequence for the input state as a string to standard input. The format of the solution sequence will be a string with two characters per move. The first character will be the color of the center cubie of the face to be rotated. The second character will be the number of 90° clockwise rotations, i.e. ∈ {1, 2, 3}. E.g., for the above non-goal state, the optimal solution would be O1W1R1Y3.


You may use a programming language of your choice for this assignment. You are responsible for choosing a programming language and making it work. If you plan to use a non-standard language, be sure to start early so you have time to change languages if your approach does not work.


In addition to the source code, report must contains the following:

• Explanation of your approach for computing and storing the tables

• Details about the tables, including number of entries and memory requirements

• Instructions for running your program

• Solutions for the ten sample states (to be provided)

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91571

Have any Question? 

Related Questions in Computer Engineering

Compare and contrast database backup amp disaster

Compare and contrast Database Backup & Disaster Planning. This research paper will describe, compare and contrast Database Backup & Disaster Planning. • This paper will be 5 pages total: • (a) Describe Database Backup - ...

What this program codehere are some requirements for the

What this program code Here are some requirements for the program : JAVA Programming The program must prompt the user to enter the amount of tickets he/she wants to purchase (must be between 1 and 5) A ticket will be mad ...

Consider the following tablea give the sql to horizontally

Consider the following table: (a) Give the SQL to horizontally fragment staff by position. Give the SQL to reconstruct the original table from the fragments. Under what conditions is the fragmentation complete? (b) Give ...

Suppose we have market baskets that satisfy the following

Suppose we have market baskets that satisfy the following assumptions: 1. The support threshold is 10,000. 2. There are one million items, represented by the integers 0, 1, . . . , 999999. 3. There are N frequent items, ...

A statistics practitioner is in the process of testing to

A statistics practitioner is in the process of testing to determine whether is enough evidence to infer that the population mean is different from 180. She calculated the mean and standard deviation of a sample of 200 ob ...

1 use the national income data in the table below compute a

1. Use the national income data in the table below, compute (a) GDP, (b) NDP, and (c) NI using the expenditure approach. National Income Accounting Data Amount (billions) Compensation of Employees $2684 U.S. Exports of g ...

A what is the premise of fagins work on dknfb summarize the

a. What is the premise of Fagin's work on DK/NF? b. Summarize the three categories of normalization theory. c. In general, how can you transform a relation not in BCNF into ones that are in BCNF? d. What is a referential ...

Create a flowchart that will containnbspfivenbspmodules

Create a flowchart that will contain  five  modules , one  to prompt the user to input the  sales amount before discount  and  the  discount percent  as a decimal, the  second  to  calculate the amount of discount , the ...

Distinguish between mobile subscriber isdn number and

Distinguish between mobile subscriber, ISDN number and mobile station roaming?

Write the code to add together the numbers stored in the

Write the code to add together the numbers stored in the first and second elements in a one-dimensional int array named nums. Display the sum on the screen.

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate