Java program to solve Word Search Puzzle.

IN
puzzle.txt
computert
oheoemfsx
mmmwlatee
meoeyrilt
atrrognig
nsyppolfk
dyevirdey
ssboaprd!

words.txt
computer
memory
power
floppy
files
tex
commands
program
port
drive
system

OUT
Words left: 0

Solved puzzle
!!!!!!!!t
!h!!e!f!!
!!!!l!!!!
!!!!y!i!!
!!!!!!n!g
!!!!!!!!k
!!!!!!!ey
!!boa!rd!

The answer is: theflyingkeyboard

 

 

Main.java

// 2018 TheFlyingKeyboard and released under MIT License 
// theflyingkeyboard.net
public class Main {
    public static void main(String[] args) {
        Solver solver = new Solver();
        FileLoader fileLoader = new FileLoader();

        solver.solve(fileLoader.load("puzzle.txt"), fileLoader.load("words.txt"));

    }
}

Solver.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 2018 TheFlyingKeyboard and released under MIT License 
// theflyingkeyboard.net
public class Solver {
    private List<String> puzzle;
    private List<String> solving;
    private List<String> words;
    private final char xMark = 'X';

    public String solve(List<String> puzzleToSolve, List<String> wordsToFind){
        puzzle = puzzleToSolve;
        solving = new ArrayList<>(puzzle);
        words = wordsToFind;

        int maxIterations = 5; //To prevent endless loops.
        int counter = 0;

        while (words.size() != 0 && counter < maxIterations){ //There might be multiple words in the same row, column or diagonal!
            solveDiagonals();
            solveRowsAndColumns();

            ++counter;
        }

        printSolution();

        return null;
    }

    private void printSolution(){
        System.out.println("Words left: " + words.size());
        for(int i = 0; i < words.size(); ++i){
            System.out.println(words.get(i));
        }

        System.out.println();
        System.out.println("Solved puzzle");
        printSolving();

        System.out.println();
        System.out.println("The answer is: " + findAnswer());
    }

    private void solveRowsAndColumns(){
        String column;

        for(int i = 0; i < puzzle.size(); ++i){
            for(int j = 0; j < words.size(); ++j){
                if(!solveRow(i, words.get(j), j)){
                    solveRow(i, new StringBuilder(words.get(j)).reverse().toString(), j);
                }
            }
        }

        for(int i = 0; i < puzzle.get(0).length(); ++i){
            column = getColumn(i);

            for(int j = 0; j < words.size(); ++j) {
                if(!solveColumn(i, column, words.get(j), j)){
                    solveColumn(i, column, new StringBuilder(words.get(j)).reverse().toString(), j);
                }
            }
        }
    }

    private void solveDiagonals(){
        String word;

        int width = puzzle.get(0).length() - 1;
        int height = puzzle.size();
        int lastRow;
        int firstRow;

        for (int i = 0; i < width + height; ++i) {
            lastRow = Math.max(0,  i - width);
            firstRow = Math.min(i, height -1);

            for(int j = 0; j < words.size(); ++j){ //First Diagonal
                word = words.get(j);

                solveDiagonal(firstRow, lastRow, i, j, word, true);
            }

            for(int j = 0; j < words.size(); ++j){ //Second Diagonal
                word = words.get(j);

                solveDiagonal(firstRow, lastRow, i, j, word, false);
            }
        }
    }

    //True if word was found.
    private void solveDiagonal(int firstRow, int lastRow, int diagonalIndex, int wordIndex, String word, boolean isFirstDiagonal){
        String diagonal = getDiagonal(firstRow, lastRow, diagonalIndex, isFirstDiagonal, false);

        if(diagonal.contains(word)){
            words.remove(wordIndex);

            removeDiagonal(firstRow, lastRow, diagonalIndex, getDiagonal(firstRow, lastRow, diagonalIndex, isFirstDiagonal, true),
                    diagonal, word, isFirstDiagonal);
        }

        if(diagonal.contains(new StringBuilder(word).reverse().toString())){
            words.remove(wordIndex);

            removeDiagonal(firstRow, lastRow, diagonalIndex, getDiagonal(firstRow, lastRow, diagonalIndex, isFirstDiagonal, true),
                    diagonal, new StringBuilder(word).reverse().toString(), isFirstDiagonal);
        }
    }

