Qbasicnews.com
September 20, 2021, 01:30:22 AM
 Pages: [1]
 Author Topic: Write a program to solve this puzzle.  (Read 8266 times)
yetifoot
Ancient Guru

Posts: 575

 « on: May 31, 2006, 11:00:22 PM »

I found the following puzzle a bit of a head-scratcher, but got there in the end.  What i'm interested in though is a computer program to solve it.

I think that it may be some kind of exact cover problem, that could be solved by Knuths DLX.  Maybe it isn't though.  I'm sure good use of Boolean Logic is the way to solve it though.

I'd love to see anyone's program.  I started one but it was a bit brute-force, so i'm going to rethink.

There will be no time-limits, or even winners to this challenge, but you do get a smug face if you can do it, and that's what counts!

Code:
Neighbours

Five people of different nationality live in a row of five houses of different colour. Each person prefers a different beverage, smokes a different brand of cigar and keeps a different kind of animal. Can you figure out who owns the fish?

1. The Brit lives in the Red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The Green house is on the left of the White house.
5. The owner of the Green house drinks coffee.
6. The person who smokes Pall Mall rears birds.
7. The owner of the Yellow house smokes Dunhill.
8. The man living in the centre house drinks milk.
9. The Norwegian lives in the first house.
10. The man who smokes Blends lives next to the man who keeps cats.
11. The man who keeps horses lives next to the man who smokes Dunhill.
12. The man who smokes Blue Master drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the Blue house.
15. The man who smokes Blends has a neighbour who drinks water.

Who owns the fish?

The German owns the fish (I hope!)
 Logged

EVEN MEN OF STEEL RUST.
Moneo
Na_th_an

Posts: 1971

 « Reply #1 on: May 31, 2006, 11:14:33 PM »

Back in 1961, when I was a programmer trainee attending the Basic Computing course at IBM in NY, they gave us this same puzzle to work out manually. I finally figured it out, but I hated it. I still hate it. But, I never thought of programming it --- hummm.
*****
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #2 on: May 31, 2006, 11:25:44 PM »

Well it all depends.

I could just do PRINT [the answer] or I could take each string and have it spit out the answer....

EDIT:

Code:
house:  unknown - unknown - unknown - unknown - unknown
nation: unknown - unknown - unknown - unknown - unknown
pet:    unknown - unknown - unknown - unknown - unknown
drink:  unknown - unknown - unknown - unknown - unknown
cigar:  unknown - unknown - unknown - unknown - unknown

8. The man living in the centre house drinks milk.
9. The Norwegian lives in the first house.

house:  unknown   - unknown - unknown - unknown - unknown
nation: norwegian - unknown - unknown - unknown - unknown
pet:    unknown   - unknown - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - unknown - unknown
cigar:  unknown   - unknown - unknown - unknown - unknown

14. The Norwegian lives next to the Blue house.

house:  unknown   - blue    - unknown - unknown - unknown
nation: norwegian - unknown - unknown - unknown - unknown
pet:    unknown   - unknown - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - unknown - unknown
cigar:  unknown   - unknown - unknown - unknown - unknown

4. The Green house is on the left of the White house.
green <- white
5. The owner of the Green house drinks coffee.

house:  unknown   - blue    - unknown - green   - white
nation: norwegian - unknown - unknown - unknown - unknown
pet:    unknown   - unknown - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - coffee  - unknown
cigar:  unknown   - unknown - unknown - unknown - unknown

1. The Brit lives in the Red house.

house:  yellow    - blue    - red     - green   - white
nation: norwegian - unknown - brit    - unknown - unknown
pet:    unknown   - unknown - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - coffee  - unknown
cigar:  unknown   - unknown - unknown - unknown - unknown

7. The owner of the Yellow house smokes Dunhill.
11. The man who keeps horses lives next to the man who smokes Dunhill.

house:  yellow    - blue    - red     - green   - white
nation: norwegian - unknown - brit    - unknown - unknown
pet:    unknown   - horses  - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - coffee  - unknown
cigar:  dunhill   - unknown - unknown - unknown - unknown

15. The man who smokes Blends has a neighbour who drinks water.

house:  yellow    - blue    - red     - green   - white
nation: norwegian - unknown - brit    - unknown - unknown
pet:    unknown   - horses  - unknown - unknown - unknown
drink:  unknown   - unknown - milk    - coffee  - unknown
cigar:  dunhill   - blends? - blends? - blends? - unknown

