Validate Mastermind Game Guesses

Problem

Mastermind is a two-player game in which the first player attempts to guess the secret code of the second. In this version, the code may be any six-digit number with all distinct digits.

Each turn the first player guesses some number, and the second player responds by saying how many digits in this number correctly matched their location in the secret code. For example, if the secret code were 123456, then a guess of 175286 would score two, since 1 and 6 were correctly placed.

Write an algorithm which, given a sequence of guesses and their scores, determines whether there exists some secret code that could have produced them.

Examples

Example 1

1
2
3


Input: {175286: 2, 293416: 3, 654321: 0}
Output: True
Explanation: The secret code 123456 produces these scores: 175286 matches at positions 0,5 (score=2), 293416 matches at positions 1,3,5 (score=3), 654321 matches at no positions (score=0).

Example 2

1
2
3


Input: {123456: 4, 345678: 4, 567890: 4}
Output: False
Explanation: No secret code can satisfy all three constraints simultaneously, as they would require overlapping digits in conflicting positions.

Example 3

1
2
3


Input: {123456: 6}
Output: True
Explanation: The secret code 123456 itself produces a perfect score of 6.

Example 4

1
2
3


Input: {111111: 1, 222222: 1, 333333: 1}
Output: False
Explanation: Since the secret code must have all distinct digits, it's impossible for repeated digit guesses to each score exactly 1.

Solution

Method 1 - Constraint Satisfaction with Backtracking

Intuition

This is a constraint satisfaction problem where we need to find a 6-digit code with distinct digits that satisfies all the given guess-score pairs. We can use backtracking to try all possible combinations and check if they satisfy all constraints. The key insight is that for each guess-score pair, exactly that many positions must match between the guess and the secret code.

Approach

Generate all possible secret codes: Create permutations of 6 distinct digits from 0-9
Validate against constraints: For each potential secret code, check if it produces the correct score for every guess
Calculate match score: For a given guess and secret code, count positions where digits match
Return result: If any secret code satisfies all constraints, return True; otherwise False
Optimization: Use early termination when a constraint is violated

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
public:
    bool isValidMastermind(map<string, int>& guesses) {
        vector<int> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        // Try all permutations of 6 distinct digits
        do {
            vector<int> code(digits.begin(), digits.begin() + 6);
            if (isValidCode(code, guesses)) {
                return true;
            }
        } while (next_permutation(digits.begin(), digits.end()));
        
        return false;
    }
    
