Search code examples
conflictminn-queens

4 queen, min conflicts

I would like some help with min-conflicts algorithm.

  A B C D
1 _ _ Q Q
2 Q _ _ _
3 _ _ _ _
4 _ Q _ _

If we are at this point,

  • will the algorithm choose randomly to move either C or D because both of them create the same number of conflicts (C in conflict with D, D in conflict with C),
  • or will it choose D because the best place we can move C is in 3rd row and that will result in 1 conflict and if we choose D and move it in 3rd row will result in 0 conflicts.
Solution

  • The relevant lines from the wikipedia page:

     var <-- a randomly chosen variable from the set of conflicted variables CONFLICTED[csp]
 value <-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
 set var = value in current_state
    1. var represents the position of queen C or D, chosen at random.
    2. Set var to the position for said queen that minimizes conflicts given the rest of the board

    So, it's your first choice, "the algoryth choose randomly to move either C or D...", but not "because both of them create the same number of conflicts." Either C or D because those participate in one or more conflicts.

    It does mention "If there is more than one value with a minimum number of conflicts, it chooses one randomly." Once you understand the basic formulation of the algorithm, it seems there may be this modification which may also be considered a min-constraints search.