Jenny is obsessed with Magic Squares. In case you have forgotten, a Magic Square contains all integers from to arranged so that every row, column, and diagonal adds up to the same number. The earliest known Magic Square is the Lo Shu Square (shown at right) discovered in China more than 2600 years ago. There are only other Magic Squares, all obtained by rotation and reflection of the original Lo Shu Square:
Jenny's friends have learned not to leave their Sudoku puzzles unattended when she's around. She will take any fully or partially completed Sudoku puzzle she finds and play a game of her own invention called "Lo Shudoku", in which she transforms the Sudoku board into a set of nine Magic Squares using a restricted set of moves. Then she writes down a "Lo Shudoku" square in the margin that shows the number of moves she used for each of the nine squares:
Original Sudoku Board
When she plays Lo Shudoku, Jenny works on each of the nine squares, turning them into Magic Squares one by one. When transforming a square, she always uses as few moves as possible, and she always proceeds in two separate phases:
- First, she fills in all the blank spaces with the remaining integers from to . Each number filled in counts as one move.
- Once all the blanks are filled, she repeatedly swaps pairs of integers until she has a Magic Square. Each swap counts as one move.
When she has transformed each square in this way, she produces her Lo Shudoku square showing the number of moves she used to create each of the nine Magic Squares. In the example above, the Lo Shudoku square shows that the top left Magic Square took moves, the ones to its right and beneath it took moves each, and so on.
Here is one way that Jenny could transform top right square from the example above:
In phase one she fills in the and first, then in phase two she makes swaps to complete the Magic Square. This is not the only way she could have made a Magic Square from the original numbers, but there is no shorter path to a Magic Square than this. She records this minimum number of moves in the top right corner of her Lo Shudoku square.
The input contains test cases. Each test case will consist of lines of digits, representing a Sudoku board. The Sudoku board might be completely filled in, or it might be partially filled in. If it is partially filled in, the blank spaces will be represented as zeros. Your program must output a Lo Shudoku square for each Sudoku board given. For ease of reading, each Lo Shudoku square should be followed by
010596873 900413006 005872419 172040090 863259000 549060038 726984351 300100004 491635782 329847651 748561392 156392478 514726839 673985124 892413765 965138247 287654913 431279586 206004900 040900100 900800002 700045090 064389270 090120004 400003008 005008020 003500407 093006500 652830070 007500036 000060108 000908000 501040000 140002600 060097315 009600280 000050086 649300070 000640100 030021009 106000708 400980030 008072000 060003852 250060000
856 577 467 --- 655 443 525 --- 787 878 888 --- 688 988 977 --- 888 787 778 ---
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org