3. The Dane drinks tea.

house:  yellow    - blue    - red     - green   - white
nation: norwegian - unknown - brit    - unknown - unknown
pet:    unknown   - horses  - unknown - unknown - unknown
drink:  not tea   - unknown - milk    - coffee  - unknown
cigar:  dunhill   - blends? - blends? - blends? - unknown

house:  yellow     - blue    - red     - green   - white
nation: norwegian  - unknown - brit    - unknown - unknown
pet:    unknown    - horses  - unknown - unknown - unknown
drink:  water/beer - tea?    - milk    - coffee  - tea?
cigar:  dunhill    - blends? - blends? - blends? - unknown

12. The man who smokes Blue Master drinks beer.

house:  yellow    - blue     - red     - green   - white
nation: norwegian - unknown  - brit    - unknown - unknown
pet:    unknown   - horses   - unknown - unknown - unknown
drink:  water     - tea/beer - milk    - coffee  - tea/beer
cigar:  dunhill   - blends?  - blends? - blends? - unknown

house:  yellow    - blue   - red     - green   - white
nation: norwegian - dane   - brit    - unknown - unknown
pet:    unknown   - horses - unknown - unknown - unknown
drink:  water     - tea    - milk    - coffee  - beer
cigar:  dunhill   - blends - unknown - unknown - blue master

13. The German smokes Prince.

house:  yellow    - blue   - red       - green   - white
nation: norwegian - dane   - brit      - german  - unknown
pet:    unknown   - horses - unknown   - unknown - unknown
drink:  water     - tea    - milk      - coffee  - beer
cigar:  dunhill   - blends - pall mall - prince - blue master

6. The person who smokes Pall Mall rears birds.
10. The man who smokes Blends lives next to the man who keeps cats.

house:  yellow    - blue   - red       - green   - white
nation: norwegian - dane   - brit      - german  - unknown
pet:    cats      - horses - birds     - unknown - unknown
drink:  water     - tea    - milk      - coffee  - beer
cigar:  dunhill   - blends - pall mall - prince - blue master

2. The Swede keeps dogs as pets.

house:  yellow    - blue   - red       - green   - white
nation: norwegian - dane   - brit      - german  - swede
pet:    cats      - horses - birds     - unknown - dogs
drink:  water     - tea    - milk      - coffee  - beer
cigar:  dunhill   - blends - pall mall - prince - blue master

-------------------------

house:  yellow    - blue    - red       - green   - white
nation: norwegian - dane    - brit      - german  - swede
pet:    cats      - horses  - birds     - FISH    - dogs
drink:  water     - tea     - milk      - coffee  - beer
cigar:  dunhill   - blends  - pall mall - prince  - blue master

EDITed for clarity.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
yetifoot
Ancient Guru

Posts: 575

 « Reply #3 on: June 01, 2006, 09:14:12 AM »

Thats great, but its not a program that solves the problem, merely one that relays your thought process.
 Logged

EVEN MEN OF STEEL RUST.
Ancient Guru

Posts: 671

 « Reply #4 on: June 01, 2006, 10:11:51 AM »

Quote from: "yetifoot"
Thats great, but its not a program that solves the problem, merely one that relays your thought process.
Is the brain not a big program?

Anywho, I suppose I *could* write a program to figure this out, but it's so much work...
 Logged
yetifoot
Ancient Guru

Posts: 575

 « Reply #5 on: June 01, 2006, 11:48:50 AM »

I've found a solver on the net, and it's actually a very small program.  I'll post it later if anyones interested.
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #6 on: June 02, 2006, 12:28:29 AM »

Well.... but then the question becomes what kind of logic the solver takes and in what form.

You could simply reduce the problem into true/false statements and by conversion finally get the answer, but then there are a variety of issues, such as:

* Should you manually convert into logic statements or put in English semantics rules to parse the words into logic?

* Should you limit the semantics rules to this particular problem set? (house per person)

* Should you limit it to the size of the problem set? (attribute size, person size.. or even a differentiation between attributes and persons...)
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
yetifoot
Ancient Guru

Posts: 575

 « Reply #7 on: June 02, 2006, 08:53:41 AM »

