Вопрос для интервью: создать объектно-ориентированный дизайн для судоку

Question

Я ответил, что у меня будет 2d массив.

И тогда у меня будет 3 функции

• одна для проверки горизонтального состояния.
• другаяфункция для проверки вертикального состояния
• и еще одна для проверки состояния блока 3 * 3.

---

Но он не удовлетворен, может ли кто-нибудь дать хороший ответ на этовопрос?

Я нашел эту ссылку переполнения стека, связанную с моим вопросом. Справка по программированию - Как структурировать программу Sudoku Solver? .

Но я хочу получить правильный объектно-ориентированный дизайн (например, классы, наследование и другие детали), которые совпадают.от меня ожидал интервьюер.

Answer 1

Для меня ваш дизайн начинается с класса "регион".Затем вы можете расширить его до «горизонтальной области», «вертикальной области» и «квадратной области» в качестве трех типов областей.Изменить: при дальнейшем рассмотрении вам на самом деле не нужно проводить это различие, если только оно не для целей отображения ... алгоритмически оно будет таким же.

Затем вы можете сделать свой 2d массив "элементов" и добавитьэлементы в соответствии с вашими регионами, которая обеспечивает сеть для ваших расчетов.Ваши элементы имеют список потенциальных значений, и ваши регионы несут ответственность за удаление этих потенциальных значений.Когда вы нашли значение, оно запускает регионы, членом которых он является, для удаления потенциальных значений из них.

Answer 2

Если вопрос был просто «Что такое объектно-ориентированный дизайн для Судоку», и вы ушли и начали рассказывать ему что-то, он, возможно, был разочарован тем, что вы не спрашивали о реальных требованиях.«Судоку» довольно широк.Просто представление данных?Решатель?А значит играть?Валидатор?Создатель головоломки?

Пока вы не знаете, что он хотел, чтобы вы строили, вы не сможете разработать решение.

Answer 3

Для базовых классов решателя я вижу хорошее начало с Cell, ValidationRegion, Board и Pattern в качестве основных классов.

Cell: содержит текущее значение ячейки, оставшиеся возможные значения ячейки и фиксированная ячейка или нет.

ValidationRegion: имеет ссылки на соответствующие ячейки.9 Cells на Board.Этот класс на самом деле не должен знать, представляет ли он горизонтальные, вертикальные или квадратные области, потому что правила одинаковы.Этот класс имеет метод validate () для проверки возможности текущего состояния региона.

Board: имеет полный макет Cells и соответствующим образом инициализирует фиксированный ValidationRegions, передаваясоответствующий Cells ссылкой.Он также имеет метод solve, который применяет Patterns в заранее определенном порядке до тех пор, пока не будет достигнуто решение или пока не будет определено, что решение невозможно (поэтому метод грубой силы должен быть последним усилием рва).

Pattern: Абстрактный класс, имеющий метод apply(Board), который применяет данный шаблон к указанному объекту платы (удаляет возможности из Cells и устанавливает их, когда он знает, что осталась только одна возможность).Начиная с Sudoku Dragon - стратегия судоку , вы, вероятно, будете реализовывать такие шаблоны, как OneChoicePattern, SinglePossibilityPattern, OnlySquareRule и т. Д.

Answer 4

Я не уверен в этом, но у меня есть ощущение, что интервьюер, вероятно, хотел что-то вроде шаблона MVC и т. Д., Дизайн / архитектура высокого уровня. Затем в этом контексте у вас будет три модуля / компонента: модель, представление и контроллер. Каждый из которых состоит из одного или нескольких классов. Для большинства интерактивных приложений применим этот шаблон или некоторый вариант / связанный шаблон.

Я бы сказал, этого было бы достаточно. Поскольку во время собеседования у вас не хватает времени на то, чтобы придумать детали занятий, этого не требуется (по крайней мере, в типичных случаях).

Answer 5

Два выдающихся класса поднимаются из этой задачи: основная игровая доска и ячейка, содержащая значение.

В C # это будет:

// Main game board
public class BoardGame{
   List<List<Cell> cells = new List<List<Cell>>();
   public BoardGame(int dimention){
      // Initialize and add cells to the cells attribute
   }
   public bool HorizLineContainsValue(int lineNumber, value){
      // return true if any cell in horiz. line number contains value
   }
   public bool VertLineContainsValue(int lineNumber, value){
      // return true if any cell in vertic. line number contains value
   }
}
public class Cell {
   // X index on the game board
   public int X{get; set;}
   // Y index on the game board
   public int Y{get; set;}
   // Value of this cell
   public int Value{get; set;}
   // Set game board 
   public GameBoard GameBoard{set;}
   public boolean AcceptValue(int value){
        // Ask the game board if cells on horizontal line X have this value
        // Ask the game board if cells on vertical line Y have this value
        // And return true or false accordingly
   }
}

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

Answer 6

Для объектно-ориентированного подхода к судоку я бы сделал что-то вроде этого (просто используя простые имена):

A NumberSpace - это один квадрат на доске Судоку и может содержать число от1-9.

A Block - это группа из 9 NumberSpace s в шаблоне 3x3, которая, вероятно, будет просто представлена ​​в классе как многомерный массив объектов NumberSpace.Методы для этого могут включать (bool)validate, который будет проверять, чтобы убедиться, что ни один номер не повторяется на блок.

Наконец, Board будет представлять всю игровую область, где будет другой массив (3x3) из Block s.Методы для этого класса будут включать средства для проверки правильности столбцов / строк.