Arthur Whitney's one liner sudoku solver (2011)
dfns.dyalog.com
dfns.dyalog.com
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x tar -cf - . | gzip | base64 | wc -l
Looking at APL -- I'm reminded of what happens if I accidentally send the gzipped output to my tty...
I'm impressed that there's anyone who can follow along (can you find the bug?) to code like
p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
It really feels like compressed binary data where everyone's got a copy of the dictionary already...
But -- (and forgive me if I'm totally wrong) -- this isn't just "non-english" but "non-phonetic" which is a smaller set of written languages, and the underlying language is ... math.... so understanding the underlying grammer itself relies on having decades of math education to really make it jive.
If this code is just a final result of "learn math for 2-3 decades, and spend years learning this specific programming language" -- my statement stands. Interacting with this kinda binary blob as a programming language is impressive. I think I read somewhere that seymour cray's wife knew he was working too hard when he started balancing the checkbook in hex...
I'm sure each of those languages makes some guarantee about the sorts of errors that can be introduced - as opposed to C (let me pick on it) where the errors you know you can introduce, and the errors that are introduced aren't a large union. However i have a hard enough time typing english consistently, so the various "symbol-y" languages just glaze my eyes, unfortunately.
It almost "feels" like these languages are an overreaction to the chestnut "they must get paid by LoC".
Probably the biggest readability concern of overly-golfed expressions really is just being dynamically typed, a problem shared with all dynamically-typed languages. But array languages have the problem worse, as nearly all operations are polymorphic over array vs number inputs, whereas in e.g. JS you can use 'a+b' as a hint that 'a' and 'b' are numbers, & similar.
If you want readable/maintainable code, adding comments and splitting things into many smaller lines is just as acceptable as in other languages.
I'm also wondering about things like (APL-style) inner products -- they are undeniably powerful, but it's hard for me to conceptual use cases above rank 3.
In my code I'd sometimes write assertions in the beginning of a function to not only ensure it's called with the right shape but also as documentation.
Also, in practice really high rank arrays aren't used much. Even 4 is pretty rare.
I basically never use the generalized inner product; it's rather unique to the original APL - J has a variant that doesn't have the built-in reduction, and k and BQN and many if not most other array languages don't have any builtin for it at all. And in general I don't typically use rank higher than like one plus the natural dimensionality of the operation/data in question.
The best analogy i can give of my thought process is that first i unfolded the problem into one or more many-dimension object(s) ... then took a different "stance" of looking at the object, then refolded them into the final solution.
So yes... I had it all in my head at some point.
The compiler's whole state is a bunch of integer vectors, and •Show [a,b,c] prints some equal-length vectors as rows of a table, so I usually use that. The relevant code is usually a few consecutive lines, and the code is composed of very basic operations like boolean logic, reordering arrays with selection, prefix sum, and so on, so they're not hard to read if you're used to them. There are a few tricks, which almost all are repeated patterns (e.g. PN, "partitioned-none" is common enough to be defined as a function). And fortunately, the line prefaced with "Permutation to reverse each expression: more complicated than it looks" has never needed to be debugged.
Basically, when you commit to writing in an array style (you don't have to! It might be impossible!) you're taking an extreme stance in favor of visible and manipulable data. It's more work up front to design the layout of this data and figure out how to process it in the way you want, but easier to see what's happening as a result. People (who don't know APL, mostly) say "write only" but I haven't experienced it.
[0] https://github.com/mlochbaum/BQN/blob/master/src/c.bqn
[1] https://mlochbaum.github.io/BQN/implementation/codfns.html#i...
Don't suppose you can point to any resources to help wrap your head around BQN, do you?
I feel like if I were able to wrap my head around it I would never want to code in anything else. Thanks again and excited to take another look at it!
What could you do with that?
I don't know, but I bet some pretty cool stuff.
Just a couple quick ideas:
fns ← f g h ⍝ array of function
fns[condition] args ⍝ select function to run
(3 0 0⌿fns) args ⍝ f f f argsI've got to say, it's a really impressive language. Very well thought through, it brings some nice ideas. And as someone still newer to the space, it seems to do a great job of eliminating some of the unnecessary complexity of other languages. The straightforward approach on syntax / parsing is really fresh air.
> can you find the bug?
Several stand out immediately:
- Two syntax errors: unclosed single quote in '⍳n n←⍴⍵ and no right operand in the second use of Jot (∘). It's not clear how those could have snuk in naturally by accident, but I'll just assume cosmic rays and that they should be simply elided.
- n n←⍴⍵ is setting n twice, which is a bit surprising, though it signals that you probably expect ⍵ to have rank 2. In such cases _ n←⍴⍵ or n←⊃⌽⍴⍵ may be more natural, depending on intent.
- However, Decode (⊥) will error if ⍴⍵ returns anything other than a single integer (or an empty vector), so n n←⍴⍵ is equivalent to just n←⍴⍵ and doubly confusing.
- Which means that (n*÷2){⍵,⍺⊥⌊⍵÷⍺}⍳n n←⍴⍵ can only return a vector, i.e. 1..n with a number tacked on the end: the value of (1-x^n)/(1-x) evaluated at sqrt(n), which is a bit of a strange data structure IMHO. Something to do with geometric series of n^2?
- The second use of Ravel (,) in ,⍵ is redundant, and given the constraints we know above, so is the first use: ,(n*÷2)...
- It also means that (↑⍵) is the same as just ⍵
- But then (⍺∨.=⍵) is always just 1
- Meaning that the whole code is essentially equivalent to p←(n+1)⍴⊂⍳n×n←⍴⍵. I.e. it just outputs n+1 vectors of the integers 1 to n^2.
- Which, without context, is hard to guess intent, but that data structure feels a bit strange. Instead of a vector of uniform-length vectors, a matrix would be more efficient: (n+1)(n*2)⍴⍳n×n←⍴⍵. But that's just a matrix with rows that are all the same, so maybe we could just use the single vector (⍳2*⍨⍴⍵) directly?
Really, despite looking strange, once you learn the symbols and basic operations, APL is surprisingly straightforward. If you're on HN, then you're already smart enough to learn the basics easily enough.
Admittedly, though, becoming proficient in APL does take some time and learning pains. Once there, though, it does feel like a superpower.
> Advocates of the language emphasize its speed, facility in handling arrays, and expressive syntax.
(source: mostly amateur k programmer, also worked with it in a bank, find it vastly easier to read/write/remember than most mainstream languages)
I suspect that to study k (and use kdb) efficiently, you need to actively forget what you knew about the syntax of other languages, and study k as a language from Mars that happens to map to ASCII characters somehow.
Secondly, the power with Uiua is you can easily split up that expression literally by just hitting enter in some spots (and line swapping but…). You can give names
And finally if you are constantly doing operations across arrays it can be more legible to go a symbol like approach, like how most people prefer x+y to add x y. The conciseness helps you build up larger expressions before you need to break things up.
A much better measure would be the number of nodes in a parse tree, of semantically meaningful non-terminals like "a constant" or "a function call".
An even better measure would also involve the depth and the branching factor of that tree.
[1] https://en.wikipedia.org/wiki/Algorithmic_information_theory
The parse tree approach is trying to get at a fuzzy notion of useful information and useful density of information.
A one line solution takes up very little visual real estate. That matters a lot when you are working on some more complex problem. Flitting your eyeballs around a screen takes orders of magnitude less effort than scrolling around and navigating files. Cognitive load is important.
We really need to burn this vague "only semantics matter" scourge that's creeped into our programmer values these days. I'm sorry, but I care about things like incentives against over-engineering, ease of directly thinking in the problem domain, and simplicity of the encompassing ecosystem.
A terse one-line solution tells me there is virtually no room for over-engineering. Even without knowing K, I can see obvious constants side-by-side, telling me it's likely using a direct data representation of the problem in its code. Does K culture encourage code like that? Does programming in K bias you towards directness and simplicity? Then please, I want some of that special sauce on my team.
</rant>
When I work on some more complex problem, I like to think about the problem, not spend energy decoding condensed text. Scrolling a bit more verbose, but clear code, is faster for me.
Any language that add complexity at that layer loses me, and APL, even with crude visuals is not far from that.
It seems like parent’s metric (size of parse tree) would easily optimize for terseness and penalize bloat, regardless of language, so maybe your reaction was too reflexive. UX of a language does matter a bit, and one that’s too terse incurs development friction and technical debt when used in larger projects. Just study the history of Perl and why it’s not widely used.
What a one liner looks like is more or less the worst possible metric to use for large software projects. In any language, the style of code changes the larger the codebase, and cleverness and terseness become a liability. https://www.teamten.com/lawrence/writings/norris-numbers.htm...
Absolutely. I'm not arguing for maximal terseness and spent a lot of words attempting to say otherwise. (IMHO, we're both reflexively reacting to our parent comments a bit).
What I am wanting to point out is that form affects function and how we think about and use our languages. This in turn shapes our ecosystems and cultures, which influence our heuristics for keeping a pulse on project health and the surrounding support structures. Which all in turn reflect back to affect the forms we like and produce!
The mechanics of middle-sized and large businesses naturally incentivize bloat and churn to some degree, not because we necessarily want those things, but because coordination and communication are large information bottlenecks, a la Mel Conway's observations [0]. When our heads are filled with syntax, tooling, best practices, and absolute ideas about what correct code looks like, we make it that much harder to fill our heads with direct problem-domain concerns.
While senior engineers can and often do successfully wade through all that, it's a long grind, and anything that empowers team members to get there faster seems like an obvious win.
I wish that we as a community could better recognize that our values like "semantics over syntax" or "code review is necessary" or "readability is good" implicitly invoke a large set of contingencies in order to become heuristics that serve well.
Tools that violate our common sense and aesthetic values present an opportunity to sanity check those sentiments and potentially sharpen our understanding of them. In my experience, APL and probably K are really excellent at that, offering a new way of thinking that highlights clear disfunctionalities within our current "mainstream" languages and cultures.
If true, isn't that something we obviously want to eagerly investigate?
So, to bring it back, I think the statement that "AST node count is a better" embodies exactly the kind of values and mindset that make it harder for us to grow. What do we think about readable, maintainable, highly terse code? Does this K sample exemplify that? Why are K and APL successfully (if quietly) running significant portions of our economy? What structural, organizational, and cultural lessons do they embody that we can learn from?
I would be willing to bet that Excel spreadsheets are running more of our economy than K code, likely by orders of magnitude. I’d also be willing to bet that COBOL exceeds K use by similar multiples. Business/economic use doesn’t seem like a very good metric for what you’re talking about.
In effect, replies here effect to provide some criteria, but each is slightly different and somewhat begs the question, since said criteria can be easily chosen to support whatever conclusion you want.
When the object level discussion (i.e. in this case, the comparison of code size metrics) is ill-defined, the only natural thing we can reach for are cached ideas, heuristics, memetic trends, etc. That is, the discussion essentially becomes an implicit sharing of which cultural ideas we consider salient and important.
That is why I keep going on about culture and values in my previous replies. I'm not saying anything about ASTs vs. token count or whatever. I'm trying to say, "Hey, fellow devs. You know all the obvious ways that K and APL violate our sense of what good and proper code should look like? You know how they feel wrong? Well, actual experience by APL and K devs provides us evidence that we're potentially wrong and should give these languages more open-minded attention."
There’s a famous couple of comments by @arcfide defending the extremely terse K/APL style of coding, and it really makes a strong case. From what I can tell, this might be what you’re trying to say. I would just say to take note that he does not try to make the poster of the comment he replied to feel wrong headed, he focuses on the positives of his own approach, and he does not project his style on everyone else or make any claims that everyone should use it, he focuses on why it works for him. https://news.ycombinator.com/item?id=13571159
It's so weird, though. Everything disagreeable you point out with my comments, I kind of feel like is true of GP's comment. It casually dismisses the content of OP, injecting a strawman about a "metrics". Wore still, it just touts normative and relatively mainstream opinions about better vs. worse thing, without even offering up a hint as to what these supposed metrics are supposed to be measuring.
That's a dick move, IMHO, and a common one at that in these array language posts. I think we as a community do ourselves a disservice by allowing ourselves to propagate such echo chambers.
Which is all a pretty different message than @arcfide (eloquently) attempts.
Please note that nowhere do I attack GP or GP's comment specifically. If you're inclined to reread my comments, please note that I really do try hard to delineate ideas and cultural trends as the target. Heck, I even own up to being part of those trends and culture. Where you have thought I say "you", try rereading it as "we".
Anyway, cheers!
I’ve reread your comments, and they still read like an attack to me, while the top comment does not. You may feel like you’ve drawn a line, but the implications you made were quite clear. Calling it a dick move is a more direct attack, and talking about how it offends you tends to demonstrate that you have been and still are in fact attacking. Using strong language in a direct reply and talking about how wrong the mentality is is always going to be taken as an attack on the comment you’re replying to.
Personally I feel like the “one line” part of the article title is intentionally provocative, and as such, it invites critique, which is what the top comment is. It’s both impressive to fit a sudoku solver on one (short) line, and also at the same time, making a claim that can’t be fairly compared to other languages. As such, it is fair to point out that there’s a more universal way to evaluate the size of Arthur Whitney’s solution that is more compatible with other languages, and combined with the fact that everyone (including you?) already agrees that lines of code aren’t a good metric for anything, it’s not clear why you’ve taken such issue with that casual comment.
The article, disappointingly, doesn’t explain Whitney’s solution in words that non K readers can understand. At a glance, I would assume it’s a more or less brute force search over all possible sudoku boards and then matching against the cells, rows, and columns rules. In a way then, Whitney’s solver might be seen as a succinct statement of the rules of sudoku, which are indeed relatively short in any language.
That said, this exchange will definitely bounce around in my subconscious, so whether or not I explicitly agree, you've definitely moved the needle!
Anyway, whatever happened here, it was a genuine meeting of minds, so much obliged fellow HNer. Be well.
APL: https://github.com/search?type=code&q=language%3AAPL
Q: https://github.com/search?type=code&q=language%3Aq
Implementation: https://aplwiki.com/wiki/List_of_open-source_array_languages
http://johnearnest.github.io/ok/index.html
if it's something you're interested in trying i'd be happy to point you toward more resources, and i'm sure there are plenty of other arraylang tinkerers reading this thread who could help, too
For example, when working with arrays of data it certainly is easier to think and write “avg a+b” to add two arrays together and then take the average.
In a non-array programming language you would probably first need to do some bounds checking, then a big for loop, a temporary variable to hold the sum and the count as you loop over the two arrays, etc.
Probably the difference between like 6ish lines of code in some language like C versus the 6 characters above in Q.
But every language has features that help you reason about certain types of problems better. Functional languages with algebraic data types and pattern matching (think OCaml or F#) are nicer than switch statements or big if-else-if statements. Languages with built-in syntactic sugar like async/await are better at dealing with concurrency, etc.
There are limits, of course, and it’s not without downsides. Still, if I have to code in something all day, I’d like that “something” be as expressive as possible.
A very real example of this is Julia. Julia is not really an array-oriented programming language, it's a general language with a strong type system and decent functional programming facilities, with some syntactic sugar that makes it look like it's a bit array oriented. You could write any Q/k program in Julia with the same complexity and it would not be any more complex. For a decently complex program Julia will be faster, and in every case it will be easier to modify and read and not any harder to write.
In fact I've seen interop between q and numpy. The two mesh well together. The differences are aesthetic more than anything else.
> tables and IPC
Sure, kdb doesn't really have an equal, though it is very niche. But for IPC I disagree. The facilities in k/q are neat and simple in terms of setup, but it doesn't have anything better than what you can do with cloudpickle, and the lack of custom types makes effective, larger-scale IPC difficult without resorting to inefficient hacks.
Tables aren't niche, they're very useful! I looked at cloudpickle, and it seems to only do serialisation, I assume you'd need something else to do IPC too? The benefit of k's IPC is it's pretty seamless.
I'm not sure what you mean by inefficient hacks, generally you wouldn't try to construct some complicated ADT in k anyway, and if you need to you can still directly pass a dictionary or list or whatever your underlying representation is.
@ and . can be done in numpy through ufunc. Once you turn your unary or binary function into a ufunc using food = np.frompyfunc, you then have foo.at(a, np.s_[fancy_idxs], (b?)) which is equivalent to @[a, fancy_idxs, f, b?]. The other ones are, like, 2 or 3 lines of code to implement, and you only ever have to do it once.
vs and sv are just pickling and unpickling.
> Tables aren't niche,
Yes, sorry, I meant that tables are only clearly superior in the q ecosystem in niche situations.
> I looked at cloudpickle, and it seems to only do serialisation, I assume you'd need something else to do IPC too? The benefit of k's IPC is it's pretty seamless.
Python already does IPC nicely through the `multiprocess` and `socket` modules of the standard library. The IPC itself is very nice in most usecases if you use something like multiprocessing.Queue. The thing that's less seamless is that the default pickling operation has some corner cases, which cloudpickle covers.
> Im not sure what you mean by inefficient hacks, generally you wouldn't try to construct some complicated ADT in k anyway, and if you need to you can still directly pass a dictionary or list or whatever your underlying representation is.
It's a lot nicer and more efficient to just pass around typed objects than dictionaries. Being able to have typed objects whose types allow for method resolution and generics makes a lot of code so much simpler in Python. This in turns allows a lot of libraries and tricks to work seamlessly in Python and not in q. A proper type system and colocation of code with data makes it a lot easier to deal with unknown objects - you don't need nested external descriptors to tag your nested dictionary and tell you what it is.
I don't see how k/q tables are only superior in niche situations, I'd much rather (and do) use them over pandas/polars/external DBs whenever I can. The speed is generally overhyped, but it is significant enough that rewriting something from pandas often ends up being much faster.
The last bits about IPC and typed objects basically boil down to python being a better glue language. That's probably true, but the ethos of array languages tends to be different, and less dependent on libraries.
What if I want to take the average difference of two arrays?
https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
This particular snippet was in the context of compilers, but the rest of the talk has more on Dyalog and APL as a system of mathematical notation. The underlying theme is that optimizing mathematical expressions may be easier than optimizing general code.
As a quant, I used kdb+/q quite a bit for 5+ years for mid-frequency strategies, but as I moved towards higher frequency trading that required calculations on the order book that couldn't be easily or efficiently vectorized, then continuing to use array-focused languages would have only complicated reasoning about those problems.
It's a useful thing to learn though. And dare I say it, fun. Even if there was zero benefit to it, it'd still be fun. As it turns out, there really are benefits.
For me, the biggest benefit is when I'm working with data interactively. The syntax allows me to do a lot of complex operations on sets of data with only a few characters, which makes you feel like you have a superpower (especially when comparing to someone using Excel to try to do the same thing).
(KQED is the Bay Area PBS partner. PBS is the US public television org.)
One line solutions are incredible, and tacit is mind-bendingly cool. To use the unique compactness of a glyph-based language as a way to efficiently describe and perform functional programming - then to do that all over arrays!? - whoever had these ideas [0] is utterly genius.
But as someone trying to make time to write a program ground up in APL, knowing that I won't be able to make it just a set of really good one liners, that example is also significant for me.
You can ofcourse removethe capability to do thatand you'll effectively force the programmer to write more venous code, but then its strength as an interfacing tool is very much reduced.
The Iversonian languages has the capability to write incredibly terse code which is really useful when working interactively. When you do, your code truly is write-only because it isn't even saved. This is the majority of code that at least I write in these languages.
When writing code that goes in a file, you can choose which style you want to use, and I certainly recommend making it a bit less terse in those cases. The Iversonian languages are still going to give you organs that are much shorter than most other languages even even it's written in a verbose style.
So I do love APL and arraylangs, and learning them was really helpful in a lot of other languages.
But they never became a daily driver for me not because of the symbols, which were honestly fine if you stick with it long enough, but after about 3-4 years of dabbling on and off I hit a wall with APL I just couldn't get past.
Most other languages I know there is a "generic-ish" approach to solving most problems, even if you have to cludge your way through suboptimally until you find "the trick" for that particular problem and then you can write something really elegant and efficient.
APL it felt like there was no cludge option -- you either knew the trick or you didn't. There was no "graceful degredation" strategy I could identify.
Now, is this actually the case? I can't tell if this is a case of "yeah, thats how it is, but if you learn enough tricks you develop an emergent problem solving intuition", or if its like, "no its tricks all the way down", or if its more like, "wait you didn't read the thing on THE strategy??".
Orrr maybe I just don't have the neurons for it, not sure. Not ruling it out.
Even today, after having worked in these languages for years, I am still put off a bit by the walls of code that some array programmers produce. I fully understand the reasoning why it's written like that, but I just prefer a few spaces in my code.
I've been working on an array language based on APL, and one of my original goals was to make "imperative style" programming more of a first-class citizen and not punish the beginner from using things like if-statements. It remains to be seen how well I succeeded, but even I tend to use a more expressive style when terseness doesn't matter.
Here's an example of code I've written which is the part of the implementation that is responsible for taking any value (such as nested arrays) and format them nicely as text using box drawing characters. I want to say that this style is a middle ground between the hardcore pure APL style found in some projects and the style you'll see in most imperative languages: https://codeberg.org/loke/array/src/branch/master/array/stan...
keys←'foo' 'bar' 'baz'
values←1729 42 0.5721
indexOf←keys∘⍳ ⍝ The dyadic ⍳ here is what builds a hashmap
data←(values⍪¯1)[indexOf 'bar' 'bar' 'baz' 'foo' 'invalid' 'foo']
k v ←'foo' 1729
k v⍪←'bar' 42
k v⍪←'baz' 0.5721
keys values←↓⍉[
'foo' 1729
'bar' 42
'baz' 0.5721]
[0]:https://help.dyalog.com/19.0/#Language/Defined%20Functions%2...
[1]:https://aplwiki.com/wiki/Array_notation
[2]:https://groups.google.com/a/jsoftware.com/g/forum/c/VYmmHyRo...
That said, it's also really not a limitation with the languages either. In my experience, punching past that wall is exactly the process of making the paradigm click. It took me a good 500 hours hacking on my YAML parser prototype over the course of a year before the puzzle pieces began to click in place.
Those lessons are still percolating out, but it feels like some combination of 1) data-driven design principles, 2) learning how to concretely leverage the Iversonian characteristics of good notation [1] in software architecture, and 3) simple familiarity with idioms and how they express domain-specific concepts.
Feel free to contact me if you'd like to chat directly about this and overcoming the wall.
[0]:https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4 [1]:https://www.jsoftware.com/papers/tot.htm
https://www.youtube.com/watch?v=DmT80OseAGs
You can try the solution at https://tryapl.org/
https://codegolf.stackexchange.com/questions/tagged/sudoku?t...
Ultimately though,they are a proxy to a more relevant but difficult to determine attributes such as
Given a reasonably proficient engineer, the amount of time it would take them to resolve a bug in code written by someone else or alternatively extend its functionality in some way.
Could have been made shorter at the price of readability.
sudoku(Rows) :-
length(Rows, 9),
maplist(same_length(Rows), Rows),
append(Rows, Vs), Vs ins 1..9,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs),
blocks(Ds, Es, Fs),
blocks(Gs, Hs, Is).
blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
blocks(Ns1, Ns2, Ns3).
If you want to learn more about it or see more of Markus's work:
https://www.metalevel.at/sudoku/
More about Scryer Prolog (a modern , performant, ISO-compliant prolog written mostly in rust)
Nebulous1:
Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,/{@[x;y;]'(!10)^x|/p[;y]=p,:,3/:-3!p:!9 9}')/&~x
Most programmers would agree the ‘/’ symbol is at least as clear as writing ‘divideBy’. The question is how often the symbols are used and if their frequency in code justifies learning them.
def solve(grid):
def find_empty(grid):
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
return r, c
return None
def is_valid(grid, num, pos):
r, c = pos
if num in grid[r]:
return False
if num in [grid[i][c] for i in range(9)]:
return False
box_r, box_c = r // 3 * 3, c // 3 * 3
for i in range(box_r, box_r + 3):
for j in range(box_c, box_c + 3):
if grid[i][j] == num:
return False
return True
def backtrack(grid):
empty = find_empty(grid)
if not empty:
return True
r, c = empty
for num in range(1, 10):
if is_valid(grid, num, (r, c)):
grid[r][c] = num
if backtrack(grid):
return True
grid[r][c] = 0
return False
backtrack(grid)
return gridIt's not clear why the poster prefers that other implementation, or that they understand APL or array programming.
So as a result the comment reads as "it's in a language I don't know. I'd prefer it in a language I do know." Which is a fairly useless comment.
If that's not what they intended, it would be helpful for them to add some context to their comment.
AFAICT AI cannot replicate this, yet, will be interesting when that day comes.
Not sure where I got that from.
Why array languages seem to gravitate to symbol soup that makes regex blush I'll never know.
They're all artificial problems, but your brain likes a challenge and you get a dopamine hit when you solve it, I suppose.
Variant sudokus on the other hand are a lot of fun. They often have very elegant solve paths and there are many neat tricks you can discover and reason about.
Some fun ones, if you'd like to try:
- https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id...
- https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id...
- https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id...
The last puzzle has no fewer than 9 custom rules, in addition to the regular Sudoku rules, and then it also says “every clue is wrogn [sic]” implying there is some meta out-of-the-box thinking required to even understand what the rules are. That is more a riddle than a logic puzzle.
By contrast, the charm of classical Sudoku is that the rules are extremely simple and straightforward (fill the grid using digits 1 through 9, so that each digit occurs exactly once in each row, column, and 3x3 box) and any difficulty solving comes from the configuration of the grid.
As for solvers, it’s a very elegant, well-formed problem with a lot of different potential solutions, many of which involve useful general techniques. I used to dabble clumsily in chess engines and honestly it’s the only time I’ve ever ended up reading Knuth directly for various bit twiddling hacks, so it’s always educational.
1: https://musgravepencil.com/products/600-news-wood-cased-roun...
Sudoku, crosswords, Simon Tatham's puzzles etc. are an excellent way to pass the time while keep training the mind. Sports are their equivalent for the body.
Finally, writing solvers for a problem, be it real or artificial, for many is just another variety of puzzle to engage in.
Puzzles in commercial collections don't usually have that problem, but those from other sources sometimes do.
Solvers also make for a nice craft exercise, as here. Simple but not trivial, you can approach them in a lot of different ways and thereby work through different techniques or constraints you mean to explore.
I would argue that puzzles in commercial collections are more likely to have that problem than ones made freely available by hobbyists, as commercial enterprises inevitably cut corners on things like labour costs for an actual human setter.
I have seen dozens of commercial puzzle games and applications that do not make any attempt to verify the (auto-generated) puzzles as solvable, but I don't think I've ever had the same problem on a site like LMD.
I enjoy running simulation after simulation after simulation, studying possible outcomes and optimising everything. Everyone is different :)
While I myself found an opportunity to reply to the GP and didn't down vote them, their comment only engaged with the article in a shallow way and only then, seemingly, to just dismiss the concept of solver altogether.
It wasn't a offensive comment, but it didn't really contribute to the site in the way many people digging into deep technical walkthroughs like this expect to see.
Some downvotes weren't guaranteed, but they're not surprising and they're probably helping new readers stay engaged with more topical and technical alternatives.
It's not the end of the world to get a few downvotes, and it's almost never personal. It certainly isn't here.
If have to ask: What's rewarding about only having your viewpoint reinforced?