perplexus.info :: Games : 3x3 Nim

3x3 Nim (Posted on 2009-06-25)

A 3x3 array of counters is laid out. Players take turns removing counters. The rule for removing counters is to pick a row or column and take any 1,2 or 3 from it. Whoever removes the last counter wins.

Does the first or second player have a winning strategy?
What is this strategy?

See The Solution Submitted by Jer

Rating: 4.0000 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

computer solution

| Comment 17 of 26 |

The second player has a winning strategy. That strategy is to leave the opponent one of the following configurations:

       |   |   |   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *|  *|  *|
       |  *|  *| * | * | **|*  |*  |* *|** |   |   |  *| * | **|*  |* *|** |***|
       | * |*  |  *|*  | **|  *| * |* *|** | * |*  |** |   |***|   |***|  *| **|
    000 012 014 021 024 033 041 042 055 066 102 104 116 120 137 140 157 161 173
    
  *| * | * | * | * | * | * | * | * | * | * | **| **| **| **| **| **| **| **| **|
***|   |   |  *| * | **|*  |* *|** |***|***|   |  *| * | **|*  |* *|** |***|***|
* *|  *|*  |   |* *|***|   | * |***| **|** | **|***|***|   |*  |** |* *|  *| * |
175 201 204 210 225 237 240 252 267 273 276 303 317 327 330 344 356 365 371 372

*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|* *|* *|** |
   |   |  *| * | **|*  |* *|** |***|***|   |  *| * | **|*  |* *|** |***|***|   |
  *| * |   |   |*  | **|***|***|* *|** |* *|***| * |** |***|   | **|  *|*  |** |
401 402 410 420 434 443 457 467 475 476 505 517 522 536 547 550 563 571 574 606

** |** |** |** |** |** |** |** |***|***|***|***|***|***|***|***|***|***|***|***|
  *| * | **|*  |* *|** |***|***|  *|  *| * | * | **| **|*  |*  |* *|* *|** |** |
  *|***|* *|***| **|   | * |*  | **|* *| **|** |  *| * |* *|** |  *|*  | * |*  |
611 627 635 647 653 660 672 674 713 715 723 726 731 732 745 746 751 754 762 764

The configurations are numbered with three digits each. Each digit represents one row of the configuration, treating the row as a binary number, with an occupied position being represented by a 1-bit and an unoccupied position by a 0-bit.

The initial configuration is therefore labeled 777, and also can't be played to win against an opponent, which is why the second player has the win:

***|
***|
***|
777

The program to produce this list is recursive, choosing the best move at each step from the initial configuration:

DECLARE SUB decode (num%)
DECLARE SUB canDoToWin ()
DECLARE FUNCTION encode% ()
CLEAR , , 30000
DEFINT A-Z
DIM SHARED size, ct, wCt, lvl
size = 3
DIM SHARED bd(size, size)
DIM SHARED rslt(511), how(511)

FOR i = 1 TO size
FOR j = 1 TO size
bd(i, j) = 1
NEXT
NEXT

CALL canDoToWin

CLS

FOR cd = 0 TO 511
IF rslt(cd) = 0 THEN
decode cd
canDoToWin
END IF
NEXT

FOR cd = 0 TO 511
IF rslt(cd) = -1 THEN

      decode cd


      wCt = wCt + 1
      pRow = wCt 20: pCol = wCt MOD 20
      IF pRow > 11 THEN pRow = pRow - 12
      LOCATE pRow * 4 + 1, pCol * 4 + 1
      IF bd(1, 1) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(1, 2) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(1, 3) THEN PRINT "*|"; : ELSE PRINT " |";
      LOCATE pRow * 4 + 2, pCol * 4 + 1
      IF bd(2, 1) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(2, 2) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(2, 3) THEN PRINT "*|"; : ELSE PRINT " |";
      LOCATE pRow * 4 + 3, pCol * 4 + 1
      IF bd(3, 1) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(3, 2) THEN PRINT "*"; : ELSE PRINT " ";
      IF bd(3, 3) THEN PRINT "*|"; : ELSE PRINT " |";
      LOCATE pRow * 4 + 4, pCol * 4 + 1
      h = cd ' how(cd)
      PRINT LTRIM$(STR$(h 64));
      PRINT LTRIM$(STR$((h 8) MOD 8));
      PRINT LTRIM$(STR$(h MOD 8));
      IF pRow = 11 AND pCol = 19 THEN DO: LOOP UNTIL INKEY$ > "": CLS
   END IF
NEXT cd

END

SUB canDoToWin
entryHasGoodResp = 0
IF encode = 0 THEN rslt(0) = -1: EXIT SUB

lvl = lvl + 1

