# Create a Flood Paint AI

In the game of Flood Paint, the goal of the game is to get the entire board to be the same colour in as few turns as possible.

The game starts with a board that looks something like this:

3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 31 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4


Currently, the number (representing a colour) at the center of the board is 3. Each turn, the square at the center will change colour, and all the squares of the same colour that are reachable from the center by moving horizontally or vertically (i.e. in the flood region of the center square) will change colours with it. So if the center square changes colour to 5:

3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 51 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4


then the 3 that was to the left of the center 3 will also change colour. Now there are a total of seven 5's reachable from the center one, and so if we then change colour to 4:

3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 41 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4


the painted region again increases in size dramatically.

Your task is to create a program that will take a 19-by-19 grid of colours from 1 to 6 as input, in whatever form you choose:

4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2


and return a sequence of colours that the center square will change to each turn, again in the format of your choosing:

263142421236425431645152623645465646213545631465


At the end of each sequence of moves, the squares in the 19-by-19 grid must all be the same colour.

Your program must be entirely deterministic; pseudorandom solutions are allowed, but the program must generate the same output for the same test case every time.

The winning program will take the fewest total number of steps to solve all 100,000 test cases found in this file (zipped text file, 14.23 MB). If two solutions take the same number of steps (e.g. if they both found the optimal strategy), the shorter program will win.

BurntPizza has written a program in Java to verify the test results. To use this program, run your submission and pipe the output to a file called steps.txt. Then, run this program with steps.txt and the floodtest file in the same directory. If your entry is valid and produces correct solutions for all the files, it should pass all the tests and return All boards solved successfully.

import java.io.*;
import java.util.*;

public class PainterVerifier {

public static void main(String[] args) throws FileNotFoundException {

char[] board = new char;

Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));

int lineNum = 0;

caseloop: while (b.hasNextLine()) {

for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}

String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();

Stack<Integer> nodes = new Stack<Integer>();

for (char c : steps) {
char targetColor = board;
char replacementColor = c;

nodes.push(180);

while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board;
for (char c : board)
if (c != center) {
s.close();
b.close();

System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}

if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');

lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}


Also, a scoreboard, since the results aren't actually sorted by score and here it actually matters a lot:

1. 1,985,078 - smack42, Java
2. 2,075,452 - user1502040, C
3. 2,098,382 - tigrou, C#
4. 2,155,834 - CoderTao, C#
5. 2,201,995 - MrBackend, Java
6. 2,383,569 - CoderTao, C#
7. 2,384,020 - Herjan, C
8. 2,403,189 - Origineil, Java
9. 2,445,761 - Herjan, C
10. 2,475,056 - Jeremy List, Haskell
11. 2,480,714 - SteelTermite, C (2,395 bytes)
12. 2,480,714 - Herjan, Java (4,702 bytes)
13. 2,588,847 - BurntPizza, Java (2,748 bytes)
14. 2,588,847 - Gero3, node.js (4,641 bytes)
15. 2,979,145 - Teun Pronk, Delphi XE3
16. 4,780,841 - BurntPizza, Java
17. 10,800,000 - Joe Z., Python
• Judging by your own submission the output shouldn't actually contain spaces? Apr 23, 2014 at 23:56
• It's worth noting that the test input data does not have spaces between the numbers. Apr 24, 2014 at 1:21
• You can still write it. If it undercuts the current winner, I will change the accepted answer. Apr 24, 2014 at 14:51
• The time constraint is "it needs to be fast enough for you to run it and post the actual results here". Apr 25, 2014 at 14:42
• @AlexanderRevo I thought I didn't move the file, but apparently the link's up and changed without me doing so. Here's the link again. Jan 20, 2016 at 16:53

# C# - 2,098,382 steps

I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post an answer.

There is certainly ways to improve this further more. I think going under the 2M steps might be possible.

It took approx 7 hours to generate results. Here is a txt file with all solutions, in case someone want to check them : results.zip

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace FloodPaintAI
{
class Node
{
public byte Value;             //1-6
public int Index;              //unique identifier, used for easily deepcopying the graph
public List<Node> Neighbours;
public List<Tuple<int, int>> NeighboursPositions; //used by BuildGraph()

public int Depth;    //used by GetSumDistances()
public bool Checked; //

public Node(byte value, int index)
{
Value = value;
Index = index;
}

public Node(Node node)
{
Value = node.Value;
Index = node.Index;
}
}

class Board
{
private const int SIZE = 19;
private const int STARTPOSITION = 9;

public Node Root;         //root of graph. each node is a set of contiguous, same color square
public List<Node> Nodes;  //all nodes in the graph, used for deep copying

public int EstimatedCost; //estimated cost, used by A* Pathfinding
public List<byte> Solution;

{
byte[,] board = new byte[SIZE, SIZE];
for(int j = 0 ; j < SIZE ; j++)
{
for(int i = 0 ; i < SIZE ; i++)
{
board[j, i] = byte.Parse(line[i].ToString());
}
}
Solution = new List<byte>();
BuildGraph(board);
}

public Board(Board boardToCopy)
{
//copy the graph
Nodes = new List<Node>(boardToCopy.Nodes.Count);
foreach(Node nodeToCopy in boardToCopy.Nodes)
{
Node node = new Node(nodeToCopy);
}

//copy "Neighbours" property
for(int i = 0 ; i < boardToCopy.Nodes.Count ; i++)
{
Node node = Nodes[i];
Node nodeToCopy = boardToCopy.Nodes[i];

node.Neighbours = new List<Node>(nodeToCopy.Neighbours.Count);
foreach(Node neighbour in nodeToCopy.Neighbours)
{
}
}

Root = Nodes[boardToCopy.Root.Index];
EstimatedCost = boardToCopy.EstimatedCost;
Solution = new List<byte>(boardToCopy.Solution);
}

private void BuildGraph(byte[,] board)
{
int[,] nodeIndexes = new int[SIZE, SIZE];
Nodes = new List<Node>();

//check how much sets we have (1st pass)
for(int j = 0 ; j < SIZE ; j++)
{
for(int i = 0 ; i < SIZE ; i++)
{
if(nodeIndexes[j, i] == 0) //not already visited
{
Node newNode = new Node(board[j, i], Nodes.Count);
newNode.NeighboursPositions = new List<Tuple<int, int>>();

BuildGraphFloodFill(board, nodeIndexes, newNode, i, j, board[j, i]);
}
}
}

//set neighbours and root (2nd pass)
foreach(Node node in Nodes)
{
node.Neighbours = new List<Node>();
node.Neighbours.AddRange(node.NeighboursPositions.Select(x => nodeIndexes[x.Item2, x.Item1]).Distinct().Select(x => Nodes[x - 1]));
node.NeighboursPositions = null;
}
Root = Nodes[nodeIndexes[STARTPOSITION, STARTPOSITION] - 1];
}

private void BuildGraphFloodFill(byte[,] board, int[,] nodeIndexes, Node node, int startx, int starty, byte floodvalue)
{
Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
queue.Enqueue(new Tuple<int, int>(startx, starty));

while(queue.Count > 0)
{
Tuple<int, int> position = queue.Dequeue();
int x = position.Item1;
int y = position.Item2;

if(x >= 0 && x < SIZE && y >= 0 && y < SIZE)
{
if(nodeIndexes[y, x] == 0 && board[y, x] == floodvalue)
{
nodeIndexes[y, x] = node.Index + 1;

queue.Enqueue(new Tuple<int, int>(x + 1, y));
queue.Enqueue(new Tuple<int, int>(x - 1, y));
queue.Enqueue(new Tuple<int, int>(x, y + 1));
queue.Enqueue(new Tuple<int, int>(x, y - 1));
}
if(board[y, x] != floodvalue)
}
}
}

public int GetEstimatedCost()
{
Board current = this;

//copy current board and play the best color until the end.
//number of moves required to go the end is the heuristic
//estimated cost = current cost + heuristic
while(!current.IsSolved())
{
int minSumDistance = int.MaxValue;
Board minBoard = null;

//find color which give the minimum sum of distance from root to each other node
foreach(byte i in current.Root.Neighbours.Select(x => x.Value).Distinct())
{
Board copy = new Board(current);
copy.Play(i);

int distance = copy.GetSumDistances();

if(distance < minSumDistance)
{
minSumDistance = distance;
minBoard = copy;
}
}
current = minBoard;
}
return current.Solution.Count;
}

public int GetSumDistances()
{
//get sum of distances from root to each other node, using BFS
int sumDistances = 0;

//reset marker
foreach(Node n in Nodes)
{
n.Checked = false;
}

Queue<Node> queue = new Queue<Node>();
Root.Checked = true;
Root.Depth = 0;
queue.Enqueue(Root);

while(queue.Count > 0)
{
Node current = queue.Dequeue();
foreach(Node n in current.Neighbours)
{
if(!n.Checked)
{
n.Checked = true;
n.Depth = current.Depth + 1;
sumDistances += n.Depth;
queue.Enqueue(n);
}
}
}
return sumDistances;
}

public void Play(byte value)
{
//merge root node with other neighbours nodes, if color is matching
Root.Value = value;
List<Node> neighboursToRemove = Root.Neighbours.Where(x => x.Value == value).ToList();
List<Node> neighboursToAdd = neighboursToRemove.SelectMany(x => x.Neighbours).Except((new Node[] { Root }).Concat(Root.Neighbours)).ToList();

foreach(Node n in neighboursToRemove)
{
foreach(Node m in n.Neighbours)
{
m.Neighbours.Remove(n);
}
Nodes.Remove(n);
}

{
}

//re-synchronize node index
for(int i = 0 ; i < Nodes.Count ; i++)
{
Nodes[i].Index = i;
}
}

public bool IsSolved()
{
//return Nodes.Count == 1;
return Root.Neighbours.Count == 0;
}
}

class Program
{
public static List<byte> Solve(Board input)
{
//A* Pathfinding
input.EstimatedCost = input.GetEstimatedCost();

while(open.Count > 0)
{
Board current = open.First.Value;
open.RemoveFirst();

if(current.IsSolved())
{
return current.Solution;
}
else
{
//play all neighbours nodes colors
foreach(byte i in current.Root.Neighbours.Select(x => x.Value).Distinct())
{
Board newBoard = new Board(current);
newBoard.Play(i);
newBoard.EstimatedCost = newBoard.GetEstimatedCost();

//insert board to open list
bool inserted = false;
for(LinkedListNode<Board> node = open.First ; node != null ; node = node.Next)
{
if(node.Value.EstimatedCost > newBoard.EstimatedCost)
{
inserted = true;
break;
}
}
if(!inserted)
}
}
}
throw new Exception(); //no solution found, impossible
}

public static void Main(string[] args)
{
{
while(!sr.EndOfStream)
{
List<Board> boards = new List<Board>();
while(!sr.EndOfStream && boards.Count < 100)
{
Board board = new Board(sr);
}
List<byte>[] solutions = new List<byte>[boards.Count];
Parallel.For(0, boards.Count, i =>
{
solutions[i] = Solve(boards[i]);
});
foreach(List<byte> solution in solutions)
{
Console.WriteLine(string.Join(string.Empty, solution));
}
}
}
}
}
}


More details about how it works :

It use A* Pathfinding algorithm.

What is difficult is to find a good heuristic. If the heuristic it underestimate the cost, it will perform like almost like Dijkstra algorithm and because of complexity of a 19x19 board with 6 colors it will run forever. If it overestimate the cost it will converge quickly to a solution but won't give good ones at all (something like 26 moves were 19 was possible). Finding the perfect heuristic that give the exact remaining amount of steps to reach solution would be the best (it would be fast and would give best possible solution). It is (unless i'm wrong) impossible. It actually require to solve the board itself first, while this is what you are actually trying to do (chicken and egg problem)

I tried many things, here is what worked for the heuristic:

