Answers.Body: <p>(Assuming we don't consider some objective function) a CSP has a finite depth that corresponds with its goal state. Think of Sudoku - every solution necessarily fills up the whole board. That is, anytime we reach a depth equal to <span class="math-container">$n$</span>, where <span class="math-container">$n$</span> is the total variables, then we have a reached a goal. Therefore, we don't care about the path that gets us to the goal. In other types of problems where we care about finding the shortest path, assigning the wrong variable might lead us to a goal with an inefficient path. In CSP though, we're happy to end up at any goal so any path we take will not affect the outcome. If we reach a dead end we can always backtrack and try a different branch.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T20:44:17.410Z
Answers.LastActivityDate: 2022-02-15T20:44:17.410Z
Answers.UserDisplayName: Jimmy Feterman
Body: <p>I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size <span class="math-container">$n!d^n$</span> where <span class="math-container">$n$</span> is the number of <strong>variables</strong> and <span class="math-container">$d$</span> the <strong>domain size</strong>. It can also be easily understood that there exists instead only <span class="math-container">$d^n$</span> complete assignments. So the reason for the the tree being so large is attributed to the fact that we are ignoring the <strong>commutative</strong> way of variable assignments in CSP. Can anyone please explain, as to how exactly this commutative property affects?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-21T04:43:58.630Z
Comments.Text: I just want to comment on my own understanding of commutative variable selection. So, if I correctly understand that if we select only a single variable at an instance and then select another one (minus the previous one) it is similar to as if we would have done the selection vice versa (commutative). So, isn't DFS following this naturally?
Comments.UserDisplayName: MuneshSingh
Tags: <constraint-satisfaction-problems>
Title: What is exactly the role of commutative property in a Constraint Satisfaction Problem?
UserDisplayName: MuneshSingh
ThreadText: # What is exactly the role of commutative property in a Constraint Satisfaction Problem?
  
  (Asked by: username_0 on 2019-12-20)
  
  I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size $n!d^n$ where $n$ is the number of **variables** and $d$ the **domain size**. It can also be easily understood that there exists instead only $d^n$ complete assignments. So the reason for the the tree being so large is attributed to the fact that we are ignoring the **commutative** way of variable assignments in CSP. Can anyone please explain, as to how exactly this commutative property affects?
  
  **Tags:** constraint-satisfaction-problems
  
  > **Comments:**
  > **username_0**: I just want to comment on my own understanding of commutative variable selection. So, if I correctly understand that if we select only a single variable at an instance and then select another one (minus the previous one) it is similar to as if we would have done the selection vice versa (commutative). So, isn't DFS following this naturally?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-15. Score: 0
  
  (Assuming we don't consider some objective function) a CSP has a finite depth that corresponds with its goal state. Think of Sudoku - every solution necessarily fills up the whole board. That is, anytime we reach a depth equal to $n$, where $n$ is the total variables, then we have a reached a goal. Therefore, we don't care about the path that gets us to the goal. In other types of problems where we care about finding the shortest path, assigning the wrong variable might lead us to a goal with an inefficient path. In CSP though, we're happy to end up at any goal so any path we take will not affect the outcome. If we reach a dead end we can always backtrack and try a different branch.
  
  
  ---
  
  