Алгоритм выигрышной руки в маджонге - PullRequest
Новая
       11

Алгоритм выигрышной руки в маджонге

2 голосов
/ 08 февраля 2011

Я ищу алгоритм, который определит, является ли текущая рука маджонга выигрышной. Если вы не знакомы с игрой, вот основная идея (упрощенно):

  • Существует три масти плиток, каждая из которых содержит плитки 1–9. Есть также специальные плитки, их семь видов. Каждая плитка существует в четырех экземплярах, поэтому существует 36 плиток каждой масти и 28 специальных плиток.
  • В руке есть 14 плиток.
  • A чау - это набор из трех плиток одного ранга в последовательности.
  • A pong - это набор из трех одинаковых плиток.
  • A kong - это набор из четырех одинаковых плиток.
  • A pair - это набор из двух одинаковых плиток.
  • Выигрышная комбинация - это та, в которой плитки образуют любое количество чау, понгов и / или конгов и одну пару.

Рука сортируется по масти, а затем по рангу. Моя идея примерно такая:

  1. Пометить все плитки как не посещенные и не выигранные.
  2. Посетите первую не посещенную плитку.
  3. Проверяйте последующие плитки до тех пор, пока не встретите чау, понг или конг или пока нет возможности этого. Если комбинация завершена, отметьте все участвующие плитки как посещенные и выигравшие
  4. Если все плитки были посещены, проверьте, все ли выигрыши. Если не все плитки были посещены, перейдите к 2.

Проблема в том, что если плитка является частью комбинации, она не может быть участником любой другой комбинации, которая может сделать руку выигрышной.

Есть идеи для рабочего алгоритма?

1 Ответ

0 голосов
/ 09 февраля 2011

Ваш алгоритм в порядке, если вы встроили его в алгоритм обратного отслеживания (http://en.wikipedia.org/wiki/Backtracking).. Самый простой способ сделать это - вызвать ваш метод рекурсивно, как только вы нашли подходящую пару / чау / ..., но сбросить текущий Если это не так. В псевдокоде это выглядит примерно так: 

1. Mark all tiles as nonwinning
2. Call function Backtracking

Function Backtracking:
1. If all tiles are marked winning return WINNING else NONWINNING
2. Visit tiles as described in your algorithm
3. When found a chow/pong/... or the first pair    
   3.1. Mark those tiles as winning.     
   3.2. Afterwards call method Backtracking.    
   3.3. If return value of 3.2 is WINNING also return WINNING    
   3.4. Else unmark the tiles as nonwinning again    
4. If not finished search for pair/chow/... by looping to 3.
5. All combinations are done and no winning movewas found so return NONWINNING

Идея состоит в том, что вы сначала пробуете каждую пару / ... как часть выигрышной руки, но если это не сработает, просто попробуйте то же самое, предполагая, что это не часть выигрышной руки.

Если вас интересует не только выигрышная комбинация, но и все возможные комбинации выигрышных пар / чау-чау / ... пропустите возврат на шаге 3.3.

...