• I build a graph of current board to evaluate. Each node represent a set of contiguous, same colored squares. Using that graph, I can easily calculate the exact minimal distance from center to any other node. For example distance from center to top left would be 10, because at minimum 10 colors separate them.
• For calculating heuristic : I play the current board until the end. For each step, I choose the color which will minimize the sum of distances from root to all other nodes.
• Number of moves needed to reach that end is the heuristic.

• Estimated cost (used by A*) = moves so far + heuristic

It is not perfect as it slightly overestimate the cost (thus non optimal solution is found). Anyway it is fast to calculate and give good results.

I was able to get huge speed improvment by using graph to perform all operations. At begining I had a 2-dimension array. I flood it and recalculate graph when needed (eg : to calculate the heuristic). Now everything is done using the graph, which calculated only at the beginning. To simulate steps, flood fill is no more needed, I merge nodes instead. This is a lot faster.

• Please don't use code blocks to emphasize text. We have italic and bold for that.
– anon
May 19, 2016 at 18:38

# Python – 10,800,000 steps

As a last-place reference solution, consider this sequence:

print "123456" * 18


Cycling through all the colours n times means that every square n steps away will be guaranteed to be of the same colour as the center square. Every square is at most 18 steps away from the center, so 18 cycles will guarantee all the squares being the same colour. Most likely it will finish in less than that, but the program is not required to stop as soon as all squares are the same colour; it's just much more beneficial to do so. This constant procedure is 108 steps per test case, for a total of 10,800,000.

• Brute force method, seriously...? Joe, I thought you had a little more experience to know better, mate? Apr 24, 2014 at 1:03
• It's not meant as a serious entry. Note that I put it up specifically as a solution to act as a catch-all in last place. Any serious entry would have a score much lower than this one. Apr 24, 2014 at 2:49
• Shouldn't there be spaces? As in 1 2 3 4 5 6 ... instead of your current solution which gives 123456.... Apr 24, 2014 at 4:53
• Would be the optimal algorithm for code golf (in some other language though "print " is too many chars). Apr 25, 2014 at 14:21
• I also don't think that the worst case of 18 steps is even possible. But of course we do know that there is no case worse than it, so this definitely works :) Apr 25, 2014 at 14:25

# Java - 2,480,714 steps

I made a little mistake before (I put one crucial sentence before a loop instead of in the loop:

import java.io.*;

public class HerjanPaintAI {

String[] map = new String;
char[][] colors = new char;
boolean[][] reached = new boolean, checked = new boolean;
int[] colorCounter = new int;
int mapCount = 0, moveCount = 0;

public HerjanPaintAI(){
nextMap();

while(true){

int bestMove = nextRound();
char t = Character.forDigit(bestMove, 10);
for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
if(reached[x][y]){
colors[x][y] = t;
}else if(checked[x][y]){
if(colors[x][y] == t){
reached[x][y] = true;
}
}
}
}

boolean gameOver = true;
for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
if(!reached[x][y]){
gameOver = false;
break;
}
}
}

for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
checked[x][y] = false;
}
}
for(int i = 0; i < 6; i++)
colorCounter[i] = 0;

if(gameOver)
nextMap();
}
}

int nextRound(){
for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
if(reached[x][y]){//check what numbers are next to the reached numbers...
check(x, y);
}
}
}

int[] totalColorCount = new int;
for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
totalColorCount[Character.getNumericValue(colors[x][y])-1]++;
}
}

for(int i = 0; i < 6; i++){
if(totalColorCount[i] != 0 && totalColorCount[i] == colorCounter[i]){//all of this color can be reached
return i+1;
}
}

int index = -1, number = 0;
for(int i = 0; i < 6; i++){
if(colorCounter[i] > number){
index = i;
number = colorCounter[i];
}
}

return index+1;
}

void check(int x, int y){
if(x<18)
handle(x+1, y, x, y);
if(x>0)
handle(x-1, y, x, y);
if(y<18)
handle(x, y+1, x, y);
if(y>0)
handle(x, y-1, x, y);
}

void handle(int x2, int y2, int x, int y){
if(!reached[x2][y2] && !checked[x2][y2]){
checked[x2][y2] = true;
if(colors[x2][y2] == colors[x][y]){
reached[x2][y2] = true;
check(x2, y2);
}else{
colorCounter[Character.getNumericValue(colors[x2][y2])-1]++;
checkAround(x2, y2);
}
}
}

void checkAround(int x2, int y2){
if(x2<18)
handleAround(x2+1, y2, x2, y2);
if(x2>0)
handleAround(x2-1, y2, x2, y2);
if(y2<18)
handleAround(x2, y2+1, x2, y2);
if(y2>0)
handleAround(x2, y2-1, x2, y2);
}

void handleAround(int x2, int y2, int x, int y){
if(!reached[x2][y2] && !checked[x2][y2]){
if(colors[x2][y2] == colors[x][y]){
checked[x2][y2] = true;
colorCounter[Character.getNumericValue(colors[x2][y2])-1]++;
checkAround(x2, y2);
}
}
}

void nextMap(){

for(int x = 0; x < 19; x++){
for(int y = 0; y < 19; y++){
reached[x][y] = false;
}
}

reached = true;

try {
if(r == null)

for(int i = 0; i < 19; i++){
}

if(map == null){
System.out.println("Maps solved: " + mapCount + " Steps: " + moveCount);
r.close();
System.exit(0);
}
} catch (Exception e) {e.printStackTrace();}

mapCount++;

for(int x = 0; x < 19; x++){
colors[x] = map[x].toCharArray();
}
}

public static void main(String[] a){
new HerjanPaintAI();
}
}

• How long did this take to run? Apr 24, 2014 at 10:29
• @ali0sha My pc took not even half a minute Apr 24, 2014 at 10:31
• Well crap. Mine has been running for half an hour... Apr 24, 2014 at 10:37
• Golfing is not required, by the way. Apr 24, 2014 at 14:12
• @m.buettner Speak of the devil, somebody did tie this solution (and had shorter code) three hours after you said that. Apr 30, 2014 at 14:40

# Java - 1,985,078 steps

https://github.com/smack42/ColorFill

Another late entry. The result file containing the 1,985,078 steps can be found here.

Some background info:

I discovered this challenge some years ago, when I started programming my own clone of the game Flood-it.

"best-of incomplete" DFS and A* algorithm
From the beginning, I wanted to create a good solver algorithm for this game. Over time, I could improve my solver by including several strategies that did different incomplete searches (similar to the ones used in the other programs here) and by using the best result of those strategies for each solution. I even re-implemented tigrou's A* algorithm in Java and added it to my solver to achieve overall better solutions than tigrou's result.

exhaustive DFS algorithm
Then I focused on an algorithm that always finds the optimal solutions. I spent a lot of effort to optimize my exhaustive depth-first search strategy. To speed up the search, I included a hashmap that stores all explored states, so that the search can avoid exploring them again. While this algorithm works fine and solves all 14x14 puzzles quickly enough, it uses too much memory and runs very slowly with the 19x19 puzzles in this code challenge.