Quote from: "Agamemnus"
Well.... but then the question becomes what kind of logic the solver takes and in what form.

You could simply reduce the problem into true/false statements and by conversion finally get the answer, but then there are a variety of issues, such as:

* Should you manually convert into logic statements or put in English semantics rules to parse the words into logic?

* Should you limit the semantics rules to this particular problem set? (house per person)

* Should you limit it to the size of the problem set? (attribute size, person size.. or even a differentiation between attributes and persons...)

All this is your choice, as I said there are no rules.  The one i started coding was very specific, and very brute force, so i ditched it to research more elegant, generic solutions.  As an idea though, the source i have found on the net is about 30-40 lines of C++, and is *very* specific to this problem.
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #8 on: June 02, 2006, 04:09:32 PM »

EDIT: I am close to finishing. Here is my code so far. All I need to do is figure out how to make the code to do the last step...

EDIT2: The last step got subdivided into about 3 steps and I'm finishing up the last part of the first step now. Also made some design changes.

EDIT3: Tired. So tired..

EDIT4: So very close. Need to figure out just one last bit of code.

Code:

'Alright, so here is something that solves this specific problem, with 5 attributes and 5 men.
'Before making the program, I want to have "clean" data.
'First, let's transform the sentences into easy to parse logic. Before that, let's define the
'variables.
DECLARE SUB setNonAdjacentValuesToZero (matrix() AS BYTE, matrixloc() AS BYTE, i, j1, j2, position as BYTE)
DECLARE SUB qsort.linked.string.lowstart (array1() AS STRING, array2() AS INTEGER, amax AS INTEGER)
DECLARE FUNCTION findValue(ats() AS STRING, vtf AS STRING, a AS INTEGER, b AS INTEGER) AS INTEGER
DEFINT A-Z

DIM testarray1(0 TO 10)
DIM shared attrib = 6
DIM shared attribpos = 5
DIM attribString\$(0 TO attrib-1)

attribString\$(0) = "brit, swede, dane, norwegian, german"
attribString\$(1) = "red, green, yellow, white, blue"
attribString\$(2) = "dogs, cats, horses, birds, fish"
attribString\$(3) = "water, beer, tea, coffee, milk"
attribString\$(4) = "pall mall, blends, dunhill, prince, blue master"
attribString\$(5) = "leftmost, 2nd, center, 4th, rightmost"

DIM totAttrib: totAttrib = attrib*attribpos
DIM matrixAttrib\$(0 TO totAttrib-1), matrixAttrib2\$(0 TO totAttrib-1)
DIM tempAttrib\$(0 TO 1)

DIM matrix(0 TO attrib-1, 0 TO attribpos-1, 0 TO attrib-1, 0 TO attribpos-1) AS byte
for i = 0 to attrib-1
for j = 0 to attribpos-1
for k = 0 to attrib-1
for m = 0 to attribpos-1
matrix(i, j, k, m) = 1
next m, k, j, i

DIM matrixSolution(0 TO attrib-1, 0 TO attribpos-1) AS BYTE

DIM logicAmount = 15
DIM matrixloc(1 to logicAmount-1, 0 TO 6) AS BYTE, locpos
DIM val1(0 TO 1), val2(0 to 1)
DIM logic\$(0 to logicAmount-1)
logic\$(0)  = "brit = red"                  '"The brit lives in the red house"
logic\$(1)  = "swede = dogs"
logic\$(2)  = "dane = tea"                  'spatial strings must be
logic\$(3)  = "green = left of white"       'on the right side.
logic\$(4)  = "green = coffee"
logic\$(5)  = "pall mall = birds"
logic\$(6)  = "yellow = dunhill"
logic\$(7)  = "center = milk"
logic\$(8)  = "leftmost = norwegian"
logic\$(9)  = "blends = next to cats"
logic\$(10) = "horses = next to dunhill"
logic\$(11) = "blue master = beer"
logic\$(12) = "german = prince"
logic\$(13) = "norwegian = next to blue"
logic\$(14) = "blends = next to water"

'Now we transform the sentences into the matrix.
'Matrix starts by default having all 1's.
'values of matrix():
'0 = false
'1 = true
'
'As an example, take:
'matrix(0, 0, 1, 1) = 1      [0 = nationality, next 0 = brit, 1 = color, next value = color type] = true/false/unknown
'matrix(0, 0, 1, 1) = 1
'matrix(0, 0, 1, 2) = 0
'matrix(0, 0, 1, 3) = 0
'matrix(0, 0, 1, 4) = 0
'This means that the brit has either a red house or a green house.

