My Fizz Buzz solutions…

Joel Grus blogged about a job interview where he was asked about the ridiculous Fizz Buzz question that apparently some companies use to weed out complete frauds from their job interview process. The task is to create a program which prints the numbers from 1 to 100, but where all numbers which are a multiple of three are replaced with “fizz”, all numbers which are multiples of five are replaced with “buzz” and all numbers which are multiples of both three and five are replaced by “fizzbuzz”.

Joel somewhat comically decided to use the TensorFlow framework and solve it with machine learning. Go read his post, it’s pretty comical. Well, if you are a programming geek, it will seem comical.

For the non programmers in my audience (are there some?) this is a trivial program to write. If a programmer can’t bust out a solution to this in a minute or two, they likely have no business calling themselves a programmer. Here’s my 30 second solution (I type moderately slow):

#include <stdio.h>

int 
main()
{
    int i ;
    for (i=1; i<=100; i++) {
        if (i % 15 == 0) {
            printf("fizzbuzz\n") ;
        } else if (i % 3 == 0) {
            printf("fizz\n") ;
        } else if (i % 5 == 0) {
            printf("buzz\n") ;
        } else {
            printf("%d\n", i) ;
        }
    }
    return 0 ;
}

No doubt there are some practitioners in the audience who think that this inefficient, because I compute multiple modulo operations per loop iteration. I’d probably argue that this is short and clear, and until profiling revealed it to be a performance problem, I wouldn’t change it. If people insisted that I do a single modulo per loop iteration, I’d probably replace it with something like:

#include <stdio.h>

int 
main()
{
    int i ;
    for (i=1; i<=100; i++) {
        switch (i % 15) {
        case 3:
        case 6:
        case 9:
        case 12:
            printf("fizz\n") ;
            break ;
        case 5:
        case 10:
            printf("buzz\n") ;
            break ;
        case 0:
            printf("fizzbuzz\n") ;
            break ;
        default:
            printf("%d\n", i) ;
            break ;
        }
    }
    return 0 ;
}

I’d submit that it is much less clear, but not too bad. I’d probably add a comment to explain the higher level idea.

If we are allowed two modulo calls per iteration, could do it this way:

int
main()
{
    int i ;
    for (i=1; i<=100; i++) {

        bool mul3 = (i % 3 == 0) ;
        bool mul5 = (i % 5 == 0) ;

        if (mul3 && mul5) {
            printf("fizzbuzz\n") ;
        } else if (mul3) {
            printf("fizz\n") ;
        } else if (mul5) {
            printf("buzz\n") ;
        } else {
            printf("%d\n", i) ;
        }
    }
    return 0 ;
}

I used boolean variables, which I think reads a little better, but you could obviously use integers.

What if you don’t want to any modulus calls? Well, you could use a state machine…

#include <stdio.h>

int 
main()
{
    int i = 1 ;
    int state = 1 ;

    while (i <= 100) {
        switch (state) {
        case 3:
        case 6:
        case 9:
        case 12:
            printf("fizz\n") ;
            break ;
        case 5:
        case 10:
            printf("buzz\n") ;
            break ;
        case 15:
            printf("fizzbuzz\n") ;
            state = 0 ;
            break ;
        default:
            printf("%d\n", i) ;
        }
        state ++ ;
        i++ ;
    }
    return 0 ;
}

I hope I never have an interview where this is the kind of question I get asked.

Shower (or should I say “cow-er”) Thought of the Day…

I just recently found out about the /r/showerthoughts subreddit, where people vote on pithy sayings. I thought this might be a fun thing to have to replace the aging and relatively static “fortune” file that I use. I used the Python “PRAW” library to fetch the top entry for the day, and then optionally pass it to the terrific “cowsay” program for formatting.

Here’s the tiny, nearly trivial code, whose code includes an example of the output of “./shower –cow”

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# a program for fetching texts from Reddit's /r/showerthoughts reddit.
#  _________________________________________
# / The guy who said “Look! Up in the sky!  \
# | It’s a bird!” in the Superman intro was |
# \ strangely excited to see a bird...      /
#  -----------------------------------------
# \   ^__^
#  \  (oo)\_______
#     (__)\       )\/\
#         ||----w |
#         ||     ||

# Written by Mark VandeWettering, no rights reserved.

import sys
import subprocess
import argparse
import textwrap
import praw