private:
    bool isValidCode(vector<int>& code, map<string, int>& guesses) {
        for (auto& pair : guesses) {
            string guess = pair.first;
            int expectedScore = pair.second;
            
            int actualScore = calculateScore(code, guess);
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
    
    int calculateScore(vector<int>& code, string& guess) {
        int score = 0;
        for (int i = 0; i < 6; i++) {
            if (code[i] == (guess[i] - '0')) {
                score++;
            }
        }
        return score;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


func isValidMastermind(guesses map[string]int) bool {
    digits := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    
    // Generate all permutations of 6 digits from 10
    return generatePermutations(digits, []int{}, 0, 6, guesses)
}

func generatePermutations(digits []int, current []int, start, length int, guesses map[string]int) bool {
    if len(current) == length {
        return isValidCode(current, guesses)
    }
    
    for i := start; i < len(digits); i++ {
        current = append(current, digits[i])
        if generatePermutations(digits, current, i+1, length, guesses) {
            return true
        }
        current = current[:len(current)-1]
    }
    
    return false
}

func isValidCode(code []int, guesses map[string]int) bool {
    for guess, expectedScore := range guesses {
        actualScore := calculateScore(code, guess)
        if actualScore != expectedScore {
            return false
        }
    }
    return true
}

func calculateScore(code []int, guess string) int {
    score := 0
    for i := 0; i < 6; i++ {
        if code[i] == int(guess[i]-'0') {
            score++
        }
    }
    return score
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class Solution {
    public boolean isValidMastermind(Map<String, Integer> guesses) {
        int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        return generateCombinations(digits, new ArrayList<>(), 0, 6, guesses);
    }
    
    private boolean generateCombinations(int[] digits, List<Integer> current, int start, int length, Map<String, Integer> guesses) {
        if (current.size() == length) {
            return isValidCode(current, guesses);
        }
        
        for (int i = start; i < digits.length; i++) {
            current.add(digits[i]);
            if (generateCombinations(digits, current, i + 1, length, guesses)) {
                return true;
            }
            current.remove(current.size() - 1);
        }
        
        return false;
    }
    
    private boolean isValidCode(List<Integer> code, Map<String, Integer> guesses) {
        for (Map.Entry<String, Integer> entry : guesses.entrySet()) {
            String guess = entry.getKey();
            int expectedScore = entry.getValue();
            
            int actualScore = calculateScore(code, guess);
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
    
    private int calculateScore(List<Integer> code, String guess) {
        int score = 0;
        for (int i = 0; i < 6; i++) {
            if (code.get(i) == (guess.charAt(i) - '0')) {
                score++;
            }
        }
        return score;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution:
    def isValidMastermind(self, guesses: Dict[str, int]) -> bool:
        from itertools import combinations
        
        digits = list(range(10))
        
        # Try all combinations of 6 distinct digits
        for combo in combinations(digits, 6):
            # Try all permutations of the selected 6 digits
            from itertools import permutations
            for perm in permutations(combo):
                if self.isValidCode(list(perm), guesses):
                    return True
        
        return False
    
    def isValidCode(self, code: List[int], guesses: Dict[str, int]) -> bool:
        for guess, expectedScore in guesses.items():
            actualScore = self.calculateScore(code, guess)
            if actualScore != expectedScore:
                return False
        return True
    
    def calculateScore(self, code: List[int], guess: str) -> int:
        score = 0
        for i in range(6):
            if code[i] == int(guess[i]):
                score += 1
        return score

Complexity

⏰ Time complexity: O(P(10,6) × G × 6), where P(10,6) = 151,200 is the number of ways to choose and arrange 6 digits from 10, G is the number of guesses, and 6 is the code length. This simplifies to O(G) since P(10,6) is constant.
🧺 Space complexity: O(6) for storing the current code candidate, which is O(1).

Method 2 - Optimized Constraint Propagation

Intuition

Instead of brute force, we can use constraint propagation to eliminate impossible digit-position combinations early. For each guess-score pair, we know exactly which positions can and cannot match. We can build a constraint system and use logical deduction to prune the search space significantly.

Approach

Initialize constraint matrix: Create a 6×10 boolean matrix where entry (i,j) indicates if digit j can be at position i
Process constraints: For each guess-score pair, derive which positions must/cannot match
Propagate constraints: Use logical deduction to eliminate impossible combinations
Backtrack with constraints: Use remaining possibilities to guide backtracking search
Validate solution: Check if any valid assignment satisfies all original constraints

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


class Solution {
public:
    bool isValidMastermind(map<string, int>& guesses) {
        vector<vector<bool>> possible(6, vector<bool>(10, true));
        vector<bool> used(10, false);
        vector<int> code(6, -1);
        
        return backtrackWithConstraints(0, code, used, possible, guesses);
    }
    
private:
    bool backtrackWithConstraints(int pos, vector<int>& code, vector<bool>& used, 
                                 vector<vector<bool>>& possible, map<string, int>& guesses) {
        if (pos == 6) {
            return isValidCode(code, guesses);
        }
        
        for (int digit = 0; digit < 10; digit++) {
            if (!used[digit] && possible[pos][digit]) {
                code[pos] = digit;
                used[digit] = true;
                
                if (backtrackWithConstraints(pos + 1, code, used, possible, guesses)) {
                    return true;
                }
                
                used[digit] = false;
                code[pos] = -1;
            }
        }
        
        return false;
    }
    
    bool isValidCode(vector<int>& code, map<string, int>& guesses) {
        for (auto& pair : guesses) {
            string guess = pair.first;
            int expectedScore = pair.second;
            
            int actualScore = 0;
            for (int i = 0; i < 6; i++) {
                if (code[i] == (guess[i] - '0')) {
                    actualScore++;
                }
            }
            
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


func isValidMastermindOptimized(guesses map[string]int) bool {
    possible := make([][]bool, 6)
    for i := range possible {
        possible[i] = make([]bool, 10)
        for j := range possible[i] {
            possible[i][j] = true
        }
    }
    
    used := make([]bool, 10)
    code := make([]int, 6)
    for i := range code {
        code[i] = -1
    }
    
    return backtrackWithConstraints(0, code, used, possible, guesses)
}

func backtrackWithConstraints(pos int, code []int, used []bool, possible [][]bool, guesses map[string]int) bool {
    if pos == 6 {
        return isValidCodeOptimized(code, guesses)
    }
    
    for digit := 0; digit < 10; digit++ {
        if !used[digit] && possible[pos][digit] {
            code[pos] = digit
            used[digit] = true
            
            if backtrackWithConstraints(pos+1, code, used, possible, guesses) {
                return true
            }
            
            used[digit] = false
            code[pos] = -1
        }
    }
    
    return false
}

func isValidCodeOptimized(code []int, guesses map[string]int) bool {
    for guess, expectedScore := range guesses {
        actualScore := 0
        for i := 0; i < 6; i++ {
            if code[i] == int(guess[i]-'0') {
                actualScore++
            }
        }
        
        if actualScore != expectedScore {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class Solution {
    public boolean isValidMastermindOptimized(Map<String, Integer> guesses) {
        boolean[][] possible = new boolean[6][10];
        for (int i = 0; i < 6; i++) {
            Arrays.fill(possible[i], true);
        }
        
        boolean[] used = new boolean[10];
        int[] code = new int[6];
        Arrays.fill(code, -1);
        
        return backtrackWithConstraints(0, code, used, possible, guesses);
    }
    
    private boolean backtrackWithConstraints(int pos, int[] code, boolean[] used, 
                                           boolean[][] possible, Map<String, Integer> guesses) {
        if (pos == 6) {
            return isValidCode(code, guesses);
        }
        
        for (int digit = 0; digit < 10; digit++) {
            if (!used[digit] && possible[pos][digit]) {
                code[pos] = digit;
                used[digit] = true;
                
                if (backtrackWithConstraints(pos + 1, code, used, possible, guesses)) {
                    return true;
                }
                
                used[digit] = false;
                code[pos] = -1;
            }
        }
        
        return false;
    }
    
    private boolean isValidCode(int[] code, Map<String, Integer> guesses) {
        for (Map.Entry<String, Integer> entry : guesses.entrySet()) {
            String guess = entry.getKey();
            int expectedScore = entry.getValue();
            
            int actualScore = 0;
            for (int i = 0; i < 6; i++) {
                if (code[i] == (guess.charAt(i) - '0')) {
                    actualScore++;
                }
            }
            
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution:
    def isValidMastermindOptimized(self, guesses: Dict[str, int]) -> bool:
        possible = [[True] * 10 for _ in range(6)]
        used = [False] * 10
        code = [-1] * 6
        
        return self.backtrackWithConstraints(0, code, used, possible, guesses)
    
    def backtrackWithConstraints(self, pos: int, code: List[int], used: List[bool], 
                               possible: List[List[bool]], guesses: Dict[str, int]) -> bool:
        if pos == 6:
            return self.isValidCode(code, guesses)
        
        for digit in range(10):
            if not used[digit] and possible[pos][digit]:
                code[pos] = digit
                used[digit] = True
                
                if self.backtrackWithConstraints(pos + 1, code, used, possible, guesses):
                    return True
                
                used[digit] = False
                code[pos] = -1
        
        return False
    
    def isValidCode(self, code: List[int], guesses: Dict[str, int]) -> bool:
        for guess, expectedScore in guesses.items():
            actualScore = 0
            for i in range(6):
                if code[i] == int(guess[i]):
                    actualScore += 1
            
            if actualScore != expectedScore:
                return False
        return True

Complexity

⏰ Time complexity: O(10^6 × G) in worst case, but typically much better due to constraint propagation pruning the search space early.
🧺 Space complexity: O(60) for the constraint matrix plus O(6) for the recursion stack, which is O(1).

Method 3 - Mathematical Constraint Analysis

Intuition

We can analyze the mathematical constraints more directly. If we have multiple guesses with high scores, there must be significant overlap in the positions where they match the secret code. We can use set theory and logical reasoning to quickly eliminate impossible scenarios before attempting any search.

Approach

Analyze score constraints: Check if the sum of scores is achievable given the overlap constraints
Detect contradictions: Look for logical impossibilities (e.g., too many high-scoring overlapping guesses)
Use inclusion-exclusion: Calculate minimum required overlaps between guesses
Early termination: Return False immediately if mathematical constraints are violated
Fallback to search: If constraints pass initial tests, use optimized backtracking

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


class Solution {
public:
    bool isValidMastermind(map<string, int>& guesses) {
        // Quick mathematical constraint checks
        if (!passesBasicConstraints(guesses)) {
            return false;
        }
        
        // If basic constraints pass, use backtracking
        vector<int> code(6, -1);
        vector<bool> used(10, false);
        return backtrack(0, code, used, guesses);
    }
    
private:
    bool passesBasicConstraints(map<string, int>& guesses) {
        // Check for impossible score combinations
        for (auto& p1 : guesses) {
            for (auto& p2 : guesses) {
                if (p1.first != p2.first) {
                    int maxPossibleOverlap = calculateMaxOverlap(p1.first, p2.first);
                    int minRequiredOverlap = p1.second + p2.second - 6;
                    
                    if (minRequiredOverlap > maxPossibleOverlap) {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
    
    int calculateMaxOverlap(const string& g1, const string& g2) {
        int overlap = 0;
        for (int i = 0; i < 6; i++) {
            if (g1[i] == g2[i]) {
                overlap++;
            }
        }
        return overlap;
    }
    
    bool backtrack(int pos, vector<int>& code, vector<bool>& used, map<string, int>& guesses) {
        if (pos == 6) {
            return isValidCode(code, guesses);
        }
        
        for (int digit = 0; digit < 10; digit++) {
            if (!used[digit]) {
                code[pos] = digit;
                used[digit] = true;
                
                if (backtrack(pos + 1, code, used, guesses)) {
                    return true;
                }
                
                used[digit] = false;
                code[pos] = -1;
            }
        }
        
        return false;
    }
    
    bool isValidCode(vector<int>& code, map<string, int>& guesses) {
        for (auto& pair : guesses) {
            string guess = pair.first;
            int expectedScore = pair.second;
            
            int actualScore = 0;
            for (int i = 0; i < 6; i++) {
                if (code[i] == (guess[i] - '0')) {
                    actualScore++;
                }
            }
            
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85


func isValidMastermindMath(guesses map[string]int) bool {
    // Quick mathematical constraint checks
    if !passesBasicConstraints(guesses) {
        return false
    }
    
    // If basic constraints pass, use backtracking
    code := make([]int, 6)
    for i := range code {
        code[i] = -1
    }
    used := make([]bool, 10)
    
    return backtrackMath(0, code, used, guesses)
}

func passesBasicConstraints(guesses map[string]int) bool {
    guessSlice := make([]string, 0, len(guesses))
    for guess := range guesses {
        guessSlice = append(guessSlice, guess)
    }
    
    for i, g1 := range guessSlice {
        for j, g2 := range guessSlice {
            if i != j {
                maxOverlap := calculateMaxOverlapGo(g1, g2)
                minRequired := guesses[g1] + guesses[g2] - 6
                
                if minRequired > maxOverlap {
                    return false
                }
            }
        }
    }
    
    return true
}

func calculateMaxOverlapGo(g1, g2 string) int {
    overlap := 0
    for i := 0; i < 6; i++ {
        if g1[i] == g2[i] {
            overlap++
        }
    }
    return overlap
}

func backtrackMath(pos int, code []int, used []bool, guesses map[string]int) bool {
    if pos == 6 {
        return isValidCodeMath(code, guesses)
    }
    
    for digit := 0; digit < 10; digit++ {
        if !used[digit] {
            code[pos] = digit
            used[digit] = true
            
            if backtrackMath(pos+1, code, used, guesses) {
                return true
            }
            
            used[digit] = false
            code[pos] = -1
        }
    }
    
    return false
}

func isValidCodeMath(code []int, guesses map[string]int) bool {
    for guess, expectedScore := range guesses {
        actualScore := 0
        for i := 0; i < 6; i++ {
            if code[i] == int(guess[i]-'0') {
                actualScore++
            }
        }
        
        if actualScore != expectedScore {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


class Solution {
    public boolean isValidMastermindMath(Map<String, Integer> guesses) {
        // Quick mathematical constraint checks
        if (!passesBasicConstraints(guesses)) {
            return false;
        }
        
        // If basic constraints pass, use backtracking
        int[] code = new int[6];
        Arrays.fill(code, -1);
        boolean[] used = new boolean[10];
        
        return backtrack(0, code, used, guesses);
    }
    
    private boolean passesBasicConstraints(Map<String, Integer> guesses) {
        String[] guessArray = guesses.keySet().toArray(new String[0]);
        
        for (int i = 0; i < guessArray.length; i++) {
            for (int j = i + 1; j < guessArray.length; j++) {
                String g1 = guessArray[i], g2 = guessArray[j];
                int maxOverlap = calculateMaxOverlap(g1, g2);
                int minRequired = guesses.get(g1) + guesses.get(g2) - 6;
                
                if (minRequired > maxOverlap) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private int calculateMaxOverlap(String g1, String g2) {
        int overlap = 0;
        for (int i = 0; i < 6; i++) {
            if (g1.charAt(i) == g2.charAt(i)) {
                overlap++;
            }
        }
        return overlap;
    }
    
    private boolean backtrack(int pos, int[] code, boolean[] used, Map<String, Integer> guesses) {
        if (pos == 6) {
            return isValidCode(code, guesses);
        }
        
        for (int digit = 0; digit < 10; digit++) {
            if (!used[digit]) {
                code[pos] = digit;
                used[digit] = true;
                
                if (backtrack(pos + 1, code, used, guesses)) {
                    return true;
                }
                
                used[digit] = false;
                code[pos] = -1;
            }
        }
        
        return false;
    }
    
    private boolean isValidCode(int[] code, Map<String, Integer> guesses) {
        for (Map.Entry<String, Integer> entry : guesses.entrySet()) {
            String guess = entry.getKey();
            int expectedScore = entry.getValue();
            
            int actualScore = 0;
            for (int i = 0; i < 6; i++) {
                if (code[i] == (guess.charAt(i) - '0')) {
                    actualScore++;
                }
            }
            
            if (actualScore != expectedScore) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


class Solution:
    def isValidMastermindMath(self, guesses: Dict[str, int]) -> bool:
        # Quick mathematical constraint checks
        if not self.passesBasicConstraints(guesses):
            return False
        
        # If basic constraints pass, use backtracking
        code = [-1] * 6
        used = [False] * 10
        
        return self.backtrack(0, code, used, guesses)
    
    def passesBasicConstraints(self, guesses: Dict[str, int]) -> bool:
        guessKeys = list(guesses.keys())
        
        for i in range(len(guessKeys)):
            for j in range(i + 1, len(guessKeys)):
                g1, g2 = guessKeys[i], guessKeys[j]
                maxOverlap = self.calculateMaxOverlap(g1, g2)
                minRequired = guesses[g1] + guesses[g2] - 6
                
                if minRequired > maxOverlap:
                    return False
        
        return True
    
    def calculateMaxOverlap(self, g1: str, g2: str) -> int:
        overlap = 0
        for i in range(6):
            if g1[i] == g2[i]:
                overlap += 1
        return overlap
    
    def backtrack(self, pos: int, code: List[int], used: List[bool], guesses: Dict[str, int]) -> bool:
        if pos == 6:
            return self.isValidCode(code, guesses)
        
        for digit in range(10):
            if not used[digit]:
                code[pos] = digit
                used[digit] = True
                
                if self.backtrack(pos + 1, code, used, guesses):
                    return True
                
                used[digit] = False
                code[pos] = -1
        
        return False
    
    def isValidCode(self, code: List[int], guesses: Dict[str, int]) -> bool:
        for guess, expectedScore in guesses.items():
            actualScore = 0
            for i in range(6):
                if code[i] == int(guess[i]):
                    actualScore += 1
            
            if actualScore != expectedScore:
                return False
        return True

Complexity

⏰ Time complexity: O(G² + 10^6 × G) where G is the number of guesses. The G² term is for constraint analysis, and the exponential term only executes if constraints pass.
🧺 Space complexity: O(6) for the recursion stack and code storage, which is O(1).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Solution#

Method 1 - Constraint Satisfaction with Backtracking#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Optimized Constraint Propagation#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Mathematical Constraint Analysis#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Solution

Method 1 - Constraint Satisfaction with Backtracking

Intuition

Approach

Code

Complexity

Method 2 - Optimized Constraint Propagation

Intuition

Approach

Code

Complexity

Method 3 - Mathematical Constraint Analysis

Intuition

Approach

Code

Complexity