Sudoku

How a 20-line program to solve sudokus came about

1 Apr 2014 | , ,
Share on:

I started using K, a predecessor language to q, in 1995. I had been hired by a large European bank to tune their databases. I found many performance and expressability problems that were forcing programmers to move analytics to C++, Java, or even Excel. Communication from one to the other often caused errors and always came with a performance penalty.

My client introduced me to Steve Apter and Arthur Whitney who showed me K, which I began to use for a project to detect unusual expenditures within one division of the company. I got hooked by the sheer power of working in a monolingual environment, the advantages of debugging in an interpretive environment, and the speed.

I’ve been using K or q ever since for prototypes for data analysis, finance, biology, and even puzzle design. One time my son, then 12, gave me a sudoku to solve when sudoku first was popular. I was on a train and staring at the paper gave me motion sickness. So I wrote a 20 line program in K to solve all sudokus. Later, I sent it to Arthur Whitney and he came back with an 80 character program. Too awesome, I know.

Over the years in conversations with Arthur, I extolled some of the benefits of relational algebra and SQL. Eventually he came out with KSQL, and then q, which is a clear semantic improvement over SQL, it subsumes SQL and includes order-dependent aggregates such as moving averages, as-of joins, and so on.

When I teach this, I refer to the model as “arrable” (for array-table). It’s a conceptually more powerful model than unordered tables and simplifies programming.

By Prof. Dennis Shasha
Department of Computer Science
Courant Institute of Mathematical Sciences
New York University

SUGGESTED ARTICLES

Kx Partner Companies Recognized for Excellence and Innovation

26 Jan 2018 | , , , , , , , ,

Over the last few months a number of startups using Kx technology have been recognized for excellence and innovation in their industries, including BrainWaveBank, 3DEO and RxDataScience (RxDS).
RxDS, is at the forefront of new types of interactive data science software applications for the pharmaceutical and healthcare industries. It uses Kx technology to power the Big Data analytics engine in its apps. Silicon Review noted RxDS’ rapid growth in revenue and customer acquisition in naming RxDS as one of the 30 Fastest Growing Private Companies to Watch.