I am looking for strategies for creating a puzzle with a unique solution, and ways of testing for uniqueness.
Specifically, I'm trying to create cross sums puzzles. How can you create one with a unique solution? The images show a small cross sum with two solutions:
If I can find a way of creating a seemingly unique solution, then how can I test for uniqueness? With cross sums the brute force approach would be to try each number permutation, correct? and on a larger puzzle this may take a long time.
Edit: Okay, thank you for the input so far! @Prem and others. Going off the part (A) that Prem offered I decided to create independent equations. So I wrote some functions to help me out. The functions create a system of independent equations by arbitrarily creating bit strings with the conditions that, the string is 9 in length, there can only be 1-9 in a traditional cross-sums and that numbers do not repeat in a string and that each string is different. Here are the java functions:
// CLASS PieceMaker
// Creates bitstrings length of 9
public String[] independentEquations(int count) {
String[] equations = new String[count];
Arrays.fill(equations, "0");
for(int itr=0;itr String equation=""; boolean loop=false;
do{ equation=""; loop=false;
for(int itr2=0;itr2<9;itr2++){
Integer temp=generator.nextInt(2);
equation+=temp.toString();
}
for(int itr3=0;itr3 }while(loop);
equations[itr]=equation;
}
return equations;
}
// Makes readable equations
public String[] turnIntoSumsString(String[] independentEquations) {
String[] temp = new String[independentEquations.length];
Arrays.fill(temp, "");
for(int itr=0;itr for(int itr2=0;itr2 if(independentEquations[itr].substring(itr2, itr2+1).equals("0")){temp[itr]+="";};
if(independentEquations[itr].substring(itr2, itr2+1).equals("1")){temp[itr]+=" + " + (itr2+1);};
}
}
independentEquations=temp;
return independentEquations;
}
Called from main:
// CLASS main
// A system of 15 independent equations
PieceMaker pm = new PieceMaker();
String[] independentEquations = pm.independentEquations(15);
for(int itr=0;itr<15;itr++){
System.out.println(independentEquations[itr]);
}
independentEquations = pm.turnIntoSumsString(independentEquations);
for(int itr=0;itr<15;itr++){
System.out.println(independentEquations[itr]);
}
And what's output:
111111100
111100111
000001111
100001111
010110001
111100010
011011000
010000101
101111001
010011100
011001010
100001000
001010101
010100001
000010101
+ 1 + 2 + 3 + 4 + 5 + 6 + 7
+ 1 + 2 + 3 + 4 + 7 + 8 + 9
+ 6 + 7 + 8 + 9
+ 1 + 6 + 7 + 8 + 9
+ 2 + 4 + 5 + 9
+ 1 + 2 + 3 + 4 + 8
+ 2 + 3 + 5 + 6
+ 2 + 7 + 9
+ 1 + 3 + 4 + 5 + 6 + 9
+ 2 + 5 + 6 + 7
+ 2 + 3 + 6 + 8
+ 1 + 6
+ 3 + 5 + 7 + 9
+ 2 + 4 + 9
+ 5 + 7 + 9
Now what remains is an algorithm to place the sums appropriately on a puzzle board. Also, the numbers should be mixed around so that they don't appear in order in the puzzle.
Answer
In your given example, the bottom 3 is obvious. That leaves 4 unknowns, which have equations like:
(E1) 7=A+B
(E2) 9=C+D
(E3) 7=A+C
(E4) 12=B+D+3
With 4 equations and 4 unknowns, we should ideally have some unique solution, but we really have only 3 equations, because (E4) is simply (E1)+(E2)-(E3). The 4 equations are not independent. This is the reason we get multiple solutions.
Strategy for getting unique solution : (A) Ensure you have N equations for N unknowns. All equations should be independent. (B) If you do not have such equations, then provide some restricting conditions like "all the 10 digits (0-9) appear once", or "all the unknowns are Different". With proper selection of this condition, all solutions except one will be eliminated. We will be left with one unique solution.
For your example, we can add a condition "all the squares have prime numbers" to make it have one unique solution.
No comments:
Post a Comment