enter image description here

Rust, 31430 used characters

This is a greedy algorithm of sorts: we start with an empty grid, and repeatedly add the word that can be added with the fewest new letters. To make this run quickly, we maintain a priority queue of candidate word placements (implemented as a vector of deques, with a deque for each number of new letters). For each newly added letter, we add to the queue all candidate placements that run through that letter.

Compile and run with rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt. On my laptop, this runs in 70 seconds, using 636 MiB RAM.

The output fits in a rectangle with 238 columns and 241 rows.

use std::collections::{HashMap, HashSet, VecDeque};
use std::io::prelude::*;
use std::iter::once;
use std::vec::Vec;
type Coord = i16;
type Pos = (Coord, Coord);
type Dir = u8;
type Word = u16;
struct Placement { word: Word, dir: Dir, pos: Pos }
static DIRS: [Pos; 8] =
 [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)];
fn fit(grid: &HashMap<Pos, u8>, (x, y): Pos, d: Dir, word: &String) -> Option<usize> {
 let (dx, dy) = DIRS[d as usize];
 let mut n = 0;
 for (i, c) in word.bytes().enumerate() {
 if let Some(c1) = grid.get(&(x + (i as Coord)*dx, y + (i as Coord)*dy)) {
 if c != *c1 {
 return None;
 }
 } else {
 n += 1;
 }
 }
 return Some(n)
}
fn main() {
 let stdin = std::io::stdin();
 let all_words: Vec<String> =
 stdin.lock().lines().map(|l| l.unwrap()).collect();
 let words: Vec<&String> = {
 let subwords: HashSet<&str> =
 all_words.iter().flat_map(|word| {
 (0..word.len() - 1).flat_map(move |i| {
 (i + 1..word.len() - (i == 0) as usize).map(move |j| {
 &word[i..j]
 })
 })
 }).collect();
 all_words.iter().filter(|word| !subwords.contains(&word[..])).collect()
 };
 let letters: Vec<Vec<(usize, usize)>> =
 (0..128).map(|c| {
 words.iter().enumerate().flat_map(|(w, word)| {
 word.bytes().enumerate().filter(|&(_, c1)| c == c1).map(move |(i, _)| (w, i))
 }).collect()
 }).collect();
 let mut used = vec![false; words.len()];
 let mut remaining = words.len();
 let mut grids: Vec<HashMap<Pos, u8>> = Vec::new();
 while remaining != 0 {
 let mut grid: HashMap<Pos, u8> = HashMap::new();
 let mut best = 0;
 let mut queue: Vec<VecDeque<Placement>> = Vec::new();
  queue.push(VecDeque::new());
 queue[0].push_back(Placement { pos: (0, 0), dir: 0, word: used.iter().position(|u| !u).unwrap() as Word });
 while best < queue.len() {
 while let Some(placement) = queue[best as usize].pop_front() {
 if used[placement.word as usize] {
 continue;
 }
 let word = words[placement.word as usize];
 if let None = fit(&grid, placement.pos, placement.dir, word) {
 continue;
  }
 let (x, y) = placement.pos;
 let (dx, dy) = DIRS[placement.dir as usize];
 let new_letters: Vec<(usize, u8)> = word.bytes().enumerate().filter(|&(i, _)| {
 !grid.contains_key(&(x + (i as Coord)*dx, y + (i as Coord)*dy))
 }).collect();
 for (i, c) in word.bytes().enumerate() {
 grid.insert((x + (i as Coord)*dx, y + (i as Coord)*dy), c);
 }
 used[placement.word as usize] = true;
 remaining -= 1;
 for (i, c) in new_letters {
 for &(w1, j) in &letters[c as usize] {
 if used[w1] {
  continue;
 }
 for (d1, &(dx1, dy1)) in DIRS.iter().enumerate() {
 let p1 = (x + (i as Coord)*dx - (j as Coord)*dx1, y + (i as Coord) - (j as Coord)*dy1);
 if let Some(n1) = fit(&grid, p1, d1 as Dir, words[w1]) {
 while queue.len() <= n1 as usize {
 queue.push(VecDeque::new());
 }
 queue[n1 as usize].push_back(Placement { pos: p1, dir: d1 as Dir, word: w1 as Word });
 if best > n1 {
 best = n1;
 }
 }
 }
 }
 }
 }
 best += 1;
 }
 grids.push(grid);
 }
 let width = grids.iter().map(|grid| {
 grid.iter().map(|(&(x, _), _)| x).max().unwrap() -
 grid.iter().map(|(&(x, _), _)| x).min().unwrap() + 1
 }).max().unwrap();
 print!(
 "{}",
 grids.iter().flat_map(|grid| {
 let x0 = grid.iter().map(|(&(x, _), _)| x).min().unwrap();
 let y0 = grid.iter().map(|(&(_, y), _)| y).min().unwrap();
 let y1 = grid.iter().map(|(&(_, y), _)| y).max().unwrap();
 (y0..y1 + 1).flat_map(move |y| {
 (x0..x0 + width).map(move |x| {
 *grid.get(&(x, y)).unwrap_or(&('.' as u8)) as char
 }).chain(once('\n').take(1))
 })
 }).collect::<String>()
 );
}

Rust, (削除) 31430 (削除ここまで) 30081 used characters

This is a greedy algorithm of sorts: we start with an empty grid, and repeatedly add the word that can be added with the fewest new letters, with ties broken by preferring longer words. To make this run quickly, we maintain a priority queue of candidate word placements (implemented as a vector of vectors of deques, with a vector for each number of new letters, containing a deque for each word length). For each newly added letter, we enqueue all candidate placements that run through that letter.

Compile and run with rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt. On my laptop, this runs in 70 seconds, using 531 MiB RAM.

