Browse Category

Logic

Reading List: ‘Absolutely Nasty Sudoku, Level 2’ (Frank Longo)

I enjoy logic puzzles (not just in a formal context, to be clear). Probably one of the most well-known genres of these is sudoku, a grid-based constraint satisfaction problem made popular by the Japanese publisher Nikoli. Given a 9 by 9 grid which may be decomposed into three 3 by 3 sub-grids (boxes), fill in numbers such that there is precisely one number from 1 to 9 in each row, column and 3 by 3 sub-grid. Some numbers are already given as clues; there is usually only one unique solution for a given clue set.

Solving a sudoku puzzle, in general terms, is NP-complete (of course, for a 9 by 9 grid, solving can be done in constant time). ‘Obvious’ strategies involve finding the only place in each row/column/box where a given number could go (since each of these must contain each digit once), or finding the only number that could be assigned to a given cell.

The next step would then involve considering interactions between cells – for example, ‘these two cells in this row can only contain 3 and 5, so no other cells can contain a 3 or a 5’, or ‘both of the cells where 7 could go in this box are in the top row, so there can’t be a 7 in the top row of the other two boxes that are horizontally aligned’ (called a pointing pair). Complexity only develops from there; there are a myriad of clever strategies as shown on the sidebar here.

Sudoku (sudokus?) are often featured in newspapers, and there are many compilations of these. However, as one gets familiar with the strategies, these can become less interesting. For example, consider this hard sudoku from the Guardian; a not-that-smooth solve yielded a 5m11s time, and the most complex technique I used was the ‘pairs’ reasoning I outlined above.

I recently discovered Frank Longo’s Absolutely Nasty Sudoku series, and thankfully this is one series which seems to live up to its name. Consider this grid (which is the puzzle above, converted into an easier to read format):

The grid pictured above is from a puzzle towards the tail end of the Level 2 book. Although no cells are obvious (and it doesn’t look like the pairs/triples logic yields anything), there are several ways to proceed from here:

  • In row 3, you can have an 8 only in columns 2 and 9. This is also true in row 6. This means that no other rows can have 8s in columns 2 and 9; in particular, the second cell in the bottom-most row can’t be an 8, and has to be a 4. (This strategy is called X-Wing.) This is arguably the most straightforward deduction here, though it wasn’t the one I saw.
  • Consider that if row 5 column 1 was a 5, then row 8 column 1 must be an 8; that forces row 9 column 2 to be a 4, and row 9 column 7 to be an 8. Alternatively, row 5 column 1 can be an 8. Either way, row 5 column 7 can’t be an 8, and must be a 4. (This strategy is called an XY-Chain.)
  • Suppose row 6 column 7 was a 9. Then, the rectangle of cells with vertices in rows 1 and 3 and columns 4 and 7 admits two solutions; without affecting other cells, I can have either a 3 or 7 be in the top left corner. Thus, row 6 column 7 can’t be a 9, and must be a 3. (This strategy is called a Unique Rectangle.) This was actually the next step I made when solving this puzzle!

A key criterion when evaluating whether a Sudoku book (or a puzzle book in general) would be the difficulty and quality of the puzzles. The difficulty level for Level 2 is well-placed for someone like me, if maybe a little on the easier side; I’m familiar with most/all of the ‘basic’ techniques, and am aware of though not confident with trickier techniques like the aforementioned Unique Rectangle. I might have preferred Level 3, actually; there were several puzzles at the beginning of Level 2 that seemed like they could be solved with techniques I’d consider as basic. I also haven’t found any “broken” puzzles which couldn’t be solved (presumably, the author would have checked these with a solver before publication)!

I also have other criteria for evaluating Sudoku books, though. I tend to write down cell candidates as well as other annotations when solving. These help me more easily remember observations like pointing pairs; I’d prefer the grids to be sufficiently large that I can comfortably write these out. The grids in this book were certainly of adequate size. While my handwriting tends to be quite small, I don’t think grid size would be problematic for most people.

