Programming Exercise #5: Solving Boggle?!
For those of you who know not what Boggle is:
http://en.wikipedia.org/wiki/Boggle So today boys and... boys, our task is to make a word finder in Boggle. Given a word list, find all the words from that list you can make on an x by x Boggle board (the game itsself is a 4x4 board, but we can do better :D) Expert Level: Do the above task with recursion :) Addeum: We can use the TWL06 as our word list. http://www.cs.bu.edu/fac/byers/cours...ndouts/TWL.txt |
So, the algorithm to find all words in a Boggle board in the most efficient way?
And, just pick random letters and find words by them? Are there any rules (Hard letters like K (2 or more), U, X, Z etc.) of letters that can be used to produce the board? |
Arguments please.
|
Quote:
As for the rules, that is the reason I linked the wiki... |
|
I'm asking what should be passed to the function x_x.
|
Quote:
You pass the board its self. That is the only thing you would ever need. If you want to give it pointers to different word lists too that is your choice. |
Do 2 letters have to link to form a word or can you pick any letter from any position to form a word?
|
Ahh, didn't see that you added a wordlist above.
|
Sudoku is better than Boggle!
|
Quote:
|
Quote:
|
Quote:
edit- answer: Let M be an n x n matrix. (meaning, let M be an n-1 x n-1 array) Let W be the set of accepted words. if a set of entries of M, called X, where each entry of M in X is adjacent to the one both preceding and following, is an element of W, then there is a word in the matrix. Problem: define the set of all possible values for X (note: the maximum length of X is n*n) how to do this: loop through all entries of M sub 'i,j', (we don't need to check if it is apart of the alphabet because this is a boggle board) then check for each entry that:
if any of those are true (and if not then move onto the next entry in the matrix), repeat the process with the new entry and see if it is an element of W.substring(1,2). if that is true, do it again with W.substring(2,3), then (3,4), and so on. how all of that looks in code talk PHP Code:
add the string W[l] to a separate array every time M[r][s] in W[l].substring(p,p+1) && p == W[l].size(), and then break; so that the search can continue. |
Quote:
I don't see a return value. I don't see handling of already used letters (you can't use the same letter/piece twice in boggle) |
All times are GMT +2. The time now is 02:09 AM. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.