    //True if word was found.
    private boolean solveRow(int row, String word, int wordIndex){
        if(puzzle.get(row).contains(word)){ //Rows
            replaceRow(row, word);
            words.remove(wordIndex);

            return true;
        }

        return false;
    }

    private void replaceRow(int row, String word){
        solving.set(row, solving.get(row).substring(0, puzzle.get(row).indexOf(word)) +
                String.join("", Collections.nCopies(word.length(), String.valueOf(xMark)))
                + solving.get(row).substring(puzzle.get(row).indexOf(word) + word.length()));
    }

    //True if word was found.
    private boolean solveColumn(int columnIndex, String column, String word, int wordIndex){
        if (column.contains(word)){
            replaceColumn(columnIndex, word.length(), column.indexOf(word));

            words.remove(wordIndex);
            return true;
        }

        return false;
    }

    private String getColumn(int index){
        StringBuilder stringBuilder = new StringBuilder();

        for(int i = 0; i < puzzle.size(); ++i){
            stringBuilder.append(puzzle.get(i).charAt(index));
        }

        return stringBuilder.toString();
    }

    private void replaceColumn(int index, int length, int beginIndex){
        for(int i = 0; i < length; ++i){
            solving.set(i + beginIndex, solving.get(i + beginIndex).substring(0, index) + xMark + solving.get(i + beginIndex).substring(index + 1));
        }
    }

    private String getDiagonal(int firstRow, int lastRow, int diagonal, boolean isFirstDiagonal, boolean useSolving){
        StringBuilder stringBuilder = new StringBuilder();

        stringBuilder.setLength(0);
        for (int row = firstRow; row >= lastRow; --row) {
            int col = diagonal - row;

            if(useSolving){
                stringBuilder.append(isFirstDiagonal ? solving.get(row).charAt(col) :
                        solving.get(row).charAt(solving.get(0).length() - col - 1));
            }else{
                stringBuilder.append(isFirstDiagonal ? puzzle.get(row).charAt(col) :
                        puzzle.get(row).charAt(puzzle.get(0).length() - col - 1));
            }
        }

        return stringBuilder.toString();
    }

    private void printSolving(){
        for(int i = 0; i < solving.size(); ++i){
            System.out.println(solving.get(i));
        }
    }

    private String findAnswer(){
        StringBuilder stringBuilder = new StringBuilder();

        for(int i = 0; i < solving.size(); ++i){
            for(int j = 0; j < solving.get(0).length(); ++j){
                if(solving.get(i).charAt(j) != xMark){
                    stringBuilder.append(solving.get(i).charAt(j));
                }
            }
        }

        return stringBuilder.toString();
    }

    private void removeDiagonal(int firstRow, int lastRow, int diagonalIndex, String solvingDiagonal, String diagonal, String word, boolean isFirstDiagonal){
        solvingDiagonal = solvingDiagonal.substring(0, diagonal.indexOf(word)) +
                String.join("", Collections.nCopies(word.length(), String.valueOf(xMark)))
                + solvingDiagonal.substring(diagonal.indexOf(word) + word.length());

        int counter = 0;
        for (int row = firstRow; row >= lastRow; --row) {
            int col = diagonalIndex - row;

            solving.set(row, isFirstDiagonal ?
                    solving.get(row).substring(0, col) + solvingDiagonal.charAt(counter) + solving.get(row).substring(col + 1) :
                    solving.get(row).substring(0, puzzle.get(0).length() - col - 1) + solvingDiagonal.charAt(counter) + solving.get(row).substring(puzzle.get(0).length() - col)
            );

            ++counter;
        }
    }
}



FileLoader.java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

// 2018 TheFlyingKeyboard and released under MIT License 
// theflyingkeyboard.net
public class FileLoader {
    public List<String> load(String fileName){
        List<String> list = new ArrayList<>();

        try (Stream<String> stream = Files.lines(Paths.get(fileName))) {
            stream.forEach(list::add);
        }
        catch (IOException e){
            e.printStackTrace();
        }

        return list;
    }

}

 



Java Word Search Puzzle Solver
Tagged on:             

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close