Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

The sudoku masters like to create more and more difficult puzzles to entertain themselves. Their newest idea is to modify the classical sudoku puzzle such that instead of the original 9x9 board they need to solve a 16x16 puzzle. A further challenge is that instead of numbers, each cell can now contain an arbitrary (but pre-defined) character.
However validating a puzzle like this by hand is no easy task, thus our objective is to create a program which is able to decide if a full-completed solution is correct or not.

Input

• The first line gives the list of usable characters for that particular test case separated by a single space.
• Each of the next 16 lines contain exactly 16 "entries" separated by a single space character.
• Note: during the exercise the word entry means a value inside a sudoku cell which is an at least 1, at most 5 character long string

Output

The output should be the word VALID if each of the below requirements are fulfilled:
• each character in each of the entries is an element of the set of the usable characters;
• there are exactly 16 different entries (not counting the whitespace which separates the cells) in the sudoku;
• the sudoku is correctly filled, so in every row, column and 4x4 subsquare the 16 entries are appearing exactly once.
Otherwise the output should be the word INVALID.
Note: a subsquare is defined the same as in the "regular" sudoku puzzle with the exception that the length of its sides is now 4 instead of the original 3.

Restrictions

• The full list of usable characters are the numbers 0,1,...,9, small and capital letters of the english alphabet and elements of the set {':', '.', ';', '_'}.
• The list of usable characters for each test case are a subset of the previous set.
• sudokui,j is a min. 1, max. 5 long string which consists of characters from the full list of characters for each 0 ≤ i,j ≤ 15.

Example

Input:
1. `0 1 2 3 4 5 6 7 8 9 A B C D E F a b x y :`
2. `8 F 6 5 12 A 7 D 4 9 C 3 2 B 0 EF29`
3. `12 4 2 3 B C EF29 9 0 6 8 D 5 F 7 A`
4. `C 7 A 9 0 4 2 3 B EF29 F 5 6 D 8 12`
5. `B 0 D EF29 F 5 8 6 7 A 2 12 4 3 C 9`
6. `2 6 4 7 D 8 9 B C 0 EF29 F 3 A 12 5`
7. `3 9 5 12 6 0 A F 2 8 B 4 C 7 EF29 D`
8. `F D 8 0 C 12 3 EF29 5 7 A 9 B 6 4 2`
9. `A B EF29 C 2 7 5 4 D 3 12 6 9 0 F 8`
10. `D 5 9 4 EF29 3 F 8 12 C 7 A 0 2 6 B`
11. `7 2 B A 9 6 D C EF29 4 0 8 F 12 5 3`
12. `0 C 3 F 4 B 12 A 6 5 D 2 EF29 8 9 7`
13. `6 EF29 12 8 5 2 0 7 9 F 3 B D C A 4`
14. `EF29 12 7 6 3 F 4 2 A D 9 C 8 5 B 0`
15. `9 8 0 2 A D 6 5 F B 4 7 12 EF29 3 C`
16. `5 A C D 8 9 B 0 3 12 6 EF29 7 4 2 F`
17. `4 3 F B 7 EF29 C 12 8 2 5 0 A 9 D 6`
1. `VALID`
2. `    `