'matrix(0, 0, 1, 0) = 0
'matrix(0, 0, 1, 1) = 1
'matrix(0, 0, 1, 2) = 1
'matrix(0, 0, 1, 3) = 1
'matrix(0, 0, 1, 4) = 1
'This means that the brit lives next to someone with a red house,
'or in other words, the brit definitely does not have a red house.
'we also must temporarily add that SOMEONE next to the Brit has
'a red house.
'matrixloc(n, 0) = 0 'nationality
'matrixloc(n, 1) = 0 'brit
'matrixloc(n, 2) = 1 'house
'matrixloc(n, 3) = 1 'red
'matrixloc(n, 4) = 2 'next to
'n = n + 1

'If we know, at some point in the future, the position of the brit,
'we can limit the color of non-nearby houses to exclude red:
'Let's say the brit is in the center house:
'
'matrix(5, 1, 1, 0) = 0      [5 = house, 2 = 2nd house, 1 = color, next value = color type]
'matrix(5, 1, 1, 1) = 1
'matrix(5, 1, 1, 2) = 1
'matrix(5, 1, 1, 3) = 1
'matrix(5, 1, 1, 4) = 1

'matrix(5, 5, 1, 0) = 0      [the 2nd house]
'matrix(5, 5, 1, 1) = 1
'matrix(5, 5, 1, 2) = 1
'matrix(5, 5, 1, 3) = 1
'matrix(5, 5, 1, 4) = 1

'Let's parse AttribString\$ into matrixAttrib\$().

k=0
FOR i = 0 TO attrib-1
startLoc = 1
FOR j = 0 TO attribpos-1
IF j < attrib-1 THEN
endLoc = INSTR(startLoc, attribString\$(i), ",")
ELSE
endLoc = LEN(attribString\$(i)) + 1
END IF
matrixAttrib\$(k) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(attribString\$(i), startLoc, endLoc-startLoc))))
matrixAttrib2\$(k) = matrixAttrib\$(k)
k = k + 1
startLoc = endLoc + 1
NEXT j, i

'To parse the logic sentences, we need a function that gives the
'attribute type [i] (e.g. house) and attribute position [j] (e.g. red)
'from the name of the attribute.

'Each attribute name corresponds to a value 0 through attrib^2-1,
'which become i = (value \ attribpos) and j = value - i * attribpos.
'We can use a B-tree to find the value given a sorted list.
'So, we must sort a duplicate of matrixAttrib\$(k) along with a value link LinksTo.

for i = 0 to totAttrib-1: LinksTo(i) = i: next i

'The structure of the sentence is:
'{spatial string set} [attribute name] = {spatial string set} [another attribute name]
'{spatial string set} = {"left of", "right of", "next to"}

'Let's parse the sentences now...

FOR i = 0 to logicAmount-1
'First, separate each word or phrase into two parts:
startLoc = 1
endLoc = INSTR(startLoc, logic\$(i), "=")
tempAttrib\$(0) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(logic\$(i), startLoc, endLoc-startLoc))))
tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(logic\$(i), endLoc+1))))
testLeft = INSTR(tempAttrib\$(1), "left of")
If testLeft THEN pos1 = 1: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testLeft+7))))
testRight = INSTR(tempAttrib\$(1), "right of")
If testRighth THEN pos1 = 2: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testRight+7))))
testNextTo = INSTR(tempAttrib\$(1), "next to")
If testNextTo THEN pos1 = 3: tempAttrib\$(1) = LCASE\$(LTRIM\$(RTRIM\$(MID\$(tempAttrib\$(1), testNextTo+7))))
for j = 0 to 1
value = linksTo(findValue(matrixAttrib2\$(), tempAttrib\$(j), 0, totAttrib-1))
val1(j) = value \ attribpos
val2(j) = value - val1(j)*attribpos
next j

SELECT CASE pos1
CASE 0
FOR k = 0 to attribpos-1
IF k <> val2(0) THEN
matrix(val1(0), k, val1(1), val2(1)) = 0
matrix(val1(1), val2(1), val1(0), k) = 0
'if i = 4 then print logic\$(i); val1(1); val2(1); val1(0); k
'if i = 4 then print logic\$(i); val1(0); k; val1(1); val2(1)
END IF
NEXT k

