Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

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.

I/O

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.

Input

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.

Output

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.

Language

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.

Report

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

1 what is the difference between half-duplex and

1. What is the difference between half-duplex and full-duplex transmission modes? 2. Name the four basic network topologies, and cite an advantage of each type. 3. For n devices in a network, what is the number of cable ...

Answer all 9 questionsshort answer 1-810 points each with

Answer All 9 questions Short Answer 1-8[10 points each with each about 3/4 - 1 page double-spaced]: 1. If the spot rate for Swiss Francs versus US Dollars is one SF equals 1.05 US$, and the annual interest rate on fixed ...

Compare and contrast the social and environmental risks and

Compare and contrast the social and environmental risks and vulnerabilities for the two counties you selected, I have selected Norman, Oklahoma and Charles County, Maryland, and summarize your findings. Describe the comm ...

1 assume a private internet uses a protocol suite totally

1. Assume a private internet uses a protocol suite totally different from the TCP/ IP protocol suite. Can this internet still use the services of UDP or TCP as an end-to-end vehicle of message communication? 2. Can you e ...

1 what is a false reject rate what is a false accept rate

1. What is a false reject rate? What is a false accept rate? What is their relationship to the crossover error rate? 2. What is the most widely accepted biometric authorization technology? Why do you think this technolog ...

1 why do optical signals used in fiber optic cables have a

1. Why do optical signals used in fiber optic cables have a very short wave length? 2. Can we say whether a signal is periodic or nonperiodic by just looking at its frequency domain plot? How? 3. Is the frequency domain ...

Show the contents of the hash table from exercise 111 after

Show the contents of the hash table from Exercise 11.1 after rehashing with a new table containing 19 entries. Exercise 11.1: Assume an initially empty hash table with 11 entries in which the hash function uses the divis ...

Adaptive unsharp masking a powerful method of sharpening

(Adaptive unsharp masking) A powerful method of sharpening images in the presence of low levels of noise (such as film grain noise) is via the following algorithm [15] . The high-pass filter which can be used for unsharp ...

1 consider proposed implementations of a systolic array you

1. Consider proposed implementations of a systolic array (you can find these in on the Internet or in technical publications). Then attempt to program the loop provided in Exercise 6.11 using this MISD model. Discuss any ...

1 in wireshark go to statistics gt summary what is the

1 .In Wireshark, go to Statistics > Summary. What is the Average Mbps? 2. Go to Statistics > Protocol Hierarchy. Which protocols use most of the bandwidth? 3. Go to Statistics > Packet Lengths > Create Stat. What percent ...

  • 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

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro