Sunday 7 February 2010

Sudoku solver in Python (part one)

I enjoy playing around with programming. Python is a good language for ease of use and built in features and readability. I'd like to see more type safety, though - Python won't complain if you try sending a list to something expecting a number. It will just crash, instead. (In contrast, C and C++ will give compiler errors before trying to run).

In any case, solving a sudoku is a fairly interesting task to tackle. Partly because there are many ways to try. I could, for example, use strictly logical methods as I would with a pen and paper. While it would easily be possible to to this, listing every method and working out exactly how to do this is a daunting task.

The other method is brute-force. Try every number in every square and see which one fits.

In this case, the solution lies somewhere between the two. The brute force solution, for a 3 x 3 grid has 60 empty squares, with a possible total of 9 values in each. This gives a total of around 1,797,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possibilities. A computer able to check a trillion possibilities every second wouldn't even scratch the surface on trying all of them if it ran from the start of the Universe to now!

So we use logical rules to narrow these down.

Let us start by creating an object that represents a Sudoku grid.


class Sudokugrid:
  def __init__(self,major_boxes):
    self.order = major_boxes
    self.size = self.order*self.order
    self.magnitude = self.order*self.order*self.order
    self.grid = []
    for column in range(self.size):
      row = []
      for box in range(self.size):
        row.append(0)
        self.grid.append(copy.deepcopy(row))
    self.conversion = " 1234567890ABCDEFGHIJKLMNOPQRTUVWXYZabcdefghijklmnopqrtuvwxyz@#"
    self.errorbox = "!"
    self.boxhighlight = "*"
    self.stepthrough = None


There are variants on Sudoku. Normally we see 9 x 9, but 16 x 16 and 4 x 4 variants are also occasionally seen. I tend to refer to this as the "order" of the puzzle. A 16 x 16 puzzle has 4 groups of 4 boxes each, and so is order 4. The standard puzzle is of order 3. This __init__ function creates a grid by making a list of lists. This allows any box to be accessed via self.grid[column][row].