FOR k = 0 to attribpos-1
IF k <> val2(1) THEN
matrix(val1(0), val2(0), val1(1), k) = 0
matrix(val1(1), k, val1(0), val2(0)) = 0
END IF
NEXT k

CASE ELSE
FOR k = 0 to attribpos-1
IF k = val2(0) THEN
matrix(val1(0), val2(0), val1(1), val2(1)) = 0
matrix(val1(1), val2(1), val1(0), val2(0)) = 0
END IF
NEXT k

matrixloc(locpos, 0) = val1(0)
matrixloc(locpos, 1) = val2(0)
matrixloc(locpos, 2) = val1(1)
matrixloc(locpos, 3) = val2(1)
matrixloc(locpos, 4) = pos1 - 1
locpos = locpos + 1

matrixloc(locpos, 0) = val1(1)
matrixloc(locpos, 1) = val2(1)
matrixloc(locpos, 2) = val1(0)
matrixloc(locpos, 3) = val2(0)
matrixloc(locpos, 4) = pos1 - 1
locpos = locpos + 1

END SELECT
pos1 = 0
NEXT i

'How the solution is found:
'we go through matrixloc() and filter it through matrix().
'step 1:
'If the location of an attribute is known that has a relative position,
'we can add it to matrix():
'e.x.:
'if brit is next to a red house,
'then if red house position is known,
'we can set all positions except those two or one nearby to false for brit.
'also, if brit position is known,
'we can set all positions except those two or one nearby to false for red house.

'We go through all of the outstanding relative position truths this way.
'
'step 2:
'then, we go through matrix() and check for all but one conditions
'being false on some attribute and set that one to true.
'Then we go back to step 1 until we know who the fish belongs to.
'(or, alternatively, that there are no unknowns)

do
ex1 = 0
FOR i = 0 to locpos - 1
for j = 0 to 1
IF matrixloc(i, 5+j) = 0 THEN
'check whether attribute 1 position is known.
'To do that, we check whether all other attributes are false.
temp1 = 0
for k = 0 to attribpos-1
IF matrix(matrixloc(i, j+j), matrixloc(i, 1+j+j), 5, k) = 1 THEN temp2 = k: temp1 = temp1 + 1
next k

IF temp1 = 1 THEN
ex1 = 1
'make non-adjacent values equal to 0...
'e.g. if house red = brit,
'set house red <> swede, house red <> german, etc.
'(the mirror value is set in the next pass of 'j', I think..)
'matrixloc(i, 4): 0 = left, 1 = right, 2 = next to.

setNonAdjacentValuesToZero matrix(), matrixloc(), i, j*2, (1-j)*2, matrix(5, k, matrixloc(i, j+j), matrixloc(i, 1+j+j))
matrixloc(i, 5+j) = 1
END IF
END IF
NEXT j
NEXT i

'Inheritance:
'If green <> white and green = coffee, then coffee <> white.
for i = 0 to attrib-1
for j = 0 to attribpos-1
'if [some attribute] <> [some other attribute]...
'and [some attribute] def.= [another attribute]...
'then [some attribute] <> [another attribute].
for k = 0 to attrib-1
for m = 0 to attribpos-1
if i * attribpos + j <> k * attribpos + m then
if matrix(i, j, k, m) = 0 THEN
for n = 0 to attrib-1
temp1 = 0
for o = 0 to attribpos-1
if matrix(i, j, n, o) = 1 then temp2 = o: temp1 = temp1 + 1
NEXT o
if i * attribpos + j <> n * attribpos + temp2 then
if k * attribpos + m <> n * attribpos + temp2 then
IF temp1 = 1 THEN
if matrix(n, temp2, k, m) <> 0 THEN
matrix(n, temp2, k, m) = 0
matrix(k, m, n, temp2) = 0
ex1 = 1
end if
end if
END IF
END IF
NEXT n
END IF
END IF
next m, k, j, i

'Inheritance2:
'if coffee = german and german = red, then coffee = red.

for i = 0 to attrib-1
for j = 0 to attribpos-1
for k = 0 to attrib-1
temp1 = 0
for m = 0 to attribpos-1
temp1 = matrix(i, j, k, m)
if matrix(i, j, k, m) = 1 THEN temp3 = o: temp1 = temp1 + 1
next m