parser = argparse.ArgumentParser(description = 'Fetch shower thoughts from reddit.')
parser.add_argument('--cow', action='store_true',
                help='pipe output through cowsay')
parser.add_argument('--cowstyle', dest='cowstyle', nargs=1, default=['default'],
                help='style passed to cowsay')
args = parser.parse_args()

r = praw.Reddit('shower')
s = r.get_subreddit('showerthoughts')

submissions = s.get_top_from_day(limit = 1)


for submission in submissions:
        if args.cow:
            ps = subprocess.Popen(['cowsay', '-f', args.cowstyle[0]], shell=False, stdin=subprocess.PIPE)
            ps.stdin.write(submission.title.encode('utf-8'))
            ps.stdin.close()
            ps.wait()
        else:
            for l in textwrap.wrap(submission.title, 60):
                print ("\t%s" % l).encode('utf-8')

Some random pictures from the Maker Faire…

Code for generating a random Latin square…

The other day I mentioned that generating random Latin squares was a bit more complicated than I thought, and that an algorithm by Jacobson and Matthews was the way that people typically did it. I worked up this implementation based on a couple of different descriptions of the algorithm (the original paper was behind a paywall). The code below simply generates a random DIMxDIM Latin square using their algorithm. I haven’t done extensive testing, but it appears to mostly work. I did run a test where I generated one million 4×4 matrices, and found that it generated all 576 different matrices in approximately the same propertion, so it appears to at least be roughly operational. I’ll eventually merge the code with my nascent KenKen generator.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/*
 * rls.c
 *
 * A straightforward implementation of the algorithm by Jacobson and 
 * Matthews, _Generating uniformly distributed random Latin square_,
 * Journal of Combinatorial Design, 1996.
 *
 * I actually couldn't find the original paper, so this is an implementation
 * based upon other descriptions of the algorithm.
 *
 * Written by Mark VandeWettering.
 *
 */


#define DIM (6)

typedef struct t_incidence_cube {
    int s[DIM][DIM][DIM] ;
} IncidenceCube ;


void
InitIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    /* First, zero the cube */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            for (k=0; k<DIM; k++)
                c->s[i][j][k] = 0 ;

    /* And then dump ones in the right place... */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            c->s[i][j][(i+j)%DIM] = 1 ;
}

void
PrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%2d ", k+1) ;
                    break ;
                }
            }
        }
        printf("\n") ;
    }
    printf("\n") ;
}

void
CompactPrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%01d", k+1) ;
                    break ;
                }
            }
        }
    }
    printf("\n") ;
}

void
ShuffleIncidenceCube(IncidenceCube *c)
{
    int i, j ;

    for (i=0; i<DIM*DIM*DIM; i++) {
        
        // Assume we have a "proper" matrix...
       
        // Pick a random zero from the incidence cube... 
        int rx, ry, rz ;
        do {
            rx = lrand48() % DIM ;
            ry = lrand48() % DIM ;
            rz = lrand48() % DIM ;
        } while (c->s[rx][ry][rz]) ;

        int ox, oy, oz ;

        for (j=0; j<DIM; j++) {
            if (c->s[j][ry][rz] == 1)
                ox = j ;
            if (c->s[rx][j][rz] == 1)
                oy = j ;
            if (c->s[rx][ry][j] == 1)
                oz = j ;
        }

        // do the +/- 1 move...  
        // These are all square with zeros in them...
        c->s[rx][ry][rz] ++ ;
        c->s[rx][oy][oz] ++ ;
        c->s[ox][ry][oz] ++ ;
        c->s[ox][oy][rz] ++ ;

        // These all have ones, except for maybe the last one...
        c->s[rx][ry][oz] -- ;
        c->s[rx][oy][rz] -- ;
        c->s[ox][ry][rz] -- ;
        c->s[ox][oy][oz] -- ;

        while (c->s[ox][oy][oz] < 0) {

            rx = ox ;
            ry = oy ;
            rz = oz ;

            // Pick one of the two 1's that are in conflict
            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            }
          
            // do the +/- 1 move...  
            // These are all square with zeros in them...
            c->s[rx][ry][rz] ++ ;
            c->s[rx][oy][oz] ++ ;
            c->s[ox][ry][oz] ++ ;
            c->s[ox][oy][rz] ++ ;

            // These all have ones, except for maybe the last one...
            c->s[rx][ry][oz] -- ;
            c->s[rx][oy][rz] -- ;
            c->s[ox][ry][rz] -- ;
            c->s[ox][oy][oz] -- ;
        }

    }
}