FOR row = 1 TO 3
FOR c1 = 0 TO 1
IF c1 = 0 OR bd(row, 1) = 1 THEN
FOR c2 = 0 TO 1
IF c2 = 0 OR bd(row, 2) = 1 THEN
FOR c3 = 0 TO 1
IF c3 = 0 OR bd(row, 3) = 1 THEN
   IF c1 AND bd(row, 1) OR c2 AND bd(row, 2) OR c3 AND bd(row, 3) THEN
     IF c1 THEN bd(row, 1) = 0
     IF c2 THEN bd(row, 2) = 0
     IF c3 THEN bd(row, 3) = 0

      IF rslt(encode) = -1 THEN
        entryHasGoodResp = 1
        saveWay = encode
      END IF
      IF rslt(encode) = 0 THEN
        canDoToWin
        IF rslt(encode) = -1 THEN
          entryHasGoodResp = 1
          saveWay = encode
        END IF
      END IF

     IF c1 THEN bd(row, 1) = 1
     IF c2 THEN bd(row, 2) = 1
     IF c3 THEN bd(row, 3) = 1
   END IF
   IF entryHasGoodResp THEN GOTO wrapUp
END IF
NEXT
END IF
NEXT
END IF
NEXT
NEXT row

FOR col = 1 TO 3
FOR r1 = 0 TO 1
IF r1 = 0 OR bd(1, col) = 1 THEN
FOR r2 = 0 TO 1
IF r2 = 0 OR bd(2, col) = 1 THEN
FOR r3 = 0 TO 1
IF r3 = 0 OR bd(3, col) = 1 THEN
   IF r1 AND bd(1, col) OR r2 AND bd(2, col) OR r3 AND bd(3, col) THEN
     IF r1 THEN bd(1, col) = 0
     IF r2 THEN bd(2, col) = 0
     IF r3 THEN bd(3, col) = 0

     IF r1 THEN bd(1, col) = 1
     IF r2 THEN bd(2, col) = 1
     IF r3 THEN bd(3, col) = 1
   END IF
   IF entryHasGoodResp THEN GOTO wrapUp
END IF
NEXT
END IF
NEXT
END IF
NEXT
NEXT col
wrapUp:
IF entryHasGoodResp THEN
   rslt(encode) = 1: how(encode) = saveWay:
ELSE
   rslt(encode) = -1
END IF

lvl = lvl - 1
END SUB

SUB decode (num)
tot = num
FOR row = 3 TO 1 STEP -1
FOR col = 3 TO 1 STEP -1
bd(row, col) = tot MOD 2
tot = tot 2
NEXT
NEXT
END SUB

FUNCTION encode
tot = 0
FOR row = 1 TO 3
FOR col = 1 TO 3
tot = tot * 2 + bd(row, col)
NEXT
NEXT
encode = tot
END FUNCTION

A minor variation of the program selects the rslt(cd) = 1, rather than -1 to get the positions from which it's possible to win. Instead of showing its own configuration number, it shows the number of the configuration shown above, to which it can be made, in order to assure a win, by using the way() array in the program.

So for example, when facing the configuration

|  *|
|* *|
|* *|

you find 055 listed below it on the table below, so you can win by leaving configuration 055 above, by taking the top-right piece.

Of course the final win is when you go to configuration 000, available when all the remaining pieces are in one row or one column.


       |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
       |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *| * | * | * | * | * | * |
      *| * | **|*  |* *|** |***|   |  *| **|* *|** |***|   | * | **|* *|** |***|
    000 000 000 000 000 000 000 000 000 012 014 014 014 000 000 021 024 024 024
    
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|
   |  *| * |*  |* *|** |***|   | **|*  |* *|** |***|   |  *| * | **|*  |** |***|
000 021 012 024 024 014 033 000 042 000 041 042 042 000 041 042 042 014 012 055

   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |  *|  *|  *|  *|  *|
** |** |** |** |** |** |** |***|***|***|***|***|***|***|***|   |   |   |   |   |
   |  *| * | **|*  |* *|***|   |  *| * | **|*  |* *|** |***|   |  *| **|* *|** |
000 041 042 041 024 021 066 000 041 042 033 024 055 066 033 000 000 102 104 104

  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|
   |  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * | **| **| **| **| **|
***|   |  *| * | **|*  |* *|***|  *| * | **|*  |* *|** |***|   |  *| * | **|*  |
104 000 000 012 102 014 104 116 021 102 120 024 120 120 120 120 120 102 033 104

  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|
 **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |
* *|** |  *| * | **|*  |* *|** |***|   |  *| * | **|*  |* *|** |   | * | **|*  |
024 116 041 042 140 104 140 140 140 140 140 102 042 104 055 116 140 102 161 104

  *|  *|  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * | * | * | * | * |
