首页 >
> 详细

CS 4613 E. K. Wong

Project 2: Futoshiki Spring 2020

Total number of points = 100.

Project Description: Design and implement a program to solve 5 × 5 Futoshiki puzzles. The

rules of the game are:

• The game board consists of 5 × 5 cells. Some of the cells already have numbers (1 to 5)

assigned to them and there are inequality signs (< or >) between some of the cells (See

Figure 1.)

• The goal is to find assignments (1 to 5) for the empty cells such that the inequality

relationships between all pairs of adjacent cells with an inequality sign between them are

satisfied. In addition, a digit can only appear once in every row and column; that is, the

digits in every row and column must be different from each other (See Figure 2.)

Figure 1. Initial game board Figure 2. Solution

As the first step in your program, use Forward Checking to reduce the domain of empty cells, based

on the values of cells that already have a number. If an empty cell has only one value left in its

domain after domain reduction, you can repeat Forward Checking on the cell’s neighbors, and so

on. If any empty cell has an empty domain after applying Forward Checking, then the puzzle does

not have a solution and the program can stop here. Next, use the Backtracking Algorithm for CSPs

(in Figure 5 on page 3) to solve the puzzle. Implement the function SELECT-UNASSIGNEDVARIABLE in the algorithm by using the most constrained variable (or minimum remaining values)

heuristic, and in case of a tie, use the most constraining variable (or degree) heuristic as tie breaker.

If there are more than one variables left after applying the most constraining variable heuristic, you

can arbitrarily choose a variable. There is no need to implement the least constraining value

heuristic in the ORDER-DOMAIN-VALUES function; instead, simply order the domain values in

increasing order (from 1 to 5.) To make it easier for you to implement the program, you do not

have to implement the INFERENCE function inside the Backtracking Algorithm.

Your program will read in values from an input text file and produce an output text file that contains

the solution. The input file contains 16 rows (or lines) of integers. The first five rows contain the

initial cell values of the game board, with each row containing five integers, ranging from 0 to 5.

Digit “0” indicates a blank cell. This is followed by a blank line. The next five rows contain the

inequalities between horizontally-adjacent cells. A value of 0 indicates no inequality between two

cells. This is followed by a blank line. The next four rows contain the inequalities between

5

2

1

2 3 1 4 5

3 5 2 1 4

5 1 4 3 2

1 4 5 2 3

4 2 3 5 1

CS 4613 E. K. Wong

Project 2: Futoshiki Spring 2020

vertically-adjacent cells. Again, a value of 0 indicates no inequality between two cells. The input

file for the initial game board in Figure 1 is as shown in Figure 3 below. The output file contains

five rows (or lines) of integers, representing the solution. Each row contains five integers, ranging

from 1 to 5, separated by blanks. The output file (solution) for the initial game board in Figure 1 is

as shown in Figure 4 below.

Testing your program: I will provide three input test files on NYU Classes for you to test your

program.

Recommended languages: Python, C++/C and Java. If you would like to use a different language,

send me an email first.

Submit on NYU Classes by due date:

1. A text file that contains the source code. Put comments in your source code to make it easier

for someone else to read your program. Points will be taken off if you do not have comments

in your source code.

2. The output text files generated by your program. Name your output files Output1.txt,

Output2.txt and Output3.txt.

3. A PDF file that contains instructions on how to run your program. If your program requires

compilation, instructions on how to compile your program should also be provided. Also, copy

and paste the output text files and your source code onto the PDF file (to make it easier for us

to grade your project.) This is in addition to the source code file and output files that you have

to submit separately (as described in 1 and 2 above.)

0 0 0 0 0

0 0 0 0 0

5 0 0 0 0

0 0 0 2 0

0 0 0 0 1

0 > 0 0

0 0 0 0

0 0 > 0

0 0 0 0

0 0 < 0

^ ^ 0 0 0

0 0 0 0 0

0 0 0 0 0

0 v 0 0 0

Figure 3. Input file for the initial game board in Figure 1. Digit 0 indicates a blank cell. > and

< are the greater than and less than characters on the keyboard. ^ is upper case 6 and v is the lower

case letter v on the keyboard.

CS 4613 E. K. Wong

Project 2: Futoshiki Spring 2020

2 3 1 4 5

3 5 2 1 4

5 1 4 3 2

1 4 5 2 3

4 2 3 5 1

Figure 4. Output file containing the solution for the initial game board in Figure 1.

Figure 5. The Backtracking Algorithm for CSPs.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Final Projects 1 2020-09-20
- Comp9021 Assignment 2 2020-09-20
- Mathematical Question 2020-09-20
- Cs825 Assignment 4 2020-09-20
- Ipal Programming In R Week 3 2020-09-20
- Programs作业代写、C++编程语言作业调试、C/C++实验作业代做、代 2020-09-20
- 代写data留学生作业、代做algorithms作业、C++程序语言作业调试 2020-09-20
- Canvas留学生作业代写、代做c/C++程序语言作业、代写c/C++课程设 2020-09-19
- Comp20008作业代做、代写data Processing作业、Pyth 2020-09-19
- Cits 3004作业代写、Python，C++程序设计作业调试、Java语 2020-09-19
- Comp2100作业代做、代写programming作业、C++程序语言作业 2020-09-19
- 代做data留学生作业、代写networks课程作业、代做python，Ja 2020-09-19
- 代写comp20003作业、Dataset作业代做、代写c/C++语言作业、 2020-09-19
- 代写el873 /代做留学生matlab实验作业 2020-08-31
- 代写math4007代做asp实验作业、Asp编程代写 2020-08-31
- 代做com6515代做留学生matlab语言程序 2020-08-31
- 代做com1005-Assignment 3代做java程序、Java实验代 2020-08-31
- 代写mast30013-Assignment 3代写留学生js... 2020-08-31
- 代写cse105代做留学生r语言、R语言代做留学生 2020-08-31
- 代做ifn647-Assignment 2代做留学生pytho... 2020-08-31