The "conversion" variable is used for displaying on screen. 16 x 16 puzzles use letters to avoid having to use multidigit numbers. As it happens, I want to write using numbers throughout (it's safer that way, I believe, and I can use the number 0 to indicate an empty box), but display using letters and numbers. The conversion has enough characters for an eighth order grid.


Now we have a grid, and we assign values to it. We can start building our solver.

Thursday 4 February 2010

Valencia testing

It's far too early to draw any conclusions on which teams are fastest. Ferrari look strong, with 1 and 2 on the timing sheets, but there are many reasons apart from raw pace that could do this.

Most interesting to me, was in the run up to the test, Fernando Alonso made some very guarded comments regarding testing. I initially figured that he was expecting a learning curve with the car to some extent, or something like that and was covering himself for a poor performance in testing. Topping the timing sheets, however, Alonso's comments may instead have been indicating something else: that Ferrari aren't confident.

There is little to be told about which teams are fastest. It is quite interesting to see how closely matched teammates are, though.

It appears Sauber have very well matched drivers, which is good for them. Torro Rosso on the other hand, may have problems, as their drivers were over a second apart.

Best matched driver pairs
Sauber: 0.038
Ferrari: 0.252
Williams: 0.292
Mercedes: 0.461
Renault: 0.671
McLaren: 0.695
Torro Rosso: 1.245
Worst matched.

It's worth mentioning that all those splits are pretty large. I still stand by my predictions from before testing.

Tuesday 2 February 2010

Three golden rules for good games to follow

Or: How to turn Assassin's Creed from an awesome game to Game of the Century.

One: Don't force the story on the player. I don't care how intricately crafted the characters are, how deep and thrilling the plot is, or how much you paid for voice actors. Sometimes I just want to play the game. (Typically, I'll want to play a second time and already know the story.)

I won't accept that the storyline is a necessary part of gameplay either (except for the RPG genre). If a game is not good enough to stand up purely on the game mechanics, it's not a good game. If you have put so much effort into the story, you can't bear the thought of players missing the storyline, then write a book/make a TV series/film.

Unskippable cutscenes are the most obvious and most common version of this, but it is also possible to achieve by not allowing the player to move on until they discover some plot point. RPG's are allowed to do this.

Everything else: if you're insistent on a player knowing a certain piece of story, mark the place to find it on the map, thank you. Cutscenes in and of themselves are not too bad, but keep them concise. It's much better from the players point of view if we find out the information by playing ourselves, but not always possible.

Notable offenders: Assassin's Creed
Surprisingly good: Knights of the Old Republic (as long as you get the bit about the Star Maps, you can play this virtually ignoring the storyline.)

Two: Don't be repetitive. Management sims are exempt from this. This is about not forcing the player to do the same thing over and over. There are many ways this can come about.

The simplest is save-points. Everyone has played a game where it saves, then has a cutscene, then a hard boss battle. Every failed attempt at the boss battle replays the cutscene.

Assassin's Creed is odd here, in that it does this well for pickpocketing (retrying after a failure skips the dialogue) but badly for informants. Every time you fail, you have to hear the same dialogue telling you why he needs you to do whatever-he's-asking-you-to-do, while I stand thinking "I know, I know, let me get on with it!"

A more subtle variant is found on the "save citizen" challenges. After every one the game makes you stand around and listen to the saved citizen thanking you, all the while you should be running from the scene. Then, the reward (scholars, or vigilantes) are focussed on before you can start fleeing. The whole process takes almost a minute. Particularly annoying here is making a big point of showing you the scholars/vigilantes you won, since they appear on the map.

This is also an excellent reason to include fast-travel between important points on the map.

Notable offender: Assassin's Creed
Surprisingly good: Half-Life 2

Three: Let the player dictate the pace. Some players like blasting through levels as fast as possible, others like to go slowly and take it all in. The latter do badly at racing games. Assassin's Creed actually gets this very right. While exploring, you have four speeds available to you, depending on whether you're sneaking up on a guard or running like hell from one. However, as Desmond you are limited to walking slowly around the office, mostly unable to interact with things.

Notable offender: Assassin's Creed (as Desmond)
Suprisingly good: Assassin's Creed (as Altiar)

Zero: Keep the player in control. In essence, all the other rules on the list come down to this. We play games because we like to play. Points where the game wrests control from the player are frustrating and totally break immersion (since we're suddenly aware of the limitations of the medium).

This is a really broad rule applying to all sorts of things. For example: in Assassin's Creed there are drunk who will, given the opportunity, wallop the player one and beggars who will just harass you.

This isn't too bad, except there's nothing you can do about it. You lose health (or synch) for retaliating. Even worse is that the drunks have a horrible tendency to totally blow your cover. Simple things that could be done about this are: let us give a few coins to the beggars; if a soldier spots a drunk taking a swing, have him come over and arrest the drunk. It would be really satisfying to see the soldiers on your side for once.

Notable offender: Assassin's Creed


So come on, designers. When are we going to see an end to needlessly poor games?

Monday 1 February 2010

My favourite things: Order of the Stick

Medium: Webcomic
Author: Richard Burlew
Updates: Irregular
Style: Stickmen, plot heavy.

Order of the Stick a stickman comic about a party of six adventurers in the D&D Universe. It starts out as a basic gag-a-day, mostly parodying Dungeons and Dragons. However, beneath the humour there is a very finely woven plot backed up
by excellent writing. The main characters all get developed adding to the depth of the jokes. The plot gains more urgency around strips 10
0-200 and drives the comic compellingly along.

Order of the Stick doesn't just to funny very well. The comedy is an excellent foil to the occasional tragedy, and named character deaths are always beautifully played. Near the end of the "Don't Split The Party" arc, an superb look at the nature of good and evil gets thrown in. These breaks aren't jarring, though, since they are worked so well into the plot.

Cast:
Order of the Stick:
Roy Greenhilt: Leader. A master fighter but stereotypically intelligent. He has taken on his father's oath to avenge himself on Xykon, the evil sorcerer. He is brave and pragmatic. Although he doesn't always make the best choices initially, he usually gets it right in the end.

Haley Starshine: Second in command. A feisty rogue who's very very
introvert. Expert at stealth and marksmanship, but tends to get overpowered in a straight fight.

Elan: A bard who mostly plays the incompetent buffoon for comic relief. He is very genre aware and able to use storytelling conventions to his advantage. He is extremely child-like, and it takes some time before the whole party accepts him.

Durkon Thundershield: Dwarf and cleric to Thor. While playing on many Dwarf stereotypes, Durkon is also the most morally upstanding and aware. He is pious, but not in an annoying, preachy way (to the reader anyway). He shows very great wisdom, and often opts for the diplomatic solution. Durkon has been exiled from his homelands.

Vaarsuvius: An androgynous elven wizard. The lack of known gender for V is a running joke (I tend to use the feminine pronouns, but masculine seems more common). V is powerful and skilled, but somewhat arrogant about it. She tries to view the world as an inherently ordered place and can be very frustrated. She is very close to Haley in the backstory. V and Belkar sniping each other is also the source of many many many moments of brilliance.

Belkar Bitterleaf: Omnicidal maniac. Oh, and a hobbit. Crazily powerful with his twin daggers, Belkar is happiest eating something, or killing something, although the party keep him in check. Thus far, Belkar is the least developed character.

Villains:
Xykon: A sorcerer who, in death, bound his soul to a phylactery and lives on as a lich. He seeks to dominate the world by taking control of one of five mystical gates (his attempts have so far mostly resulted in the destruction of said gate...if too many gates get destroyed, the Universe ends, though. So that's quite bad). Xykon thinks nothing of the lives of others, gets bored easily and is viciously powerful in combat. He is so stylish about being evil, though.

Redcloak: Guardian of Xykon's phylactery. Redcloak is a goblic cleric who seeks to destroy all humans. He is subervient to Xykon, but uses his better organised nature and longer attention span to maintain some control over him.

Monster in the Dark: Unknown monster enshrouded at all times in a magical darkness. We only ever see his yellow eyes. Very child-like, really powerful, easily distracted. I'm not totally convinced of the evilness of this beast though. We wait and see.


Check OotS out. You won't regret it!