1 /* 2 SPDX-FileCopyrightText: 2009-2011 Graeme Gott <graeme@gottcode.org> 3 4 SPDX-License-Identifier: GPL-3.0-or-later 5 */ 6 7 #ifndef TANGLET_SOLVER_H 8 #define TANGLET_SOLVER_H 9 10 #include "trie.h" 11 12 #include <QHash> 13 #include <QPoint> 14 #include <QVector> 15 16 /** 17 * @brief The Solver class finds all of the words on a board. 18 */ 19 class Solver 20 { 21 /** 22 * @brief The Solver::Cell struct represents a letter on the board. 23 */ 24 struct Cell 25 { 26 QString text; /**< text of the letter */ 27 QVector<Cell*> neighbors; /**< which letters are connected to this one */ 28 QPoint position; /**< location on the board */ 29 bool checked; /**< has it been used while building a word */ 30 }; 31 public: 32 /** 33 * Constructs a solver instance. 34 * @param words the optimized word list 35 * @param size the size of the board 36 * @param minimum the shortest allowed word 37 */ 38 Solver(const Trie& words, int size, int minimum); 39 40 /** 41 * Finds the solution to a board. 42 * @param letters the board layout 43 */ 44 void solve(const QStringList& letters); 45 46 /** 47 * @return how many words were found 48 */ count()49 int count() const 50 { 51 return m_count; 52 } 53 54 /** 55 * @return all of the words and their locations on the board 56 */ solutions()57 QHash<QString, QList<QList<QPoint>>> solutions() const 58 { 59 return m_solutions; 60 } 61 62 /** 63 * The maximum score available on the board. 64 * @param max how many words to limit the score to 65 * @return the score of the board 66 */ 67 int score(int max = -1) const; 68 69 /** 70 * The score for a word. 71 * @param word the word to check 72 * @return how many points there word is worth 73 */ 74 static int score(const QString& word); 75 76 /** 77 * Sets if the solve keeps track of the locations of words as it solves. 78 * @param track_positions whether to track positions 79 */ 80 void setTrackPositions(bool track_positions); 81 82 private: 83 /** 84 * Checks if cell is part of or the final cell of a word while solving. 85 * @param cell location to check 86 */ 87 void checkCell(Cell& cell); 88 89 private: 90 const Trie* m_words; /**< fast access word list */ 91 const Trie::Node* m_node; /**< current letter being checked in word list */ 92 int m_size; /**< how many cells wide is the board */ 93 int m_minimum; /**< the shortest allowed word */ 94 bool m_track_positions; /**< remember locations of each word when solving */ 95 QVector<QVector<Cell>> m_cells; /**< layout of board */ 96 97 QString m_word; /**< word currently being assembled */ 98 QList<QPoint> m_positions; /**< locations of letters in word being assembled */ 99 100 QHash<QString, QList<QList<QPoint>>> m_solutions; /**< words found and their positions on the board */ 101 int m_count; /**< how many words have been found */ 102 }; 103 104 #endif // TANGLET_SOLVER_H 105