The choice of ring binding seems to make sense, too; the book needs to remain open when one is solving. Generally I found the paper to be very smooth to write on. I don’t have many complaints here.

The book has a very brief foreword, and then gets straight into the puzzles (with solutions at the back). The target audience is clearly people who are well-accustomed to Sudoku. As mentioned earlier, this is the second in a five-part series and based on online reviews I determined this to be a good place to start. I wouldn’t recommend this for someone just starting out with Sudoku, though.

Unwinding Logical Threads (Hotseat: WPF Puzzle GP 2017, Round 1C)

Background

The World Puzzle Federation is an international organisation which, among other things, organises annual puzzle contests. These involve solving puzzles that rely on logical deduction and observation. That said, maybe because I’m pretty new to these, sometimes backtracking algorithms are the order of the day!

The Puzzle GP is a series of distributed puzzle competitions run throughout the year. The GP is split into three series: C, B and A (in increasing order of difficulty). Puzzles in group C are likely to be largely accessible to general audiences (and that’s what I’m covering today); group B puzzles are typically drawn from a selection of “well-known” puzzle types, and group A puzzles often feature extensions of group B puzzles in unusual ways.

Contestants are given 60 minutes for each set of puzzles. I have very little experience with these puzzles, so I think I’ll start with group C.

(The puzzle set can be found here.)

Performance

I started off with the Darts puzzles, for which I had a strategy in mind. I then struggled with the Matches puzzles, only solving C7, before moving on to the Arithmetic Squares, both of which were solved quickly. I then spent probably a good ten minutes digging through the Word Search. I finished the easy Scrabble task and almost finished the harder one, though I failed to see a simple move near the end of the puzzle. I then started on Products, which I probably should have prioritised more highly as I think I figured out the mathematical logic behind it. I solved the 120-pointer C18 after the contest, and it was actually not too hard. With three minutes left to go after finishing C17, I took a stab at the Fill in the Blank series and managed to solve two of them.

I solved the remaining puzzles after the time ran out, apart from C3. Elastic Bands was actually very easy. I have a bit of an aversion to spatial reasoning puzzles, but recognised the problem as graph isomorphism and had some techniques for it based on that. Old Maid was also easy; I didn’t get round to it in time. The last Fill in the Blank and both instances of Count the Shapes both gave me headaches.

Selected Problems in Depth

C5-C6: Darts

Given a dartboard which has several regions with k point values and m darts, find a way to throw the darts on the dartboard such that the darts add up to a target value. Each dart must score, and each region can have only up to 1 dart. For example, with regions [4, 21, 8, 11, 13], two darts and a target of 19, the correct answer is [8, 11].

To solve this for two darts, one good solution could be to iterate through the list. On a computer, using a hash-set could be a good solution; when we look at a number, if it’s in our “target set” we’re done – otherwise we add the number we would need to make up the target to the target set. It’s a simple O(n) solution.

I think implementing a hash set on paper for me would be too troublesome. There’s an alternative which I used: sort the array in O(n \log n) and then, use a pair of pointers, one starting at the beginning and one at the end of the array. Adding the numbers up, if we’re over the target we bring the pointer at the end back, and if we’re under the target we push the pointer at the start forward.

The problem had three darts; I simply picked the overall largest number and solved the appropriately reduced target with the two-dart algorithm above, backtracking where needed to smaller largest numbers. Binary insertion sort is probably pretty reasonable to do by hand.

C10: Elastic Bands

Given a network with nodes marked with letters, and another network with edges provided, give a labelling of the nodes such that the networks are identical. This is basically finding what’s called a graph isomorphism in discrete mathematics.

I didn’t solve this in the contest, but probably should have. I split the nodes by degree, and then tried to identify relationships between these. For example, there was a single degree 4 node in the puzzle that wasn’t connected to any of the other degree 4 nodes, so I was able to uniquely identify it quickly.

C16-C18: Products

Given an N \times N grid, place the numbers from 1, 2, \ldots, 2N in the grid once each. Each row and column must contain two numbers, and numbers cannot share a cell. Clue numbers are given by the side of the grid and sometimes on diagonals. Where given, the product of numbers in the relevant row, column or diagonal must equal the clue.

