July 3, 2022 by Lucian Mogosanu

Back in the 1990s, and perhaps in the 1980s as well, anyone who lived in ye olde Bükreş would find at the local newspaper kiosk a periodic magazine called a Rebus, otherwise known as Integrame, filled with naught else but crossword puzzles and associated hints, such as the name of a city, or a photo of a movie star or whatever. My mind tends to associate these magazines with Bucharest's Northern railway station, since the salesmen there would go as far as to board the trains that had yet to leave in order to sell their wares; and in the days before smartphones, laptops and the interwebs, most folks would indeed pass their travellin' time solving these.

At some point around 2005, the same folks started publishing another set of magazines, this time containing a particular type of number games along with, or instead of the popular crossword puzzles. By far the most popular among the games there was (and still is, I suppose) one named Sudoku. Mind you, not that the vast majority of Romanians doing these have even heard of Nikoli or any of their other logic games. Some of them, among which yours truly, have ventured further into, say, Simon Tatham's puzzle collection to try out nonograms, tentai show or futoshiki -- if one looks carefully, he or she may observe a variation on wordle that was part of that collection for quite a long while.

Furthermore, nowadays programmable computers are so accessible that modelling any such game and scrutinizing its boundaries has become a breeze, at least to the thinking man. From a computational point of view, all the aforementioned games have something in common: a subset of the space of inputs, e.g. incomplete game maps, form a so-called linear region, that is, a set of inputs, each of which admits a unique solution which may be found without requiring the so-called AI to resort to brute-force, i.e. backtracking or similar general state-space search techniques. In most cases a "deductive" method of finding solutions is possible, that involves the mere iterative application of constraints until the solution reveals itself. This linear region is what is usually fed to people in the magazines over in the train station, while for the content designer establishing whether a given input is to be solved linearly or not depends on how much of the initial information, e.g. Sudoku numbers, it provides to the player.

My own interest for this type of games was recently rekindled after exploring variations on Sudoku, among which the so-called Kuromasu/Kurodoko referenced in the title. I have thus begun writing a literate Common Lisp implementation for it: begun, since the implementation is far for complete, or otherwise perfect; literate, since at least from my point of view the code itself and the comments are a more interesting subject of study than the results of program execution on a machine, and thus said program is entirely lacking in bells and whistles to make the experience more "user-friendly"; Common Lisp since I like the language and after almost ten years of discovering it, and among all the programming systems that I've humbly tried, I still find it the most powerful for solving problems of arbitrary complexity.

Below lies the Kuromasu V tree. For now I will keep it up to date, so make sure to check it out periodically.

Filed under: computing, gaming, lisp.
RSS 2.0 feed. Comment. Send trackback.

