Writing a Word Search puzzle solver in SQL
Brace yourself for yet another pretty useless demonstration of the unexpected wonders of SQL as well as my apparent lack of meaningful things to do with my life.
Undoubtedly, you are familiar with Word Search puzzles, the type of puzzle that present a matrix with a mash of letters in which specific words have been hidden. For example:
This Word Search contains the names of several countries (such as italy, holland, poland, spain, france, japan, togo, peru). If you look closely, you will find them:
In this article, I will show you – and I know this is something you have been waiting for – how a SQL Query can solve these puzzles for you:
The first in solving our Word Search puzzles is expressing them in a format we can handle in a SQL query. Of course we can store them in database tables, but we can take a short-cut, using a Collection Type and the Table Operator.
We define the type WORD_LIST
create type word_list is table of varchar2(500)/
and use it to instantiate in situ in our query a collection of strings, each representing one row in the Word Search Matrix:
with matrix as( select rownum seq , lower(column_value) txt from table ( word_list( 'FYYHNRD' , 'RLJCINU' , 'AAWAAHR' , 'NTKLPNE' , 'CILFSAP' , 'EOGOTPN' , 'HPOLAND' ) ))
The above in-line view is the initial section our Word Search Solving Query. The result of this query is:
The basic algoritm of the Word Search Solver is like this:
- iterate over all cells in the matrix (all letters in the diagram)
- from each cell, start a search in all eight directions: up and down, left and right and four diagonal combinations of up & down and left & right
- for each all eight searches, check if one of the looked for words is found; if so, report the word, the cell where it starts and the direction in which it was found
The key to implementing this algoritm is an hierarchical query – as we shall see in a moment.
For the matrix in line view demonstrated above, our next step is an in-line view to visit all individual cells (letters) in the matrix. This is relatively simple:
, cells as ( select distinct seq, col , substr(txt, col, 1) cell from matrix cross join ( select rownum col from matrix ) )
Going forward, we have to explore eight directions. Directions are defined by two parameters that specify the movement along the horizontal and the vertical axis. The parameters can be -1, 0 or 1 – meaning [left, no horizontal movement, right] and [up, no vertical movement, down] respectively. Note that they cannot both be 0, as that would mean no exploration at all. These directions are generated in another in-line view in a somewhat contrived way; here is definitely room for improving the query.
, direction as ( select distinct sign(rownum - 2) dir from ( select count(*) from dual group by cube (1,2) ) ), directions as ( select h.dir hor , v.dir ver , case h.dir when 1 then 'left' when -1 then 'right' end horizontal , case v.dir when -1 then 'down' when 1 then 'up' end vertical from direction h inner join direction v on ( not (h.dir=0 and v.dir=0) ) )
However, it does the job. Note that the directions in-line view returns all eight routes, both expressed in -1/0/1 notation as well as human-readable format.
The final in-line view we use is the one that provides the list of words to search for. In the example, we are looking for the names of countries. We inject these names in the following way into our query:
, words as ( select column_value word from table( word_list('italy', 'holland' , 'poland' ,'france' ,'canada', 'japan','india','china','togo','peru' ) ) )
Here of course we use the same ‘trick’ as before of generating rows on the fly by dynamically, inside the query, instantiating a collection and accessing it through the TABLE operator.
Now that all preparations have been made – the inline views that prepared all data used in the query (and note that we do not query any data at all from any database table or view) – we can start looking for answers.
The real heart of the query is this piece:
from ( select c1.* , hor , ver , horizontal , vertical from cells c1 cross join directions ) cross join wordsstart with cell = substr(words.word,1,1)connect by prior col-hor = col and prior seq-ver = seq and prior hor = hor and prior ver = ver and level < length(words.word)+1 and cell = substr(words.word, level,1)
Here we join cells with directions – giving us one row to process for each cell for each of the eight directions. Then we join with words, to start an exploration from each cell in each of the eight directions for all of the search words. Alternatively, we could perhaps find all paths from all cells and try to join those paths to the search words. I leave that as an exercise to the reader.. (as lazy authors tend to write in their books).
The heart of the matter is next. We only start exploring from a cell if it contains the first letter of the current search word, why else bother. Then we start an hierarchical query, going from one cell to the next depending on the current direction, as specified by hor and ver (for horizontal and vertical movement). Suppose we are at cell row 4, column 3 and hor and ver are 1 (to the left) and -1 (going down). The hierarchical condition prior col-hor = col states that for the next cell in the hierarchical path its col value should be equal to the prior col value (which is 3) minus hor (which is 1) – so the next cell’s col value should be 2. Following similar reasoning, the next cell’s seq (or row) value should be 4 – (-1) = 5. So the next cell in the hierarchical path is row 5, column 2 – indeed going down and to the left.
The next two conditions ensure that we continue in the same direction from each subsequent cell in the hierarchical path. The last two conditions ensure that we do not keep exploring an obviously fruitless path: if the we have traversed more levels than the search word has characters we can stop the search and if the current cell does not contain the character it should for the current search word, we too can quit.
Adding a thin additional layer on top of this query, in order to filter all rows that did not find a search word, the final Word Search query becomes the following:
with matrix as( select rownum seq , lower(column_value) txt from table ( word_list( 'FYYHNRD' , 'RLJCINU' , 'AAWAAHR' , 'NTKLPNE' , 'CILFSAP' , 'EOGOTPN' , 'HPOLANDI' ) )), cells as ( select distinct seq, col , substr(txt, col, 1) cell from matrix cross join ( select rownum col from matrix ) ), direction as ( select distinct sign(rownum - 2) dir from ( select count(*) from dual group by cube (1,2) ) ), directions as ( select h.dir hor , v.dir ver , case h.dir when 1 then 'left' when -1 then 'right' end horizontal , case v.dir when -1 then 'down' when 1 then 'up' end vertical from direction h inner join direction v on ( not (h.dir=0 and v.dir=0) ) ), words as ( select column_value word from table( word_list('italy', 'holland' , 'poland' ,'france' ,'canada', 'japan','india','china','togo','peru' ) ) )select seq + ver * (length(word)-1) "Starting at row", col + hor * (length(word)-1) " and Column ", horizontal "Going", vertical " ", cast(word as varchar2(25)) "you will find the word"from ( select distinct cell , seq , col , hor , ver , sys_connect_by_path(cell,'*') p , word , horizontal , vertical from ( select c1.* , hor , ver , horizontal , vertical from cells c1 cross join directions ) cross join words start with cell = substr(words.word,1,1) connect by prior col-hor = col and prior seq-ver = seq and prior hor = hor and prior ver = ver and level < length(words.word)+1 and cell = substr(words.word, level,1) )where translate(p,'Q*','Q') = word/
Let’s try a somewhat more challenging puzzle as well:
The solution – searching for terminology very much part of our daily life at AMIS – looks like this:
The query outlined above returns with:
The correct answer – after four minutes. It is clear that the search time increases rapidly with a larger set of search words and especially a larger matrix.
Download the queries demonstrated above: wordSearchQueries.txt.
- JHeadstart – Querying a Master for its Details – for example: search Departments with at least one Clerk
- Using a SelectMany… component in a JHeadstart Advanced Search Form – search for all CLERKS & SALESMEN
- Creating your own advanced search engine for any website – using Oracle Text – Searching the AMIS Technology Weblog
- Google Desktop Search – no more agonizing searches for lost documents
- Getting started with Lucene 2.0 â€“ A powerful java search engine
- Oracle SQL – Finding free adjacent seats in an airplane, using Subquery Factoring, Analytical Functions (LISTAGG and LEAD), Outer Join, PIVOT and good old INSTR
- Oracle SQL – spotting combinations that occur and those that do not – demonstrating Analytical Functions, Outer Join and SubQuery Factoring
- Oracle SQL: Using subquery factoring in an INSERT statement
- OTN Yathra 2013 – Spreading the story of Oracle across India – (Half time)
- ADF DVT Speed Date: Present Metrics per Year, Quarter and Month using a zoom-enabled ADF DVT Resource Utilization Gantt and ADF BC
- Using TRUNC in SQL to get the first date in a period
- ADF DVT: Visualizing valid periods using Project and Scheduling Gantt Charts
- Advanced SQL to find valid periods – juggling with outer joins, running totals and analytical functions
- The Very Very Latest in Database Development – slides from the Expertezed presentation
- AMIS Masterclass Advanced SQL – scherp je SQL skills in een pittige en praktijkgerichte dag – maandag 10 december