Tiling: The precondition to the problem is that you are given three integers n, i, j, where i and j are in the range 1 to 2n. You have a 2n by 2n square board of squares. You have a sufficient number of tiles each with the shape . Your goal is to place nonoverlapping tiles on the board to cover each of the 2n × 2n tiles except for the single square at location i, j. Give a recursive algorithm for this problem in which you place one tile yourself and then have four friends help you. What is your base case?

Tiling: The precondition to the problem is that you are given three integers n, i, j, where i and j are in the range 1 to 2n. You have a 2n by 2n square board of squares. You have a sufficient number of tiles each with the shape . Your goal is to place nonoverlapping tiles on the board to cover each of the 2n × 2n tiles except for the single square at location i, j. Give a recursive algorithm for this problem in which you place one tile yourself and then have four friends help you. What is your base case?

C++ for Engineers and Scientists

4th Edition

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Bronson, Gary J.

Chapter4: Selection Structures

Section: Chapter Questions

Problem 14PP

See similar textbooks

Similar questions

Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker to one of three squares: 1. the square immediately above 2. the square that is one up and one to the left (but only if the checker if not already in the leftmost column) 3. the square that is one up and one to the right (but only if the checker is not already in the rightmost column). 1 Each time you move from square x to square y, you receive p(x, y) dollars. You are given p(x, y) for all pairs (x, y) for which a move from x to y is legal. Do not assume that p(x, y) is positive. design a recursive backtracking algorithm that determines the maximum amount of money you can recieve, when moving a checker frmo somewhere on the bottom row to somewhere on the top row. your algorithm is free to pick any squrre along the bottom row as a starting point and any square along…
The game of Chomp is played by two players. In this game, cookies are laid out on a rectangular grid. The cookie in the top-left position is poisoned. The two players take turns making moves; at each move, a player is required to eat a remaining cookie, together with all cookies to the right and/or below (that is all the remaining cookies in the rectangle, in which the first cookie eaten is the top left corner). The loser is the player who has no choice but to eat the poisoned cookie. Prove that if the board is square (and bigger than 1 × 1) then the first player has a winning strategy.
In a card game, your opponent places n monster cards onto the board, the i th of which has hi health points. You in turn have m ≥ n hero cards in your hand, the j th of which deals dj damage per turn. To begin the game, you will choose n heroes from your hand and assign each of them to a different enemy monster. Each turn, your heroes will deal damage equal to their damage power to the opposing enemy. If at any point an opponent’s monster reaches 0 health or less, then it is destroyed. You are given a limited number of turns k to destroy all enemy monsters. Design an algorithm which runs in O(m + n log n) time and determines whether it is possible to assign your heroes in such a way as to destroy all enemy monsters in k turns or fewer First develop a Θ(m log m) time algorithm, then improve it to Θ(m + n log n) Do not write the code, give steps and methods. Explain the steps of algorithm, time complexity, and the logic behind these steps in plain English Input is the number of monsters…
In a card game, your opponent places n monster cards onto the board, the i th of which has hi health points. You in turn have m ≥ n hero cards in your hand, the j th of which deals dj damage per turn. To begin the game, you will choose n heroes from your hand and assign each of them to a different enemy monster. Each turn, your heroes will deal damage equal to their damage power to the opposing enemy. If at any point an opponent’s monster reaches 0 health or less, then it is destroyed. You are given a limited number of turns k to destroy all enemy monsters. Design an algorithm which runs in O(m + n log n) time and determines whether it is possible to assign your heroes in such a way as to destroy all enemy monsters in k turns or fewer First develop a Θ(m log m) time algorithm, then improve it to Θ(m + n log n) Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English input is The number of monsters n, the health…
A hungry mouse wants to eat all four fruits in a maze such as the one below, in as few moves as possible.. At each turn the mouse can move any number of squares in one of the directions up, down, left or right, but it is not allowed to enter (or jump over) any walls (i.e., the black squares). Thus, the mouse moves just like a rook in chess. To eat a fruit, the mouse has to stop at that square. Assume that the maze has 4 fruits, and the size of b xh squares. 1. Give a suitable representatión of the states in this searching problem. 2. How many possible actions can the mouse perform at each move? (1.e., what is the branching factor?)
Can you help me with this code I only need help with two of the parts. I have attached my code in the photo. question that i need help with: the Eight Puzzle consists of a 3 x 3 board of sliding tiles with a single empty space. For each configuration, the only possible moves are to swap the empty tile with one of its neighboring tiles. The goal state for the puzzle consists of tiles 1-3 in the top row, tiles 4-6 in the middle row, and tiles 7 and 8 in the bottom row, with the empty space in the lower-right corner.you will develop two solvers for a generalized version of the Eight Puzzle, in which the board can have any number of rows and columns. A natural representation for this puzzle is a two-dimensional list of integer values between 0 and r · c -1 (inclusive), where r and c are the number of rows and columns in the board, respectively. In this problem, we will adhere to the convention that the 0-tile represents the empty space.tasks: In the TilePuzzle class, write a method…
Can you help me with this code because i am struggling and I don't know what to do with this part: he Eight Puzzle consists of a 3 x 3 board of sliding tiles with a single empty space. For each configuration, the only possible moves are to swap the empty tile with one of its neighboring tiles. The goal state for the puzzle consists of tiles 1-3 in the top row, tiles 4-6 in the middle row, and tiles 7 and 8 in the bottom row, with the empty space in the lower-right corner. In this section, you will develop two solvers for a generalized version of the Eight Puzzle, in which the board can have any number of rows and columns. We have suggested an approach similar to the one used to create a Lights Out solver in Homework 2, and indeed, you may find that this pattern can be abstracted to cover a wide range of puzzles. If you wish to use the provided GUI for testing, described in more detail at the end of the section, then your implementation must adhere to the recommended interface. However,…
The compass gradient operators of size 3x3 are designed to measure gradients of edges oriented in eight directions: E, NE, N, NW, W, SW, S, and SE. i) Give the form of these eight operators using coefficients valued 0, 1 or – 1. ii) Specify the gradient vector direction of each mask, keeping in mind that the gradient direction is orthogonal to the edge direction.
On a chess board of r rows and c columns there is a lone white rook surrounded by a group of opponent's black knights. Each knight attacks 8 squares as in a typical chess game, which are shown in the figure - the knight on the red square attacks the 8 squares with a red dot. The rook can move horizontally and vertically by any number of squares. The rook can safely pass through an empty square that is attacked by a knight, but it must move to a square that is not attacked by any knight. The rook cannot jump over a knight while moving. If the rook moves to a square that contains a knight, it may capture it and remove it from the board. The black knights. never move. Can the rook eventually safely move to the designated target square? The figure illustrates how the white rook can move to the blue target square at the top-right corner in the first sample case. The rook captures one black knight at the bottom-right of the board on its way. Rok nd kight lcoes by Chunen Input The first line…
Problem You have a fence post located at the point (x,y) where a goat is tethered by a rope. You also have a house, which is a rectangle with diagonally opposite corners at the points bottom-left: (x1,y1) and top-right: (x2,y2). You want to pick a length of rope that guarantees the goat cannot reach the house. Determine the minimum distance from the fence post to the house, so that you can make sure to use a shorter rope. Recall that the distance formula is: (x2−x1)2+(y2−y1)2 The input consists of a single line containing six space-separated integer values: x, y, x1, y1, x2, and y2. You are guaranteed that x1<x2 and y1<y2, and that (x,y) is strictly outside the axis-aligned rectangle with corners at (x1,y1) and (x2,y2). Return the minimum distance from the goat’s post to the house as a floating-point value from main(). Learning Objectives Be able to create a program with a lesser template. Be able to calculate the min/max of integers. Be able to write a mathematical…
You are given a 2 by n grid, where the cell on row i column j contains a non-negative number ai,j . You can start at either cell in the lefttmost column, and your goal is to reach either cell in the rightmost column by a sequence of moves. You can move to an adjacent cell (if it exists) in each of the 4 cardinal directions (up,down, left and right). A path achieves a score equal to the sum of values in its cells. Note that a cell which is used twice in a path only counts its value once to the score of that path.Design an algorithm which runs in O(n) time and finds a path of minimum score from the leftmost column to the rightmost column.
Computer Science There is an n × n grid of squares. Each square is either special, or has a positive integer costassigned to it. No square on the border of the grid is special.A set of squares S is said to be good if it does not contain any special squares and, starting fromany special square, you cannot reach a square on the border of the grid by performing up, down,left and right moves without entering a cell belonging to S. 5 3 4 9 4 X 3 6 1 9 X 4 1 2 3 5 - Design an algorithm which receives an arbitrary n × n grid, runs in time poly-nomial in n and determines a good set of squares with minimum total cost.