if i * attribpos + j <> k * attribpos + temp3 then
if temp1 = 1 then

for n = 0 to attrib-1
temp1 = 0
for o = 0 to attribpos-1
if matrix(i, j, n, o) = 1 then temp2 = o: temp1 = temp1 + 1
NEXT o
if i * attribpos + j <> n * attribpos + temp2 then
if k * attribpos + temp3 <> n * attribpos + temp2 then
IF temp1 = 1 THEN
if matrix(k, temp3, n, temp2) <> 0 THEN
matrix(k, temp3, n, temp2) = 0
matrix(n, temp2, k, temp3) = 0
ex1 = 1
end if
end if
END IF
END IF
NEXT n

END IF
END IF
next k, j, i

if ex1 = 0 then exit do
loop

for i = 0 to attrib-1
for j = 0 to attribpos-1

for k = 0 to attrib-1
for m = 0 to attribpos-1
IF matrixAttrib\$(i * attribpos + j) = "center" THEN
IF matrix(i, j, k, m) = 0 THEN PRINT matrixAttrib\$(i * attribpos + j); " <> " ; matrixAttrib\$(k * attribpos + m); i ; j ; k; m
END IF
next m, k, j, i

for i = 0 to attrib-1
for j = 0 to attribpos-1
for k = 5 to 5
temp1 = 0
for m = 0 to attribpos-1
if matrix(i, j, k, m) = 1 then temp2 = m: temp1 = temp1 + 1
next m
if temp1 = 1 then
matrixSolution(i, j) = k*attribpos + temp2
else
matrixSolution(i, j) = -1
end if
next k, j, i

print
for i = 0 to attrib-1
for j = 0 to attribpos-1
if matrixSolution(i, j) <> -1 then
PRINT matrixAttrib\$(i * attribpos + j);" - ";matrixAttrib\$(matrixSolution(i,j))
end if
next i, j

sleep
system

SUB setNonAdjacentValuesToZero (matrix() AS BYTE, matrixloc() AS BYTE, i, j1, j2, position AS BYTE)
FOR x = 0 to attribpos-1
SELECT CASE matrixloc(i, 4)
CASE 0: IF x = leftadj THEN GOTO nextfor
CASE 1: IF x = rightadj THEN GOTO nextfor
CASE 2: IF x = leftadj OR x = rightadj THEN GOTO nextfor
END SELECT
matrix(5, x, matrixloc(i, j2), matrixloc(i, j2+1)) = 0
matrix(matrixloc(i, j2), matrixloc(i, j2+1), 5, x) = 0
nextfor:
NEXT x

END SUB

FUNCTION findValue(ats() AS STRING, vtf AS STRING, a AS INTEGER, b AS INTEGER) AS INTEGER
DO
IF a > b then exit do
n = (a + b) / 2
IF vtf = ats(n) THEN findValue = n: EXIT FUNCTION
IF vtf < ats(n) THEN
b = n - 1
ELSE
a = n + 1
END IF
LOOP
findValue = -1
END FUNCTION

SUB qsort.linked.string.lowstart (array1() AS STRING, array2() AS INTEGER, amax AS INTEGER)
DIM g2(0 TO amax) AS INTEGER, h2(0 TO amax) AS INTEGER, i AS INTEGER, j AS INTEGER, r AS INTEGER, E AS INTEGER, g AS INTEGER, h AS INTEGER, k AS STRING
E = 0: g2(0) = 0: h2(0) = amax
e1: g = g2(E): h = h2(E)
e2: i = g: j = h: r = (g + h) \ 2: k = array1(r)
e3: IF array1(i) < k THEN i = i + 1: GOTO e3
e4: IF array1(j) > k THEN j = j - 1: GOTO e4
IF i <= j THEN SWAP array1(i), array1(j): SWAP array2(i), array2(j): i = i + 1: j = j - 1: IF i <= j THEN GOTO e3
IF j - g + i < h THEN
IF i < h THEN g2(E) = i: h2(E) = h: E = E + 1
h = j
ELSE
IF g < j THEN g2(E) = g: h2(E) = j: E = E + 1
g = i
END IF
IF g < h THEN GOTO e2 ELSE E = E - 1: IF E >-1 THEN GOTO e1
ERASE g2, h2
END SUB
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Agamemnus
x/ \z

