TopCoder problem "SillySudoku" used in SRM 315 (Division I Level Two)



Problem Statement

    This problem statement contains images that may appear incorrectly or not appear at all in some plugins. In that case, use the standard view in the arena to see it correctly.

Little Johnny has just learned about Sudoku, but finds these puzzles annoyingly hard, so he plays a much simpler version. He plays on a 4x4 table where each cell is either empty or contains a single number between 1 and 4, inclusive. The purpose of the game is to fill the entire table with numbers so that each row, each column, and each 2x2 square (labeled A, B, C, and D in the picture below) contains each of the numbers 1, 2, 3, and 4 exactly once.

You are given a String[] board. The jth character of the ith element of board represents the cell at row i, column j. The '-' character represents an empty cell. Cells that are filled with numbers are represented by the characters '1', '2', '3', and '4'. Return the number of different ways this puzzle can be solved.

 

Definition

    
Class:SillySudoku
Method:countWays
Parameters:String[]
Returns:int
Method signature:int countWays(String[] board)
(be sure your method is public)
    
 

Constraints

-table will contain exactly 4 elements.
-Each element will have exactly four characters.
-Each character will be '-', '1', '2', '3' or '4'.
 

Examples

0)
    
{"--21", 
 "--34", 
 "2143", 
 "3412"}
Returns: 1
This puzzle has only one solution: 

4321
1234
2143
3412




Each row contains 1, 2, 3, and 4: 



 4321

 1234

 2143

 3412




Each column contains 1, 2, 3, and 4: 



 4  3  2  1
 1  2  3  4
 2  1  4  3
 3  4  1  2




And each of the four 2x2 squares contains 1, 2, 3, and 4: 



 43  21
 12  34

 21  43
 34  12
1)
    
{"--1-", 
 "--1-", 
 "----", 
 "----"}
Returns: 0
This is a clearly invalid puzzle since it contains two 1s in the upper right 2x2 square.
2)
    
{"1---", 
 "-42-", 
 "-3--", 
 "----"}
Returns: 3
3)
    
{"1---", 
 "--1-", 
 "-1--", 
 "---1"}
Returns: 18
4)
    
{"1---", 
 "----", 
 "----", 
 "----"}
Returns: 72

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9995&pm=6629

Writer:

Cosmin.ro

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Brute Force