16
$\begingroup$

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:

Solution 1

Solution 2

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<count;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<count;itr3++){if(equations[itr3].equals(equation)){loop=true;};}
            }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<independentEquations.length;itr++){
                for(int itr2=0;itr2<independentEquations[itr2].length();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.

$\endgroup$
9
  • $\begingroup$ how does the white 3 in the black triangle fit in? $\endgroup$
    – JLee
    Commented Jun 5, 2015 at 2:53
  • 2
    $\begingroup$ Welcome to Puzzling.SE! Your question is a great question, clearly written and with a narrow, specific goal- the kind we like. We hope to see you keep this high level of question posts moving forward, which makes the site better. $\endgroup$
    – JLee
    Commented Jun 5, 2015 at 2:55
  • $\begingroup$ @JLee The white 3 tells you that the numbers in the horizontal row of white squares to the right of that three (namely, the single white square) must sum to 3. This is the trivial case where "clue" just tells you what number to put in that box. $\endgroup$ Commented Jun 5, 2015 at 3:21
  • $\begingroup$ I see that kind of logic puzzles has few numbers pre-written, so you can provide '2' or '1' on top-right to have unique solution...... If you can solve a puzzle without guessing that means puzzle is unique. $\endgroup$ Commented Jun 5, 2015 at 3:47
  • 1
    $\begingroup$ I'm a bit confused on the work up to here. If I go by the list of 15 independant equations with 9 variables, this doesn't seem to add up with the math I was taught. If you row-reduce that matrix to it's echelon form, you should have at least 6 'non-independent' equations. $\endgroup$ Commented Jun 9, 2015 at 16:53

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Splitting on the diagonal is standard notation for cross sum puzzles. I don't really think there's a need to split it into four pieces. $\endgroup$
    – Tryth
    Commented Jun 5, 2015 at 4:25
  • $\begingroup$ @Tryth , I was not aware of such standard notation for puzzles (I usually make it unambiguous, or state the notation in the puzzle), and even the question does not mention Kakuro, but your point is valid, so I removed that comment about 4 pieces. $\endgroup$
    – Prem
    Commented Jun 5, 2015 at 6:06
4
$\begingroup$

Writing and sanity-checking this kind of puzzle ends up being a very similar process to solving it.

First, make sure your ground rules are clear. Most Kakuro puzzles operate on only digits 1-9, excluding zero; and require that each digit in a sum is unique (thus 45 is the max, with one of every digit appearing). If your puzzle doesn't follow these rules, you should be explicit in how you deviate from them. If your puzzle DOES follow these rules, you should also state that, or link to a place that describes the standard rules. Advanced puzzle writers may choose to omit this if they think their audience is clever enough to disambiguate, but tread carefully here. If your puzzle uses standard notation but doesn't follow standard rules, your solver needs to be able to notice this early, or he/she will become frustrated.

Second, start with digit ranges that are highly constrained. For example, a 7 in three boxes must be 1+2+4 in some order; there's no way to include a 3 without duplicating numbers in the sum. A 16 in two boxes must be 7+9 in some order because you can't duplicate the 8. These constrained ranges can force digits of your solution at intersections.

Example: A 17 in five boxes intersects with a 24 in three boxes. The 17 has two possibilities (1+2+3+4+7 or 1+2+3+5+6) while 24 is constrained to be (7+8+9). Only the 7 can be at this intersection. Now that the 7 is fixed, maybe a different crossing will take advantage of the fact that the 17 sum can no longer contain a digit >=5. A chain reaction begins to take place as parts of the puzzle become more and more constrained.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.