Puchert A* algorithm
A few months ago I was contacted to look at the Flood-It solver by Aaron and Simon Puchert. That program uses an A*-type algorithm with an admissible heuristic (in contrast to tigrou's) and move pruning similar to Jump-Point Search. I quickly noticed that this program is very fast and finds the optimal solutions!

Of course, I had to re-implement this great algorithm and added it to my program. I made an effort to optimize my Java program to run about as fast as the original C++ program by the Puchert brothers. Then I decided to make an attempt at the 100,000 test cases of this challenge. On my machine the program ran for more than 120 hours to find the 1,985,078 steps, using my implementation of the Puchert A* algorithm.

This is to be the best possible solution to this challenge, unless there are some bugs in the program that would result in sub-optimal solutions. Any feedback is welcome!

edit: added relevant parts of the code here:

class AStarPuchertStrategy

/**
* a specific strategy for the AStar (A*) solver.
* <p>
* the idea is taken from the program "floodit" by Aaron and Simon Puchert,
* which can be found at <a>https://github.com/aaronpuchert/floodit</a>
*/
public class AStarPuchertStrategy implements AStarStrategy {

private final Board board;
private final ColorAreaSet visited;
private ColorAreaSet current, next;
private final short[] numCaNotFilledInitial;
private final short[] numCaNotFilled;

public AStarPuchertStrategy(final Board board) {
this.board = board;
this.visited = new ColorAreaSet(board);
this.current = new ColorAreaSet(board);
this.next = new ColorAreaSet(board);
this.numCaNotFilledInitial = new short[board.getNumColors()];
for (final ColorArea ca : board.getColorAreasArray()) {
++this.numCaNotFilledInitial[ca.getColor()];
}
this.numCaNotFilled = new short[board.getNumColors()];
}

* @see colorfill.solver.AStarStrategy#setEstimatedCost(colorfill.solver.AStarNode)
*/
@Override
public void setEstimatedCost(final AStarNode node) {

// quote from floodit.cpp: int State::computeValuation()
// (in branch "performance")
//
// We compute an admissible heuristic recursively: If there are no nodes
// left, return 0. Furthermore, if a color can be eliminated in one move
// from the current position, that move is an optimal move and we can
// simply use it. Otherwise, all moves fill a subset of the neighbors of
// the filled nodes. Thus, filling that layer gets us at least one step
// closer to the end.

node.copyFloodedTo(this.visited);
System.arraycopy(this.numCaNotFilledInitial, 0, this.numCaNotFilled, 0, this.numCaNotFilledInitial.length);
{
final ColorAreaSet.FastIteratorColorAreaId iter = this.visited.fastIteratorColorAreaId();
int nextId;
while ((nextId = iter.nextOrNegative()) >= 0) {
--this.numCaNotFilled[this.board.getColor4Id(nextId)];
}
}

// visit the first layer of neighbors, which is never empty, i.e. the puzzle is not solved yet
node.copyNeighborsTo(this.current);
int completedColors = 0;
{
final ColorAreaSet.FastIteratorColorAreaId iter = this.current.fastIteratorColorAreaId();
int nextId;
while ((nextId = iter.nextOrNegative()) >= 0) {
final byte nextColor = this.board.getColor4Id(nextId);
if (--this.numCaNotFilled[nextColor] == 0) {
completedColors |= 1 << nextColor;
}
}
}
int distance = 1;

while(!this.current.isEmpty()) {
this.next.clear();
final ColorAreaSet.FastIteratorColorAreaId iter = this.current.fastIteratorColorAreaId();
int thisCaId;
if (0 != completedColors) {
// We can eliminate colors. Do just that.
// We also combine all these elimination moves.
distance += Integer.bitCount(completedColors);
final int prevCompletedColors = completedColors;
completedColors = 0;
while ((thisCaId = iter.nextOrNegative()) >= 0) {
final ColorArea thisCa = this.board.getColorArea4Id(thisCaId);
if ((prevCompletedColors & (1 << thisCa.getColor())) != 0) {
// completed color
// expandNode()
for (final int nextCaId : thisCa.getNeighborsIdArray()) {
if (!this.visited.contains(nextCaId)) {
final byte nextColor = this.board.getColor4Id(nextCaId);
if (--this.numCaNotFilled[nextColor] == 0) {
completedColors |= 1 << nextColor;
}
}
}
} else {
// non-completed color
// move node to next layer
}
}
} else {
// Nothing found, do the color-blind pseudo-move
// Expand current layer of nodes.
++distance;
while ((thisCaId = iter.nextOrNegative()) >= 0) {
final ColorArea thisCa = this.board.getColorArea4Id(thisCaId);
// expandNode()
for (final int nextCaId : thisCa.getNeighborsIdArray()) {
if (!this.visited.contains(nextCaId)) {
final byte nextColor = this.board.getColor4Id(nextCaId);
if (--this.numCaNotFilled[nextColor] == 0) {
completedColors |= 1 << nextColor;
}
}
}
}
}

// Move the next layer into the current.
final ColorAreaSet tmp = this.current;
this.current = this.next;
this.next = tmp;
}
node.setEstimatedCost(node.getSolutionSize() + distance);
}

}


part of class AStarSolver

private void executeInternalPuchert(final ColorArea startCa) throws InterruptedException {
final Queue<AStarNode> open = new PriorityQueue<AStarNode>(AStarNode.strongerComparator());
open.offer(new AStarNode(this.board, startCa));
AStarNode recycleNode = null;
while (open.size() > 0) {
if (Thread.interrupted()) { throw new InterruptedException(); }
final AStarNode currentNode = open.poll();
if (currentNode.isSolved()) {
return;
} else {
// play all possible colors
int nextColors = currentNode.getNeighborColors(this.board);
while (0 != nextColors) {
final int l1b = nextColors & -nextColors; // Integer.lowestOneBit()
final int clz = Integer.numberOfLeadingZeros(l1b); // hopefully an intrinsic function using instruction BSR / LZCNT / CLZ
nextColors ^= l1b; // clear lowest one bit
final byte color = (byte)(31 - clz);
final AStarNode nextNode = currentNode.copyAndPlay(color, recycleNode, this.board);
if (null != nextNode) {
recycleNode = null;
this.strategy.setEstimatedCost(nextNode);
open.offer(nextNode);
}
}
}
recycleNode = currentNode;
}
}


part of class AStarNode

/**
* check if this color can be played. (avoid duplicate moves)
* the idea is taken from the program "floodit" by Aaron and Simon Puchert,
* which can be found at <a>https://github.com/aaronpuchert/floodit</a>
* @param nextColor
* @return
*/
private boolean canPlay(final byte nextColor, final List<ColorArea> nextColorNeighbors) {
final byte currColor = this.solution[this.solutionSize];
// did the previous move add any new "nextColor" neighbors?
boolean newNext = false;
next:   for (final ColorArea nextColorNeighbor : nextColorNeighbors) {
for (final ColorArea prevNeighbor : nextColorNeighbor.getNeighborsArray()) {
if ((prevNeighbor.getColor() != currColor) && this.flooded.contains(prevNeighbor)) {
continue next;
}
}
newNext = true;
break next;
}
if (!newNext) {
if (nextColor < currColor) {
return false;
} else {
// should nextColor have been played before currColor?
for (final ColorArea nextColorNeighbor : nextColorNeighbors) {
for (final ColorArea prevNeighbor : nextColorNeighbor.getNeighborsArray()) {
if ((prevNeighbor.getColor() == currColor) && !this.flooded.contains(prevNeighbor)) {
return false;
}
}
}
return true;
}
} else {
return true;
}
}

/**
* try to re-use the given node or create a new one
* and then play the given color in the result node.
* @param nextColor
* @param recycleNode
* @return
*/
public AStarNode copyAndPlay(final byte nextColor, final AStarNode recycleNode, final Board board) {
final List<ColorArea> nextColorNeighbors = new ArrayList<ColorArea>(128);  // constant, arbitrary initial capacity
final ColorAreaSet.FastIteratorColorAreaId iter = this.neighbors.fastIteratorColorAreaId();
int nextId;
while ((nextId = iter.nextOrNegative()) >= 0) {
final ColorArea nextColorNeighbor = board.getColorArea4Id(nextId);
if (nextColorNeighbor.getColor() == nextColor) {
}
}
if (!this.canPlay(nextColor, nextColorNeighbors)) {
return null;
} else {
final AStarNode result;
if (null == recycleNode) {
result = new AStarNode(this);
} else {
// copy - compare copy constructor
result = recycleNode;
result.flooded.copyFrom(this.flooded);
result.neighbors.copyFrom(this.neighbors);
System.arraycopy(this.solution, 0, result.solution, 0, this.solutionSize + 1);
result.solutionSize = this.solutionSize;
//result.estimatedCost = this.estimatedCost;  // not necessary to copy
}
// play - compare method play()
for (final ColorArea nextColorNeighbor : nextColorNeighbors) {
}
result.neighbors.removeAll(result.flooded);
result.solution[++result.solutionSize] = nextColor;
return result;
}
}

• Welcome to PPCG! Could you include the relevant code for the solver in the answer itself, so that it's self-contained, should your github repo ever move or go down? Mar 15, 2018 at 22:07
• Added the most relevant parts of the code here: my implementation of the "Puchert A* algorithm". (this code excerpt is not self-contained and can't be compiled as-is) Mar 15, 2018 at 22:38
• I am happy someone found a perfect / optimal solution for this. But on the other side, it means there will be no more competition / new answers. Sep 10, 2019 at 13:13

C - 2,075,452

I know I'm extremely late to the party, but I saw this challenge and wanted to have a go.

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

uint64_t rand_state;

uint64_t rand_u64(void) {
return (rand_state = rand_state * 6364136223846793005ULL + 1442695040888963407ULL);
}

uint64_t better_rand_u64(void) {
uint64_t r = rand_u64();
r ^= ((r >> 32) >> (r >> 60));
return r + 1442695040888963407ULL;
}

uint32_t rand_u32(void) {return rand_u64() >> 32;}

float normal(float mu, float sigma) {
uint64_t t = 0;
for (int i = 0; i < 6; i++) {
uint64_t r = rand_u64();
uint32_t a = r;
uint32_t b = r >> 32;
t += a;
t += b;
}
return ((float)t / (float)UINT32_MAX - 6) * sigma + mu;
}

typedef struct {
uint8_t x;
uint8_t y;
} Position;

#define ncolors 6
#define len 19
#define cells (len * len)
#define max_steps (len * (ncolors - 1))
#define center_x 9
#define center_y 9
#define center ((Position){center_x, center_y})

uint64_t zobrist_table[len][len];

void init_zobrist() {
for (int y = 0; y < len; y++) {
for (int x = 0; x < len; x++) {
zobrist_table[y][x] = better_rand_u64();
}
}
}

typedef struct {
uint64_t hash;
uint8_t grid[len][len];
bool interior[len][len];
int boundary_size;
Position boundary[cells];
} Grid;

void transition(Grid* grid, uint8_t color, int* surrounding_counts) {
int i = 0;
while (i < grid->boundary_size) {
Position p = grid->boundary[i];
uint8_t x = p.x;
uint8_t y = p.y;
bool still_boundary = false;
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (!(dx == 0 || dy == 0)) {
continue;
}
int8_t x1 = x + dx;
if (!(0 <= x1 && x1 < len)) {
continue;
}
int8_t y1 = y + dy;
if (!(0 <= y1 && y1 < len)) {
continue;
}
if (grid->interior[y1][x1]) {
continue;
}
uint8_t color1 = grid->grid[y1][x1];
if (color1 == color) {
grid->boundary[grid->boundary_size++] = (Position){x1, y1};
grid->interior[y1][x1] = true;
grid->hash ^= zobrist_table[y1][x1];
} else {
surrounding_counts[color1]++;
still_boundary = true;
}
}
}
if (still_boundary) {
i += 1;
} else {
grid->boundary[i] = grid->boundary[--grid->boundary_size];
}
}
}

void reset_grid(Grid* grid, int* surrounding_counts) {
grid->hash = 0;
memset(surrounding_counts, 0, ncolors * sizeof(int));
memset(&grid->interior, 0, sizeof(grid->interior));
grid->interior[center_y][center_x] = true;
grid->boundary_size = 0;
grid->boundary[grid->boundary_size++] = center;
transition(grid, grid->grid[center_y][center_x], surrounding_counts);
}

bool load_grid(FILE* fp, Grid* grid) {
memset(grid, 0, sizeof(*grid));
char buf[19 + 2];
size_t row = 0;
while ((fgets(buf, sizeof(buf), fp)) && row < 19) {
if (strlen(buf) != 20) {
break;
}
for (int i = 0; i < 19; i++) {
if (!('1' <= buf[i] && buf[i] <= '6')) {
return false;
}
grid->grid[row][i] = buf[i] - '1';
}
row++;
}
return row == 19;
}

typedef struct Node Node;

struct Node {
uint64_t hash;
float visit_counts[ncolors];
float mean_cost[ncolors];
float sse[ncolors];
};

#define iters 15000
#define pool_size 32768
#define pool_nodes (pool_size + 100)

Node pool[pool_nodes];

void init_node(Node* node, uint64_t hash, int* surrounding_counts) {
node->hash = hash;
for (int i = 0; i < ncolors; i++) {
if (surrounding_counts[i]) {
node->visit_counts[i] = 1;
node->mean_cost[i] = 20;
node->sse[i] = 400;
}
}
}

Node* lookup_node(uint64_t hash) {
size_t index = hash & pool_mask;
for (int i = index;; i++) {
uint64_t h = pool[i].hash;
if (h == hash || !h) {
return pool + i;
}
}
}

int rollout(Grid* grid, int* surrounding_counts, char* solution) {
for (int i = 0;; i++) {
int nonzero = 0;
uint8_t colors;
for (int i = 0; i < ncolors; i++) {
if (surrounding_counts[i]) {
colors[nonzero++] = i;
}
}
if (!nonzero) {
return i;
}
uint8_t color = colors[rand_u32() % nonzero];
*(solution++) = color;
assert(grid->boundary_size);
memset(surrounding_counts, 0, 6 * sizeof(int));
transition(grid, color, surrounding_counts);
}
}

int simulate(Node* node, Grid* grid, int depth, char* solution) {
float best_cost = INFINITY;
uint8_t best_color = 255;
for (int color = 0; color < ncolors; color++) {
float n = node->visit_counts[color];
if (node->visit_counts[color] == 0) {
continue;
}
float sigma = sqrt(node->sse[color] / (n * n));
float cost = node->mean_cost[color];
cost = normal(cost, sigma);
if (cost < best_cost) {
best_color = color;
best_cost = cost;
}
}
if (best_color == 255) {
return 0;
}
*solution++ = best_color;
int score;
int surrounding_counts[ncolors] = {0};
transition(grid, best_color, surrounding_counts);
Node* child = lookup_node(grid->hash);
if (!child->hash) {
init_node(child, grid->hash, surrounding_counts);
score = rollout(grid, surrounding_counts, solution);
} else {
score = simulate(child, grid, depth + 1, solution);
}
score++;
float n1 = ++node->visit_counts[best_color];
float u0 = node->mean_cost[best_color];
float u1 = node->mean_cost[best_color] = u0 + (score - u0) / n1;
node->sse[best_color] += (score - u0) * (score - u1);
return score;
}

int main(void) {
FILE* fp;
if (!(fp = fopen("floodtest", "r"))) {
return 1;
}
Grid grid;
init_zobrist();

memset(pool, 0, sizeof(pool));
int surrounding_counts[ncolors] = {0};

reset_grid(&grid, surrounding_counts);
Node root = {0};

init_node(&root, grid.hash, surrounding_counts);

char solution[max_steps] = {0};
char best_solution[max_steps] = {0};

int min_score = INT_MAX;

uint64_t prev_hash = 0;
uint64_t hash = 0;
int same_count = 0;

for (int iter = 0; iter < iters; iter++) {
reset_grid(&grid, surrounding_counts);
int score = simulate(&root, &grid, 1, solution);
if (score < min_score) {
min_score = score;
memcpy(best_solution, solution, score);
}
hash = 0;
for (int i = 0; i < score; i++) {
hash ^= zobrist_table[i%len][(int)solution[i]];
}
if (hash == prev_hash) {
same_count++;
if (same_count >= 10) {
break;
}
} else {
same_count = 0;
prev_hash = hash;
}
}
int i;
for (i = 0; i < min_score; i++) {
best_solution[i] += '1';
}
best_solution[i++] = '\n';
best_solution[i++] = '\0';
printf(best_solution);
fflush(stdout);
}
return 0;
}


