# Stateful Solvers and Iterators

Rust, yet again! Let’s take what we did last time with Solving Sudoku (again) and improve the code structure a bit more.

Goals:

• Create a ‘Solver’ struct that can maintain state (such as how many states we’ve visited, how much time we’ve spent)
• Track the above stats
• Turn the ‘Solver’ into an iterator which will iterate through given solutions (a single call will give the first solution or you can run through the iterator to get all of them)

# Solving Sudoku (again)

More Rust! This time, I want to go back to my post on A Generic Brute Force Backtracking Solver. For one, because I’m learning Rust. For two, because there is a crate specifically for im mutable data structures. And for three, because I expect it will be much faster. We shall see!

# Solving Snakebird

Snakebird!

A cute little puzzle game, where you move around snake(birds). Move any number of snakes around the level, eating fruit, and getting to the exit. The main gotchas are that you have gravity to content with–your snake will easily fall off the edge of the world–and each time you eat a fruit, your snake gets bigger. This can help get longer to get into hard to reach places or it can cause trouble when you trap yourself in corners.

Let’s use the new immutable.js solver to solve these problems!

# Immutable.js Solvers

A bit ago I wrote about writing a generic brute force solver (wow, was that really two months ago?). It got … complicate. Mostly, because every time I wrote a step function, I had to be careful to undo the same. Wouldn’t it be nice if we could just write a step function and get backtracking for ‘free’?

Well, with immutability you can!

# AoC 2016 Day 24: Venti

### Source: Air Duct Spelunking

Part 1: Given a map of the form:

########### #0.1…..2# #.#######.# #4…….3# ###########

# AoC 2016 Day 17: Md5 Maze

### Source: Two Steps Forward

Part 1: Create a 4x4 grid of rooms with doors Up, Down, Left, and Right from each location. To determine if a door is currently open:

• Calculate MD5(salt + sequence) where sequence is a string containing any combination of UDLR depending on how you got to this room
• The first four hex values represent the doors Up, Down, Left, and Right respectively: bcdef means open; anything else is closed

Find the shortest path from (0, 0) to (3, 3).

# AoC 2016 Day 11: Radiation Avoider

Part 1: Input will be a list of the following form:

• The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
• The second floor contains a hydrogen generator.
• The third floor contains a lithium generator.
• The fourth floor contains nothing relevant.

You have an elevator that can move exactly 1 or 2 items. You can only leave a microchip on a floor with a non-matching generator if a matching generator is also present.

Move all items to the top (4th) floor.

# Takuzu solver

Based on a /r/dailyprogrammer puzzle: Takuzu solver.

Basically, Takuzu is a logic puzzle similar to Sudoku. You are given a grid partially filled with 0s and 1s. You have to fill in the rest of the grid according to three simple rules:

• You cannot have more than three of the same number in a line
• Each column must have an equal number of 0s and 1s1
• No two rows or no two columns can be identical

Thus, if you have a puzzle like this:

0.01.1
0....1
..00..
..00..
1....0
10.0.0


One valid solution (most puzzles should have only a single valid answer, but that doesn’t always seem to be the case):

010101
001101
110010
010011
101100
101010


Let’s do it!

# Tile Puzzle

It’s been a while1, but I’m back. Today’s post is inspired by a post from /r/dailyprogrammer almost a month ago now: Challenge #183 [Intermediate] Edge Matching Tile Puzzle. Basically, we’re going to solve puzzles like this:

If you look carefully, the tiles are the same between the two, although they might be rotated.