int
main()
{
    IncidenceCube c ;
    int i ;

    srand48(getpid()) ;
    InitIncidenceCube(&c) ;
    ShuffleIncidenceCube(&c) ;
    PrintIncidenceCube(&c) ;
    return 1 ;
}

Atinlay Aresquares…

My last post dealt with a solver for KenKen puzzles. Once you have one of those, then the obvious thing to work on next (in your copious spare time) is a generator for KenKen puzzles. It didn’t seem too hard. You’d begin by generating a random Latin square, then divide it up into “cages”, assign an operator to them, and then see if that has a unique solution. If it doesn’t, well, try again.

But it turns out that each of these steps hides inner difficulties, as well as a certain amount of mathematical beauty. Tom and I were discussing the first bit (generating random Latin square) over lunch, and I thought I’d summarize some of our discussion.

First of all, consider the following “canonical” Latin square of order 4:

1 2 3 4
4 1 2 3
3 4 1 2 
2 3 4 1

It’s pretty easy to generate this Latin square, and it’s pretty easy to generate other Latin squares by swapping either rows or columns. But the question is, can I generate all other Latin squares from this one by doing row and column swap operations?

Tom assured me that the answer was no, which wasn’t at all apparent to me until he presented an interesting example, so I thought I would summarize some of the ideas here. My presentation will take a slightly different path than our discussion, but it ends in the same place.

Let’s consider each square to have a canonical form, where the first row and first column are in sorted order. It should be relatively obvious that you can place any matrix into this form by a series of row and column operations. For example, the matrix above can be placed in canonical form by swapping the second and fourth row.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3 

But let’s consider a different matrix in canonical form formed by swapping 1 and 3 in rows 2 and 4.

1 2 3 4
2 1 4 3
3 4 1 2 
4 3 2 1 

We can’t convert this matrix into the previous one by only swapping rows and columns. Thus, if we try to generate a random Latin square by just beginning with a canonical one, there are possible Latin squares which can never be generated by just swapping row and column operations. Too bad, since this is really easy to implement.

Another easy thing to implement would be to just generate all possible Latin squares, store them in a table, and select one at random. That doesn’t seem too bad, until you consider that there are 812,851,200 possible Latin Squares to consider. Sure, disks are big, but that seems excessive.

It turns out that the algorithm that most people seem to use is the from 1996 by Jacobson and Matthews, which is hard to find online as a full paper. It uses a similar idea, but instead of swapping full rows and columns, it applies a different operator that mutates a given Latin square, and in the limit produces a distribution which is the same as the random distribution. It’s a little tricky to understand, but I am going to try to have an implementation in Python later tonight.

Here’s a report that provides some details and the skeleton of an implementation in Java.

KenKen puzzle solver…

Lately, my lunch hours have been spent working on the NYT Crossword with my lunch companion Tom. While I find that the Thursday crosswords are often beyond my ability to do in the allotted time, between the two of us, more often than not we manage to plow through them. Slowly over time, we’ve begun to solve them slightly quicker, so I’ve branched out to doing the KenKen puzzles.

For those of you who haven’t seen these before, you can learn about them on their official website here. The 4×4 ones are usually pretty easy, but the last couple days have done some 6×6 puzzles have been shockingly hard. So much so, that today I got to this state on today’s puzzle:

IMG_1128

Yes, I was using pen. And I made a mistake, although I can’t see what I was thinking when I did. And because I made a mistake, I couldn’t spot it, and I was hung up. The “4” in first column was wrong. I knew it could not be a 6 or 1, or a 3, or a 4, but for some reason I thought that the final column couldn’t be 4 and 3, but..

Never mind, it doesn’t matter what the mistake was.

By the end up twenty minutes I was annoyed, knew I had made a mistake, but decided to give into the urge to write a program to solve it. How long could it take?

Well, the answer was about 27 minutes.

This program doesn’t have any interface or flexibility, everything is hard coded. Basically it uses backtracking and fills in each square in order from bottom left to top right, and as the top most, right most square of each outlined area is finished, it checks to make sure that the sums/differences/whatever for the filled in region sum to the right values. I didn’t know how I was going to encode those constraints, so I just ended up writing a function that computes the proper constraint. This is not really the right way to do it: it’s error prone and requires recompilation of the code to change the puzzle. But it does work fairly well, once you type the expressions in correctly.