The algorithm is based on Monte-Carlo Tree Search with Thompson sampling, and a transposition table to reduce the search space. It takes about 12 hours on my machine. If you want to check the results, you can find them at https://dropfile.to/pvjYDMV.

• User smack42 suggests changing hash ^= zobrist_table[i][(int)solution[i]]; to hash ^= zobrist_table[i%len][(int)solution[i]]; to fix program crash. Jul 19, 2017 at 13:42
• @StepHen I don't see how a score can be greater than len. Do you have an input which makes this crash? Do you have a link to your conversation with smak42? Even if can't crash, I suppose there's no harm in being on the safe side with code which isn't performacne-critical. Jul 20, 2017 at 15:11
• No, sorry, it was in suggested edits. Here is the review: codegolf.stackexchange.com/review/suggested-edits/42008 Jul 20, 2017 at 15:13
• +1 for beating me at this. But beware, there might be some improvements to come ;) Jan 17, 2018 at 15:22

# Java - 2,434,108 2,588,847 steps

Currently winning (~46K ahead of Herjan) as of 4/26

Welp, so not only did MrBackend beat me, but I found a bug which produced a deceptively good score. It's fixed now (was also in the verifier! Ack), but unfortunately I don't have any time at the moment to try and take back the crown. Will attempt later.

This is based off of my other solution, but instead of painting with the color most common to the fill edges, it paints with the color that will result in exposing edges that have many adjacent squares of the same color. Call it LookAheadPainter. I'll golf it later if necessary.

import java.io.*;
import java.util.*;

static final boolean PRINT_FULL_OUTPUT = true;

public static void main(String[] a) throws IOException {

int totalSteps = 0, numSolved = 0;

char[] board = new char;
Scanner s = new Scanner(new File("floodtest"));
long startTime = System.nanoTime();

caseloop: while (s.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String line = s.nextLine();
if (line.isEmpty())
continue caseloop;
System.arraycopy(line.toCharArray(), 0, board, l * 19, 19);
}

List<Character> colorsUsed = new ArrayList<>();

for (;;) {

FillResult fill = new FillResult(board, board, (char) 48, null);

if (fill.nodesFilled.size() == 361)
break;

int[] branchSizes = new int;

for (int i = 1; i < 7; i++) {
List<Integer> seeds = new ArrayList<>();
for (Integer seed : fill.edges)
if (board[seed] == i + 48)

branchSizes[i] = new FillResult(fill.filledBoard, (char) (i + 48), (char) 48, seeds).nodesFilled.size();
}

int maxSize = 0;
char bestColor = 0;

for (int i = 1; i < 7; i++)
if (branchSizes[i] > maxSize) {
maxSize = branchSizes[i];
bestColor = (char) (i + 48);
}

for (int i : fill.nodesFilled)
board[i] = bestColor;

totalSteps++;
}
numSolved++;

if (PRINT_FULL_OUTPUT) {
if (numSolved % 1000 == 0)
System.out.println("Solved: " + numSolved); // So you know it's working
String out = "";
for (Character c : colorsUsed)
out += c;
System.out.println(out);
}

}
s.close();
System.out.println("\nTotal steps to solve all cases: " + totalSteps);
System.out.printf("\nSolved %d test cases in %.2f seconds", numSolved, (System.nanoTime() - startTime) / 1000000000.);
}

private static class FillResult {

Set<Integer> nodesFilled, edges;
char[] filledBoard;

FillResult(char[] board, char target, char replacement, List<Integer> seeds) {
Stack<Integer> nodes = new Stack<>();
nodesFilled = new HashSet<>();
edges = new HashSet<>();

if (seeds == null)
nodes.push(180);
else
for (int i : seeds)
nodes.push(i);

filledBoard = new char;
System.arraycopy(board, 0, filledBoard, 0, 361);

while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (filledBoard[n] == target) {
filledBoard[n] = replacement;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
} else
}
}
}
}


EDIT: I wrote a verifier, feel free to use, it expects a steps.txt file containing the steps your program outputs as well as the floodtest file: Edit-Edit: (See OP)

If anyone finds a problem, please report it to me!

• Nice, Pizza! And that verifier is a smart one indeed! The OP should have made something like this/a control program (that would have solved a lot of problems). Apr 27, 2014 at 11:48

# C - 2,480,714 steps

Still not optimal, but it is now faster and scores better.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char map, reach;
int reachsum, totalsum;

{
char buf[19 + 2];
size_t row = 0;

while (fgets(buf, sizeof buf, fp) && row < 19) {
if (strlen(buf) != 20)
break;
memcpy(map[row++], buf, 19);
}
return row == 19;
}

void calcreach(bool first, size_t row, size_t col);
void check(char c, bool first, size_t row, size_t col)
{
if (map[row][col] == c)
calcreach(first, row, col);
else if (first)
calcreach(false, row, col);
}

void calcreach(bool first, size_t row, size_t col)
{
char c = map[row][col];

reach[row][col] = c;
reachsum[c - '1']++;
if (row < 18 && !reach[row + 1][col])
check(c, first, row + 1, col);
if (col < 18 && !reach[row][col + 1])
check(c, first, row, col + 1);
if (row > 0 && !reach[row - 1][col])
check(c, first, row - 1, col);
if (col > 0 && !reach[row][col - 1])
check(c, first, row, col - 1);
}

void calctotal()
{
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
totalsum[map[row][col] - '1']++;
}

void apply(char c)
{
char d = map;
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
if (reach[row][col] == d)
map[row][col] = c;
}

int main()
{
char c, best;
size_t steps = 0;
FILE *fp;

if (!(fp = fopen("floodtest", "r")))
return 1;

do {
memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);
if (reachsum[map - '1'] == 361)
break;

memset(totalsum, 0, sizeof totalsum);
calctotal();

reachsum[map - '1'] = 0;
for (best = 0, c = 0; c < 6; c++) {
if (!reachsum[c])
continue;
if (reachsum[c] == totalsum[c]) {
best = c;
break;
} else if (reachsum[c] > reachsum[best]) {
best = c;
}
}

apply(best + '1');
} while (++steps);
}

fclose(fp);

printf("steps: %zu\n", steps);
return 0;
}

• Nice done Willem, thanks for mentioning me in your description. I am honored by your grace. Apr 24, 2014 at 17:26
• No problem, dear Herjan Apr 24, 2014 at 17:27
• By the way, your statement "it scores marginally better than Herjan's" is already outdated, I just applied the improvement where I spoke of (in the mail) ;) Good luck beating me now! Apr 24, 2014 at 17:38
• 515 steps ahead of you, ever heard of adding/removing a '=', in a comparison, heheh Apr 28, 2014 at 13:20
• Indeed, Herjan. I will update my submission according to your suggestion. Apr 28, 2014 at 13:27

# Java - 2,245,529 2,201,995 steps

Parallel & caching tree search at depth 5, minimizing the number of "islands". Since the improvement from depth 4 to depth 5 was so small, I don't think there is much point in improving it much more. But if it were to need improvement, my gut feeling says to work with calculating the number of islands as a diff between two states, instead of recalculating everything.

Currently outputs to stdout, until I know the verifier's input format.

import java.io.BufferedReader;
import java.io.IOException;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;

public class FloodPaint {

private static final ForkJoinPool FORK_JOIN_POOL = new ForkJoinPool();

public static void main(String[] arg) throws IOException, InterruptedException, ExecutionException {
int sum = 0;
while (initState != null) {
List<Integer> solution = generateSolution(initState);
System.out.println(solution);
sum += solution.size();
}
System.out.println(sum);
}
}

int[] initGrid = new int[State.DIM * State.DIM];
while ((line != null) && line.isEmpty()) {
}
if (line == null) {
return null;
}
for (int rowNo = 0; rowNo < State.DIM; ++rowNo) {
for (int colNo = 0; colNo < State.DIM; ++colNo) {
initGrid[(State.DIM * rowNo) + colNo] = line.charAt(colNo) - '0';
}
}
return new State(initGrid);
}

private static List<Integer> generateSolution(State initState) throws InterruptedException, ExecutionException {
StateFactory stateFactory = new StateFactory();
State state = initState;
while (!state.isSolved()) {
int num = findGoodNum(state, stateFactory);
state = state.getNextState(num, stateFactory);
}
return solution;
}

private static int findGoodNum(State state, StateFactory stateFactory) throws InterruptedException, ExecutionException {
}

}

private static final int DEPTH = 5;

private final State state;
private final StateFactory stateFactory;

this.state = state;
this.stateFactory = stateFactory;
}

@Override
protected Integer compute() {
try {
for (int num = 1; num <= 6; ++num) {
if (num != state.getCenterNum()) {
State nextState = state.getNextState(num, stateFactory);
}
}
int bestValue = Integer.MAX_VALUE;
int bestNum = -1;
if (value < bestValue) {
bestValue = value;
}
}
return bestNum;
} catch (InterruptedException | ExecutionException ex) {
throw new RuntimeException(ex);
}
}

}

private static final int DEPTH_THRESHOLD = 3;

private final State state;
private final int depth;
private final StateFactory stateFactory;

AnalyzerTask(State state, int depth, StateFactory stateFactory) {
this.state = state;
this.depth = depth;
this.stateFactory = stateFactory;
}

@Override
protected Integer compute() {
return (depth < DEPTH_THRESHOLD) ? analyze() : split();
}

private int analyze() {
return analyze(state, depth);
}

private int analyze(State state, int depth) {
if (state.isSolved()) {
return -depth;
}
if (depth == 0) {
return state.getNumIslands();
}
int bestValue = Integer.MAX_VALUE;
for (int num = 1; num <= 6; ++num) {
if (num != state.getCenterNum()) {
State nextState = state.getNextState(num, stateFactory);
int nextValue = analyze(nextState, depth - 1);
bestValue = Math.min(bestValue, nextValue);
}
}
return bestValue;
}

private int split() {
try {
if (state.isSolved()) {
return -depth;
}
for (int num = 1; num <= 6; ++num) {
State nextState = state.getNextState(num, stateFactory);
}
int bestValue = Integer.MAX_VALUE;
bestValue = Math.min(bestValue, nextValue);
}
return bestValue;
} catch (InterruptedException | ExecutionException ex) {
throw new RuntimeException(ex);
}
}

}

class StateFactory {

private static final int INIT_CAPACITY = 40000;
private static final float LOAD_FACTOR = 0.9f;

private final Map<List<Integer>,State> cache = new HashMap<>(INIT_CAPACITY, LOAD_FACTOR);

State get(int[] grid) {
List<Integer> stateKey = new IntList(grid);
State state;
try {
state = cache.get(stateKey);
} finally {
}
if (state == null) {
cacheLock.writeLock().lock();
try {
state = cache.get(stateKey);
if (state == null) {
state = new State(grid);
cache.put(stateKey, state);
}
} finally {
cacheLock.writeLock().unlock();
}
}
return state;
}

}

