write a program to solve the puzzle problem below using a programming language of your choice. Run several test cases using different sizes of inputs and record how long it takes for the program to finish. Keep increasing the input size until your computer is unable to calculate the result within one minute.

Cross Sum (also known as Kakuro) is a number puzzle played on an m n grid of black and white squares. White squares form horizontal and vertical lines of two or more adjoining squares. Each horizontal and vertical line is labelled with a number representing its sum. The goal is to place a digit between 1...9 in every white box so that the sum of every line is equal to the label of that line, and so that no number is repeated for any one sum. See Figure 3 for an example. Deciding the solvability of Cross Sum has been shown to be NP-Complete by Takahiro (2001). Takahiro further defines (N,l,L) -CROSS SUM as the same problem except that every line of white has n boxes such that l n L, and each digit placed lies between 1...N. Then (9,2,6) -CROSS SUM is NP-Complete, (N,2,5) -CROSS SUM (with 7 N< ) is NP-Complete,(N,1,3) -CROSS SUM (with 7 N< ) is NP-Complete, (N,l,2) -CROSS SUM is linearly solvable, and (2,l,L) -CROSS SUM isalso linearly solvable. See Takahiro (2001) for further information. We cannot find any other references to Cross Sum. For more information see http://www.pro.or.jp/ fuji/java/puzzle/crosssum/index-eng.html, which details some combinations of numbers that can be used to help find a solution, and lists some example problems and their solutions.

DECISION QUESTION

(Takahiro, 2001) (also see Yato and Seta, 2003): Does the given instance have any configuration of numbers in the white boxes such that (1) the numbers in the white boxes are 1..9, (2) the sum of numbers in any row/column is equal to the corresponding number in the black box, and (3) a number only appears once in any given row/column?