Program "Maze Generator"

Rajah 1: Maze Generator, Compute! December 1981

Lagi sekali, kita selongkar majalah Compute! di www.archive.org. Kali ini kita lihat isu 19, Disember 1981.  Ada suatu artikel di mukasurat 54 serta program yang menarik perhatian saya iaitu "Maze Generator".

Ianya ialah mengenai suatu algotrima pendek yang mampu menghasilkan sebuah maze secara rawak. Perinciannya meliputi komputer Commodore Pet (Microsoft BASIC) dan Atari 400/800. Contoh maze yang terhasil adalah seperti dalam Rajah 2.

Rajah 2: Contoh Maze

Rajah 3: Carta Alir "Maze Generator"

Algoritmanya adalah seperti dalam Rajah 3. Asasnya, maze dibina di dalam sebuah medan yang dinamakan "Background field" (BF). Ia terdiri daripada baris-baris (Y) yang jumlahnya ganjil. Setiap baris pula terbina dengan sel-sel (X) yang juga jumlahnya ganjil. Ianya membentuk jajaran (array) 2 dimensi X*Y; dengan koordinat (X,Y) = (0,0) terletak di penjuru atas-kanan.

"Maze Generator"

Pembinaan maze dimulakan dengan meletak penanda khas di sel (1,1). Kemudian nombor rawak 0 - 3 dipilih untuk menentukan arah pergerakan ke sel baharu (B). Sel baharu ini terletak selang satu sel daripada sel asal (A). Sel (penghadang) yang berada di antara dua sel tadi -- (A) dan (B) -- dipadam. Sekarang sel (B) menjadi sel (A); dan proses tadi diulang untuk mencari sel (b) yang baru; sehingga ketemu "jalan buntu".

Jika kebuntuan terjadi kurang daripada lima langkah, laluan yang telah terlakar akan diunduri sehingga bertemu dengan sel yang belum dipadam. Dari situ laluan baru akan dilakarkan dengan mengulangi lagi langkah-langkah tersebut di atas.

Program versi Microsoft BASIC

Berikut ialah program yang ditulis dengen Microsoft BASIC untuk Commodore Pet:

Pentomino versi Python

Ini adalah beberapa rakaman video (youtube) yang saya buat bagi program 'PENTOMINOS' yang saya tulis semula dalam Python. Saja untuk suka-suka. Video yang pertama ini ialah untuk puzzle bersaiz 3x20 sel.

3x20 sel

Program asal adalah seperti yang dibincangkan dalam pos bertajuk "Pentominos: A Puzzle-Solving Program | The BASIC Programs". Program asal ditulis dalam bahasa BASIC untuk mikrokomputer Commodore. Versi Python ini adalah lebih-kurang berdasarkan program BASIC yang asal.

Algoritma utamanya ialah seperti berikut:

slotno = 0
while slotno < 12:
full = get_next_empty_spot()
if full:
end
while not all_pieces_tried( slotno ):
p = get_untried_piece( slotno )
if p==-1: break
fit = try_piece( p, slotno )
if fit:
place_piece( p, nextrot, slotno )
pieceno[slotno] = p
rotation[slotno] = nextrot
slotno = slotno + 1
break
else:
tried[slotno][p] = True
if not fit:
reset_unused_pieces( slotno )
slotno = slotno - 1
if slotno<0: slotno="0</font">
undraw_piece( slotno )

Berikut ini adalah rakaman-rakaman video untuk puzzle bersaiz 4x15, 5x12 dan 6x10.

4x15 sel

5x12 sel

6x10 sel