## backtracking minimum remaining values USA map

Expand Messages
• Hello, after having programming a backtracking with minimum remaining values, and tested it with a map coloring problem with the USA map, it comes out that the
Message 1 of 3 , Jan 17, 2005
Hello,
after having programming a backtracking with minimum remaining values,
and tested it with a map coloring problem with the USA map, it comes out
that the algorithm requires 5409 consistency checks, and not more than
1,000,000 as printed on page 143 of the international edition.

I wonder if somebody else have applied that algorithm to that problem
and got similar results, or my result is faulty:

[{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]

Regards,
Iván Villanueva
• ... It seems that the above result has been a lucky coincidence. After changing a little bit the code, the algorithm doesn t find the solution any more. I
Message 2 of 3 , Jan 18, 2005
On Mon, Jan 17, 2005 at 12:24:58PM +0100, Ivan Villanueva wrote:
>
> Hello,
> after having programming a backtracking with minimum remaining values,
> and tested it with a map coloring problem with the USA map, it comes out
> that the algorithm requires 5409 consistency checks, and not more than
> 1,000,000 as printed on page 143 of the international edition.
>
> I wonder if somebody else have applied that algorithm to that problem
> and got similar results, or my result is faulty:
>
> [{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
> RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
> IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
> NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
> NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
> MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
> ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]

It seems that the above result has been a lucky coincidence. After
changing a little bit the code, the algorithm doesn't find the solution
any more. I suppose that the first version of my algorithm (just by
chance) chose the right variables at the beginning of the search, and/or
the right values.

Iván Villanueva
• ... I apology for using this mailing list as a blog, but maybe some day some one is interested in this issue. Forget the last paragraph, the program was buggy.
Message 3 of 3 , Jan 24, 2005
On Tue, Jan 18, 2005 at 06:59:59PM +0100, Ivan Villanueva wrote:
> On Mon, Jan 17, 2005 at 12:24:58PM +0100, Ivan Villanueva wrote:
> >
> > Hello,
> > after having programming a backtracking with minimum remaining values,
> > and tested it with a map coloring problem with the USA map, it comes out
> > that the algorithm requires 5409 consistency checks, and not more than
> > 1,000,000 as printed on page 143 of the international edition.
> >
> > I wonder if somebody else have applied that algorithm to that problem
> > and got similar results, or my result is faulty:
> >
> > [{LA=red, DC=red, MN=red, WA=red, DE=red, WV=red, KA=red, TN=red,
> > RI=red, MT=re , OK=blue, VT=red, AL=blue, UT=red, WY=blue, MO=green,
> > IA=blue, SC=red, VA=blue GA=green, OH=blue, KY=yellow, IL=red, OR=blue,
> > NM=red, MA=blue, MS=green, HI=red, FL=red, SD=green, AK=red, ID=green,
> > NY=green, NC=yellow, NH=green, WI=green, CO=green, NE=yellow, NV=yellow,
> > MD=green, MI=red, TX=green, AZ=blue, IN=blue, C=red, PA=yellow,
> > ND=blue, AR=yellow, CT=green, NJ=blue, ME=red}]
>
> It seems that the above result has been a lucky coincidence. After
> changing a little bit the code, the algorithm doesn't find the solution
> any more. I suppose that the first version of my algorithm (just by
> chance) chose the right variables at the beginning of the search, and/or
> the right values.

I apology for using this mailing list as a blog, but maybe some day some
one is interested in this issue. Forget the last paragraph, the program was buggy.

I have changed again my program. Now it chooses randomly the order of
the variables. Here are the results of two representative runs:

[ivan@golem:classes]\$ java com/artificialidea/problemsolving/constraintsearch/EfficientBacktrackingSearch
Solving USA example with forward checking and minimum remaining value:
Consistency checks: 4819
Milliseconds needed: 1424
Solving USA example with minimum remaining value:
Consistency checks: 5407
Milliseconds needed: 1433
Solving USA example with forward checking:
Consistency checks: 552
Milliseconds needed: 1111
[ivan@golem:classes]\$ java com/artificialidea/problemsolving/constraintsearch/EfficientBacktrackingSearch
Solving USA example with forward checking and minimum remaining value:
Consistency checks: 4633
Milliseconds needed: 1379
Solving USA example with minimum remaining value:
Consistency checks: 5402
Milliseconds needed: 1436
Solving USA example with forward checking:
Consistency checks: 1360121
Milliseconds needed: 2358269

As you can see, minimum remaining values solves the problem much more
faster than pointed out in the book, but forward checking can take a
eternity to solve it, or can be very fast (it depends of the order of
the variables; here they were randomly chosen, thus the huge difference
between the two runs for forward checking).

Iván Villanueva.
Your message has been successfully submitted and would be delivered to recipients shortly.