AI THEORY

Answer to q1

Description of the grid: As specified in the problem the 7x8 grid and the location of
Goal State and special states (W and X) can be represented as given below. Note that
the special cell denoted by L in the grid as represented as state X in the grid given
below:

Answer to Q(1): PEAS description

PEAS stands for Performance, Environment, Actuators and Sensor. The PEAS

description for given problem is as follows:

Performance: Performance factors for the problem include reaching the goal state G,
reach G with minimum possible cost by preferring down or left moves to up and right
moves, avoid X cells (as the agent will be taken to initial state) and prefer W Cells (as
the agent will be teleported to a cell adjacent to goal state G).
Environment: The 7x8 grind of cells describe the problem environment. The agent
can navigate through the grid by moving left, right, up or down, one cell at a time,
except at edges and corners (where the move will be restricted such that the agent will
not move out of the 7x8 grid). There is goal cell marked G. Some cells are marked X,
which teleports the agent to the start state. Some cells are marked W, which teleport
the agent to an adjacent cell of the goal state.

Actuators: Actuators are the tools used by the agent for navigation by which the
agent can can turn left or right and then move one cell forward at a time.

Sensors: The agent can sense the cell number in terms of row and column numbers. It
can also sense whether the cell is a goal state or cells marked with a ‘W’ or ‘X’

Answer to Q(2): Task Environment

The task environment of the problem consists of an 7x8 grid of cells. The agent can
navigate through the grid by moving left, right, up or down, one cell at a time, except
at edges and corners (where the move will be restricted such that the agent will not
move out of the 7x8 grid). There is goal cell marked G. Some cells are marked X,
which teleports the agent to the start state. Some cells are marked W, which teleport
the agent to an adjacent cell of the goal state. The task environment of the problem is
characterised by:

Complete – The task environment of the problem is complete as the 7x8 grid and their
elements are well-defined.

Fully-observable – The task environment of the problem is fully-observable as the

7x8 grids, initial state, final state, types of moves and their costs, other favourable and
unfavourable components of the environment, etc., are well-defined.

Non-competitive – The task environment of the problem is non-competitive as there

exist only a single agent.

Static – The task environment of the problem is static as the 7x8 grids, initial state,
final state, types of moves and their costs, other favourable and unfavourable
components of the environment, etc., are well-defined in advance and no dynamic
element exist in the environment.

Discrete – The task environment of the problem is discrete as the each step in the
environment can be taken based the current position and not depends on the previous
history. That is the given task environment is not continuous.
Deterministic – The task environment of the problem is deterministic as there is no
element of uncertainty in the environment that hinders reaching the goal state.

Answer to Q(3): Search Problem

To enable the search, the given problem can be stated as a state space search
representation problem that specifies the State Space, Initial State(s) and Goal
State(s).

State Space: The state space of the problem consists of the set of all cells that can
reached from the cell marked as A. The state space can be represented by the ordered
pair G(x,y), where 7<=x>=1 and 8<=y>=1. X is the row that ranges from 1..7 and y is
the column that ranges from 1..8. The examples of the states include G(1,1), G(1,2),
G(1,3) … G(1,8), G(2,1), G(2,2), … G(7,8).

Initial State: The Cell Marked as A in 7x8 Grid (G), that G(4,8)=A

Goal State: The Cell Marked as G in 7x8 Grid (G), that is, G(1,1)=A

Search Task: The task can now be modelled as a search problem. The task is to
search through the state space starting from the initial state until the goal state is
reached.

Answer to Q(4): Branching Factor

The average branching factor of the problem can be calculated as follows:

Total numbers states = 56 (as there are 56 cells in the grid)

Cells with 4 moves (all inner cells except the edges and corner cell) = 30 (with
30*4=120 moves)

Cells with 3 moves (all edges cells except the corner cell) = 22 (with 22*3=66 moves)

Cells with 2 moves (all corner cell) = 4 (with 4*2=8 moves)

Total moves = 120 + 66 + 4 = 190