class State {

static final int DIM = 19;
private static final int CENTER_INDEX = ((DIM * DIM) - 1) / 2;

private final int[] grid;
private int numIslands;

State(int[] grid) {
this.grid = grid;
numIslands = calcNumIslands(grid);
}

private static int calcNumIslands(int[] grid) {
int numIslands = 0;
BitSet uncounted = new BitSet(DIM * DIM);
uncounted.set(0, DIM * DIM);
int index = -1;
while (!uncounted.isEmpty()) {
index = uncounted.nextSetBit(index + 1);
BitSet island = new BitSet(DIM * DIM);
generateIsland(grid, index, grid[index], island);
++numIslands;
uncounted.andNot(island);
}
return numIslands;
}

private static void generateIsland(int[] grid, int index, int num, BitSet island) {
if ((grid[index] == num) && !island.get(index)) {
island.set(index);
if ((index % DIM) > 0) {
generateIsland(grid, index - 1, num, island);
}
if ((index % DIM) < (DIM - 1)) {
generateIsland(grid, index + 1, num, island);
}
if ((index / DIM) > 0) {
generateIsland(grid, index - DIM, num, island);
}
if ((index / DIM) < (DIM - 1)) {
generateIsland(grid, index + DIM, num, island);
}
}
}

int getCenterNum() {
return grid[CENTER_INDEX];
}

boolean isSolved() {
return numIslands == 1;
}

int getNumIslands() {
return numIslands;
}

State getNextState(int num, StateFactory stateFactory) {
int[] nextGrid = grid.clone();
if (num != getCenterNum()) {
flood(nextGrid, CENTER_INDEX, getCenterNum(), num);
}
State nextState = stateFactory.get(nextGrid);
return nextState;
}

private static void flood(int[] grid, int index, int fromNum, int toNum) {
if (grid[index] == fromNum) {
grid[index] = toNum;
if ((index % 19) > 0) {
flood(grid, index - 1, fromNum, toNum);
}
if ((index % 19) < (DIM - 1)) {
flood(grid, index + 1, fromNum, toNum);
}
if ((index / 19) > 0) {
flood(grid, index - DIM, fromNum, toNum);
}
if ((index / 19) < (DIM - 1)) {
flood(grid, index + DIM, fromNum, toNum);
}
}
}

}

class IntList extends AbstractList<Integer> implements List<Integer> {

private final int[] arr;
private int hashCode = -1;

IntList(int[] arr) {
this.arr = arr;
}

@Override
public int size() {
return arr.length;
}

@Override
public Integer get(int index) {
return arr[index];
}

@Override
public Integer set(int index, Integer value) {
int oldValue = arr[index];
arr[index] = value;
return oldValue;
}

@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof IntList) {
IntList arg = (IntList) obj;
return Arrays.equals(arr, arg.arr);
}
return super.equals(obj);
}

@Override
public int hashCode() {
if (hashCode == -1) {
hashCode = 1;
for (int elem : arr) {
hashCode = 31 * hashCode + elem;
}
}
return hashCode;
}

}

• Impressive, can you make it writes the steps to a file? So that we can check it? Apr 28, 2014 at 18:51
• @Herjan it appears his code is self-validating. See isSolved() Apr 28, 2014 at 20:30
• @BurntPizza So? My code is also self-validating, lol... I mean, that can be just as wrong as my own code. Apr 28, 2014 at 20:34
• isSolved() is not for validation, it's for termination. As for write - will do in next version. Apr 28, 2014 at 21:06
• I'd be interested if a heuristic that made it search 5 steps deep only if the number of steps found for 4 was more than 24 would result in much more efficient runtime. Apr 29, 2014 at 0:51

# My Last Entry: C - 2,384,020 steps

This time a 'check-all-possibilities' one... This score is gained with Depth set on 3. Depth at 5 should give ~2.1M steps... TOO SLOW. Depth 20+ gives the least amount of steps possible (it just checks all matches and the shortest wins ofcourse)... It has the least amount of steps, though I hate it since it only is a tiny bit better, but performance sucks. I prefer my other C entry, which is also in this post.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char map, reach;
int reachsum, totalsum, mapCount = 0;
FILE *stepfile;

{
fprintf(stepfile, "%s", "\n");

mapCount++;

char buf[19 + 2];
size_t row = 0;

while (fgets(buf, sizeof buf, fp) && row < 19) {
if (strlen(buf) != 20)
break;
memcpy(map[row++], buf, 19);
}
return row == 19;
}

void calcreach(bool first, size_t row, size_t col);
void check(char c, bool first, size_t row, size_t col)
{
if (map[row][col] == c)
calcreach(first, row, col);
else if (first)
calcreach(false, row, col);
}

void calcreach(bool first, size_t row, size_t col)
{
char c = map[row][col];

reach[row][col] = c;
reachsum[c - '1']++;
if (row < 18 && !reach[row + 1][col])
check(c, first, row + 1, col);
if (col < 18 && !reach[row][col + 1])
check(c, first, row, col + 1);
if (row > 0 && !reach[row - 1][col])
check(c, first, row - 1, col);
if (col > 0 && !reach[row][col - 1])
check(c, first, row, col - 1);
}

void calctotal()
{
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
totalsum[map[row][col] - '1']++;
}

void apply(char c)
{
char d = map;
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
if (reach[row][col] == d)
map[row][col] = c;
}

int pown(int x, int y){
int p = 1;
for(int i = 0; i < y; i++){
p = p * x;
}

return p;
}

int main()
{
size_t steps = 0;
FILE *fp;

if (!(fp = fopen("floodtest", "r")))
return 1;
if(!(stepfile = fopen("steps.txt", "w")))
return 1;

const int depth = 5;
char possibilities[pown(6, depth)][depth];
int t = 0;
for(int a = 0; a < 6; a++){
for(int b = 0; b < 6; b++){
for(int c = 0; c < 6; c++){
for(int d = 0; d < 6; d++){
for(int e = 0; e < 6; e++){
possibilities[t] = (char)(a + '1');
possibilities[t] = (char)(b + '1');
possibilities[t] = (char)(c + '1');
possibilities[t] = (char)(d + '1');
possibilities[t++] = (char)(e + '1');
}
}
}
}
}
poes:
do {
char map2;
memcpy(map2, map, sizeof(map));

memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);

int best = 0, index = 0, end = depth;
for(int i = 0; i < pown(6, depth); i++){
for(int d = 0; d < end; d++){

apply(possibilities[i][d]);

memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);

if(reachsum[map - '1'] == 361 && d < end){
end = d+1;
index = i;
break;
}
}
if(end == depth && best < reachsum[map - '1']){
best = reachsum[map - '1'];
index = i;
}

memcpy(map, map2, sizeof(map2));
memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);
}

for(int d = 0; d < end; d++){

apply(possibilities[index][d]);

memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);

fprintf(stepfile, "%c", possibilities[index][d]);
steps++;
}
if(reachsum[map - '1'] == 361)
goto poes;
} while (1);
}

fclose(fp);
fclose(stepfile);

printf("steps: %zu\n", steps);
return 0;
}


# Another Improved AI written in C - 2,445,761 steps

Based on SteelTermite's:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char map, reach;
int reachsum, totalsum, mapCount = 0;
FILE *stepfile;

{
fprintf(stepfile, "%s", "\n");

if(mapCount % 1000 == 0)
printf("mapCount = %d\n", mapCount);

mapCount++;

char buf[19 + 2];
size_t row = 0;

while (fgets(buf, sizeof buf, fp) && row < 19) {
if (strlen(buf) != 20)
break;
memcpy(map[row++], buf, 19);
}
return row == 19;
}

void calcreach(bool first, size_t row, size_t col);
void check(char c, bool first, size_t row, size_t col)
{
if (map[row][col] == c)
calcreach(first, row, col);
else if (first)
calcreach(false, row, col);
}

void calcreach(bool first, size_t row, size_t col)
{
char c = map[row][col];

reach[row][col] = c;
reachsum[c - '1']++;
if (row < 18 && !reach[row + 1][col])
check(c, first, row + 1, col);
if (col < 18 && !reach[row][col + 1])
check(c, first, row, col + 1);
if (row > 0 && !reach[row - 1][col])
check(c, first, row - 1, col);
if (col > 0 && !reach[row][col - 1])
check(c, first, row, col - 1);
}

void calctotal()
{
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
totalsum[map[row][col] - '1']++;
}

void apply(char c)
{
char d = map;
size_t row, col;

for (row = 0; row < 19; row++)
for (col = 0; col < 19; col++)
if (reach[row][col] == d)
map[row][col] = c;
}

int main()
{
size_t steps = 0;
FILE *fp;

if (!(fp = fopen("floodtest", "r")))
return 1;
if(!(stepfile = fopen("steps.txt", "w")))
return 1;

do {
memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);
if (reachsum[map - '1'] == 361)
break;

memset(totalsum, 0, sizeof totalsum);
calctotal();

reachsum[map - '1'] = 0;
for (best = 0, c = 0; c < 6; c++) {
if (!reachsum[c])
continue;
if (reachsum[c] == totalsum[c]) {
best = c;
goto outLoop;
} else if (reachsum[c] > reachsum[best]) {
best = c;
}
}

char map2;
memcpy(map2, map, sizeof(map));

int temp = best;
for(c = 0; c < 6; c++){

if(c != best){

apply(c + '1');

memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);
if (reachsum[best] == totalsum[best]) {

memcpy(map, map2, sizeof(map2));
memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);

if(temp == -1)
temp = c;
else if(reachsum[c] > reachsum[temp])
temp = c;
}

memcpy(map, map2, sizeof(map2));
memset(reach, 0, sizeof reach);
memset(reachsum, 0, sizeof reachsum);
calcreach(true, 9, 9);
}
}

outLoop:    answer = (char)(temp + '1');
} while (++steps);
}

fclose(fp);
fclose(stepfile);

printf("steps: %zu\n", steps);
return 0;
}

• ...and ~200K to beat mine ;) Apr 28, 2014 at 18:36
• You should post each entry as an individual answer. Apr 29, 2014 at 14:48
• @JoeZ. Sorry, but it felt like spamming, so I decided to assemble them in one answer (it doesn't matter since only the best (the best = the AI with lowest amount of steps) counts). At least thats what I thought. Apr 30, 2014 at 9:11

# Java - 2,610,797 4,780,841 steps

(Fill-Bug fixed, score is now dramatically worse -_- )

This is my basic reference algorithm submission, simply makes a histogram of the squares on the edges of the painted area, and paints with the most common color. Runs the 100k in a couple minutes.

Obviously won't win, but it's certainly not last. I'll probably make another submission for clever stuff. Feel free to use this algorithm as a starting point.

Un-comment the commented lines for the full output. Defaults to printing the # of steps taken.

import java.io.*;
import java.util.*;

public class PainterAI {

public static void main(String[] args) throws IOException {

int totalSteps = 0, numSolved = 0;

char[] board = new char;
Scanner s = new Scanner(new File("floodtest"));
long startTime = System.nanoTime();
caseloop: while (s.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String line = s.nextLine();
if (line.isEmpty())
continue caseloop;
System.arraycopy(line.toCharArray(), 0, board, l * 19, 19);
}

List<Character> colorsUsed = new ArrayList<>();
Stack<Integer> nodes = new Stack<>();

for (;; totalSteps++) {
char p = board;
int[] occurrences = new int;
int numToPaint = 0;
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == p) {
board[n] = 48;
numToPaint++;
if (n % 19 > 0)
nodes.push(n - 1);
if(n%19<18)
nodes.push(n + 1);
if(n/19>0)
nodes.push(n - 19);
if(n/19<18)
nodes.push(n + 19);
} else
occurrences[board[n] - 48]++;
}
if (numToPaint == 361)
break;
char mostFrequent = 0;
int times = -1;
for (int i = 1; i < 7; i++)
if (occurrences[i] > times) {
times = occurrences[i];
mostFrequent = (char) (i + 48);
}
for (int i = 0; i < 361; i++)
if (board[i] == 48)
board[i] = mostFrequent;
}
numSolved++;

/*String out = "";
for (Character c : colorsUsed)
out += c;
System.out.println(out); //print output*/
}
s.close();
System.out.println("Total steps to solve all cases: " + totalSteps);
System.out.printf("\nSolved %d test cases in %.2f seconds", numSolved, (System.nanoTime() - startTime) / 1000000000.);
}
}


Golfs to 860 chars (not including the newlines for formatting), but could be shrunk more if I felt like trying:

