## Friday, November 11, 2011

### Game Description: Battle Sudoku

One thing I've slowly been chewing on this year is a two-player Sudoku game. The rules are very simple: each turn, you fill in a box with a number not yet in that row, column or sub-square (quadrant in the 4 x 4 case). As with normal play, if you can't move, you lose!

In January, I played with a bunch of games starting with an empty board, but realized there was a simple symmetry strategy for the second player. We brainstormed some potential starting boards to fix things, but more complicated symmetry strategies arose.

After returning to Wittenberg, Noam Elkies and I corresponded, finally working out the current starting board. All the flaws we'd seen were fixed.

Here is the starting board:

My plan was to bring the game to Integers to play with people. Beforehand, I tested it out on my WittSem class, and it proved challenging. My student Patrick also took interest and showed a pseudo-symmetry strategy I was afraid of could be broken! Awesome! (I still don't recall how he does it!)
Here is a .pdf of a sheet of games! :) Enjoy!

Next week, I will be in Seattle for Supercomputing for most of the week, so there may not be regular posts.

1. In perfect play, the second player will always win. Was that intentional?

2. It certainly was not my intention, though I'm not disappointed! I have not drawn out the entire game tree; is there a simpler proof of this?

3. Hi Kyle. This is the OP again.

With a 4 x 4 board, the player filling in an even number box will have the final 16th box remaining on their turn.

If this is following the traditional Sudoku rules then the example board has an error as each quadrant would have to contain all four integers.

Running out of moves then becomes a matter of an intentional error on the board.

4. With the initial board given above, it is true that not all of the boxes will be full at the end of the game. It is expected that not all of them are fillable, otherwise it wouldn't be very exciting!

There are certainly game paths that have an even number of moves and also those that have an odd number of moves! Different moves could change the parity of the available moves left.

The game does not end when the sixteenth box is filled in, it ends when no more numbers can legally be put in boxes.