Branching factor = Total Move/Total States = 190/56 = 3.39 branches per state

Answer to Q(5): BFS or DFS on this problem

As the state space and the branching factor of the given problem are limited, the given
problem does not cause any combinatorial explosion. Since there exist no chance for
any combinatorial explosion in the given problem, the DFS and BFS search
algorithms can return solutions to the given problem. However, if the size of grid
increases to a large number, both DFS and BFS may fail to return a solution and may
breakdown as it cannot handle combinatorial explosion. In the given case, BFS will
guarantee to return an optimal solution as it proceeds to further level in depth only
after exploring all the nodes the current level. However, in the given environment,
DFS may fail to return an optimal solution, as it explores further levels in depth before
exploring other nodes in the current level.

Answer to Q(6): Path that Will Be Discovered by UCS

If the search is considered as a Uniform Cost Search (UCS), the explored states in
UCS will be as follows. As shown in the tree, the cost of reaching from the state A to
state G is 16.5. The path explored is depicted as thick GREEN LINES.
Answer to Q(7): BFS & UCS

Answer to q2:
Executioner Sudoku is a riddle that joins components of sudoku and kakuro. In spite of the name,
the more straightforward executioner sudokus can be simpler to understand than ordinary
sudokus, contingent upon the solver's ability at mental number-crunching; the hardest ones,
nonetheless, can take hours to break.

An ordinary issue is appeared on the right, utilizing hues to characterize the gatherings of cells.
All the more frequently, puzzles are imprinted clearly, with slender spotted lines used to layout
the "confines".

The goal is to fill the framework with numbers from 1 to 9 out of a way that

the accompanying conditions are met:

* Each line, segment, and nonet contains each number precisely once.

* The aggregate of all numbers in an enclosure must match the modest number printed

in its corner.

* No number shows up more than once in a pen. (This is the standard guideline

for executioner sudokus, and suggests that no confine can incorporate more

than 9 cells.)

Complexity- In the event that we are to illuminate Sudoku utilizing a bruteforce strategy, our
calculation would need to attempt each accessible number over every vacant cell. Such a
calculation would have a runtime unpredictability of O(N^(N²)), where n is the size of the
Sudoku puzzle. For a 9x9 Sudoku puzzle (N = 9), the calculation would perform 2*10⁷⁷ tasks to
discover an answer. That would not be commonsense. Practically speaking, the runtime would
differ as per the trouble of the riddle itself and the quantity of choices for each unfilled cell. For
instance, a 17-piece of information puzzle with slanting evenness is one of the hardest to tackle
because of an enormous number of up-and-comers and branches.

In 'Executioner X', an extra standard is that every one of the long diagonals

contains each number once.

The yield is:

215647398

368952174

794381652

586274931

142593867

973816425

821739546

659428713

437165289

In this way, Here you go...

Answer to q3
raffic control signals are devices placed along, beside, or above a roadway to guide,
warn, and regulate the flow of traffic, which includes motor vehicles, motorcycles,
bicycles, pedestrians, and other road users.

RED—A red signal light means STOP.

A right turn can be made against a red light ONLY after you stop and yield to
pedestrians and vehicles in your path. DO NOT turn if there is a sign posted for NO
TURN ON RED.

RED ARROW—A red arrow means STOP until the green signal or green arrow
appears. A turn may not be made against a red arrow.

FLASHING RED—A flashing red signal light means exactly the same as a stop sign:
STOP! After stopping, proceed when safe and observe the right-of-way rules.
YELLOW—A yellow signal light warns you that the red signal is about to appear.
When you see the yellow light, you should stop, if you can do so safely. If you can't
stop, look out for vehicles that may enter the intersection when the light changes.

FLASHING YELLOW—A flashing yellow signal light warns you to be careful. Slow
down and be especially alert.
YELLOW ARROW—A lighted red arrow is about to appear. Stop if you are not
already in the intersection.

GREEN—A green light means GO, but you must first let any vehicles, bicycles, or
pedestrians remaining in the intersection get through before you move ahead.