Skip to content →

Category: featured

dvonn (1) mobility

Published January 7, 2006 by lievenlb

[Dvonn](http://www.gipf.com/dvonn $ is
the fourth game in the [Gipf Project](http://www.gipf.com/project_gipf/index.html) and the most
mathematical of all six. It is a very fast (but subtle) game with a
simple [set of rules](http://www.gipf.com/dvonn/rules/rules.html). Here
is a short version

DVONN is a stacking game. It is played
on an elongated hexagonal board, with 23 white, 23 black and 3 red
DVONN-pieces. In the beginning the board is empty. The players first
place the DVONN-pieces on the board and next their own pieces. Then they
start stacking pieces on top of each other. A single piece may be moved
1 space in any direction, a stack of two pieces may be moved two spaces,
etc. A stack must always be moved as a whole and a move must always end
on top of another piece or stack. If pieces or stacks lose contact with
the DVONN pieces, they must be removed from the board. The game ends
when no more moves can be made. The players put the stacks they control
on top of each other and the one with the highest stack is the winner.
That’s all!

All this will become clearer once we fix a
specific end-game, for example

$\xymatrix@=.3cm @!C @R=.7cm{ & &
\Black{2} \connS & & \bull{d}{5} \conn & & \bull{e}{5} \conn & &
\bull{f}{5} \conn & & \bull{g}{5} \conn & & \bull{h}{5} \conn & &
\SWhite \connS & & \SWhite \connS & & \SWhite \conneS & & \\ &
\bull{b}{4} \conn & & \SBlack \connS & & \Black{6} \connS & &
\bull{e}{4} \conn& & \bull{f}{4} \conn & & \bull{g}{4} \conn & &
\bull{h}{4} \conn & & \SWhite \connS & & \SWhite \connS & & \SWhite
\conneS & \\ \SBlack \connbeginS & & \SBlack \connS & & \BDvonn{7}
\connS & & \bull{d}{3} \conn & & \SBlack \connS & & \BDvonn{6} \connS &
& \bull{g}{3} \conn & & \bull{h}{3} \conn & & \Dvonn \connS & & \SWhite
\connS & & \SWhite \connendS \\ & \Black{5} \connbeginS & &
\bull{b}{2} \conn & & \SBlack \connS & & \bull{d}{2} \conn & &
\bull{e}{2} \conn & & \bull{f}{2} \conn & & \bull{g}{2} \conn & &
\bull{h}{2} \conn & & \SWhite \connS & & \SWhite \connendS & \\ & &
\bull{a}{1} \con & & \bull{b}{1} \con & & \Black{5} \conS & &
\bull{d}{1} \con & & \bull{e}{1} \con & & \bull{f}{1} \con & &
\bull{g}{1} \con & & \bull{h}{1} \con & & \White{2} & &} $

with
White to move. Some comments about notation : the left-slanted columns
are denoted by letters from a (left) to k (right) and the rows are
labeled 1 to 5 from bottom to top (surprisingly this ‘standard’
webgame-notation differs from the numbering on my Dvonn-board where the
rows are labeled from top to bottom…). So, for example, the three
spots on the upper right are k3,k4 and k5 (there are no k1 or k2 spots).
The three Dvonn pieces are colored red and in the course of the game a
stack may land on a Dvonn piece and so stacks containing a Dvonn piece
are denoted with a red halo. For example, the symbol on spot f3 stands
for for a stack of 6 pieces, one of which is a red Dvonn piece, under
the control of Black (that is, the top-piece is Black). Further note
that a piece or stack can only move if it is not surrounded by 6 other
pieces or stacks (so the White pieces on j3 and j4 cannot (yet) move). A
piece can only move by one step in either line-direction provided there
is another piece or stack on that position. The same applies for stacks
: an height 3 stack for example can move in each lin-direction by
exactly 3 steps provided there is a piece or stack to jump onto. For
example, the height 6 stack on d4 can only move to j4 whereas the height
6 stack on f3 cannot move at all! Similarly, the two black height 5
stacks are immobile. At the moment black has all its stacks defended,
that is, if White should be able to jump onto one of them (which White
cannot at the moment), Black can use one of its neighbouring pieces to
take the stack back under its control. So, any computer program would
‘evaluate’ the position as favourable for Black : Black has stacks of
total height 34 safely under control (there are no immediate threats to
be seen : the [horizon effect](http://www.comp.lancs.ac.uk/computing/research/aai-aied/people/paulb/old243prolog/subsection3_7_5.html) in such programs) whereas White
can only claim potential stacks of total height 13… Still, Black
has already lost the game. White has more pieces which are quite mobile
as opposed to the immobile black stacks, so Black will soon run out of
moves to make and his end position will have some large stacks on the
third row. All white has to do is to let Black run out of moves and then
continue (Dvonn forces each player to make a move if they still can and
to pass the move otherwise, so the most mobile player can still continue
long after the other player was forced to stop) to build a White stack
of the appropriate height on the third row to jump on the highest Black
stack with its last move! Here is how the play continued : 1) j2-k3 ;
a3-b3 2) i1-k3 ; c5-c3 3) i2-i3 ; c2-c3 4) i3-k3 ; d4-j4 5)
j3-j4 ; e3-f3 6) i4-j4 ; c4-b3 to arrive at the position where
Black is no longer able to make any moves at all