import java.io.*;import java.util.*;class P{
public static void main(String[]a)throws Exception{int t=0;char[]b=new char;
Scanner s=new Scanner(new File("floodtest"));c:while(s.hasNextLine()){
for(int l=0;l<19;l++){String L=s.nextLine();if(L.isEmpty())continue c;
System.arraycopy(L.toCharArray(),0,b,l*19,19);}List<Character>u=new ArrayList<>();
int m=0;while(!q.empty()){int n=q.pop();if(n<0|n>360)continue;if(b[n]==p){b[n]=48;m++;
char f=0;int h=0;for(int i=1;i<7;i++)if(o[i]>h){h=o[i];f=(char)(i+48);}
System.out.println(y);}s.close();System.out.println("Steps: "+t);}}

• The only reason it's "certainly not last" is because my reference solution is there to pad things out. It's actually last place out of all the submissions by other people at the moment :P Apr 26, 2014 at 15:51
• @JoeZ. Well it was in front of SteelTermite's, but he improved his. I meant this as the "next logical step from naive" approach. I would be concerned if it was doing well ;P Apr 26, 2014 at 19:49

Algorithm is similar to the one suggested by MrBackend in the comments. The difference is: his suggestion finds the cheapest path to the highest cost square, mine greedily reduces the graph eccentricity at every step.

import Data.Array
import qualified Data.Map as M
import Data.Word
import Data.List
import Data.Maybe
import Data.Function (on)
import Data.Monoid
import Control.Arrow
import System.IO
import System.Environment
import Control.Parallel.Strategies
import Control.DeepSeq

type Grid v = Array (Word8,Word8) v

main = do
(ifn:_) <- getArgs
sp <- liftM parseFile $hGetContents hr let (len,sol) = turns (map solve sp using parBuffer 3 (evalList rseq)) putStrLn$ intercalate "\n" $map (concatMap show) sol putStrLn$ "\n\nTotal turns: " ++ (show len)

turns :: [[a]] -> (Integer,[[a]])
turns l = rl' 0 l where
rl' c [] = (c,[])
rl' c (k:r) = let
s = c + genericLength k
(s',l') = s seq rl' s r
in (s',k:l')

centrepoint :: Grid v -> (Word8,Word8)
centrepoint g = let
((x0,y0),(x1,y1)) = bounds g
med l h = let t = l + h in t div 2 + t mod 2
in (med x0 x1, med y0 y1)

neighbours :: Grid v -> (Word8,Word8) -> [(Word8,Word8)]
neighbours g (x,y) = filter
(inRange $bounds g) [(x,y+1),(x+1,y),(x,y-1),(x-1,y)] areas :: Eq v => Grid v -> [[(Word8,Word8)]] areas g = p$ indices g where
p [] = []
p (a:r) = f : p (r \\ f) where
f = s g [a] []
s g [] _ = []
s g (h:o) v = let
n = filter (((==) on (g !)) h) $neighbours g h in h : s g ((n \\ (o ++ v)) ++ o) (h : v) applyFill :: Eq v => v -> Grid v -> Grid v applyFill c g = g // (zip fa$ repeat c) where
fa = s g [centrepoint g] []

solve g = solve' gr' where
aa = areas g
cp = centrepoint g
ca = head $head$ filter (elem cp) aa
gr' = M.fromList $map ( \r1 -> (head r1, map head$ filter (
(not $null$ intersect (concatMap (neighbours g) r1) r2)
) aa
)
) aa
solve' gr
| null $tail$ M.keys $gr = [] | otherwise = best : solve' ngr where djk _ [] = [] djk v ((n,q):o) = (n,q) : djk (q:v) ( o ++ zip (repeat (n+1)) ((gr M.! q) \\ (v ++ map snd o)) ) dout = djk [] [(0,ca)] din = let m = maximum$ map fst dout
s = filter ((== m) . fst) dout
in djk [] s
rc = filter (flip elem (gr M.! ca) . snd) din
frc = let
m = minimum $map fst rc in map snd$ filter ((==m) . fst) rc
msq = concat $filter (flip elem frc . head) aa clr = map (length &&& head)$ group $sort$ map (g !) msq
best = snd $maximumBy (compare on fst) clr ngr = let ssm = filter ((== best) . (g !))$ map snd rc
sml = (concatMap (gr M.!) ssm)
ncl = ((gr M.! ca) ++ sml) \\ (ca : ssm)
brk = M.insert ca ncl $M.filterWithKey (\k _ -> (not . flip elem ssm) k ) gr in M.map (\l -> nub$ map (\e -> if e elem ssm then ca else e) l)
brk

parseFile :: String -> [Grid Word8]
parseFile f = map mk $filter (not . null . head)$ groupBy ((==) on null) $map (map ((read :: String -> Word8) . (:[])))$ lines f where
mk :: [[Word8]] -> Grid Word8
mk m = let
w = fromIntegral (length $head m) - 1 h = fromIntegral (length m) - 1 in array ((0,0),(w,h)) [ ((x,y),v) | (y,l) <- zip [h,h-1..] m, (x,v) <- zip [0..] l ] showGrid :: Grid Word8 -> String showGrid g = intercalate "\n" l where l = map sl$ groupBy ((==) on snd) $sortBy ((flip (compare on snd)) <> (compare on fst))$
indices g
sl = intercalate " " . map (show . (g !))