Once I got those straightened out, it blats out the solution in less than 1 millisecond on my desktop.

+---+---+---+---+---+---+
| 6 | 1 | 5 | 2 | 4 | 3 |
+---+---+---+---+---+---+
| 2 | 6 | 1 | 3 | 5 | 4 |
+---+---+---+---+---+---+
| 1 | 4 | 6 | 5 | 3 | 2 |
+---+---+---+---+---+---+
| 3 | 2 | 4 | 6 | 1 | 5 |
+---+---+---+---+---+---+
| 5 | 3 | 2 | 4 | 6 | 1 |
+---+---+---+---+---+---+
| 4 | 5 | 3 | 1 | 2 | 6 |
+---+---+---+---+---+---+

1 solutions found

It points out that the 4 should have been a 2 (IDIOT!) and then it all works out.

The code is 178 lines long, but is not particularly pretty/short/adaptable. Some day, I’ll have to tidy it up and make a better version.

But in case people find this stuff interesting, here it is. Remember: 27 minutes to write.

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

/*
 * kenken.c
 *
 * A program inspired by a particular tough 6x6 puzzle that appeared
 * on Thursday, May 11, 2016, which Tom Duff and I could not appear to
 * get the answer to during our lunch hour.  I thought that it was possible
 * that I could write a program to solve the puzzle in less than an hour.
 *
 * Hence, this code.
 *
 */

int total = 0 ;

#define DIM     (6)

typedef struct t_puzzle_state {
    int sq[DIM][DIM] ;
    int r[DIM] ;            // bitflag for values left in rows...
    int c[DIM] ;            // bitflag for values available in columns
} PuzzleState ;


void
PrintPuzzleState(PuzzleState *p)
{
    int i, j ;

    printf("+") ;
    for(j=0; j<DIM; j++)
        printf("---+") ;
    printf("\n") ;

    for (i=0; i<DIM; i++) {
        printf("|") ;
        for (j=0; j<DIM; j++) {

            if (p->sq[DIM-1-i][j])
                printf(" %1d |", p->sq[DIM-1-i][j]) ;
            else
                printf("   |") ;
        }
        printf("\n+") ;
        for(j=0; j<DIM; j++)
            printf("---+") ;
        printf("\n") ;
    }
    printf("\n") ;
}

void
InitializePuzzleState(PuzzleState *p)
{
    int i, j ;

    memset((void *) p, 0, sizeof(*p)) ;

    for (i=0; i<DIM; i++) {
        for (j=1; j<=DIM; j++) {
            p->r[i] |= (1<<j) ;
            p->c[i] |= (1<<j) ;
        }
    }
}

void
HardcodePuzzleState(PuzzleState *p, int r, int c, int val)
{
    p->sq[r] = val ;
    p->r[r] &= ~(1<<val) ;
    p->c &= ~(1<<val) ;
}

#define SQUARE(i, j)    ((i)*DIM+(j))
#define ABS(x)          ((x)<0?(-(x)):(x))

int
ConstraintSatisfied(PuzzleState *p, int i, int j)
{
    switch (SQUARE(i,j)) {
    case SQUARE(0,1):
        return ABS(p->sq[0][0] - p->sq[0][1]) == 1 ;
    case SQUARE(0,2):
        return p->sq[0][2] == 3 ;
    case SQUARE(1, 3):
        return (p->sq[0][3]+p->sq[1][3]) == 5 ;
    case SQUARE(1, 4):
        return (p->sq[0][4] * p->sq[0][5] * p->sq[1][4]) == 72 ;
    case SQUARE(2, 2):
        if (p->sq[2][2] == 2 * p->sq[1][2])
            return 1 ;
        if (p->sq[1][2] == 2 * p->sq[2][2])
            return 1 ;
        return 0 ;
    case SQUARE(2, 4):
        return ABS(p->sq[2][4] - p->sq[2][3]) == 5 ;
    case SQUARE(3, 1):
        if (p->sq[3][1] == 2 * p->sq[2][1])
           return 1 ;
        if (p->sq[2][1] == 2 * p->sq[3][1])
           return 1 ;
        return 0 ;
    case SQUARE(3, 5):
        return (p->sq[3][5]+p->sq[2][5]+p->sq[1][5]) == 8 ;
    case SQUARE(4, 2):
        return ABS(p->sq[4][2] - p->sq[4][1]) == 5 ;
    case SQUARE(4, 3):
        return p->sq[4][3] == 3 ;
    case SQUARE(4, 4):
        return (p->sq[4][4]+p->sq[3][2]+p->sq[3][3]+p->sq[3][4]) == 19 ;
    case SQUARE(5, 1):
        return (p->sq[4][0]*p->sq[5][0]*p->sq[5][1]) == 12 ;
    case SQUARE(5, 4):
        return (p->sq[5][2]+p->sq[5][3]+p->sq[5][4]) == 11 ;
    case SQUARE(5, 5):
        return (p->sq[5][5]+p->sq[4][5]) == 7 ;
    default:
        return 1 ;
    }

    return 1 ;
}