The output fits in a rectangle with 248 columns and 253 rows.

use std::collections::{HashMap, HashSet, VecDeque};
use std::io::prelude::*;
use std::iter::once;
use std::vec::Vec;
type Coord = i16;
type Pos = (Coord, Coord);
type Dir = u8;
type Word = u16;
struct Placement { word: Word, dir: Dir, pos: Pos }
static DIRS: [Pos; 8] =
 [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)];
fn fit(grid: &HashMap<Pos, u8>, (x, y): Pos, d: Dir, word: &String) -> Option<usize> {
 let (dx, dy) = DIRS[d as usize];
 let mut n = 0;
 for (i, c) in word.bytes().enumerate() {
 if let Some(c1) = grid.get(&(x + (i as Coord)*dx, y + (i as Coord)*dy)) {
 if c != *c1 {
 return None;
 }
 } else {
 n += 1;
 }
 }
 return Some(n)
}
struct PlacementQueue { queue: Vec<Vec<VecDeque<Placement>>>, extra: usize }
impl PlacementQueue {
 fn new() -> PlacementQueue {
 return PlacementQueue { queue: Vec::new(), extra: std::usize::MAX }
 }
 fn enqueue(self: &mut PlacementQueue, extra: usize, total: usize, placement: Placement) {
 while self.queue.len() <= extra {
 self.queue.push(Vec::new());
 }
 while self.queue[extra].len() <= total {
 self.queue[extra].push(VecDeque::new());
 }
 self.queue[extra][total].push_back(placement);
 if self.extra > extra {
 self.extra = extra;
 }
 }
 fn dequeue(self: &mut PlacementQueue) -> Option<Placement> {
 while self.extra < self.queue.len() {
 let mut subqueue = &mut self.queue[self.extra];
 while !subqueue.is_empty() {
 let total = subqueue.len() - 1;
 if let Some(placement) = subqueue[total].pop_front() {
 return Some(placement);
 }
 subqueue.pop();
 }
 self.extra += 1;
 }
 return None
 }
}
fn main() {
 let stdin = std::io::stdin();
 let all_words: Vec<String> =
 stdin.lock().lines().map(|l| l.unwrap()).collect();
 let words: Vec<&String> = {
 let subwords: HashSet<&str> =
 all_words.iter().flat_map(|word| {
 (0..word.len() - 1).flat_map(move |i| {
 (i + 1..word.len() - (i == 0) as usize).map(move |j| {
 &word[i..j]
 })
 })
 }).collect();
 all_words.iter().filter(|word| !subwords.contains(&word[..])).collect()
 };
 let letters: Vec<Vec<(usize, usize)>> =
 (0..128).map(|c| {
 words.iter().enumerate().flat_map(|(w, word)| {
 word.bytes().enumerate().filter(|&(_, c1)| c == c1).map(move |(i, _)| (w, i))
 }).collect()
 }).collect();
 let mut used = vec![false; words.len()];
 let mut remaining = words.len();
 let mut grids: Vec<HashMap<Pos, u8>> = Vec::new();
 while remaining != 0 {
 let mut grid: HashMap<Pos, u8> = HashMap::new();
 let mut queue = PlacementQueue::new();
 for (w, word) in words.iter().enumerate() {
 if used[w] {
 continue;
 }
 queue.enqueue(0, word.len(), Placement {
 pos: (0, 0),
 dir: 0,
 word: w as Word
 });
 }
 while let Some(placement) = queue.dequeue() {
  if used[placement.word as usize] {
 continue;
  }
 let word = words[placement.word as usize];
 if let None = fit(&grid, placement.pos, placement.dir, word) {
 continue;
 }
 let (x, y) = placement.pos;
 let (dx, dy) = DIRS[placement.dir as usize];
  let new_letters: Vec<(usize, u8)> = word.bytes().enumerate().filter(|&(i, _)| {
 !grid.contains_key(&(x + (i as Coord)*dx, y + (i as Coord)*dy))
 }).collect();
 for (i, c) in word.bytes().enumerate() {
 grid.insert((x + (i as Coord)*dx, y + (i as Coord)*dy), c);
 }
 used[placement.word as usize] = true;
 remaining -= 1;
 for (i, c) in new_letters {
 for &(w1, j) in &letters[c as usize] {
 if used[w1] {
  continue;
 }
  let word1 = words[w1];
 for (d1, &(dx1, dy1)) in DIRS.iter().enumerate() {
 let pos1 = (
 x + (i as Coord)*dx - (j as Coord)*dx1,
 y + (i as Coord) - (j as Coord)*dy1);
  if let Some(extra1) = fit(&grid, pos1, d1 as Dir, word1) {
 queue.enqueue(extra1, word1.len(), Placement {
 pos: pos1,
  dir: d1 as Dir,
 word: w1 as Word
 });
 }
 }
 }
 }
 }
 grids.push(grid);
 }
 let width = grids.iter().map(|grid| {
 grid.iter().map(|(&(x, _), _)| x).max().unwrap() -
 grid.iter().map(|(&(x, _), _)| x).min().unwrap() + 1
 }).max().unwrap();
 print!(
 "{}",
 grids.iter().flat_map(|grid| {
 let x0 = grid.iter().map(|(&(x, _), _)| x).min().unwrap();
 let y0 = grid.iter().map(|(&(_, y), _)| y).min().unwrap();
 let y1 = grid.iter().map(|(&(_, y), _)| y).max().unwrap();
 (y0..y1 + 1).flat_map(move |y| {
 (x0..x0 + width).map(move |x| {
 *grid.get(&(x, y)).unwrap_or(&('.' as u8)) as char
 }).chain(once('\n').take(1))
 })
 }).collect::<String>()
 );
}