testsolve = do
sp <- liftM (head . parseFile) $hGetContents hr let sol = solve sp a = snd$ mapAccumL (\g s -> let g' = applyFill s g in (g',g')) sp sol
sequence_ $map (\g -> putStrLn (showGrid g) >> putStrLn "\n") a  • Has it finished running yet? Apr 28, 2014 at 1:21 • Not yet, it might have finished by now if I'd let it run overnight, but the fan was noisy so I hibernated the computer. It's running again now, will check again when I get home from work. Apr 28, 2014 at 1:54 • It crashed due to a stack overflow, modifying now to avoid that. Apr 28, 2014 at 11:34 ## C#- 2,383,569 It's a depth traversal of possible solutions that roughly chooses the path of best improvement (similar/same as Herjan's C entry), except I cleverly reversed the order of candidate solution generation after seeing Herjan posted the same numbers. Takes a good 12+ hours to run though. class Solver { static void Main() { int depth = 3; string text = File.ReadAllText(@"C:\TEMP\floodtest.txt"); text = text.Replace("\n\n", ".").Replace("\n", ""); int count = 0; string[] tests = text.Split(new char[] { '.' }, StringSplitOptions.RemoveEmptyEntries); for (int i = 0; i < tests.Length; i++) { Solver s = new Solver(tests[i]); string k1 = s.solve(depth); count += k1.Length; Console.WriteLine(((100 * i) / tests.Length) + " " + i + " " + k1.Length + " " + count + " " + k1); } Console.WriteLine(count); } public readonly int MAX_DIM; public char[] board; public Solver(string prob) { board = read(prob); MAX_DIM = (int)Math.Sqrt(board.Length); } public string solve(int d) { var sol = ""; while (score(eval(copy(board), sol)) != board.Length) { char[] b = copy(board); eval(b, sol); var canidates = new List<string>(); buildCanidates("", canidates, d); var best = canidates.Select(c => new {score = score(eval(copy(b), c)), sol = c}).ToList().OrderByDescending(t=>t.score).ThenBy(v => v.sol.Length).First(); sol = sol + best.sol; } return sol; } public void buildCanidates(string b, List<string> r, int d) { if(b.Length>0) r.Add(b); if (d > 0) { r.Add(b); for (char i = '6'; i >= '1'; i--) if(b.Length == 0 || b[b.Length-1] != i) buildCanidates(b + i, r, d - 1); } } public char[] read(string s) { return s.Where(c => c >= '0' && c <= '9').ToArray(); } public void print(char[] b) { for (int i = 0; i < MAX_DIM; i++) { for(int j=0; j<MAX_DIM; j++) Console.Write(b[i*MAX_DIM+j]); Console.WriteLine(); } Console.WriteLine(); } public char[] copy(char[] b) { char[] n = new char[b.Length]; for (int i = 0; i < b.Length; i++) n[i] = b[i]; return n; } public char[] eval(char[] b, string sol) { foreach (char c in sol) eval(b, c); return b; } public void eval(char[] b, char c) { foreach (var l in flood(b)) b[l] = c; } public int score(char[] b) { return flood(b).Count; } public List<int> flood(char[] b) { int start = (MAX_DIM * (MAX_DIM / 2)) + (MAX_DIM / 2); var check = new List<int>(MAX_DIM * MAX_DIM); bool[] seen = new bool[b.Length]; var hits = new List<int>(MAX_DIM*MAX_DIM); check.Add(start); seen[start]=true; char target = b[start]; int at = 0; while (at<check.Count) { int toCheck = check[at++]; if (b[toCheck] == target) { addNeighbors(check, seen, toCheck); hits.Add(toCheck); } } return hits; } public void addNeighbors(List<int> check, bool[] seen, int loc) { int x = loc / MAX_DIM; int y = loc % MAX_DIM; addNeighbor(check, seen, x, y - 1); addNeighbor(check, seen, x, y + 1); addNeighbor(check, seen, x - 1, y); addNeighbor(check, seen, x + 1, y); } public void addNeighbor(List<int> check, bool[] seen, int x, int y) { if (x >= 0 && x < MAX_DIM && y >= 0 && y < MAX_DIM) { int l = (x * MAX_DIM) + y; if (!seen[l]) { seen[l] = true; check.Add(l); } } } }  ## Java - 2,403,189 BUILD SUCCESSFUL (total time: 220 minutes 15 seconds)  This was supposed to be my attempt at a brute force. But! My first implementation of single-depth "best" choice yielded: 2,589,328 - BUILD SUCCESSFUL (total time: 3 minutes 11 seconds)  The code used for both is the same with the brute force storing a "snapshot" of the other possible moves and running the algorithm over all of them. • Issues If running with the "multi" pass approach random failures will occur. I setup the first 100 puzzle entries in a unit test and can achieve a 100% pass but not 100% of the time. To compensate, I just tracked the current puzzle number at fail time and started a new Thread picking up where the last one left off. Each thread wrote their respective results to a file. The file pool was then condensed into a single file. • Approach Node represents a tile/square of the board and stores a reference to all of it's neighbors. Track three Set<Node> variables: Remaining, Painted, Targets. Each iteration looks at Targets to group all candidate nodes by value, selecting the target value by the number of "affected" nodes. These affected nodes then become the targets for the next iteration. The source is spread across many classes and snippets aren't very meaningful away from the context of the whole. My source can be browsed via GitHub. I also messed around with a JSFiddle demo for visualization. Nevertheless, my workhorse method from Solver.java: public void flood() { final Data data = new Data(); consolidateCandidates(data, targets); input.add(data.getTarget()); if(input.size() > SolutionRepository.getInstance().getThreshold()){ //System.out.println("Exceeded threshold: " + input.toString()); cancelled = true; } paintable.addAll(data.targets()); remaining.removeAll(data.targets()); if(!data.targets().isEmpty()){ targets = data.potentialTargets(data.targets(), paintable); data.setPaintable(paintable); data.setRemaining(remaining); data.setInput(input); SolutionRepository.getInstance().addSnapshot(data, input); } }  ## C#- 2,196,462 2,155,834 This is effectively the same 'look for best descendant' approach as my other solver, but with a few optimizations that just barely, with parallelism, allow it go to depth 5 in a little under 10 hours. In the course of testing this I also found a bug in the original, such that the algorithm would occasionally take inefficient routes to the end state (it wasn't accounting for depth of states with score=64; discovered while toying with results of depth=7). The main difference between this and the previous solver is that it keeps the Flood Game States in memory, so it doesn't have to regenerate 6^5 states. Based on CPU use during running, I'm fairly certain this has moved from CPU bound to memory bandwidth bound. Great fun. So many sins. Edit: Because of reasons, the depth 5 algorithm doesn't always produce the best result. To improve performance, let's just do depth 5... and 4... and 3 and 2 and 1, and see which is best. Did shave off another 40k moves. Since depth 5 is the bulk of the time, adding 4 through 1 only increases runtime from ~10hrs to ~11hrs. Yay! using System; using System.Diagnostics; using System.IO; using System.Linq; using System.Collections.Generic; public class Program { static void Main() { int depth = 5; string text = File.ReadAllText(@"C:\TEMP\floodtest.txt"); text = text.Replace("\n\n", ".").Replace("\n", ""); int count = 0; string[] tests = text.Split(new [] { '.' }, StringSplitOptions.RemoveEmptyEntries); Stopwatch start = Stopwatch.StartNew(); const int parChunk = 16*16; for (int i = 0; i < tests.Length; i += parChunk) { //did not know that parallel select didn't respect order string[] sols = tests.Skip(i).Take(parChunk).AsParallel().Select((t, idx) => new { s = new Solver2(t).solve(depth), idx}).ToList().OrderBy(v=>v.idx).Select(v=>v.s).ToArray(); for (int j = 0; j < sols.Length; j++) { string k1 = sols[j]; count += k1.Length; int k = i + j; int estimate = (int)((count*(long)tests.Length)/(k+1)); Console.WriteLine(k + "\t" + start.Elapsed.TotalMinutes.ToString("F2") + "\t" + count + "\t" + estimate + "\t" + k1.Length + "\t" + k1); } } Console.WriteLine(count); } } public class Solver2 { public readonly int MAX_DIM; public char[] board; public Solver2(string prob) { board = read(prob); MAX_DIM = (int)Math.Sqrt(board.Length); } public string solve(int d) { string best = null; for (int k = d; k >= 1; k--) { string c = subSolve(k); if (best == null || c.Length < best.Length) best = c; } return best; } public string subSolve(int d) { State current = new State(copy(board), '\0', flood(board)); var sol = ""; while (current.score != board.Length) { State nextState = subSolve(current, d); sol = sol + nextState.key; current = nextState; } return sol; } public State subSolve(State baseState, int d) { if (d == 0) return baseState; if (!baseState.childrenGenerated) { for (int i = 0; i < baseState.children.Length; i++) { if (('1' + i) == baseState.key) continue; //no point in even eval'ing char[] board = copy(baseState.board); foreach(int idx in baseState.flood) board[idx] = (char)('1' + i); List<int> f = flood(board); if (f.Count != baseState.score) baseState.children[i] = new State(board, (char)('1' + i), f); } baseState.childrenGenerated = true; } State bestState = null; for (int i = 0; i < baseState.children.Length; i++) if (baseState.children[i] != null) { State bestChild = subSolve(baseState.children[i], d - 1); baseState.children[i].bestChildScore = bestChild.bestChildScore; if (bestState == null || bestState.bestChildScore < bestChild.bestChildScore) bestState = baseState.children[i]; } if (bestState == null || bestState.bestChildScore == baseState.score) { if (baseState.score == baseState.board.Length) baseState.bestChildScore = baseState.score*(d + 1); return baseState; } return bestState; } public char[] read(string s) { return s.Where(c => c >= '1' && c <= '6').ToArray(); } public char[] copy(char[] b) { char[] n = new char[b.Length]; for (int i = 0; i < b.Length; i++) n[i] = b[i]; return n; } public List<int> flood(char[] b) { int start = (MAX_DIM * (MAX_DIM / 2)) + (MAX_DIM / 2); var check = new List<int>(MAX_DIM * MAX_DIM); bool[] seen = new bool[b.Length]; var hits = new List<int>(MAX_DIM * MAX_DIM); check.Add(start); seen[start] = true; char target = b[start]; int at = 0; while (at < check.Count) { int toCheck = check[at++]; if (b[toCheck] == target) { addNeighbors(check, seen, toCheck); hits.Add(toCheck); } } return hits; } public void addNeighbors(List<int> check, bool[] seen, int loc) { //int x = loc / MAX_DIM; int y = loc % MAX_DIM; if(loc+MAX_DIM < seen.Length) addNeighbor(check, seen, loc+MAX_DIM); if(loc-MAX_DIM >= 0) addNeighbor(check, seen, loc-MAX_DIM); if(y<MAX_DIM-1) addNeighbor(check, seen, loc+1); if (y > 0) addNeighbor(check, seen, loc-1); } public void addNeighbor(List<int> check, bool[] seen, int l) { if (!seen[l]) { seen[l] = true; check.Add(l); } } } public class State { public readonly char[] board; public readonly char key; public readonly State[] children = new State; public readonly List<int> flood; public readonly int score; public bool childrenGenerated; public int bestChildScore; public State(char[] board, char k, List<int> flood) { this.board = board; key = k; this.flood = flood; score = flood.Count; bestChildScore = score; } }  • I tried your code and it does not compile. There is a error near one solve method call. Beside that, there is also a few "using" statements missing. Anyway, If your program just solve everything in 2.1M steps, congrats, this is rather impressive. May 5, 2014 at 21:22 • @tigrou I haven't had any problems with using statements; fixed the solve call error- it was an artifact from trying to just update the code instead of re-(copy/paste)-ing it. Sorry 'bout that. May 5, 2014 at 22:02 • blarg. You meant using == namespace import. Fixing that too. May 5, 2014 at 22:03 • What CPU do you use to solve all boards at depth 5 in 11 hours? I have run program under a I5 [email protected]. It took 30min to output each chunk of 256 boards. Based on that, it would took 8 days to solve the 100.000 boards. The CPU was bouncing between 80-100% usage during that time, all four cores used. Maybe there is a issue virtualbox machine used to ran the tests, but thats about 16x times slower than you (you said it took 11 hours). May 6, 2014 at 14:11 • @tigrou I'm running on an i5 [email protected] (3-4 year old hardware). Under VS, Debug vs Release mode is a 50% difference, but I doubt that'd explain a 16x difference. If you're running under a linux host you might try compiling with mono May 6, 2014 at 17:11 # Delphi XE3 2,979,145 steps Ok so this is my attempt. I call the changing part a blob, each turn it will make a copy of the array and test every possible color to see which color will give the biggest blob. Runs all puzzles in 3 hours and 6 minutes program Main; {$APPTYPE CONSOLE}

{\$R *.res}

uses
SysUtils,
Classes,
Generics.Collections,
math,
stopwatch in 'stopwatch.pas';

type
myArr=array[0..1]of integer;
const
MaxSize=19;
puzLoc='here is my file';
var
L:TList<TList<integer>>;
puzzles:TStringList;
sc:TList<myArr>;
a:array[0..MaxSize-1,0..MaxSize-1] of Integer;
aTest:array[0..MaxSize-1,0..MaxSize-1] of Integer;
turns,midCol,sX,sY,i:integer;
currBlob,biggestBlob,ColorBigBlob:integer;
sTurn:string='';
GLC:integer=0;

procedure FillArrays;
var
ln,x,y:integer;
puzzle:TStringList;
begin
sc:=TList<myArr>.Create;
puzzle:=TStringList.Create;
while puzzle.Count<19 do
begin
if puzzles[GLC]='' then
begin
inc(GLC);
continue
end
else
inc(GLC)
end;
for y:=0to MaxSize-1do
for x:=0to MaxSize-1do
a[y][x]:=Ord(puzzle[y][x+1])-48;
puzzle.Free;
end;
function CreateArr(nx,ny:integer):myArr;
begin
Result:=nx;
Result:=ny;
end;

procedure CreateBlob;
var
tst:myArr;
n,tx,ty:integer;
currColor:integer;
begin
n:=0;
sc.Clear;
currColor:=a[sy][sx];
repeat
tx:=sc[n];
ty:=sc[n];
if tx>0 then
if a[ty][tx-1]=currColor then
begin
tst:=CreateArr(tx-1,ty);
if not sc.Contains(tst)then
end;
if tx<MaxSize-1 then
if a[ty][tx+1]=currColor then
begin
tst:=CreateArr(tx+1,ty);
if not sc.Contains(tst)then
end;
if ty>0 then
if a[ty-1][tx]=currColor then
begin
tst:=CreateArr(tx,ty-1);
if not sc.Contains(tst)then
end;
if ty<MaxSize-1 then
if a[ty+1][tx]=currColor then
begin
tst:=CreateArr(tx,ty+1);
if not sc.Contains(tst)then
end;
inc(n);
until (n=sc.Count);
end;

function BlobSize:integer;
var
L:TList<myArr>;
tst:myArr;
n,currColor,tx,ty:integer;
begin
n:=0;
L:=TList<myArr>.Create;
currColor:=aTest[sy][sx];

repeat
tx:=L[n];
ty:=L[n];
if tx>0then
if aTest[ty][tx-1]=currColor then
begin
tst:=CreateArr(tx-1,ty);
if not L.Contains(tst)then
end;
if tx<MaxSize-1then
if aTest[ty][tx+1]=currColor then
begin
tst:=CreateArr(tx+1,ty);
if not L.Contains(tst)then
end;
if ty>0then
if aTest[ty-1][tx]=currColor then
begin
tst:=CreateArr(tx,ty-1);
if not L.Contains(tst)then
end;
if ty<MaxSize-1then
if aTest[ty+1][tx]=currColor then
begin
tst:=CreateArr(tx,ty+1);
if not L.Contains(tst)then
end;
inc(n);
until n=l.Count;
Result:=L.Count;
L.Free;
end;

function AllsameColor(c:integer):boolean;
var
cy,cx:integer;
begin
Result:=true;
for cy:=0to MaxSize-1do
for cx:=0to MaxSize-1do
if a[cy][cx]=c then
continue
else
exit(false);
end;
procedure ChangeColors(old,new:integer; testing:boolean=false);
var
i,j:integer;
tst:myArr;
begin
if testing then
begin
for i:= 0to MaxSize-1do
for j:= 0to MaxSize-1do
aTest[i][j]:=a[i][j];
for I:=0to sc.Count-1do
begin
tst:=sc[i];
aTest[tst][tst]:=new;
end;
end
else
begin
for I:=0to sc.Count-1do
begin
tst:=sc[i];
a[tst][tst]:=new;
end;
end;
end;
var
sw, swTot:TStopWatch;
solved:integer=0;
solutions:TStringList;
steps:integer;
st:TDateTime;
begin
st:=Now;
writeln(FormatDateTime('hh:nn:ss',st));
solutions:=TStringList.Create;
puzzles:=TStringList.Create;
swTot:=TStopWatch.Create(true);
turns:=0;
repeat
sTurn:='';
FillArrays;
sX:=Round(Sqrt(MaxSize))+1;
sY:=sX;
repeat
biggestBlob:=0;
ColorBigBlob:=0;
midCol:=a[sy][sx];
CreateBlob;
for I:=1to 6do
begin
if I=midCol then continue;
ChangeColors(midCol,I,true);
currBlob:=BlobSize;
if currBlob>biggestBlob then
begin
biggestBlob:=currBlob;
ColorBigBlob:=i;
end;
end;
ChangeColors(midCol,ColorBigBlob);
inc(turns);
if sTurn='' then
sTurn:=IntToStr(ColorBigBlob)
else
sTurn:=sTurn+', '+IntToStr(ColorBigBlob);
until AllsameColor(a[sy][sx]);
inc(solved);
if solved mod 100=0then
writeln(Format('Solved %d puzzles || %s',[solved,FormatDateTime('hh:nn:ss',Now-st)]));
until GLC>=puzzles.Count-1;
swTot.Stop;
WriteLn(Format('solving these puzzles took %d',[swTot.Elapsed]));
writeln(Format('Total moves: %d',[turns]));
solutions.SaveToFile('save solutions here');
end.


Thinking about a bruteforce backtracing method too.
Maybe fun for this weekend ^^

## Javascript/node.js - 2,588,847

Algoritm is a bit different then most here as it makes use of precalculated regions and diff states between calculations. It runs under 10 minutes here if you are worried about speed because of javascript.

var fs = require('fs')

var boards = file.split('\n\n');
var linelength  = boards.split('\n').length;
var maxdim = linelength* linelength;

var board = function(info){
this.info =[];
this.sameNeighbors = [];
this.differentNeighbors = [];
this.samedifferentNeighbors = [];
for (var i = 0;i <info.length;i++ ){
this.info.push(info[i]|0);
};

this.getSameAndDifferentNeighbors();
}

board.prototype.getSameAndDifferentNeighbors = function(){
var self = this;
var info = self.info;
function getSameNeighbors(i,value,sameneighbors,diffneighbors){

var neighbors = self.getNeighbors(i);
for(var j =0,nl = neighbors.length; j< nl;j++){
var index = neighbors[j];
if (info[index]  === value ){
if( sameneighbors.indexOf(index) === -1){
sameneighbors.push(index);
getSameNeighbors(index,value,sameneighbors,diffneighbors);
}
}else if( diffneighbors.indexOf(index) === -1){
diffneighbors.push(index);
}
}

}

var sneighbors = [];
var dneighbors = [];
var sdneighbors = [];

for(var i= 0,l= maxdim;i<l;i++){
if (sneighbors[i] === undefined){
var sameneighbors = [i];
var diffneighbors = [];
getSameNeighbors(i,info[i],sameneighbors,diffneighbors);
for (var j = 0; j<sameneighbors.length;j++){
var k = sameneighbors[j];
sneighbors[k] = sameneighbors;
dneighbors[k] = diffneighbors;
}
}

}

for(var i= 0,l= maxdim;i<l;i++){
if (sdneighbors[i] === undefined){
var value = [];
var dni = dneighbors[i];
for (var j = 0,dnil = dni.length; j<dnil;j++){
var dnij = dni[j];
var sdnij = sneighbors[dnij];
for(var k = 0,sdnijl = sdnij.length;k<sdnijl;k++){
if (value.indexOf(sdnij[k])=== -1){
value.push(sdnij[k]);
}
}
};
var sni = sneighbors[i];
for (var j=0,snil = sni.length;j<snil;j++){
sdneighbors[sni[j]] = value;
};
};
}
this.sameNeighbors = sneighbors;
this.differentNeighbors =  dneighbors;
this.samedifferentNeighbors =sdneighbors;

}

board.prototype.getNeighbors = function(i){
var returnValue = [];

var index = i-linelength;
if (index >= 0){
returnValue.push(index);
}

index = i+linelength;
if (index < maxdim){

returnValue.push(index);
}

index = i-1;

if (index >= 0 && index/linelength >>> 0 === i/linelength  >>> 0){
returnValue.push(index);
}
index = i+1;
if (index/linelength >>> 0 === i/linelength >>> 0){
returnValue.push(index);
}

if (returnValue.indexOf(-1) !== -1){
console.log(i,parseInt(index/linelength,10),parseInt(i/linelength,10));
}
return returnValue
}

board.prototype.solve = function(){
var i,j;
var info = this.info;
var sameNeighbors = this.sameNeighbors;
var samedifferentNeighbors = this.samedifferentNeighbors;
var middle = 9*19+9;
var maxValues = [];

var done = {};
for (i=0; i<sameNeighbors[middle].length;i++){
done[sameNeighbors[middle][i]] = true;
}
var usefullNeighbors = [[],[],[],[],[],[],[]];
var diff = [];
var count = ;

count = 0;
count = 0;
count = 0;
count = 0;
count = 0;
count = 0;

var indexsamedifferentNeighbors =samedifferentNeighbors[index];
for (var i=0;i < indexsamedifferentNeighbors.length;i++){
var is = indexsamedifferentNeighbors[i];
var value = info[is];
if (done[is] === undefined && usefullNeighbors[value].indexOf(is) === -1){
usefullNeighbors[value].push(is);
diff.push(value);
}

}
}

while(  usefullNeighbors.length > 0 || usefullNeighbors.length > 0 ||
usefullNeighbors.length > 0 || usefullNeighbors.length > 0 ||
usefullNeighbors.length > 0 || usefullNeighbors.length > 0 ){
for (i=0;i < diff.length;i++){
count[diff[i]]++;
};
var maxValue = count.indexOf(Math.max.apply(null, count));
diff.length = 0;
var used = usefullNeighbors[maxValue];
for (var i=0,ul = used.length;i < ul;i++){
var index = used[i];
if (info[index] === maxValue){
done[index] = true;
}
}
used.length = 0;
count[maxValue] = 0;

maxValues.push(maxValue);
}
return maxValues.join("");
};
var solved = [];
var start = Date.now();
for (var boardindex =0;boardindex < boards.length;boardindex++){
var b = boards[boardindex].replace(/\n/g,'').split('');
var board2 = new board(b);
solved.push(board2.solve());
};
var diff = Date.now()-start;
console.log(diff,boards.length);
console.log(solved.join('').length);
console.log("end");

