TopCoder problem "NewMagicSquare" used in SRM 351 (Division I Level Three)



Problem Statement

    

You are to populate a 5x5 square with each of the numbers between 1 and 25, inclusive. The numbers in each row must be in increasing order from left to right. Some of the cells are already filled in, but no more than one number per row. You must fill in the remaining cells.

You will be given a String[] square. Each row is given as a space-separated list of cells. Each cell is either a number written with two digits (numbers less than 10 have an additional leading zero) or two '?' characters which represent an empty cell. Your method should return a String[] in the same format, but with all the empty cells filled in. If there are no arrangements possible return an empty String[]. If there are several arrangements possible return the one with the smallest first number in the first row. If there are still several arrangements possible return the one with the smallest second number in the first row, and so on.

 

Definition

    
Class:NewMagicSquare
Method:completeTheSquare
Parameters:String[]
Returns:String[]
Method signature:String[] completeTheSquare(String[] square)
(be sure your method is public)
    
 

Constraints

-square will contain exactly 5 elements.
-Each element of square will contain exactly 14 characters.
-Each element of square will be a space-separated list of cells.
-Each cell will be either a number written with two digits or two '?' characters.
-Each element of square will contain at most one filled cell.
-All numbers in square will be between 1 and 25, inclusive.
-All numbers in square will be distinct.
 

Examples

0)
    
{"?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??"}
Returns: 
{"01 02 03 04 05",
"06 07 08 09 10",
"11 12 13 14 15",
"16 17 18 19 20",
"21 22 23 24 25" }
You are not limited by prefilled cells. The answer is the lexicographically smallest square.
1)
    
{"?? ?? 20 ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? 05 ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??"}
Returns: 
{"01 06 20 21 22",
"07 08 09 10 11",
"02 03 04 05 12",
"13 14 15 16 17",
"18 19 23 24 25" }
2)
    
{"?? ?? ?? ?? ??", 
 "?? ?? ?? ?? 24", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "21 ?? ?? ?? ??"}
Returns: { }
You should place four numbers greater than 21 into the 5th row. There are four such numbers - 22, 23, 24 and 25, but 24 is already used in the second row.
3)
    
{"?? ?? 15 ?? ??", 
 "02 ?? ?? ?? ??", 
 "?? ?? ?? 07 ??", 
 "?? ?? 16 ?? ??", 
 "?? ?? ?? ?? 21"}
Returns: 
{"01 03 15 17 18",
"02 08 09 10 22",
"04 05 06 07 23",
"11 12 16 24 25",
"13 14 19 20 21" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7247

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10675&pm=7247

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Math