Как сделать судоку на java
Обновлено: 06.07.2024
Сейчас мы будем делать следующее:
1. анализировать задачу, варианты реализации программы и разрабатывать требования к ней;
2. выполнить анализировать требования и проектировать;
3. реализовывать программу и проверять правильность ее работы.
1 Анализ задания на разработку
1.1 Процесс игры
При игре на бумаге, нередко возникают ситуации, когда игрок поставил неправильную цифру (например, две одинаковые цифры в строке), но не заметил это и продолжил играть. При игре на компьютере этого можно избежать, например, подсвечивая строку, столбец или квадрат, в котором допущена ошибка. В остальном процесс игры на компьютере не отличается от классических правил [1]:
Игровое поле представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9), называемые подсказками. От игрока требуется заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
На рисунке показан результат подсветки строки и маленького квадрата при некорректном вводе (была введена цифра 5).
1.2 Рейтинг, авторизация
В старых компьютерных играх, которые тоже были однопользовательскими, нередко после успешного завершения игры проверялся факт попадания результата пользователя в таблицу рекордов. В случае попадания — выпадала форма ввода логина. Однако, в данном случае, было бы здорово сразу после запуска программы открыть пользователю тот уровень, который он еще не прошел — для этого нужно сразу запросить у пользователя логин и пароль, то есть нужна форма авторизации.
1.3 Форматы файлов
Программа хранит в файлах информацию о пользователях и использует файлы уровней (загружает с них информацию). Все файлы должны находиться в текущем каталоге приложения.
Чтобы добавить в игру новые уровни достаточно добавить в каталог программы новые файлы в заданном формате.
2 Проектирование
2.1 Модель предметной области
В соответствии с описанием задачи можно сразу выделить ряд сущностей — построить модель предметной области (словарь системы). В статье [2] отмечается что для этого удобно использовать нотацию диаграммы классов UML. Соответствующая диаграмма приведена на рисунке:
На рисунке показано, что приложение состоит из ряда окон — GameWidget , AuthWidget и TopResults , назначение которых понятно из названия.
Игровой экран содержит игровое поле ( Field ) и таймер ( TimerWidget ), при этом игровое поле состоит из ячеек ( Item ). Отношение композиции на диаграмме классов показывается стрелкой с ромбом.
Все три типа окон зависят от данных о пользователях, объект управляющий пользователями обозначен как Users . Зависимость (ассоциация) на диаграмме показана штриховой линией.
2.2 Диаграмма потока экранов
Значительную часть поведения системы занимает описание логики переключения экранов, Фаулер предложил использовать для этого диаграмму потока экранов [3], в других источниках подобный вид диаграмм называется картой диалоговых окон , стандарта на него нет, однако могут использоваться элементы нотации диаграммы классов UML [4].
Соответствующая диаграмма приведена на рисунке:
3 Реализация и тестирование
Для реализации программы выбран язык С++ и библиотека Qt5, для разработки используется IDE Qt Creator.
3.1 Верстка графического интерфейса
Основная сложность в работе этой программы заключается в разработке удобного пользовательского интерфейса. В IDE Qt Creator для этого можно использовать встроенный инструмент Qt Designer, позволяющий разрабатывать интерфейс путем перетаскивания элементов на форму мышкой. Таким образом сверстаны окно авторизации и окно таблицы рекордов. На рисунке показан процесс верстки:
Процесс верстки при этом сводится к:
- 1. перетаскиванию нужных элементов на форму;
- 2. установки компоновщика (в обоих формах используется компоновка по сетке).
- 3. установка имен объектов (панель справа на рисунке).
Итак, было сверстано 2 формы. Для окна GameWidget класс создавался вручную, так как он содержит не очень много элементов управления, но они являются нестандартными. Для размещения объектов на форме при этом использовался компоновщик QGridLayout (приведен фрагмент кода конструктора GameWidget ):
3.2 Реализация поведения
3.2.1 Класс таймера
Подход к реализации таймера описан там. Тут приведена несколько другая реализация (использует QLabel вместо QLCDNumber и имеет пару дополнительных функций.
В библиотеке Qt есть типа QTime для представления времени и класс QTimer для отсчета промежутков времени. Однако, нет готового элемента для отображения таймера. Такой элемент был создан вручную.
TimerWidget использует QLabel для отображения текста на экране, QTime для хранения текущего времени и QTimer для отсчета секунд. Виджет создает все эти объекты, настраивает QTimer на выдачу сигналов раз в секунду и подписывается на эти сигналы. При получении сигнала увеличивает хранимое значение времени и обновляет содержимое на QLabel . Наиболее интересным при этом является конструктор (выполняющий настройку таймера ( setInterval ) и подписку на сигнал ( connect ):
3.2.2 Классы Item
Объекты типа Item должны располагаться на классе Field (виджете). При этом удобно использовать компоновку по сетке ( QGridLayout ), поэтому класс Item наследуется от QWidget .
Все ячейки на поле могут менять цвет если пользователь допускает ошибку, для этого базовый класс Item хранит поле color и имеет метод установки цвета. Тип цвета реализован с помощью enum :
enum class Color < Ok, Wrong >;
Установка цвета ячейки реализована с помощью каскадных таблиц стилей Qt (QSS):
Ячейка возвращает значение (имеет метод value ), если значение не установлено — вернет ноль. Это заведомо некорректное значение (пользователь такое значение в ячейку ввести не сможет) — поэтому можно будет узнать что ячейка пуста.
Проверка пользовательского ввода — запрет ввода в ячейки символов, отличных от цифр и ввод чисел не принадлежащих диапазону [1,9] реализована с помощью стандартного валидатора Qt — QIntValidator, настройка которого выполняется в конструкторе класса ItemEdit .
3.2.3 Окно игры
Виджет игры помимо добавления элементов интерфейса выполняет загрузку данных уровня с файла и обработку событий:
- начало игры (от кнопки);
- открытия статистики (от кнопки);
- победы (от игрового поля), при этом изменяется информация об уровне игрока и загружается новый уровень:
- загрузки нового уровня, при этом извлекается информация об уровне игрока ( N ), формируется строка типа "level_N" и выполняется попытка открытия файла с последующей загрузкой данных уровня в объект класса Field :
Наиболее сложным классом в игре является игровое поле (класс Field ), он хранит набор ячеек ( Item ) в виде двумерного вектора:
и реализует достаточно простые методы для проверки корректности строки, столбца и квадрата (части матрицы), заданного двумя углами. Аналогичный набор метод добавлен для установки цвета (если в линии найдена ошибка — то линии выставляется соответствующий цвет).
При проверке на наличие ошибок используется структура данных std::set (словарь), которая хранит данные в упорядоченном виде, за счет чего позволяет быстро выполнять поиск. В этот словарь последовательно помещаются все элементы заданной части матрицы, при этом если окажется что значение очередного элемента было добавлено в словарь ранее — значит пользователь допустил ошибку (в строке/столбце или квадрате две одинаковые цифры):
- в 6 строке выполняется проверка клетки на пустоту (пустые клетки игнорируются);
- в 8 строке выполняется поиск текущего числа в словаре, если он найден — то функция find вернет итератор, отличный от end(), тогда функция возвращается false. Иначе — выполняется вставка и переход к следующему числу.
3.2.4 Работа с пользователями
Частично работа с пользователями описана в статье «Реализация авторизации и регистрации«, однако там не затронута реализация таблицы рекордов.
Работа с пользователями реализована в классе Users , при этом одного пользователя описывает такая структура
Для пользователя определен оператор сравнения для того, чтобы сортировать их по уровню и затраченному времени (в таблице рекордов):
Список пользователей хранится в бинарном файле, но в объекте типа Users он же хранится в виде вектора — это позволяет более эффективно получать информацию о них, ведь эта информация в программе нужна многократно (при авторизации, смене уровня или просмотре статистики).
Класс Users позволяет загружать данные с файла в вектор, сохранять их в файле, выполнять поиск пользователя по паре логин/пароль и просто по логину, добавление пользователя, добавления пройденного уровня для пользователя и получение списка всех пользователей.
3.3 Тестирование программы
В моем последнем вопросе, который мы видели здесь: Sudoku - региональное тестирование Я спросил, как проверить регионы 3x3, и кто-то смог дать мне удовлетворительный ответ (хотя в нем участвовало много времени, чтобы заставить его работать так, как я хотел, Назовите, что такое класс table_t.)
Я закончил проект и смог создать генератор судоку, но он чувствует, что он надуман. И я чувствую, что я как-то переусердствовал, приняв очень грубый подход к созданию головоломок.
По сути, моя цель - создать сетку 9x9 с областями 9- 3x3. Каждая строка /col/region должна использовать числа 1-9 только один раз.
Способ, которым я решил это решить, состоял в использовании двумерного массива для случайного размещения чисел, по 3 строки за раз. После того, как будут выполнены 3 строки, он проверит 3 строки и 3 области и каждую вертикальную колонку до 3-й позиции. По мере его повторения он будет делать то же самое до тех пор, пока массив не будет заполнен, но из-за того, что я заполнял rand и проверял каждую строку/столбец/область несколько раз, он считался очень неэффективным.
Есть ли "более простой" способ сделать это с помощью любого типа данных, кроме двухмерного массива? Есть ли более простой способ проверить каждую область 3x3, которая может совпадать с проверкой верста или горизонтали лучше? С точки зрения вычисления я не вижу слишком много способов сделать это более эффективно, не сильно увеличивая размер кода.
Я понимаю, как он проверяет строки и столбцы, но для валидатора сетки 3x3:
Что такое offset и как он помогает проверить каждую ячейку в сетке 3x3? Я перебрал его и попробовал сначала x=0, y=0 , offset=0 и offset=1 , но offset=1 дает int ox = 1%3 = 1; и int oy = 1/3 , поэтому >, а что представляет собой ячейка [1/3] и так далее?
3 ответа
Когда вы делите n на m, оба являются int (либо литералами, либо переменными), результат также является int, поэтому 1/3 -> 0 Следовательно, когда offset == 0 => ox = 0, oy = 0 offset == 1 = > ox = 1, oy = 0 offset == 2 => ox = 2, oy = 0 offset == 3 -> ox = 0, oy = 1 . следовательно, вы будете красиво зацикливать 3 строки и 3 столбца
Ваш подход HashSet выглядит неплохо, но требует небольшой настройки .
Предполагается, что если в первом блоке отсутствует дублирование и одна и та же позиция во всех блоках также не дублируется, тогда судоку решается.
Во внешнем цикле вы должны просмотреть значения только первого блока.
Большой трюк состоит в том, чтобы избежать отдельных циклов для координат x и y .
Поскольку Java является объектно-ориентированным языком программирования, я предлагаю использовать объекты для определения координат. Мы могли бы хранить их в массиве (установить закладку, вместо этого я обычно говорю "Коллекция" . ) и перебирать ее с помощью простого цикла форчинга .
Также нам нужно иметь дело с фиксированным количеством объектов, которые мы знаем заранее (есть 9 блоков по 9 позиций в каждом . ) поэтому я предлагаю использовать Java enums следующим образом: Итак, ваша логика должна выглядеть так:
Надеюсь, я продемонстрировал полезность перечислений Java и важность хороших имен идентификаторов.
Igor, потому что язык элементарный, учится за день почти полностью) открыл документацию, прочитал, поехали.
Там же нету ничего, что можно было бы думать.
Kirill, посмотрите. Я отрицательно отношусь к пропагандистским авторам, но этот видос и правда очень-очень, да и крыть его нечем. Там мальчик сделал картонный танк и тестировал его призматическую броню из спичкострела.
Kirill, если находите время отвечать в ВК-шечке, то и видос есть время посмотреть на YouTube. Узнаете там в себе одного из персонажей.
Igor, если вы хотите сказать, что я зря гоню на js, то я это делаю не зря. Учиться надо на нормальных языках, в которых достаточно костылей, чтобы на них учиться.
А на js надо просто начать кодить, если решил заниматься фронтом. Js язык плохой, и сделать лучше нельзя.
Читайте также: