All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
3x3 Nim (Posted on 2009-06-25) Difficulty: 3 of 5
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.)
misère form | Comment 23 of 26 |

In the misere form, the person to take the last piece would lose. Here are the positions from which one can't make a winning play in the misere form, and so you'd want to leave the opponent with one of these positions:

       |   |   |   |   |   |   |   |   |   |   |   |   |   |   |  *|  *|  *|  *|
       |   |   |  *| * | **| **| **|*  |* *|* *|* *|** |** |** |   |  *| * | * |
      *| * |*  |   |   | **|* *|** |   | **|* *|** | **|* *|** |   |** | **|*  |
    001 002 004 010 020 033 035 036 040 053 055 056 063 065 066 100 116 123 124
  *|  *|  *|  *|  *| * | * | * | * | * | * | * | * | * | **| **| **| **| **| **|
 **|*  |*  |* *|** |   |  *|  *| * | **|*  |*  |* *|** |   |   |   |  *| * | **|
 * | * |* *|*  |  *|   | **|*  |* *|  *|  *|** | * |*  | **|* *|** | * |  *|   |
132 142 145 154 161 200 213 214 225 231 241 246 252 264 303 305 306 312 321 330
 **| **| **| **|*  |*  |*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|
*  |* *|** |***|   |  *|  *| * | * | **|*  |* *|** |   |   |   |  *| * | **|*  |
*  |   |   |***|   | * |* *|  *|** |*  | **|  *| * | **|* *|** |*  | * |   |  *|
344 350 360 377 400 412 415 421 426 434 443 451 462 503 505 506 514 522 530 541
* *|* *|* *|** |** |** |** |** |** |** |** |** |** |***|***|***|***|***|***|
* *|** |***|   |   |   |  *| * | **|*  |* *|** |***| **|* *|** |***|***|***|
   |   |***| **|* *|** |  *|*  |   | * |   |   |***|***|***|***| **|* *|** |
550 560 577 603 605 606 611 624 630 642 650 660 677 737 757 767 773 775 776


Here are the positions from which a winning move is possible, again with the number code of what you'd want to leave the opponent with, as labelled in the above chart (other winning moves are possible; one is shown for each position):

       |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
       |   |   |   |   |  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * |
       | **|* *|** |***|  *| * | **|*  |* *|** |***|  *| * | **|*  |* *|** |***|
    end 002 004 004 004 001 002 010 004 010 010 010 001 002 020 004 020 020 020
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|** |** |** |
   |  *| * |*  |***|  *| * | **|*  |* *|** |***|   |  *| * |*  |***|   |  *| * |
020 001 002 004 036 001 002 040 004 040 040 040 040 001 002 004 056 040 001 002
   |   |   |   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|
** |** |***|***|***|***|***|***|***|***|   |   |   |   |   |   |   |  *|  *|  *|
*  |***|   |  *| * | **|*  |* *|** |***|  *| * | **|*  |* *|** |***|   |  *| * |
004 066 040 001 002 063 004 065 066 033 001 002 100 004 100 100 100 010 100 002
  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|
  *|  *|  *|  *| * | * | * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |
 **|*  |* *|***|   |  *| * |* *|** |***|   |  *| **|*  |* *|** |***|   |  *| **|
002 004 004 116 020 020 100 124 124 124 100 020 033 124 035 036 132 040 040 142
  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|  *|
*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|
*  |** |***|   |  *| * | **|* *|** |***|   | * | **|*  |* *|** |***|   |  *| * |
100 142 145 100 040 142 053 055 056 154 100 142 063 124 065 066 161 100 161 142
  *|  *|  *|  *|  *| * | * | * | * | * | * | * | * | * | * | * | * | * | * | * |
***|***|***|***|***|   |   |   |   |   |   |   |  *|  *|  *|  *|  *|  *| * | * |
 **|*  |* *|** |***|  *| * | **|*  |* *|** |***|   |  *| * |* *|** |***|   |  *|
123 154 145 116 066 001 002 200 004 200 200 200 010 200 010 214 214 214 020 001
 * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * |
 * | * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |* *|* *|
 * | **|*  |** |***|   | * | **|*  |* *|** |***|   | * | **|*  |* *|***|   |  *|
200 001 004 004 225 200 010 033 214 035 036 231 040 040 241 200 241 246 200 241
 * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * | * |
* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|***|***|***|***|
 **|*  |* *|** |***|   |  *| * | **|* *|** |***|   |  *| * | **|*  |* *|** |***|
053 214 055 056 252 200 241 040 063 065 066 264 200 241 252 213 264 225 246 055
 **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **|
   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * | **|
   |  *| * |*  |***|   |  *| **|*  |* *|** |***|   | * | **|*  |* *|** |***|  *|
