75:
202:
pedestals of matching color until one player connects the two opposite sides of the board marked in the player's color. A variant of the game is described in the instructions: each player gets a limited number of bridges, say 10. If neither player has won when all the bridges are placed, a player in his turn, may reposition one of his bridges until a winner results. The game is long out of production.
174:
201:
under the name Bridg-It. The game consisted of a plastic board with two interleaved 5x6 rectangular grids of pedestals (one set yellow, the other red), two sets of 20 each red and yellow plastic bridges, and matching pegs to mount them on. Players alternate placing a bridge across any two adjacent
193:
Oct. 1958, two grids of differently-colored dots are overlaid at an offset. One player links orthogonally adjacent dots on one grid, and the other player uses the other. One player attempts to link the top of their grid to the bottom, while the other tries to link their left side to the right. The
243:
An extension of Gale, called Qua, is played by three players on a 3D game board cube composed of a grid of N cells. N is an odd number equal to the number of cells along the edges of the game board cube. The initial Qua Cube game board layout and rules are described at its Board Game Geek entry.
240:". Players alternate drawing in a vertical or horizontal line connecting any two adjacent dots. When a line completes a square, the player initials the square. After all the lines have been filled in, the player who has taken the most squares is the winner.
232:
is played on a grid of hexagons, and has 6-connectivity. Generalized Hex is played on a graph, just like the
Shannon game, but instead of coloring the edges, in Hex the players color the vertices. These games have completely different structure and properties.
50:. One player has the goal of connecting two distinguished vertices by a path of edges of their color. The other player aims to prevent this by using their color instead (or, equivalently, by erasing edges). The game is commonly played on a
118:, Short wins. The game always terminates after a finite number of moves, and one of the two players has to win. Either Short, Cut, or the player moving first is guaranteed the existence of a winning strategy on any given graph.
102:, and alternate moves. On Cut's turn, Cut deletes from the graph a non-colored edge of their choice. On Short's turn, Short colors any edge still in the graph. If Cut manages to turn the graph into one where
569:
Cláudio, A. P.; Fonseca, S.; Sequeira, L.; Silva, I. P. (2015). "Shannon switching game and directed variants". In
Bourguignon, J.-P.; Jeltsch, R.; Pinto, A.A.; Viana, M. (eds.).
318:
298:
278:
355:
of the starting graph. The problem of testing for the existence of two disjoint trees, each connecting the distinguished vertices, can be represented as a
194:
game is equivalent to the
Shannon switching game played on a rectangular grid. No draw can result; the first player can always win with correct play.
129:
games are a duality; that is, the game can be restated so that both players have the same goal: to secure a certain edge set with distinguished edge
571:
Dynamic, Games and
Science: International Conference and Advanced School Planet Earth, DGS II, Portugal, August 28–September 6, 2013
236:
Another connectivity game played with paper and pencil on a rectangular array of dots (or graph paper) is the children's game of "
586:
46:, the "father of information theory", some time before 1951. Two players take turns coloring the edges of an arbitrary
280:
including the two distinguished vertices, as well as two disjoint subsets of the remaining unchosen edges supported on
761:
787:
782:
542:
458:
359:
problem, which can be solved in polynomial time. Alternatively, it is possible to solve the same problem using
146:
47:
300:, such that either of the two subsets (together with already chosen edges) would connect all vertices in
165:
have been described for theoretical purposes; but no corresponding commercial games have been published.
792:
777:
499:
17:
797:
252:
An explicit solution for the undirected switching game was found in 1964 for any such game using
737:
479:
442:
360:
356:
352:
138:
8:
198:
741:
696:
677:
537:
518:
430:
303:
283:
263:
222:
94:. Each edge of the graph can be either colored or removed. The two players are called
582:
555:
54:; this special case of the game was independently invented by American mathematician
522:
745:
725:
716:
700:
686:
654:
650:
574:
551:
508:
467:
422:
229:
162:
110:
are no longer connected, Cut wins. If Short manages to create a colored path from
733:
617:
578:
475:
438:
340:
35:
601:
78:
Player Cut took 3 turns (dotted edges), player Short took 4 turns (green edges).
672:
471:
392:
237:
206:
186:
158:
43:
771:
605:
83:
691:
513:
494:
397:
The Second
Scientific American Book of Mathematical Puzzles and Diversions
668:
641:
Mansfield, Richard (1996). "Strategies for the
Shannon switching game".
197:
A commercial board game implementing the scheme was marketed in 1960 by
729:
456:
Hayward, Ryan B.; van
Rijswijck, Jack (2006). "Hex and combinatorics".
434:
182:
55:
51:
339:
hard, optimal moves for the undirected switching game can be found in
74:
39:
495:"An implemented graph algorithm for winning Shannon Switching Games"
426:
324:
can make a move that results in a position with this property, then
225:, in which the winning patterns for the Maker are connecting paths.
573:. CIM Series in Mathematical Sciences. Springer. pp. 187–199.
413:
Lehman, Alfred (1964). "A solution of the
Shannon switching game".
260:
should aim for a position in which there exists a set of vertices
253:
210:
673:"A Combinatorial Problem Which is Complete in Polynomial Space"
336:
221:
The
Shannon switching game can be seen as a special case of a
415:
Journal of the
Society for Industrial and Applied Mathematics
372:
328:
can win regardless of what the other player does; otherwise,
145:
makes up a cutset, the minimal set of edges that connect two
343:
per move. After removing from the graph the edges chosen by
173:
568:
375:, a different and harder connection game on the square grid
764:, a Java implementation of the Shannon switching game
714:
Reisch, Stefan (1981). "Hex ist PSPACE-vollständig".
540:(1986). "Directed switching on graphs and matroids".
306:
286:
266:
535:
455:
157:Versions of the Shannon switching game played on a
312:
292:
272:
141:, while Cut tries to secure an edge set that with
335:Unlike some other connection games, which can be
769:
492:
181:In this game invented by American mathematician
133:. Short tries to secure the edge set that with
216:
205:An electronic implementation of the Game of
247:
690:
640:
512:
399:. NY: Simon and Schuster. pp. 86–87.
634:
408:
406:
172:
73:
391:
14:
770:
713:
412:
347:, and contracting the edges chosen by
42:mathematician and electrical engineer
403:
667:
24:
58:in the late 1950s and is known as
25:
809:
755:
643:The American Mathematical Monthly
228:A weakly-related connection game
27:Pencil and paper connection game
707:
661:
543:Journal of Combinatorial Theory
82:The game is played on a finite
655:10.1080/00029890.1996.12004732
610:
595:
562:
529:
486:
449:
385:
13:
1:
379:
38:for two players, invented by
579:10.1007/978-3-319-16118-1_10
556:10.1016/0095-8956(86)90083-3
7:
366:
351:, the resulting graph is a
217:Relationship to other games
152:
10:
814:
472:10.1016/j.disc.2006.01.029
500:Communications of the ACM
493:Stephen M. Chase (1972).
248:Computational complexity
86:with two special nodes,
69:
788:Abstract strategy games
536:Hamidoune, Yahya Ould;
168:
783:Paper-and-pencil games
314:
294:
274:
178:
79:
32:Shannon switching game
692:10.1145/321978.321989
514:10.1145/361284.361293
315:
295:
275:
177:A win for red in Gale
176:
77:
466:(19–20): 2515–2528.
459:Discrete Mathematics
357:matroid partitioning
304:
284:
264:
209:is available in the
538:Las Vergnas, Michel
199:Hassenfeld Brothers
191:Scientific American
730:10.1007/BF00288964
678:Journal of the ACM
310:
290:
270:
223:Maker-Breaker game
211:Ludii Games Portal
179:
80:
588:978-3-319-16117-4
313:{\displaystyle S}
293:{\displaystyle S}
273:{\displaystyle S}
185:and described in
16:(Redirected from
805:
793:Connection games
778:Positional games
750:
749:
717:Acta Informatica
711:
705:
704:
694:
671:(October 1976).
665:
659:
658:
638:
632:
631:
629:
628:
614:
608:
599:
593:
592:
566:
560:
559:
533:
527:
526:
516:
490:
484:
483:
453:
447:
446:
410:
401:
400:
389:
319:
317:
316:
311:
299:
297:
296:
291:
279:
277:
276:
271:
163:oriented matroid
52:rectangular grid
21:
813:
812:
808:
807:
806:
804:
803:
802:
768:
767:
758:
753:
712:
708:
666:
662:
639:
635:
626:
624:
616:
615:
611:
600:
596:
589:
567:
563:
534:
530:
491:
487:
454:
450:
427:10.1137/0112059
411:
404:
390:
386:
382:
369:
341:polynomial time
305:
302:
301:
285:
282:
281:
265:
262:
261:
250:
219:
171:
155:
72:
36:connection game
28:
23:
22:
15:
12:
11:
5:
811:
801:
800:
798:Claude Shannon
795:
790:
785:
780:
766:
765:
757:
756:External links
754:
752:
751:
724:(2): 167–191.
706:
685:(4): 710–719.
660:
649:(3): 250–252.
633:
609:
594:
587:
561:
550:(3): 237–239.
528:
507:(4): 253–256.
485:
448:
421:(4): 687–725.
402:
383:
381:
378:
377:
376:
368:
365:
309:
289:
269:
249:
246:
238:dots and boxes
218:
215:
187:Martin Gardner
170:
167:
159:directed graph
154:
151:
71:
68:
44:Claude Shannon
26:
9:
6:
4:
3:
2:
810:
799:
796:
794:
791:
789:
786:
784:
781:
779:
776:
775:
773:
763:
760:
759:
747:
743:
739:
735:
731:
727:
723:
719:
718:
710:
702:
698:
693:
688:
684:
680:
679:
674:
670:
664:
656:
652:
648:
644:
637:
623:
622:BoardGameGeek
619:
613:
607:
606:BoardGameGeek
603:
598:
590:
584:
580:
576:
572:
565:
557:
553:
549:
545:
544:
539:
532:
524:
520:
515:
510:
506:
502:
501:
496:
489:
481:
477:
473:
469:
465:
461:
460:
452:
444:
440:
436:
432:
428:
424:
420:
416:
409:
407:
398:
394:
388:
384:
374:
371:
370:
364:
362:
358:
354:
350:
346:
342:
338:
333:
331:
327:
323:
307:
287:
267:
259:
255:
245:
241:
239:
234:
231:
226:
224:
214:
212:
208:
203:
200:
195:
192:
189:'s column in
188:
184:
175:
166:
164:
160:
150:
148:
144:
140:
136:
132:
128:
124:
119:
117:
113:
109:
105:
101:
97:
93:
89:
85:
76:
67:
65:
61:
57:
53:
49:
45:
41:
37:
33:
19:
721:
715:
709:
682:
676:
663:
646:
642:
636:
625:. Retrieved
621:
612:
597:
570:
564:
547:
546:. Series B.
541:
531:
504:
498:
488:
463:
457:
451:
418:
414:
396:
387:
363:algorithms.
361:network flow
348:
344:
334:
329:
325:
321:
257:
251:
242:
235:
227:
220:
204:
196:
190:
180:
156:
142:
134:
130:
126:
122:
120:
115:
111:
107:
103:
99:
95:
91:
87:
81:
63:
59:
31:
29:
393:Gardner, M.
137:makes up a
772:Categories
762:Graph Game
627:2020-08-28
380:References
183:David Gale
56:David Gale
332:can win.
147:subgraphs
669:Even, S.
602:Bridg-it
523:21110956
395:(1961).
367:See also
256:theory.
153:Variants
64:Bridg-It
40:American
18:Bridg-It
746:9125259
738:0599616
701:8845949
480:2261917
443:0173250
435:2946344
254:matroid
161:and an
139:circuit
744:
736:
699:
585:
521:
478:
441:
433:
337:PSPACE
742:S2CID
697:S2CID
618:"Qua"
519:S2CID
431:JSTOR
373:TwixT
353:minor
349:Short
326:Short
322:Short
320:. If
258:Short
123:Short
96:Short
84:graph
70:Rules
48:graph
34:is a
583:ISBN
207:Gale
169:Gale
125:and
121:The
106:and
98:and
90:and
60:Gale
30:The
726:doi
687:doi
651:doi
647:103
604:at
575:doi
552:doi
509:doi
468:doi
464:306
423:doi
345:Cut
330:Cut
230:Hex
127:Cut
114:to
100:Cut
62:or
774::
740:.
734:MR
732:.
722:15
720:.
695:.
683:23
681:.
675:.
645:.
620:.
581:.
548:40
517:.
505:15
503:.
497:.
476:MR
474:.
462:.
439:MR
437:.
429:.
419:12
417:.
405:^
213:.
149:.
66:.
748:.
728::
703:.
689::
657:.
653::
630:.
591:.
577::
558:.
554::
525:.
511::
482:.
470::
445:.
425::
308:S
288:S
268:S
143:e
135:e
131:e
116:B
112:A
108:B
104:A
92:B
88:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