$\xymatrix@=.3cm
@!C @R=.7cm{ & & \bull{c}{5} \conn & & \bull{d}{5} \conn & & \bull{e}{5}
\conn & & \bull{f}{5} \conn & & \bull{g}{5} \conn & & \bull{h}{5} \conn
& & \SWhite \connS & & \SWhite \connS & & \SWhite \conneS & & \\ &
\bull{b}{4} \conn & & \bull{c}{4} \conn & & \bull{d}{4} \conn & &
\bull{e}{4} \conn& & \bull{f}{4} \conn & & \bull{g}{4} \conn & &
\bull{h}{4} \conn & & \bull{i}{4} \connS & & \White{9} \connS & &
\SWhite \conneS & \\ \bull{a}{3} \connbegin & & \Black{3} \connS & &
\BDvonn{10} \connS & & \bull{d}{3} \conn & & \bull{e}{3} \conn & &
\BDvonn{7} \connS & & \bull{g}{3} \conn & & \bull{h}{3} \conn & &
\bull{i}{3} \conn & & \bull{j}{3} \conn & & \WDvonn{6} \connendS \\ &
\Black{5} \connbeginS & & \bull{b}{2} \conn & & \bull{c}{2} \conn & &
\bull{d}{2} \conn & & \bull{e}{2} \conn & & \bull{f}{2} \conn & &
\bull{g}{2} \conn & & \bull{h}{2} \conn & & \bull{i}{2} \conn & &
\bull{j}{2} \connend & \\ & & \bull{a}{1} \con & & \bull{b}{1} \con & &
\bull{c}{1} \con & & \bull{d}{1} \con & & \bull{e}{1} \con & &
\bull{f}{1} \con & & \bull{g}{1} \con & & \bull{h}{1} \con & &
\bull{i}{1} & &} $

Note that all pieces and stacks no longer
connected to a Dvonn piece must be removed. So, for example, after the
third move by Black, the Black height 5 stacks on c1 was removed. All
white now has to do is to built an height 8 stack on k3 and jump onto
the height 10 Black stack on c3 to win the game. The (only) way to do
this is by 7. j5-k5 and 8. k5-k3 to finish with 9. k3-c3 with final
position (note again that the White right-hand pieces and stacks are no
longer connected to a Dvonn piece and are hence removed)

