Practice Optimization with the exercise "Killer Sudoku Extreme Challenge"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Optimization

Statement

Goal

This puzzle builds on the concepts explored in the Killer Sudoku Solver puzzle by @odaxav. Please consider solving that puzzle before solving this one.

https://www.codingame.com/training/medium/killer-sudoku-solver

In this challenge, the goal is to generate a 9x9 grid of integers by solving Killer Sudoku puzzles. Your 9x9 answer grid is initially filled with zeros. Each time you solve a Killer Sudoku puzzle, add the number found in each Killer Sudoku cell to the the same cell in the answer grid. After solving every Killer Sudoku puzzle, output the 9x9 matrix of integers found in your answer grid.

As the number of puzzles increases, speed and efficiency become critical. All Killer Sudoku puzzles in this challenge begin with empty grids. None of the puzzles have any numbers identified to start. The only input you have to work with is the cage layout and the cage values.

Here are the 4 rules of Killer Sudoku:
1. Each row must have numbers from 1 to 9 with no repetition
2. Each column must have numbers from 1 to 9 with no repetition
3. Each region (3x3 square) must have numbers from 1 to 9 with no repetition
4. Each cage's cell numbers must sum to the cage value, with no repetition among numbers

The cages are represented in a 9x9 grid with an identifier from a-zA-Z. For this challenge, each puzzle's cages have been compressed into a single line by concatenating the rows of the 9x9 cage layout grid. The starting number grids have been omitted from this challenge since they are all empty.

Input

Line 1: An integer numPuzzles for the number of Killer Sudoku puzzles to be solved.

Next numPuzzles lines: cageID for each of the 81 cells in the corresponding Killer Sudoku puzzle. Each character of the input line is mapped to the Killer Sudoku puzzle from left to right and then top to bottom.

Next numPuzzles lines: The list of the cages with the sum of the cells cageID=cageSum

Note: Cage layouts and cage sums correspond to each other in the same order they appear in the input.

Output

9 lines: Sums of all solutions to the Killer Sudoku puzzles. (separated by spaces)

Constraints

Each Killer Sudoku puzzle in each test case has only one solution.

Example

Input

1
abcccdeeefbbgddhiefjggdkhilfjmgkknilooppqqnrrsotuvqnnwxxtuyyzzABCDDEFzAABBDGGGzzz
a=2 b=22 c=12 d=22 e=23 f=8 g=16 h=6 i=18 j=13 k=16 l=8 m=5 n=20 o=12 p=11 q=21 r=10 s=7 t=6 u=9 v=6 w=5 x=15 y=4 z=28 A=17 B=15 C=3 D=18 E=4 F=2 G=21

Output

2 6 8 1 3 5 7 9 4
1 9 7 4 2 6 5 8 3
4 5 3 7 9 8 1 6 2
3 8 5 2 7 1 9 4 6
9 1 6 5 8 4 2 3 7
7 2 4 3 6 9 8 1 5
8 7 2 6 1 3 4 5 9
5 3 9 8 4 2 6 7 1
6 4 1 9 5 7 3 2 8

Solve it

A higher resolution is required to access the IDE