wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Cooperative Checkers
        
(Message started by: James Fingas on Nov 25^th, 2002, 2:18pm)

Title: Cooperative Checkers
Post by James Fingas on Nov 25^th, 2002, 2:18pm

Is it possible for two checker players, playing cooperatively, to king all twelve of both players' checkers? Keep in mind the following rules of checkers:

1) The initial checkers setup is to use only the black squares of a chessboard, with red checkers on the 12 North-most squares, and black checkers on the 12 South-most squares.

2) Players alternate turns, and cannot pass their turn

3) If a player can "jump" an opposing player's piece, he must do so. This is where all the difficulty arises.

4) If a player cannot jump, then he must move one of his checkers diagonally. All non-kinged checkers can only move forward.

5) When a checker gets to the opposing end of the board, it is "kinged" and can now move backwards as well as forwards.

Title: Re: Cooperative Checkers
Post by Garzahd on Dec 5^th, 2002, 11:37am

Cool puzzle!

I thought it impossible at first (and it may yet be) but I've managed to get 4 of each kinged successfully before getting stuck.

http://www.cs.caltech.edu/~vhuang/cs20/c/applet/ is an excellent way to try out solutions (sadly it's missing an undo feature)

Title: Re: Cooperative Checkers
Post by Garzahd on Dec 9^th, 2002, 12:45pm

Shameless bump because I'm still working on this.

I've got a solution now that makes 7 kings for each player. And it's symmetric, which is kinda cute.

Anyone else have some inspiration on this problem?

Title: Re: Cooperative Checkers
Post by James Fingas on Dec 9^th, 2002, 1:20pm

Garzahd,

That's very good! I know it's cruel to tell you this at this point, but I don't know the answer to this one myself. I started out trying to maximize the number of kings I could get, but I found that during my first few moves I would set up a situation on the board that I would never be able to eliminate. Probably you have already thought of this, but for instance, if I make the following set of moves (symmetrically):

C6->A4
D7->C6
E6->D5

After these moves, consider the following pieces (symmetrically): A4, D5, G6. You will see that you can never move any of these without being taken. For instance, A4 cannot move until B3 is out of the way. B3 cannot move until D5 is gone. D5 cannot move unless either B3 is gone, or E4 moves. Of course E4 cannot move either, and so on.

This impasse cannot be resolved, so I had to concentrate on avoiding it at all costs. This makes the problem a little trickier, but I can still king some checkers while avoiding this particular trap. There may be other equivalent traps that make things tricky.

Title: Re: Cooperative Checkers
Post by Garzahd on Dec 9^th, 2002, 4:34pm

I noticed the same impasse, and managed to make progress without ever moving your C6 as far as A4.

By the way, assuming that chess and checkers follow the same "white on right" orientation, you're backwards.

Here's my beginning of my solution thus far, on a non-backwards board (use the applet if you want): c3b4, d2c3, e3d4, g3h4 (so g3 no longer causes the impasse), b4d6, a3b4, b2a3, c1b2, d6e7, d4c5(!), f2d4, c5d6, e7f8, d6e7, d4c5, g1d4.
The problem is, at this point the only available thing to do is e1g3, and although this lets you conga-line 7 pieces to the king line (a little asymmetry may be required to get the last couple pieces out the door), it eventually results in the same impasse at g3, just with more kings on the board. The pieces at c3,d4,h2,g3,h4 are just hosed now.

Title: Re: Cooperative Checkers
Post by James Fingas on Jun 19^th, 2003, 8:02am

Because of the forced jumps. It seems like you didn't try to solve it by hand first, or you would have realized that sooner...

Title: Re: Cooperative Checkers
Post by ziep on Jan 31^st, 2004, 3:27am

This was solved for 10x10 polish checkers.
The rules are different:
-pawns move forwards, but they can take forwards and backwards.
-kings can move and take by long-jump.

It takes 381 moves; happily this applet http://10x10.org/problems/40kings.html has an autoplay-feature.

Title: Re: Cooperative Checkers
Post by THUDandBLUNDER on Jan 31^st, 2004, 8:39am

The theoretical minimum is 168.

- -9 - -9 24-28 - -8 - - - - - 6- 10-15 1-6 7-10 5-1 --29 10-6 3-7 - 18- 15- - 28-32 9- - - - 28- - - - 21- -7 25- -- 25- - 30- -

204 moves (including getting back to 1-12 and 21-32).