The first two puzzles had N=10; the third had N=15. I think my main strategy here involved searching for prime factors that would uniquely identify numbers along the rows and columns. For N=10 this would be [11, 13, 17, 19]; for N=15 this included [17, 19, 23, 29]. I also usually started looking for very large numbers (because they might have a unique factorization in the allowed range) or small ones (e.g. in the first puzzle, there was only one column and one row with a product less than or equal to 20, implying that the 1 had to be in that column/row).

I also considered the places where a given number might fit, and in the later puzzles noticed when multiple columns could definitively use certain numbers. For example, if 5 was already used in an N=10 puzzle, and there were two 20 row hints, I could eliminate 1, 20, 2 and 10 from consideration for the other rows.

This wasn’t too difficult, though I can imagine that puzzles with only partial hints might be substantially more challenging!

Meta-Analysis

A score of 262 would have placed 12th out of 215 contestants (2nd out of 139 for contestants not in higher divisions). To be fair, this is in part because many top solvers don’t participate in the division C contests at all. Some of this might also be because there would have been less pressure as I was doing this on my own, not as part of a real contest.

Looking at the top end of the scoreboard, the Darts, Arithmetic Square, first instance of Matches and first instance of Products were solved by most of the leaders. Elastic Bands and Old Maid (I didn’t solve either of these two), as well as the Word Search were also fairly common. Thereafter, contestants varied quite a bit in what they solved. As might be expected, the contestants that solved the final instance of Products generally did very well (it was worth 120 points by itself).

A Tour of Two Islands (IJCAI-17 Reflections)

Over the past two weeks, I took some time out from work and visited two islands, one substantially larger in land area than the other (and, incidentally, I am returning to another island). I’ve been to both at some point in the past; the larger one for vacation, and the smaller for study, work, visiting family and friends and for vacation as well. The latter is not too difficult to guess – it’s Singapore; the former is Australia.

Academic Program

I was in Melbourne for the twenty-sixth International Joint Conference on Artificial Intelligence (IJCAI-17). Of course, the main highlight for me was presenting “Model Checking Multi-Agent Systems against LDLK Specifications“, a paper which built on parts of my Masters’ thesis on MCMAS-Dynamic. This was my first time presenting at an academic conference, though it’s not my first publication (that’s in AAMAS 17 on CTL*K); it was a little nerve-wracking, though I practiced the presentation a number of times beforehand and I think that helped a lot. Prof. Michael Wooldridge (the author of a commonly used textbook on multi-agent systems) even gave me a compliment that it was confidently presented. I’m not so sure about that, but I guess I have some private local state, and in any case deontic logic doesn’t typically have box p implies p as an axiom.

I also enjoyed the rest of the academic program as well. Apart from Alessio, I had the opportunity to meet up with several other academics whose names, at least, were very familiar. The keynote was delivered by Prof. Stuart Russell (one of the co-authors of the well-known Introduction to AI textbook), and discussed the concept of provably beneficial AI. Essentially, humans tend to be poor at specifying things (e.g. King Midas); many naive specifications of goals or objective functions naturally lead to agents enforcing self-preservation; more informally, “you can’t fetch the coffee if you’re dead”. The talk then discussed a way of formulating a problem such that it would always be a dominant strategy for an AI agent to allow itself to be switched off (as compared to not allowing itself to be switched off); see [Hadfield-Menell et al. 2016] (The Off-Switch Game) for more detail. The other invited speakers also had fairly interesting topics, discussing applications of AI in teaching, commerce and Texas hold-em poker.

I made it a point to attend as many paper presentation sessions as feasible. Expectedly, at a top conference like IJCAI there were quite a number of talks, especially in areas further removed from my work, that proved largely inscrutable. I think my presentation would also have been tricky to follow if one was not reasonably acquainted with temporal logic and/or multi-agent systems. Nonetheless, I gave my best effort in trying to follow the presentations, and there were certainly many interesting talks.