fs.writeFileSync('solution.txt',solved.join('\n'),'utf8');


C code that is guaranteed to find an optimal solution by simple brute force. Works for arbitrary size grids and all inputs. Takes a very, very long time to run on most grids.

The flood fill is extremely inefficient and relies on recursion. Might need to make your stack bigger if it is very small. The brute force system uses a string to hold the numbers and simple add-with-carry to cycle through all possible options. This is also extremely inefficient as it repeats most of the steps quadrillions of times.

Unfortunately I was unable to test it against all the test cases, since I'll die of old age before it finishes.

#include <stdio.h>
#include <string.h>

#define GRID_SIZE       19

char grid[GRID_SIZE][GRID_SIZE] = { {3,3,5,4,1,3,4,1,5,3,3,5,4,1,3,4,1,5},
{5,1,3,4,1,1,5,2,1,3,3,5,4,1,3,4,1,5},
{6,5,2,3,4,3,3,4,3,3,3,5,4,1,3,4,1,5},
{4,4,4,5,5,5,4,1,4,3,3,5,4,1,3,4,1,5},
{6,2,5,3,3,1,1,6,6,3,3,5,4,1,3,4,1,5},
{5,5,1,2,5,2,6,6,3,3,3,5,4,1,3,4,1,5},
{6,1,1,5,3,6,2,3,6,3,3,5,4,1,3,4,1,5},
{1,2,2,4,5,3,5,1,2,3,3,5,4,1,3,4,1,5},
{3,6,6,1,5,1,3,2,4,3,3,5,4,1,3,4,1,5} };
char grid_save[GRID_SIZE][GRID_SIZE];

char test_grids[GRID_SIZE][GRID_SIZE];

void flood_fill(char x, char y, char old_colour, char new_colour)
{
if (grid[y][x] == new_colour)
return;

grid[y][x] = new_colour;

if (y > 0)
{
if (grid[y-1][x] == old_colour)
flood_fill(x, y-1, old_colour, new_colour);
}
if (y < GRID_SIZE - 1)
{
if (grid[y+1][x] == old_colour)
flood_fill(x, y+1, old_colour, new_colour);
}

if (x > 0)
{
if (grid[y][x-1] == old_colour)
flood_fill(x-1, y, old_colour, new_colour);
}
if (x < GRID_SIZE - 1)
{
if (grid[y][x+1] == old_colour)
flood_fill(x+1, y, old_colour, new_colour);
}
}

bool check_grid(void)
{
for (char i = 0; i < 6; i++)
{
if (!memcmp(grid, &test_grids[i], sizeof(grid)))
return(true);
}

return(false);
}

void inc_string_num(char *s)
{
char *c;

c = s + strlen(s) - 1;
*c += 1;

// carry
while (*c > '6')
{
*c = '1';
if (c == s) // first char
{
strcat(s, "1");
return;
}
c--;
*c += 1;
}
}

void print_grid(void)
{
char x, y;
for (y = 0; y < GRID_SIZE; y++)
{
for (x = 0; x < GRID_SIZE; x++)
printf("%d ", grid[y][x]);
printf("\n");
}
printf("\n");
}

int main(int argc, char* argv[])
{
// create test grids for comparisons
for (char i = 0; i < 6; i++)
memset(&test_grids[i], i+1, GRID_SIZE*GRID_SIZE);

char s = "0";
//char s = "123456123456123455";
memcpy(grid_save, grid, sizeof(grid));

print_grid();
do
{
memcpy(grid, grid_save, sizeof(grid));
inc_string_num(s);

for (unsigned int i = 0; i < strlen(s); i++)
{
flood_fill(4, 4, grid, s[i] - '0');
}
} while(!check_grid());
print_grid();

printf("%s\n", s);

return 0;
}


As far as I can tell this is the current winner. The competition requires that:

Your program must be entirely deterministic; pseudorandom solutions are allowed, but the program must generate the same output for the same test case every time.

Check

The winning program will take the fewest total number of steps to solve all 100,000 test cases found in this file (zipped text file, 14.23 MB). If two solutions take the same number of steps (e.g. if they both found the optimal strategy), the shorter program will win.

Since this always finds the lowest number of steps to complete every board and none of the others do, it is currently ahead. If someone can come up with a shorter program they could win, so I present the following size optimized version. Execution is a bit slower, but execution time isn't part of the winning conditions:

#include <stdio.h>
#include <string.h>
#define A 9
int g[A][A]={{3,3,5,4,1,3,4,1,5},{5,1,3,4,1,1,5,2,1},{6,5,2,3,4,3,3,4,3},{4,4,4,5,5,5,4,1,4},{6,2,5,3,3,1,1,6,6},{5,5,1,2,5,2,6,6,3},{6,1,1,5,3,6,2,3,6},{1,2,2,4,5,3,5,1,2},{3,6,6,1,5,1,3,2,4}};
int s[A][A];
int t[A][A];
void ff(int x,int y,int o,int n)
{if (g[y][x]==n)return;g[y][x]=n;if (y>0){if(g[y-1][x]==o)ff(x,y-1,o,n);}if(y<A-1){if(g[y+1][x]==o)ff(x,y+1,o,n);}if(x>0){if (g[y][x-1] == o)ff(x-1,y,o,n);}if(x<A-1){if(g[y][x+1]==o)ff(x+1,y,o,n);}}
bool check_g(void)
{for(int i=0;i<6;i++){if(!memcmp(g,&t[i],sizeof(g)))return(true);}return(0);}
void is(char*s){char*c;c=s+strlen(s)-1;*c+=1;while(*c>'6'){*c='1';if (c==s){strcat(s,"1");return;}c--;*c+=1;}}
void pr(void)
{int x, y;for(y=0;y<A;y++){for(x=0;x<A;x++)printf("%d ",g[y][x]);printf("\n");}printf("\n");}
int main(void)
{for(int i=0;i<6;i++)memset(&t[i],i+1,A*A);char s="0";memcpy(s,g,sizeof(g));pr();do{memcpy(g,s,sizeof(g));is(s);for(int i=0;i<strlen(s);i++){ff(4,4,g,s[i]-'0');}}while(!check_g());
pr();printf("%s\n",s);return 0;}

• So far it is the only entry that gets the most optimal solution every time. I'd argue it is a better last-place reference solution too. In fact, I'm not convinced that there is actually a better way that guarantees to get an optimal solution in every case, and so far no-one else has proven otherwise.
– user
Apr 25, 2014 at 15:08
• Until you can actually find the exact number of steps it will take, I can't accept this solution even if it is (theoretically) the best one. Apr 25, 2014 at 15:43
• Also, the grid size is 19, not 9. Apr 25, 2014 at 15:43
• Okay, I fixed the grid size. Does anyone know how to calculate the theoretical minimum number of steps required?
– user
Apr 26, 2014 at 8:40
• Nope. You'd have to use a program to solve for it, which is what you have right now. Apr 26, 2014 at 14:04