Posts: 3491

 « Reply #9 on: June 08, 2006, 09:56:22 PM »

I have not been able to crack the locational issues with "regular" logic so here is a possible system to do it, but I would rather use regular logic as this is a bit cumbersome...

1) First, construct a physical link map:

"The Green house is on the left of the White house." & "The owner of the Green house drinks coffee. " translates to:

G(a)-W(a)
|
C(d)

2) Now, take the current physical map that is available:

1. 2. 3. 4. 5.
a. 0  B  0  0  0
b. N  0  0  0  0
c. 0  0  0  0  0
d. 0  0  M  0  0
e. 0  0  0  0  0

3) From that, test the link possibilities, starting with C:
* which d. location(s) can C. fit in?
* a1) If it fits, check the next on the link and wait for a position or 0. If you get a position, return your position and the previous one, else return 0.
* a2) If it fits and it's the last one, return the position that it fits in.
* b) If it doesn't fit, check the next possibility.
* c) If no more possibilities, return 0.

Note: Obviously this can be solved much faster through brute force, as there are only 5^5 possible combinations. (Don't quote me on that.)
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
DrV
Na_th_an

Posts: 1553

 « Reply #10 on: June 12, 2006, 09:10:06 PM »

I tried solving that problem by hand once too, and it drove me nuts; maybe I'll have time to code up a solver...
 Logged
yetifoot
Ancient Guru

Posts: 575

 « Reply #11 on: June 14, 2006, 03:14:55 PM »

Sorry i've been too busy to post, or work on my solver.  You code looks interesting though aga, i will take the time to look at it properly when i can.

Also i've lost the short one i downloaded, but heres another one i dug up.  A lot larger but less obfuscated than the other one i lost.

Code:
//  einstein.cpp  (c) Klaus Betzler 20011218

//  Klaus.Betzler@uos.de

//  `Einstein's RiddleŽ, the rules:

//  1 The Brit lives in the red house
//  2 The Swede keeps dogs as pets
//  3 The Dane drinks tea
//  4 The green house is on the left of the white house
//  5 The green house's owner drinks coffee
//  6 The person who smokes Pall Mall rears birds
//  7 The owner of the yellow house smokes Dunhill
//  8 The man living in the centre house drinks milk
//  9 The Norwegian lives in the first house
// 10 The person who smokes Marlboro lives next to the one who keeps cats
// 11 The person who keeps horses lives next to the person who smokes Dunhill
// 12 The person who smokes Winfield drinks beer
// 13 The German smokes Rothmans
// 14 The Norwegian lives next to the blue house
// 15 The person who smokes Marlboro has a neigbor who drinks water

#undef WIN32           // #undef for Linux

#include <stdio.h>
#ifdef WIN32
#include <windows.h>
#endif

inline unsigned long BIT(unsigned n) {return 1<<n;}

const unsigned long
yellow = BIT(0),
blue = BIT(1),
red = BIT(2),
green = BIT(3),
white = BIT(4),

norwegian = BIT(5),
dane = BIT(6),
brit = BIT(7),
german = BIT(8),
swede = BIT(9),

water = BIT(10),
tea = BIT(11),
milk = BIT(12),
coffee = BIT(13),
beer = BIT(14),

dunhill = BIT(15),
marlboro = BIT(16),
pallmall = BIT(17),
rothmans = BIT(18),
winfield = BIT(19),

cat = BIT(20),
horse = BIT(21),
bird = BIT(22),
fish = BIT(23),
dog = BIT(24);

const char * Label[] = {
"Yellow","Blue","Red","Green","White",
"Norwegian","Dane","Brit","German","Swede",
"Water","Tea","Milk","Coffee","Beer",
"Dunhill","Marlboro","Pallmall","Rothmans","Winfield",
"Cat","Horse","Bird","Fish","Dog"
};

const unsigned long color = yellow+blue+red+green+white;
const unsigned long country = norwegian+dane+brit+german+swede;
const unsigned long drink = water+tea+milk+coffee+beer;
const unsigned long cigar = dunhill+marlboro+pallmall+rothmans+winfield;
const unsigned long animal = cat+horse+bird+fish+dog;

unsigned long house[5] = {norwegian,blue,milk,0,0};  // rules 8,9,14
unsigned long result[5];

const unsigned long comb[] = { // simple rules
brit+red,                    // 1
swede+dog,                   // 2
dane+tea,                    // 3
green+coffee,                // 5
pallmall+bird,               // 6
yellow+dunhill,              // 7
winfield+beer,               // 12
german+rothmans              // 13
};

country+color,
country+animal,
country+drink,
color+drink,
cigar+animal,
color+cigar,
cigar+drink,
country+cigar
};