void
SolvePuzzleState(PuzzleState *p, int i, int j)
{
    int v ;

    if (i >= DIM) {
        PrintPuzzleState(p) ;
        total ++ ;
        return ;
    }
        
    int pval = p->r[i] & p->c[j] ;

    for (v=1; v<=DIM; v++) {
        if ((pval & (1<<v)) == 0)
            continue ;
        // Try to place v in sq[i][j] ;
        p->sq[i][j] = v ;

        if (ConstraintSatisfied(p, i, j)) {
            p->r[i] &= ~(1<<v) ;
            p->c[j] &= ~(1<<v) ;

            int ni, nj ;
            nj = j + 1 ;
            if (nj < DIM) {
                ni = i ;
            } else {
                ni = i + 1 ;
                nj = 0 ;
            }

            SolvePuzzleState(p, ni, nj) ;

            p->r[i] |= (1<<v) ;
            p->c[j] |= (1<<v) ;
        } 
    }
    p->sq[i][j] = 0 ;
}

main()
{
    PuzzleState p ;
    InitializePuzzleState(&p) ;
    // HardcodePuzzleState(&p, 0, 2, 3) ;
    // HardcodePuzzleState(&p, 4, 3, 3) ;

    SolvePuzzleState(&p, 0, 0) ;
    fprintf(stderr, "%d solutions found\n", total) ;
}

A couple of cool solar powered FPV planes…

Just a pointer to a cool project which appeared on Hackaday: a solar powered FPV plane that can fly forever (or at least until the sun goes down). Pretty spiffy!

The comments show a link to this solar powered plane developed at ETH:

It was in the air for 81.5 hours, and had a continuous flight distance of 2316km. It’s a slow flyer: average speed is just under 18mph. At the end, you can see that the wind conditions had deteriorated seriously. Pretty nifty.

A story from SIGGRAPH past…

I’ve been meaning to write down this story for a while, because it represents a time when I was booed away from a microphone by a crowd of two thousand people, and I always think that stories like this are fun.

Back in 1996, I attended SIGGRAPH in New Orleans. I remember flying out early and arriving somewhere around 7:00AM and being unable to check into my hotel room, so I went down to the French Quarter and had beignets and coffee. It was a wonderful city for one of my favorite activities: eating. Pixar alumnus and foodie Steve Upstill had given out a list of restaurants in New Orleans for me to try, and I don’t think I had a bad meal the entire week. From gumbo to po’boy sandwiches, it was all amazing and delicious.

But back to the conference..

There was a panel that I attended called “Graphics PCs will Put Workstation Graphics in the Smithstonian”. The panelists were:

  • Sam Uselton, from MRJ, Inc. served as organizer.
  • Michael Cox, from S3
  • Jay Tayborg, from Microsoft
  • Michael Deering, from Sun Microsystems
  • Kurt Akeley, from SGI

It was an interesting discussion, with the first two taking the the side of PCs, and the second two, standing up for the workstations. I had been working in scientific visualization at Princeton, and had then been at Pixar for about five years. My own opinions were that economies of scale would eventually destroy the workstation market. I had worked with high end SGI products, as well as workstations such as Stellar/Ardent/Stardent but had also been tracking the developments in the game world, and to me the writing on the wall was clear.

I remember approaching the microphone and asking a question like “Given what we’ve seen with Moore’s law and the increase in capabilities in microcomputers, and the increasing availability of operating systems like Linux and BSD-based systems,isn’t it reasonable to conclude that the same kind of thing will happen in the graphics market?”