** |** |** |***|***|***|***|***|***|   |   |   |   |   |   |  *|  *|  *|  *|  *|
* *|** |***|   |  *| * |*  |** |***|   | * | **|* *|** |***|  *| * | **|*  |* *|
161 066 161 140 161 102 104 116 157 000 000 201 204 204 204 201 012 210 014 210

 * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * |
  *|  *| * | * | * | * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |
** |***|   |  *| * | **|*  |** |***|   |  *| * | **|*  |* *|** |  *| * | **|*  |
210 210 000 021 000 201 024 204 225 210 201 210 033 204 225 014 041 042 240 204

 * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * |
*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|
* *|** |***|   |  *| **|*  |* *|** |***|   |  *| * | **|*  |* *|** |   |  *| * |
240 240 240 240 201 252 204 055 252 252 240 201 240 041 204 225 066 240 201 252

 * | * | * | **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **|
***|***|***|   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *| * | * | * |
*  |* *|***|   |  *| * |*  |* *|** |***|   |  *| * | **|*  |* *|** |   |  *| * |
204 225 267 000 201 102 204 204 104 303 210 210 012 303 014 204 116 120 021 120

 **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **|
 * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|
 **|*  |* *|** |  *| * | **|*  |* *|** |***|   |  *| * | **|* *|** |***|   |  *|
303 024 225 104 330 330 033 330 330 330 237 240 041 042 303 344 344 344 240 240

 **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **|*  |*  |
* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|***|***|   |   |
 * | **|*  |* *|***|   |  *| * | **|*  |** |***|   | **|*  |* *|** |***|   | **|
252 303 344 055 157 140 161 140 303 344 066 267 330 273 344 175 276 327 000 402

*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |
   |   |   |   |  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * | **| **|
*  |* *|** |***|  *| * | **|*  |* *|** |***|  *| * | **|*  |* *|** |***|   |  *|
000 401 402 402 401 012 410 014 410 410 410 021 402 420 024 420 420 420 420 401

*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |
 **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |
 * | **|* *|** |***|   |  *| * |*  |* *|** |***|   |  *| * | **|*  |* *|** |   |
402 033 434 434 434 000 041 042 000 401 402 443 410 401 402 443 410 055 012 420

*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|* *|
** |** |** |** |** |** |***|***|***|***|***|***|   |   |   |   |   |   |   |  *|
  *| * | **|*  |* *|** |   |  *| * | **|*  |***|   |  *| * | **|*  |** |***|   |
401 402 443 420 021 066 420 401 402 443 434 467 000 401 402 402 104 102 505 410

* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|
  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * | **| **| **| **| **| **| **|
  *| * | **|*  |* *|** |   |  *| **|*  |* *|** |***|   |  *| * | **|*  |* *|***|
410 012 402 014 505 116 420 021 522 024 505 522 522 420 420 522 033 434 505 137

* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|
*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |
   |  *| * | **|*  |* *|** |  *| * | **|*  |* *|** |***|   |  *| * |*  |* *|** |
140 041 042 443 140 505 102 550 550 550 550 055 550 457 120 161 522 120 505 066

* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |** |** |** |** |** |** |** |
** |***|***|***|***|***|***|   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *|
***|   | * | **|* *|** |***|   |  *| * | **|*  |* *|***|   | * | **|*  |* *|** |
467 550 522 173 475 476 547 000 401 402 401 204 201 606 410 012 611 014 611 606

** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |
  *| * | * | * | * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |
***|   |  *| * | **|*  |* *|** |   |  *| * | **|*  |** |***|   |  *| * | **|*  |
611 420 021 420 401 024 225 606 410 611 410 033 434 606 237 240 041 042 443 240

** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |
*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|
* *|** |   |  *| * |*  |* *|** |***|  *| * | **|*  |* *|** |***|   |  *| **|* *|
201 606 210 611 252 210 055 606 457 660 660 660 660 660 066 467 660 611 273 475

** |** |***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|
***|***|   |   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *| * | * | * | * |
** |***|   |  *| * | **|*  |* *|** |***|   |  *| * |*  |** |***|   |  *| * |*  |
476 647 000 401 402 303 204 505 606 303 410 611 012 014 116 517 420 021 522 024

***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|
 * | * | **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|
* *|***|   | **|*  |* *|** |***|   |  *| * | **|*  |***|   | * | **|* *|** |***|
225 627 330 033 434 635 536 237 240 041 042 443 344 647 550 252 653 055 356 457

***|***|***|***|***|***|***|***|***|***|***|***|***|
** |** |** |** |** |** |***|***|***|***|***|***|***|
   |  *| **|* *|** |***|   |  *| * | **|*  |* *|** |
660 161 563 365 066 467 330 571 672 273 674 475 476

I don't know of an easy way of categorizing the 80 positions to try to get the opponent to confront (including the opening position of all 9).

Edited on June 26, 2009, 9:52 am

Posted by Charlie on 2009-06-26 09:50:05

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info