Description:
- Local search methods typically work with “complete” states
- i.e., all variables assigned
- Basically, assign every variable with a random value then change nodes in unsatisfied constrant
- No need fringe
Algorithm:
- While not solved
- randomly select any conflicted variable
- select value with min-conflicts heuristics (value that violate the fewest constraints) of that variable
- Can be solved quite fast, except for narrow range of the ratio
