Göm menyn

Japanska pyssel

Detta projekt går ut på att skriva program som genererar eller löser olika typer av pyssel. Projektet kallas Japanska pyssel eftersom många av de problem som kan komma ifråga har sitt ursprung i Japan, eller åtminstone har givits japanska namn. Det finns ett flertal olika pyssel som är lämpliga och här ges några exempel.

Nonogram

De pyssel som här kallas nonogram är även kända under många andra namn: Griddler, Hanjie, Paint by numbers. Ursprunget kan spåras till Japan, men de har också publicerats i engelska dagstidningar under flera år. Idén bakom nonogram är mycket enkel. Du ska bygga upp en bild genom att fylla i rutorna i ett rutnät. Siffror som står till höger och under rutnätet anger hur många rutor som ska vara ifyllda i varje rad respektive kolumn. Nedanstående nonogram får tjäna som exempel.

Siffrorna ska tolkas så att på den första raden ska fyra rutor vara ifyllda. På den tredje raden ska tre sekvenser om vardera två rutor vara ifyllda, naturligtvis med minst en tom ruta mellan sig. På samma sätt gäller förden femte kolumnen att två sekvenser om sju respektive två rutor ska vara ifyllda i ordning uppifrån och ner. Lösningen på detta enkla nonogram blir helt enkelt:

En lämplig startpunkt för att lösa nonogrammet här ovan kan vara raderna i mitten. De ska uppenbarligen vara helt ifyllda. På samma sätt kan man fylla i de mittersta kolumnerna. Två sekvenser om totalt nio rutor ska fyllas i och det kan man bara göra på ett sätt i en kolumn med tio platser. Under själva lösandet av nonogrammet brukar man markera rutor som man vet ska vara tomma med en liten prick.

Läs igenom våra tips om hur man löser nonogram innan ni börjar fundera över hur ni ska lösa problemet. Använd gärna något av våra exempelnonogram som första testfall.

Följande länkar ger mer information om nonogram:

  • Acticity Workshop förklarar vad nonogram är, ger tips på hur man löser dem för hand samt erbjuder några exempel.
  • Stephen Simpson erbjuder bland annat en nonogramlösare on-line.
  • Griddlers.net erbjuder ett stort antal nonogrampyssel on-line.
  • Wikipedia har en intressant artikel som förklarar historien bakom nonogram och ger exempel på lösningstekniker.
  • Puzzle Museum informerar om nonogrammens historia och lösningstekniker.
  • Hanjie är ett alternativt namn på samma typ av pyssel.

Slitherlink

Pysslet Slitherlink går ut på att koppla samman olika punkter i ett rutnät. När man är färdig ska det ha uppstått en enda sammanhållen kedja av punkter som dessutom är sluten. Till sin hjälp har man ett antal siffror mellan punkterna som anger hur många (0-3) linjer som ska finnas runt den aktuella rutan.

  • Puzzle Loop har ett antal slitherlink-pyssel som man kan pröva att lösa on-line.
  • Puzzle Club har ett antal slitherlink-pyssel.

Sudoku

Fenomenet Sudoku torde inte vara obekant för oss svenskar. Detta pyssel har på senare år blivit mycket populärt och förekommer fortfarande i flera tidningar. Utgångspunkten är att man ska fylla i ett rutnät om 9x9 rutor så att siffrorna 1-9 förekommer exakt en gång per rad, per kolumn och inom de nio 3x3-regioner som spelplanen är indelad i.

För det här projektets syfte är Sudoku egentligen alldeles för lätt. Att skriva ett program som löser ett givet sudokupyssel kanske låter svårt till en början, men det visar sig att det blir mindre omfattande än för övriga pyssel som exemplifierats ovan. Om man vill arbeta med sudokupyssel kommer vi därför att kräva att man gör något mer än enbart löser dem. Man kan t.ex. lösa lite mer komplicerade sudokupyssel som har extrakrav, generera sudokupyssel, lösa sudoku och bedöma svårighetsgraden eller lägga på ett grafiskt gränssnitt.

  • Sudoku.com innehåller en beskrivning av problemet samt ger några exempel.
  • Web Sudoku erbjuder ett stort antal pyssel i olika svårighetsgrader.

Mosaik

Mosaik-pyssel består av en tom matris där vissa rutor innehåller något av talen 0-9. Målet är att fylla i vissa av rutorna och den enda regeln är att talen anger hur många av de omgivande rutorna (inklusive rutan med siffran i) som ska vara ifyllda.

Hur man löser problemet

Gemensamt för de flesta av dessa pyssel är att de, om man skrapar lite på ytan, visar sig bottna i grundläggande diskretmatematiska principer. De lämpar sig alltså utmärkt för en C- eller D-student att sätta tänderna i. Det finns två huvudsakliga frågor som man bör ställa sig i början av projektet och som behöver besvaras i specifikationen:

  • Hur kan man utforma en algoritm som löser ett godtyckligt pyssel av en viss typ? (Det kan vara en god idé att börja med att lösa några pyssel för hand för att få en känsla för hur man gör överhuvudtaget.)
  • Hur ska man representera pysslet i datorn? (Vilka abstrakta datatyper och primitiva funktioner behövs?)

Projektidé av Peter Dalenius 2002.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2011-11-08