Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3411/9814 Artificial Intelligence Term 1, 2024

Assignment 1 – Bridge Puzzle

Due: Friday 15 March, 10pm

Marks: 12% of final assessment

Specification

This project is based on a popular puzzle, variously known as "Hashiwokakero", "Hashi" or "Bridges". You will need to write a program to solve this puzzle, and provide a brief description of the algorithm and data structures you have used. The  input to your program will be a rectangular array of numbers and dots, for example:

Each number represents an "island", while the dots represent the empty space (water) between the islands. Numbers larger than 9 are indicated by 'a' (10), 'b' (11) or 'c' (12). The aim is to connect all the islands with a network of bridges, satisfying these rules:

.1...6...7....4.4.2.

1. all bridges must run horizontally or vertically

2. bridges are not allowed to cross each other, or other islands

3. there can be no more than three bridges connecting any pair of islands

4. the total number of bridges connected to each island must be equal to the number on the island

For example, after reading the 10-line input above, your program might produce this output: Note that single bridges are indicated by the characters '-' or '|', pairs of bridges by '=' or '"' and triples by 'E' or '#', depending on whether they run horizontally or vertically. Water between bridges and islands is indicated by space characters ' '.

In some cases, there may be many solutions, in which case your program should only print one solution. More details about the puzzle can be found on this Wikipedia page. Note, however, that our version allows up to 3 bridges instead of 2; also, we do not insist that the entire graph be connected.

1---6EEE7====4=4=2

4-2" 2 " 3E8EEE6 2

# |2 " "   "   # "

5EcE7EEaEa==5"6EE8=5

" #    " #  #2#    |

" #5===9Ea--8=bE8E4|

4=5#   " #  " # " |3

#2==4 #1-5 # 2 |"

2=7=4===7=2" 5===3"

4==3-1 2

Tools

An executable file called is provided in the tools directory which can be used to generate sample data of any specified size (type for details). Another executable   called is also provided, to help you test the validity of your solutions (see FAQ for details).  bridgen  bridgen -help  bridgecheck

Questions

At the top of your code, in a block of comments, you must provide a brief answer (one or two paragraphs) to this Question:

Briefly describe how your program works, including any algorithms and data structures employed, and explain any design decisions you made along the way.

Language Options

You are free to write the code in a language of your choosing.

If you write in C, C++, or another compiled languge, your program will be invoked by:

You should submit your source files (no object files) as well as a which, when invoked with the command , will produce an executable called

./hashi  Makefile  make  hashi