There was a session devoted rather specifically to the discussion of AI applied in the context of computer games. I found [Dann et al. 2017] (Real-Time Navigation in Classical Platform Games via Skill Reuse) to be particularly interesting; the key idea was having the agent acquire skills for small local movements, such as making a single jump to jump on top of a block three cells above the ground. The agent learns success probabilities for these skills, and uses a variant of Dijkstra with log-likelihood to find the “most likely” way to reach the goal safely (though there are some complications with re-planning if a step fails). The authors also demonstrated that the model performs better than the state of the art algorithm, which is based on A*, for maze-like levels. Other talks in the session also discussed level generation and physics engine inference (for platformers), RTS combat planning, narrative control in an educational RPG… and strategy derivation in Hex (this felt a bit out of place, but I guess they must have had exactly five papers that fit the theme well; sessions had either four or six presentations).

In terms of tutorials, I was unfortunately rather sleepy when I landed in Melbourne on Sunday. I did attend the tutorials on Monday, though; there was a very gently paced introduction to argumentation theory (the course Argumentation and Multi-Agent Systems which Prof. Francesca Toni teaches at Imperial would likely have covered this material, though she was on sabbatical when I was in year 4), and a less gently paced overview of heterogeneous learning (machine learning where some differences in the data sources can be exploited to yield better results).

Non-Academic Program

Stepping back from the academic side of IJCAI, I also enjoyed the social events at the conference, and I think they were run fairly well; that said, I acknowledge I don’t have a benchmark at all. The reception at the Melbourne Cricket Ground was very generous, especially in terms of dessert (chocolate tarts!), and the conference in the Docklands was certainly done to a high standard. It also introduced me to the “alternating drop” protocol, which is apparently common (but peculiar to) Australia. Essentially, given two choices of main course X and Y, instead of having guests indicate their preference, they are served XYXYXY… around the table (of course, those with dietary restrictions are excluded). I can see how this is logistically advantageous (you know beforehand that it will suffice to prepare just over N/2 of both options, given N guests), but I’m not sure I like the probability of not getting my preference…

I stayed at the “recommended” Crown Metropol which was certainly luxurious. The hotel is located south of the Yarra river in Melbourne, and is part of the Crown Entertainment Complex – among other things, this features a fairly large casino, several restaurants and luxury shopping (way out of my budget range). Nonetheless, it was a good base from which I could easily explore the city, especially on the few days I stayed on after IJCAI.

Post-Conference

I made it a point to leave a few days after the conference itself was over to explore the city, as I knew the conference days themselves were going to be fairly packed (8 am – 6.30 pm usually, running till 11 or so on the night of the Reception and Banquet). Like many work trips, the “official business” part of the trip was fairly draining – I perhaps should have seen this coming. I did manage to have a look around, though; I took a river cruise, walked through a few parts of the city and indulged in a bit of outlet shopping. I also sought out a local fast-food chain (Red Rooster, specialising in grilled chicken).

Given that I’d flown this far across the globe when going from London to Melbourne (it’s roughly 20 hours in the sky) I also decided to spend a few days in Singapore on the way back. For the most part I focused on spending time with family, though I also managed to find some time to flip through some of the IJCAI proceedings.

General Thoughts


It’s surprisingly difficult to leave work behind…

This is certainly the first time I’ve had a two-week break since I started full-time at Palantir. (I had some things I decided I would clear out last year around the Christmas and New Year period, so no long break for me then.) That said, rather unsurprisingly in hindsight attending and presenting at IJCAI was easily just as intellectually stimulating and demanding as my regular work, so it felt more like a one-week break. Still, it was quite a dramatic slowdown.

I think the break worked well. It came at a time just after I launched some fairly hefty deliverables; knowing that I was leaving for two weeks, I had been pushing somewhat hard to get things out before I left. I hadn’t been back home for 11 months. I was initially a little apprehensive about going off for two consecutive weeks, though the logistics of course made sense, and I don’t think I have major regrets, at least not yet!