Project 4 Solution

Write a C program project4.c that operates as follows. First read two command-line arguments which are the names of an input file and an output file, respectively. Next read from the input file an integer value N ≤ 100, followed by the elements of a 2- dimensional array with N rows and N columns such that each array element is in the range from 0 to N.

The goal is to replace each 0 element with some value in the range from 1 to N such that all the following conditions will be satisfied:




Each row contains each distinct integer from 1 to N.



Each column contains each distinct integer from 1 to N.



Each longest diagonal (there are two with length N) contains each distinct integer from 1 to N.



Your program must not modify any of the non-0 elements, because these are constraints that restrict the possible solutions.

Your program will search for all possible solutions and count the number of distinct solutions. Hint: use recursion to search for all the solutions. Choose some 0 element, try replacing it with each value from 1 through N, and then call recursively to continue the search. For efficiency, prune the search whenever a chosen value would cause a violation that prevents obtaining a solution (due to a repeated non-0 value in the same row or column or longest diagonal). So your recursive function will call itself recursively at most N times, and it will not make any recursive calls if no 0 elements remain.

Finally your program will write to the output file the number of distinct solutions, followed by any one solution (unless the count is 0). So your program will need to remember one of the solutions that it finds during the search.

Motivation: The problem described here is similar to solving a magic square or Sudoku puzzle or many other similar kinds of puzzles. (An element with value 0 represents a location that is currently blank.) Writing the program is also an excellent way to practice using both 2-dimensional arrays and recursion.

Examples: Run the program by using a command with this format: ./a.out input1.txt output1.txt




Input1


Output1


(only one solution exists for this input)
4
0
0 3
1
4 2
3


1
1


0
2
0 0
3
2 4
1


0
0
3 0
4
1 3
2


2
0
0 4
2
3 1
4





Input2
Output2
Output2’
(there are two solutions for this input)
4
2
2


1000
1342
1423


0200
4213
3241


0030
2431
4132


0004
3124
2314





Input3








Output3
Output3’
(also 46 more solutions not shown here)
5










48
48


00010


23415
54312


01000


31542
41235


00001


54321
23451


00100


42153
35124


10000


15234
12543


Input4








Output4
(no possible solutions for this input)
6
0
0
0
0
4
0




1






0
2
0
0
6
0






0
0
3
2
0
0






0
0
5
4
0
0






0
1
0
0
5
0






3
0
0
0
0
6












Please carefully read the following requirements:




You must do your own work. You must not borrow any code from any other person, book, website, or any other source. You also must not share your code with any other person, or post it on any website. We run plagiarism detection software on every project. So if you violate these rules, you may receive an invitation to the dean’s office to discuss the penalties for academic misconduct.



Make sure your program runs properly on the cs-intro.ua.edu server. Your program will be graded on that system using this command: gcc project4.c –Wall –lm –std=c99. In particular, make sure your program initializes the values of all variables when they are declared or allocated. Otherwise it might behave differently on Linux than it does on a PC or Mac.



Compress your project into a zip file that contains your C program source file. Right-click (or secondary click) on your project directory, and then (depending on your operating system) select either the Compress option or Send To → Compress from the popup menu. Finally upload your .zip file that contains your .c file for this project to Blackboard.



If you violate the above requirements such that it breaks our grading script, your project will be assessed a significant point deduction, and extreme or multiple violations may cause the project to be considered ungradable.



Every semester many students lose some points because they don’t follow all the instructions. So please read and follow all the project specifications precisely to prevent losing points unnecessarily. If anything is unclear, please ask for clarification well before the project is due. Please pay particular attention to input and output formats.



Submit your project on Blackboard by the due date (11:59pm Friday). There is a grace period of 24 hours (until 11:59pm Saturday). Projects submitted on Sunday will be assessed a late penalty of 5% per hour. No projects will be accepted after Sunday. Once it is graded, your project score will be posted on Blackboard and the results of the grading script will be sent to your Crimson email account.
Double-check and triple-check your submission when you submit it. Errors discovered later cannot be fixed and resubmitted after the project is graded. Projects will not be re-graded unless an error is found in the grading script or in the input/output files that are used during grading.