I recall that Akeley and Deering tried to answer with something along the lines of “only workstations have the fast buses/high performance memory subsystems/careful and accurate rasterization that is necessary to do real graphics. I didn’t find that answer particularly helpful and tried to ask a followup and…

Was enthusiastically booed away from the microphone. It was really impressive, to have a couple of thousand people heckle you at once.

But in the end… I think that history points out that I was more or less correct. By no means did I contribute to this trend, but I did recognize it at the time, in a way that the majority of professionals at SIGGRAPH largely did not.

1995 was the apex for SGI, with a market cap of over 7 billion dollars. Ten years later, it was delisted from the NYSE because its stock price had fallen to below one dollar, with a market cap of just $120 million dollars. It was effectively bankrupt in 2006.

Sun would take a different path, riding the dot.com bubble up with its server hardware into the year 2000, and then riding it down to destruction. It never really became a big player in graphics.

Meanwhile, nVidia was formed in 1993 by Huang, Malachowsky and Priem (from AMD, Sun Micro and Sun Micro, respectively). In 1999 they released their Geforce board, which brought hardware with a full transform and light pipeline to the consumer market. They would absorb many other players, and became the destination for a lot of talent who had previously been at SGI. It currently has a market cap of about $18.6 billion dollars.

Mind you, nVidia didn’t pursue a strategy driven entirely by consumer products, and Sun and SGI failed not just because of their graphics strategy. But I do think that I what I said was mostly right, and it didn’t take forever for my prediction to come true.

Another press account of the session.

The summary page from the 1996 SIGGRAPH proceedings

Solving the N queens problem, again…

Backtracking is a better technique, obviously. The version from earlier today was actually not very clever, and took half an hour to find the 73,712 solutions to the 13×13 checkerboard. This version is less code (just 91 lines, compared to 107 for yesterdays) and finds all the 13×13 solutions in just 2.5 seconds (a speed up of around 720x).

#include <stdio.h>
#include <stdlib.h>

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))


void
place(int r, int n)
{
    int i, j ;
    if (r == n) {
        // We filled in all rows...
        total++ ;
        print(board, n) ;
    } else {
        for (i=0; i<n; i++) {
           board[r] = i ;
           for (j = 0; j<r; j++) {
                if (board[j] == board[r])
                    goto skipit ;
                if (abs(board[j]-board[r]) == abs(j-r))
                    goto skipit ;
           }
           place(r+1, n) ;
skipit:
           continue ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}

Fun.

Solving the N Queens Problem…

A question on Quora set me thinking about solving the N Queens problem, which is to list all ways that N queens can be positioned on an NxN checkerboard such that no queen can attack the other. I seemed to have misplaced my implementation of this that I did in Python, so I decided to do one in C while watching Agents of Shield. The code in general shows the lack of attention, but it does work. It can find all 92 solutions for the 8×8 checkerboard in under one second, but slows down rapidly after that, taking nearly half an hour to find all 73,712 solutions for the 13×13 board.

This program isn’t completely unclever (in fact, I think it is too clever in a way) but it should be properly described as a brute force search, since it generates all N! ways of positioning N queens in different rows, and tests them for diagonals. Thus, it’s runtime is O(N!), which isn’t great. It doesn’t even do backtracking, which would undoubtedly help a great deal.

One good page I found googling this morning is this one by Jeff Somer. His program is much more clever than mine. My estimate is that my program would take well over 100,000 years to count all the positions for a 21×21 board, Jeff’s does it in about a week.

Another cool page is this one, which introduces the idea of “super-queens”, which also capture with the same moves as a knight. Only one unique solution for N=10 exists, which is pretty cool. For higher N, more solutions become possible.

Code is archived here.

#include <stdio.h>
#include <stdlib.h>

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))

void
check(int board[MAX_N], int n)
{
    int col[MAX_N] ;
    int i, j ;

    for (i=n-1; i>=0; i--) {
        col[i] = board[i] ;
        for (j=i+1; j<n; j++) {
            if (col[i] <= col[j]) 
                col[j]++ ;
        }
    }

    // now, check for diagonals.. 
    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            if (abs(col[i]-col[j]) == abs(j-i))
                return ;

    // we have a winner...
    total++ ;
    print(col, n) ;
}

void
place(int i, int n)
{
    if (i == n) {
        // check board 
        check(board, n) ;
    } else {
        int which ;
        for (which=0; which < n-i; which++) {
            board[i] = which ;
            // recurse...
            place(i+1, n) ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}