$\xymatrix@=.3cm @!C @R=.7cm{ & & \bull{c}{5} \conn & & \bull{d}{5}
\conn & & \bull{e}{5} \conn & & \bull{f}{5} \conn & & \bull{g}{5} \conn
& & \bull{h}{5} \conn & & \bull{i}{5} \conn & & \bull{j}{5} \conn & &
\bull{k}{5} \conne & & \\\ & \bull{b}{4} \conn & & \bull{c}{4} \conn &
& \bull{d}{4} \conn & & \bull{e}{4} \conn& & \bull{f}{4} \conn & &
\bull{g}{4} \conn & & \bull{h}{4} \conn & & \bull{i}{4} \conn & &
\bull{j}{4} \conn & & \bull{k}{4} \conne & \\\ \bull{a}{3} \connbegin
& & \Black{3} \connS & & \WDvonn{18} \connS & & \bull{d}{3} \conn & &
\bull{e}{3} \conn & & \BDvonn{7} \connS & & \bull{g}{3} \conn & &
\bull{h}{3} \conn & & \bull{i}{3} \conn & & \bull{j}{3} \conn & &
\bull{k}{3} \connend \\\ & \Black{5} \connbeginS & & \bull{b}{2} \conn
& & \bull{c}{2} \conn & & \bull{d}{2} \conn & & \bull{e}{2} \conn & &
\bull{f}{2} \conn & & \bull{g}{2} \conn & & \bull{h}{2} \conn & &
\bull{i}{2} \conn & & \bull{j}{2} \connend & \\\ & & \bull{a}{1} \con &
& \bull{b}{1} \con & & \bull{c}{1} \con & & \bull{d}{1} \con & &
\bull{e}{1} \con & & \bull{f}{1} \con & & \bull{g}{1} \con & &
\bull{h}{1} \con & & \bull{i}{1} & & } $

