Sudoku is a hot intellectual game nowadays. It is generally believed that its origin is "Latin square", which was invented by the great mathematician Euler in 1783.
As shown in Figure [1.jpg], the lattice of 6x6 is divided into six parts (distinguished by different colors in the figure), each part contains six lattices (hereinafter referred to as grouping).
At the beginning, the letters (one of ABCDEF) had been filled in in some small boxes. You need to fill in the letters in all the remaining cells.
The following constraints must be met after all fillings are completed:
-
Only one of the letters A, B, C, D, E and F is allowed.
-
In the six cells of each line, the letters should not be repeated.
-
The letters in the six boxes in each column cannot be repeated.
-
Each group (see the different color representations in the figure) contains six cells in which the filled letters cannot be repeated.
For the convenience of representation, we use the following 6-order matrix to represent the grouping situation of graph [1.jpg] (group number is 0-5):
000011
022013
221113
243333
244455
445555
Use the following data to show how the existing letters are filled in:
02C
03B
05A
20D
35E
53F
Obviously, the first list shows the line number, the second list shows the column number, and the third list shows the filled letters. Line and column numbers are calculated from 0.
A feasible way to fill in this question (the only answer to this question) is as follows:
E F C B D A
A C E D F B
D A B E C F
F B D C A E
B D F A E C
C E A F B D
Your task is to write a program to solve the general Latin block problem. If you have multiple solutions, you need to find all the solutions.
[Input and output format requirements]
The user first enters six rows of data to represent the grouping of Latin squares.
Then the user enters an integer n (n < 36) to indicate the number of rows that follow.
Then enter n rows of data, each representing a pre-filled letter.
The program outputs all possible solutions (the order between solutions is not important).
Each unoccupied 7 lines.
That is, first an integer is output to indicate the sequence number of the solution (starting from 1), and then a 6x6 alphabetic matrix is output to represent the solution.
The letters of the solution are separated by spaces.
If no solution satisfies the condition, the output is "unsolvable"
For example, user input:
000011
022013
221113
243333
244455
445555
6
02C
03B
05A
20D
35E
53F
Then program output:
1
E F C B D A
A C E D F B
D A B E C F
F B D C A E
B D F A E C
C E A F B D
Again, user input:
001111
002113
022243
022443
544433
555553
7
04B
05A
13D
14C
24E
50C
51A
Then program output:
1
D C E F B A
E F A D C B
A B F C E D
B E D A F C
F D C B A E
C A B E D F
2
D C E F B A
E F A D C B
A D F B E C
B E C A F D
F B D C A E
C A B E D F
3
D C F E B A
A E B D C F
F D A C E B
B F E A D C
E B C F A D
C A D B F E
4
D C F E B A
B E A D C F
A D C F E B
F B E A D C
E F B C A D
C A D B F E
5
D C F E B A
E F A D C B
A B C F E D
B E D A F C
F D B C A E
C A E B D F
6
D C F E B A
E F A D C B
A B D F E C
B E C A F D
F D B C A E
C A E B D F
7
D C F E B A
E F A D C B
A D B F E C
B E C A F D
F B D C A E
C A E B D F
8
D C F E B A
F E A D C B
A D B C E F
B F E A D C
E B C F A D
C A D B F E
9
D C F E B A
F E A D C B
A F C B E D
B D E A F C
E B D C A F
C A B F D E
[Attention]
Please debug it carefully! Your program only has the chance to score if it runs correctly!
The input data used in marking papers may be different from the sample data given in the paper.
Please write all the functions in the same file, after debugging, copy them to the "Answer. txt" of the corresponding title under the "Candidate Folder".
Do not copy relevant engineering documents.
Source code cannot use APIs such as drawing, Win32 API, interrupt calls, hardware operations, or operating system-related APIs.
STL class libraries are allowed, but non-ANSI c++ standard class libraries such as MFC or ATL cannot be used.
For example, you can't use CString type (belonging to MFC class library); for example, you can't use randomize, random function (not belonging to ANSI C++ standard)
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static int[][] map = new int[6][6];
public static char[][] value = new char[6][6];
public static int[][] group = new int[6][6];
public static int[][] ring = new int[6][6];
public static int[][] row = new int[6][6];
public static ArrayList<String> list = new ArrayList<String>();
public void init() {
for(int i = 0;i < 6;i++) {
for(int j = 0;j < 6;j++) {
value[i][j] = '-';
group[i][j] = -1;
ring[i][j] = -1;
row[i][j] = -1;
}
}
}
public boolean check(int step, int i) {
int x = step / 6;
int y = step % 6;
if(group[map[x][y]][i] == -1 && ring[x][i] == -1 && row[y][i] == -1
&& value[x][y] == '-')
return true;
return false;
}
public void dfs(int step) {
if(step == 36) {
StringBuilder temp = new StringBuilder("");
for(int i = 0;i < 6;i++) {
for(int j = 0;j < 6;j++) {
temp.append(value[i][j]);
if(j != 5)
temp.append(" ");
}
if(i != 5)
temp.append("\n");
}
if(!list.contains(temp.toString()))
list.add(temp.toString());
return;
} else {
for(int i = 0;i < 6;i++) {
int x = step / 6;
int y = step % 6;
if(check(step, i)) {
group[map[x][y]][i] = 1;
ring[x][i] = 1;
row[y][i] = 1;
value[x][y] = (char) ('A' + i);
dfs(step + 1);
group[map[x][y]][i] = -1;
ring[x][i] = -1;
row[y][i] = -1;
value[x][y] = '-';
}
if(value[x][y] != '-')
dfs(step + 1);
}
}
}
public void getResult(String[] M, String[] P) {
init();
for(int i = 0;i < M.length;i++)
for(int j = 0;j < M[i].length();j++)
map[i][j] = M[i].charAt(j) - '0';
for(int i = 0;i < P.length;i++) {
int x = P[i].charAt(0) - '0';
int y = P[i].charAt(1) - '0';
int z = P[i].charAt(2) - 'A';
ring[x][z] = 1;
row[y][z] = 1;
group[map[x][y]][z] = 1;
value[x][y] = P[i].charAt(2);
}
dfs(0);
if(list.size() == 0) {
System.out.println("unsolvable");
return;
}
for(int i = 0;i < list.size();i++) {
System.out.println((i + 1));
System.out.println(list.get(i));
}
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
String[] M = new String[6];
for(int i = 0;i < 6;i++)
M[i] = in.nextLine();
int n = in.nextInt();
in.nextLine();
String[] P = new String[n];
for(int i = 0;i < n;i++)
P[i] = in.nextLine();
test.getResult(M, P);
}
}