inline bool SimpleRule(unsigned nr, unsigned which)
{
if (which<8) {
return false;
else {
house[nr]|=comb[which];
return true;
}
}
else {           // rule 4
if ((nr==4)||((house[nr]&green)==0))
return false;
else
if ((house[nr+1]&color)>0)
return false;
else {
house[nr+1]|=white;
return true;
}
}
}

inline void RemoveSimple(unsigned nr, unsigned which)
{
if (which<8)
house[nr]&=~comb[which];
else
house[nr+1]&=~white;
}

inline bool DunhillRule(unsigned nr, int side)  // 11
{
if (((side==1)&&(nr==4))||((side==-1)&&(nr==0))||((house[nr]&dunhill)==0))
return false;
if ((house[nr+side]&animal)>0)
return false;
house[nr+side]|=horse;
return true;
}

inline void RemoveDunhill(unsigned nr, unsigned side)
{
house[nr+side]&=~horse;
}

inline bool MarlboroRule(unsigned nr)    // 10 + 15
{
if ((house[nr]&cigar)>0)
return false;
house[nr]|=marlboro;
if (nr==0) {
if ((house[1]&(animal+drink))>0)
return false;
else {
house[1]|=(cat+water);
return true;
}
}
if (nr==4) {
if ((house[3]&(animal+drink))>0)
return false;
else {
house[3]|=(cat+water);
return true;
}
}
int i,k;
for (i=-1; i<2; i+=2) {
if ((house[nr+i]&animal)==0) {
house[nr+i]|=cat;
for (k=-1; k<2; k+=2) {
if ((house[nr+k]&drink)==0) {
house[nr+k]|=water;
return true;
}
}
}
}
return false;
}

void RemoveMarlboro(unsigned m)
{
house[m]&=~marlboro;
if (m>0)
house[m-1]&=~(cat+water);
if (m<4)
house[m+1]&=~(cat+water);
}

void Recurse(unsigned recdepth)
{
unsigned n, m;
for (n=0; n<5; n++) {
if (recdepth<9) {    // simple rules
if (SimpleRule(n, recdepth)) {
Recurse(recdepth+1);
RemoveSimple(n, recdepth);
}
}
else {               // Dunhill and Marlboro
for (int side=-1; side<2; side+=2)
if (DunhillRule(n, side)) {
for (m=0; m<5; m++)
if (MarlboroRule(m))
for (int r=0; r<5; r++)
result[r] = house[r];
else
RemoveMarlboro(m);
RemoveDunhill(n, side);
}
}
}
}

int main()
{
int index, i;
#ifdef WIN32
LARGE_INTEGER time0, time1, freq;
QueryPerformanceCounter(&time0);
#endif
Recurse(0);
#ifdef WIN32
QueryPerformanceCounter(&time1);
QueryPerformanceFrequency(&freq);
printf("\nComputation Time: %ld microsec\n\n",
#endif
if (result[0]==0) {
printf("No solution found !?!\n");
return 1;
}
for (i=0; i<5; i++)
if ((result[i]&animal)==0)
for (index=0; index<25; index++)
if (((result[i]&country)>>index)==1)
printf("Fish Owner is the %s !!!\n\n", Label[index]);
for (i=0; i<5; i++) {
printf("%d: ",i+1);
for (index=0; index<25; index++)
if (((result[i]>>index)&1)==1)
printf("%-12s",Label[index]);
printf("\n\n");
}
return 0;
}
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #12 on: June 14, 2006, 06:44:26 PM »

Ah, a recursive depth-first search using the rules to backtrack. Maybe I could try it in QB.

But, what is the computation time in C?
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
yetifoot
Ancient Guru

Posts: 575

 « Reply #13 on: June 15, 2006, 12:38:08 PM »

~ 45 microseconds.
 Logged

EVEN MEN OF STEEL RUST.
 Pages: [1]