200 001 002 004 306 010 200 213 214 305 116 312 020 100 123 124 225 306 321 231
 **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **| **|
 **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|
 * | **|*  |* *|** |***|   |  *| * | **|* *|** |***|  *| * | **|*  |* *|** |***|
132 033 330 035 036 330 040 241 142 303 145 246 344 350 252 053 154 055 056 350
 **| **| **| **| **| **| **| **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |
** |** |** |** |** |** |** |***|***|***|***|***|***|***|   |   |   |   |   |   |
  *| * | **|*  |* *|** |***|   |  *| * | **|*  |* *|** |  *| * | **|*  |* *|** |
161 360 063 264 065 066 360 360 321 312 303 344 305 306 001 002 400 004 400 400
*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |
   |  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | **| **| **| **| **| **| **|
***|   |  *| **|*  |** |***|   | * | **|*  |* *|***|   |  *| * | **|* *|** |***|
400 010 400 412 010 412 415 020 400 421 020 421 426 400 421 412 033 035 036 434
*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |*  |
*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |
   |  *| * |*  |* *|** |***|   | * | **|*  |* *|** |***|   |  *| **|*  |* *|** |
040 001 002 400 001 002 443 400 412 053 010 055 056 451 400 421 063 020 065 066
*  |*  |*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|
** |***|***|***|***|***|***|***|***|   |   |   |   |   |  *|  *|  *|  *|  *|  *|
***|   |  *| * | **|*  |* *|** |***|   |  *| * |*  |***|   |  *| * | **|* *|** |
462 400 451 462 443 434 415 426 033 400 001 002 004 506 010 400 412 503 415 116
* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|
  *| * | * | * | * | * | * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |
***|   |  *| **|*  |* *|** |***|  *| * | **|*  |* *|** |***|   | * | **|*  |* *|
514 020 421 123 124 505 426 522 530 132 033 434 035 036 530 040 142 443 100 145
* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|* *|
*  |*  |* *|* *|* *|* *|* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|
** |***|  *| * | **|*  |* *|** |***|  *| * | **|*  |* *|** |***|   |  *| * | **|
506 541 451 550 053 154 055 056 550 161 462 063 560 065 066 560 560 541 522 503
* *|* *|* *|** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |
***|***|***|   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * |
*  |* *|** |   |  *| * |*  |***|   | * | **|*  |* *|** |***|   |  *| * | **|* *|
514 505 506 400 001 002 004 606 010 412 213 214 415 606 611 020 421 400 603 225
** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |
 * | * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|
** |***|  *| * | **|*  |* *|** |***|   |  *| **|*  |* *|** |***|  *| * | **|*  |
426 624 231 630 033 434 035 036 630 040 241 443 200 605 246 642 451 252 053 650
** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |** |***|***|***|
* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|***|***|***|   |   |   |
* *|** |***|  *| * | **|*  |* *|** |***|   |  *| * | **|*  |* *|** |   |  *| * |
055 056 650 660 462 063 264 065 066 660 660 611 642 603 624 605 606 400 001 002
***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|
   |   |   |   |   |  *|  *|  *|  *|  *|  *|  *|  *| * | * | * | * | * | * | * |
 **|*  |* *|** |***|   |  *| * | **|*  |* *|** |***|   |  *| * | **|*  |* *|** |
603 004 605 606 303 010 611 412 213 514 415 116 606 020 421 522 123 624 225 426
***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|
 * | **| **| **| **| **| **| **|*  |*  |*  |*  |*  |*  |*  |*  |* *|* *|* *|* *|
***|   |  *| * | **|*  |* *|** |   |  *| * | **|*  |* *|** |***|   |  *| * | **|
505 630 231 132 033 434 035 036 040 541 642 443 344 145 246 303 650 451 252 053
***|***|***|***|***|***|***|***|***|***|***|***|***|***|***|
* *|* *|* *|** |** |** |** |** |** |** |***|***|***|***|***|
*  |* *|** |   |  *| * | **|*  |* *|** |   |  *| * |*  |***|
154 055 056 660 161 462 063 264 065 066 330 660 550 330 677

The only change to the program was to have

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

instead of

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

In the misere form, the first player has a win, rather than the second player.

Note some hopeless positions are the same as for the regular form.

A summary of where you can't successfully play from:

single piece:
|   |
|   |
| * |
4-rectangle:
|   |
| **|
| **|
trapezoid:
| **|
|   |
|* *|
lozenge:
|   |
| **|
|** |
two perpendicular sticks:
|  *|
|  *|
|** |
big diagonal:
|  *|
| * |
|*  |
loose triangle:
|  *|
|*  |
| * |
Y:
|  *|
|** |
|  *|
diamond:
| * |
|* *|
| * |
one piece missing:
| **|
|***|
|***|


 


  Posted by Charlie on 2009-06-28 14:13:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information