12 Responses to “Kuromasu”

  1. #1:
    Cel Mihanie says:

    Since you're using/promoting this 'V' which appears to be a custom version control system, it might be nice if you made a post going into the basics of it, i.e. how is it different vs Git, where do we download the utilities, how can we at least do a check out and examine the history.

    The 'V' link on your blog leads to a message like "This page used to contain some meanwhile deprecated stuff. See src/." - not very encouraging. Clicking through the posts a bit more, it seems a writeup once resided at cascadianhacker.com , but the link (and site) is deader than disco. One is left with no alternative but to try to piece together some understanding by doing a deep dive on Diana Coman's blog, which is both inefficient (many posts in, I'm still not seeing any clear description) and maybe not the best starting experience if you don't entirely agree with the philosophy, politics and personalities involved.. :)

  2. #2:
    spyked says:

    For what it's worth, there's an archived version of Ben's article, for however long that'll last on the interwebs. I just left the link here for reference.

    Unfortunately, I don't think one can decouple V from it's socio-cultural and political context, in fact I can indeed understand how in the lack of such a context, the thing looks like a meaningless soup of ???. As for the other, I don't think a comparison to git does it any justice, so I will attempt to provide a coherent explanation from a whole different angle.

    In 99.99% of cases when you read about "V" in some TMSR-related context, the text doesn't refer to any particular implementation of a version control system, but rather first and foremost to a particular set of methods for doing version control. These methods rely on two additions to the classical diff/patch tools.

    The more obvious addition among the two is a so-called "seal", in practice a detached ASCII-armored PGP signature -- detached, because you may want to have more than one; ASCII-armored because why bother with binary formats when you can have text for the same costs; and PGP for the lack of a better tool, or, as the poet once said, "altceva n-a fost". Anyway, say I want to sync some code on a new machine that I'm bootstrapping; assuming that I or someone I trust (in practice: someone whose *public key* I trust) has signed that code in the past, seals allow me to verify the authenticity of said code regardless of the medium of transport that I choose (FTP, HTTP, CD, torrents, whatever). Which is how it oughta always work, regardless of what the HTTPS shills would have us believe.

    I know git allows signing one's commits, but that's a bolt-on after-the-fact optional "feature", while seals are an integral part of V. There's simply no place for comparison between the two here. Also note that while V enables collaboration between folks who trust each other (and who thusly also become liable for the code they write), this isn't a strict prerequisite and, more importantly, it works both ways: it's enough for *me* to sign the code that *I* trust and leave out whichever patches are published by my enemies.

    The second addition becomes apparent by looking at the patch itself: for each file that is modified through the process of patching, one may record a summary (in practice: a hash) of the previous (---) and subsequent (+++) versions of said file. This sets a partial ordering on patches, allowing one to apply (in V jargon: press) them in a particular order. In practice, that is also the historical order in which the patches were created.

    That's about it, in essence. All the rest of V-related stuff comprises code, convention, mechanism, whatever, but they're not essential to what V means. As I've said, V is an enabler, but it's by no means mandatory, as far as I know the so-called "vpatches" are backwards compatible with ye olde patch -p1. Only, at least in my humble view, "backwards" is a double-entendre in this case.

    I was going to say that I'm not really into promoting V (since the last guy that I tried to convince replied with "yeah, this sounds interesting" and moved on to other things), but if anything, this is as good a PR campaign I can do it. Maybe not a very good one, since it doesn't fit into the postmodern view of "explain like I'm five"/one minute pitch, but whatever.

  3. #3:
    spyked says:

    Ah, how silly of me, I've forgotten to link to an implementation: Diana's V-starter IMHO makes a more than decent means of bootstrapping.

    Even sillier yet, I haven't mirrored it anywhere, I guess I'll get to it sometime.

  4. #4:
    Verisimilitude says:

    Well, this game is neat, like nonogram puzzles, and may make a nice candidate for a little machine code game I can write later in the year. By the by, CELL-IN-BOUNDS-P, or at least its body, should be replaced by COMMON-LISP:ARRAY-IN-BOUNDS-P.

  5. #5:
    spyked says:

    Right you are, I will fix this in the next iteration.

  6. #6:
    spyked says:

    > Even sillier yet, I haven't mirrored it anywhere, I guess I'll get to it sometime.

    And done.

  7. #7:
    spyked says:

    Updated with a dumb iterative solver.

  8. #8:
    spyked says:

    Updated with an enormous (algorithmic) performance optimization.

  9. #9:
    spyked says:

    Updated with a new heuristic for eliminating "dead end" states in allocators.

    This directs the player's eye towards a general set of primitives for verifying the validity of partial and final table states, which primitives in turn direct one towards a general efficient state space searcher. The only reason why I didn't jump into this in the first place is because it's the easy way out, as modelling the game in a general SAT solver would have yielded pretty much the same "state space" approach. Instead I went about mapping the deductive, "intuitive to the human mind" methods, to a set of procedures, which led to the current state of affairs. Which is what "artificial intelligence" is all about in the first place.

    Other than that, there's yet a whole lot more to be added on the other side: a graphical interface, a visualizer for potential colourings, a random table generator and perhaps more. I guess I'll get back to this in a couple of months from now, since for now I have other things to look at.

  10. [...] say this "intentional stance" hasn't already manifested itself? Say, after I code an agent to solve a particular problem, who's to say that its so-called "intention" isn't then to solve the problem? By the way, can you [...]

  11. [...] the recent discussions on Lisp and V, I've decided to review (or re-re-re-review, rather?) Esthlos' Common Lisp Vtron1. I've only [...]

  12. [...] environment, you may attach a public key to it, assuming that said agent is capable of emitting signed artifacts. In most cases however you attach particular actions, which provides you with a model of how it [...]

Leave a Reply