Miten kannattaisi toteuttaa seuraavan ongelman ratkaiseva ohjelma? Jos keksit ratkaisun todistukseen ilman algoritmia, sekin kelpaa.
On annettu 8x8-lauta {(i,j), 1 <= i,j <= 8}. Siihen laitetaan 1x3 ja 3x1 laattoja siten, että yksi ruutu jää peittämättä ja laatat eivät peitä toisiaan. Missä kohdassa peittämätön ruutu voi olla?
Jaska kirjoitti:
Jos keksit ratkaisun todistukseen ilman algoritmia, sekin kelpaa.
En tiä todistuksesta, mutta kynää ja paperia käyttäen sain ekalla yrityksellä ratkaisun.
| | | | | | | |
| | | | | | | |
| | | | | | | |
- - - | | - - -
- - - | | - - -
| | | | | x | |
| | | - - - | |
| | | - - - | |
Editoin että sähän haluut kaikki mahdolliset ratkaisut?
pipo kirjoitti:
Editoin että sähän haluut kaikki mahdolliset ratkaisut?
Jeps. Yksittäisratkaisun minäkin löysin.
Laudalle jää väkisinkin vähintään yksi tyhjä kolo. Jotta kolosia olisi tasan yksi, täytyy palikat asetella näin:
| | - - -
| | - - -
| | x | |
- - - | |
- - - | |
Joku matemaatikko voi tämän kai jakojäännöksellä tms osoittaa, mutta noinhan se on.
Lopun laudan täyttämiseen on muutama vaihtoehto, mutta se ei ole oleellista. Yllä oleva 5x5 lauta sijoitetaan yhteen kohtaan* 8x8 lautaa ja loput täytetään annetuilla laatoilla. Sitten käännellään lautaa kolme kertaa ja näin löytyi neljä ratkaisua.
Jos joku tekee tästä koodin käyttämättä graafista ratkaisua -vektoreita tms- niin muakin kiinnostaisi nähdä se.
*mahtuu muuten vain siten että pieni lauta on isomman laudan kulmassa.
Numeroidaan laudan ruudut yhdestä kolmeen seuraavalla tavalla.
12312312 31231231 23123123 12312312 31231231 23123123 12312312 31231231
Nyt jokaisen palikan sijoitus peittää kolme eri numeroa. Tämän näkee siitä, että joka rivillä ja sarakkeella on aina kahden saman numeron välissä kaksi muuta eri numeroa. Näin ollen 21:n palikan asettamisen jälkeen meillä on yksi ykkönen peittämättä.
Toisaalta laudan voi numeroida näin.
21321321 13213213 32132132 21321321 13213213 32132132 21321321 13213213
Sama argumentti kertoo, että taas jää yksi ykkönen peittämättä.
Vain sellaiset kohdat, mitkä on merkitty ykkösellä molemmissa taulukoissa voidaan jättää tyhjäksi jossakin ratkaisussa. Jatko jätetään lukijalle.
Jos et kaipaa mitään hienoa algoritmia, niin kaikkien vaihtoehtojen kokeilu kertoo vastauksen nopeasti, kun ruudukko on niin pieni.
Ohjelmani mukaan ratkaisuja on 1424 - onko joku muu saanut saman tuloksen?
Mahdollisista tyhjistä paikoista ohjelmani on ainakin samaa mieltä P. Karjalaisen kanssa.
Tällaista tehtävää ratkaistessa yksinkertaisella ohjelmalla käytän mieluummin vaikkapa Pythonin sanakirjaa kuin taulukoita. Ei tarvitse niin hikoilla, että missä ne laidat ovat :)
Onhan tämä hidas! Menee useita sekunteja. Vaan jaksaako sitä välittää kerran ajettavan ohjelman nopeudesta?
squares = [(x,y) for x in range(1, 9) for y in range(1, 9)]
initial = dict(zip(squares, '.'*64))
empty, hole = ".x"
horiz, vert = 0, 1
sol_count = 0
def places(where, oriented):
"Find the three places that a piece will fill."
x, y = where
if oriented == horiz: return [(x,y), (x+1,y), (x+2,y)]
else: return [(x,y), (x,y+1), (x,y+2)]
def put_piece(board, where, oriented):
"Add a piece on board and return True if possible. Otherwise False."
mark = "-|"[oriented]
pls = places(where, oriented)
# are the places empty and on the board?
for p in pls:
if p not in board or board[p] != empty: return False
# they are
for p in pls:
board[p] = mark
return True
def rem_piece(board, where, oriented):
"Remove a piece from board. Assumes we put it there correctly before."
for p in places(where, oriented):
board[p] = empty
def next_location(x, y):
"Next place on board or None if at end."
if (x,y) == (8,8): return None
elif x == 8: return (1,y+1)
else: return (x+1,y)
def print_board(board):
"Print the board."
global sol_count
sol_count += 1
place = (1,1)
brd = "\n"
while place is not None:
brd += board[place]
brd += " \n"[place[0]==8]
place = next_location(*place)
print brd
def depth_first_search(board, had_hole, placed, curr_loc):
"Use the depth first search, Luke!"
# had_hole indicates whether we've skipped over one spot already
# placed tells us how many pieces we've placed; 21 and it's solved
# curr_loc iterates from the first row to the right one step at a time
if placed == 21:
print_board(board)
return
# an empty place is guaranteed before we fall off the board
# when there are less than 21 pieces placed
while board[curr_loc] != empty:
curr_loc = next_location(*curr_loc)
for oriented in [horiz, vert]:
if put_piece(board, curr_loc, oriented):
depth_first_search(board, had_hole, placed + 1,
next_location(*curr_loc))
rem_piece(board, curr_loc, oriented)
# a solution must have only one hole in it
if not had_hole:
board[curr_loc] = hole
depth_first_search(board, True, placed, next_location(*curr_loc))
board[curr_loc] = empty
return
if __name__ == '__main__':
depth_first_search(initial, False, 0, (1,1))
print "Found %d solutions" % sol_countTulee 1424 tälläkin.
Tuossa on minun ohjelmani:
#include <stdio.h>
int taulu[8][8];
int maara = 0;
void piirra(void) {
int i, j;
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
printf("%c", taulu[i][j]);
}
printf("\n");
}
printf("\n");
}
void haku(int y, int x, int n) {
if (y == 8) {
if (n == 21) {
maara++;
piirra();
}
return;
}
if (x == 8) {
haku(y+1, 0, n);
return;
}
if (taulu[y][x]) {
haku(y, x+1, n);
return;
}
if (x < 6 && !taulu[y][x+1] && !taulu[y][x+2]) {
taulu[y][x] = taulu[y][x+1] = taulu[y][x+2] = '-';
haku(y, x+3, n+1);
taulu[y][x] = taulu[y][x+1] = taulu[y][x+2] = 0;
}
if (y < 6 && !taulu[y+1][x] && !taulu[y+2][x]) {
taulu[y][x] = taulu[y+1][x] = taulu[y+2][x] = '|';
haku(y, x+1, n+1);
taulu[y][x] = taulu[y+1][x] = taulu[y+2][x] = 0;
}
}
int main(void) {
int i, j;
for (i = 0; i < 8; i++) {
for (j = 0; j < 8; j++) {
taulu[i][j] = ' ';
haku(0, 0, 0);
taulu[i][j] = 0;
}
}
printf("%i\n", maara);
}Ohjelmaa voisi vielä nopeuttaa ottamalla huomioon ruudukon symmetriat.
Hetkinen. Siis 1424 ratkaisua. Eikös 8x8 laudalla ole vain 64 ruutua, jossa se puuttumaton ruutu voi olla? Ja eikös ne paikat löydy niistä kohdista, joissa Pekka Karjalaisen antamissa numeroruudukoissa ole ykköset kohdikkain?
Siis on 1424 eri 1x3- ja 3x1-laattojen sijoitustapaa, joissa koko ruudukko on täytetty yhtä ruutua lukuun ottamatta. Laskimme siis saman tien vähän enemmän kuin alun perin kysyit.
Ah. Niinpä tietysti.
Mun mielestä neljä oli ihan sopivasti d8)
Saavatko laatat ylittää laudan reunan? Jos saavat, niin eihän laudan kasvamisella olisi mitään väliä(?)
Eikös se peittämätön ruutu voi olla missä tahansa kohtaa lautaa.
teksturi kirjoitti:
Eikös se peittämätön ruutu voi olla missä tahansa kohtaa lautaa.
Voi, mutta ei niin, että sitten olisi ainoastaan yksi peittämätön ruutu.
Jos numeroargumenttini on pätevä, niin seuraavanlaiset neliölaudat voivat sisältää koloja merkityissä kohdissa. Kolmella jaollinen laidan pituus johtaa siihen, että koloa ei voi olla ollekaan, joten ne on jätetty tästä pois. Laudalla kokoa 2x2 ei voi olla yhtään palikkaa, ja 1x1 on jätetty itse kunkin mietittäväksi.
x . . x . . . . . . . . x . . x . . . . . . . . . . . . x . . . . . . . . . . . . x . . x . . x . . . . . . . . . . . . . . x . . x . . x . . . . . . . . . . . . . . x . . x . . x . . . . . . . . . . . . . . . . . . x . . x . . . . . . . . . . . . . . . . . . . . x . . x . . . . . . . . . . . . . . . . . . x . . x . . x . . x . . . . . . . . . . . . . . . . . . . . x . . x . . x . . x . . . . . . . . . . . . . . . . . . . . x . . x . . x . . x . . . . . . . . . . . . . . . . . . . . x . . x . . x . . x
Näyttäisi siis, että mahdolliset kolot ovat harvan ristikon muotoisessa kuviossa, jonka keskipiste on samassa kohdassa kuin laudan keskipiste. Joku fiksu ja ahkera voisi miettiä, mitä tapahtuu suorakulmaisilla laudoilla eli kokoa mxn olevilla, missä m != n.
Noita varten tein pienen ohjelman. Toivottavasti meni oikein ;-)
(Pienet laudat voi ainakin varmistaa itsekin kokeilemalla.)
pipo kirjoitti:
| | - - -
| | - - -
| | x | |
- - - | |
- - - | |
Pekka Karjalainen kirjoitti:
. . . . . . . .
. . . . . . . .
. . x . . x . .
. . . . . . . .
. . . . . . . .
. . x . . x . .
. . . . . . . .
. . . . . . . .
Kiitos tulkinnasta! Edelleen neljä ratkaisua(?) Noita ruudukoita on sangen antoisaa kirjoitella.
| | - - - . . .
| | - - - . . .
| | x | | x . .
- - - | | . . .
- - - | | . . .
. . x . . x . .
. . . . . . . .
. . . . . . . .
Käänsin Antti Laaksosen ohjelman lcc-win32 kääntäjälläni (1.1sec). Lisäsin loppuun pysäytyksen nähdäkseni lopputuloksen. Ongelma muistuttaa hiukan kauan sitten käymieni Fortran-kurssien shakkiruudukkotehtäviä. Aion tutkia ohjelman toimintaa debuggerin avulla. JVM
Aihe on jo aika vanha, joten et voi enää vastata siihen.