So White wins with 18 to
Black’s 15. This shows that it is important to maintain mobility and
also that it is possible to win a Dvonn-game from computers. In fact,
the above end-game was played against a computer-program (Black). The
entire game can be found
[here](http://www.littlegolem.net/jsp/game/game.jsp?gid=426457&nmove=91)
.

One Comment

a Da Vinci chess problem

Published December 30, 2005 by lievenlb

2005
was the year that the DaVinci code craze hit Belgium. (I started reading Dan Brown’s
Digital Fortress and Angels and Demons a year
before on the way back from a Warwick conference and when I read DVC a
few months later it was an anti-climax…). Anyway, what better way
to end 2005 than with a fitting chess problem, composed by Noam Elkies

The problem is to give an infinite sequence
of numbers, the n-th term of the sequence being the number of ways White
can force checkmate in exactly n moves. With the DVC-hint given, clearly
only one series can be the solution… To prove it, note that
White’s only non-checkmating moves are with the Bishop traveling
along the path (g1,h2,g3,h4) and use symmetry to prove that the number
of paths of length exactly k starting from h2 is the same as those
starting from g3…

If that one was too easy for you,
consider the same problem for the position

Here the solution are the 2-powers of those
of the first problem. The proof essentially is that White has now two
ways to deliver checkmate : Na6 and Nd7… For the solutions and
more interesting chess-problems consult Noam Elkies’ excellent
paper New directions in
enumerative chess problems. Remains the problem which sequences can
arise on an $N \\times N$ board with an infinite supply of chess
pieces!

Leave a Comment

bivalue Sudoku graphs

Published December 27, 2005 by lievenlb

Here is
a ‘difficult but not unsolvable’ Sudoku from David Eppstein‘s paper Nonrepetitive paths and cycles
in graphs with application to Sudoku.

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. | |
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y1 $

As always I try to solve
Sudokus without having to use backtracking (that
is, making a guess and working from there on to a solution or a
contradiction in which case one uses the other option). Clearly, this is
not well defined. When one starts solving Sudokus one often resorts to
backtracking but after a while one discovers rules which seem to avoid
backtracking (but in a sense are still). For example, if two cells in a
same block (or row or column) can only be filled with two numbers one
can use this fact by forbidding other numbers to occupy those cells.
However, this is a mini-backtracking strategy. Still, I allow all such
rules. More precisely, any formal rule is non-backtracking in my
dictionary. In Eppstein’s paper there is a good summary of the rules
most people apply when starting a Sudoku. He calls them the ‘local
rules’. Here they are

  • If a digit x has only one remaining
    cell that it can be placed in, within some row, column, or square, then
    we place it in that cell. Any potential positions of x incompatible with
    that cell (because they lie in the same row, column, or square) are
    removed from future consideration.
  • If a cell has only one
    digit x that can be placed in it, we place x in that cell. Incompatible
    positions for x are removed from future consideration.
  • If
    some three cells, formed by intersecting a row or column with a square,
    have three digits whose only remaining positions within that row,
    column, or square are among those three cells, we prevent all other
    digits from being placed there. We also remove positions for those three
    forced digits outside the triple but within the row, column, or square
    containing it.
  • If the cells of a square that can contain a
    digit x all lie in a single row or column, we eliminate positions for x
    that are outside the square but inside that row or column. Similarly, if
    the cells that can contain x within a row or column all lie in a single
    square, we eliminate positions that are inside that square but outside
    the row or column.
  • If two digits x and y each share the same
    two cells as the only locations they may be placed within some row,
    column, or square, then all other digits must avoid those two cells.
  • If the placement of digit x in cell y can not be extended to a
    placement of nine copies of x covering each row and column of the grid
    exactly once, we eliminate cell y from consideration as a placement for
    x.
  • If the placement of a digit x in cell y within a single
    row, column, or square can not be extended to a complete solution of
    that row, column, or square, then we eliminate that placement from
    consideration.

But even if one manages to use all
these rules (and frankly I only use a subset) one might get stuck. I
don’t know how many cells you can fill in the above problem with these
local rules, I’m afraid I only managed $5 $… At such
moments, the bivalue Sudoku-graph may come in handy. Eppstein defines
this as follows

In this graph, we create a vertex
for each cell of the Sudoku grid that has not yet been filled in but for
which we have restricted the set of digits that can fill it to exactly
two digits. We connect two such vertices by an edge when the
corresponding two cells both lie in a single row, column, or square, and
can both be filled by the same digit; the label of the edge is the
digit they can both be filled by.

Eppstein then goes
on to define new rules (each of which is a mini-backtracking strategy)
which often help to crack the puzzle. Here are Eppstein’s ‘global
rules’

  • If an edge in the bivalue graph belongs to a
    nonrepetitive cycle, the digit labeling it must be placed at one of its
    two endpoints, and can be ruled out as a potential value for any other
    cell in the row, column, or square containing the edge.
  • If
    the bivalue graph has a cycle in which a single pair of consecutive
    edges has a repeated label, that label can not be placed at the cell
    shared by the two edges, so that cell must be filled by the other of its
    two possible values.
  • If the bivalue graph contains two
    paths, both starting with the same label from the same cell, both
    ending at cells in the same row, column, or square, and such that in the
    two ending squares the values not occurring on the incident edge labels
    are equal, then the cell at the start of the paths can not be filled by
    the start label of the paths, and must be filled by the other of its two
    possible values.

For example, in the above problem it
is not hard to verify that the indicated places X,Y and Z form a
nonrepetitive cycle in the bivalue graph so applying the first global
rule we have two choices of filling these places (one leading to a
solution, the other to a contradiction)

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |.
|X|Y|8|3| |9| |2|Z|. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| |
|1| | | | |3|. \end{sudoku-block}y2 $

In fact, it turns out
that making this choice is enough to solve the puzzle by simple local
rules. So, if I change the original puzzle by filling in the cell X

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |.
| | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. |6|
|8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1|
| | | |3|. \end{sudoku-block}y3 $

you will have no problem
solving the puzzle.

Leave a Comment