My Java solution can solve the 100x100 board in 5.5ms (on my 2.5GHz Intel Core 2 Duo laptop). (Actually, it can solve the the 100x100 board 10,000 times in 55 seconds.) I actually provide two solutions: a very small heuristic-less solution, and a longer one based on Warnsdorff's heuristic.
/** * Knight.java * author: Kevin Greer * date: Dec 1, 2008
Gives the following output for SIZE = 8
1 50 15 32 61 28 13 30
16 33 64 55 14 31 60 27
51 2 49 44 57 62 29 12
34 17 56 63 54 47 26 59
3 52 45 48 43 58 11 40
18 35 20 53 46 41 8 25
21 4 37 42 23 6 39 10
36 19 22 5 38 9 24 7
**/ public class Knight { static final int SIZE = 100; static final int[][] b = new int[SIZE][SIZE]; static final int[][] M = { {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1} };
static void displayBoard() { for ( int c = 0 ; c < SIZE ; c++ ) { for ( int r = 0 ; r < SIZE ; r++ ) System.out.print(String.format(" %4d", b[r][c])); System.out.println("\n"); } }
// Simple Heuristic-less solution static boolean s(int x,int y, int i) { if ( x < 0 || y < 0 || x >= SIZE || y >= SIZE || b[x][y] != 0 ) return false; if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; } return s(x+2,y+1,i) || s(x+2,y-1,i) || s(x-2,y+1,i) || s(x-2,y-1,i) || s(x+1,y+2,i) || s(x+1,y-2,i) || s(x-1,y+2,i) || s(x-1,y-2,i) || ( b[x][y] = 0 ) == 1; }
// Solution using Warnsdorff's Heuristic static boolean isGood(int x, int y) { return x >= 0 && y >= 0 && x < SIZE && y < SIZE && b[x][y] == 0; } static boolean solve(int x, int y, int i) { if ( ! isGood(x, y) ) return false; try { if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; } int[] friends = new int[M.length]; for ( int m = 0 ; m < M.length ; m++ ) if ( isGood(x+M[m][0], y+M[m][1]) ) for ( int m2 = 0 ; m2 < M.length ; m2++ ) if ( isGood(x+M[m][0]+M[m2][0], y+M[m][1]+M[m2][1]) ) friends[m]++; for ( int n = 0 ; n < M.length ; n++ ) for ( int m = 0 ; m < M.length ; m++ ) if ( friends[m] == n && solve(x+M[m][0], y+M[m][1], i) ) return true; return false; } finally { b[x][y] = 0; } }
public static void main(String[] argv) { // Perform more iterators for more accurate benchmarks for ( int i = 0 ; i < 1 ; i++ ) { solve(0,0,1); } } }
1. This sounds kinda strange until you consider that most animals actually have skins rather than shells.
2. You could make the whole car be one giant airbag. Just before you detect an imminent crash you could inflate the whole car.
3. While driving you could extend the bumpers by a foot or two to improve safety. As you slow down to park the bumpers could retract. This would also improve your aerodynamics.
4. If this were used for a sedan or mini-van you could collapse the rear-half or passenger-side when not being used to improve aerodynamics.
5. For cold (or hot) climates you could add insulation by using fabric with (synthetic) fur. It might be better to put the fur on the inside.
6. Rather than having the front wheels turn for steering, you could put a large pivot in the center of the car and keep all of the wheels fixed.
I wonder if it would be economically viable to farm mammoths for their ivory and meat? Mammoth tusks are much larger than elephant tusks (16' vs 10') and so would provide an excellent source of ivory. There wouldn't be any trade restrictions on Mammoth ivory because Mammoth's aren't endangered, they're extinct! This would help elephants by reducing the incentive to poach them. Mammoth meat probably tastes very good given that humans ate them into extinction.
There are plenty of compelling easy-entry programming environments out there and they're all better than BASIC. Logo, Squeak, Scratch, StarLogo TNG, Linda, MS's Kid's Programming Language, etc. More information with links on my blog.
The Morris Worm - it didn't improve anything and it was buggy to boot
Replace:
Excel with Visicalc - Excel just represents the inventiable progression of the idea. They didn't really do anything unexpected or exceptional with the idea (like say Lotus Improv did).
They can't pick Mosaic over Firefox and then not pick Visicalc over Excel.
Add the following to make it a top 14 list.
Xerox Star (including Bravo, the first WYSIWYG word processor), I would actually put this one very near the top.
Smalltalk 80
Douglas Englebart's NLS
Napster
Ivan Sutherland's Sketchpad
Honourable Mentions
Lotus Improv for Next
Adobe Photoshop
Final Fantasy VII
TRS-80 Deskmate
PalmOS
OpenGL
Lisp 1.5
Emacs
QNX
Some people argue that the 'C' programming language should be included but I think that
it would be redundant considering that it is a part of Unix.
I'm glad to see Java included and I think that he got #1 (BSD Unix) correct.
CORBA supports low-level asynchronous communications in the form of "one-way" methods which return immediately. The higher-level "Event" and "Notification" services provide higher-level async/Message-Oriented-Middleware (MOM) solutions.
CORBA is used extensively in telecom, and I don't see the situation changing anytime soon. The reason for this is that CORBA is the only (relatively) mainstream high-performance middleware to support heterogeneous environments. WebServices are (mostly) heterogeneous and RMI is high-performance, but if you want both, then CORBA is the only game in town. There is still no replacement for CORBA.
Another thing that many don't realize is that EJB's use CORBA for remoting (but they can also use RMI).
Ten years ago many developers found CORBA difficult to use but I think a lot of the problem was really that they found "distributed computing" difficult in general. I think that you'll find that if you do a side-by-side comparison of CORBA and a full WebServices stack, you'll probably conclude that CORBA is actually the much simpler of the two.
I wonder if the open-source community will rise to the challenge of providing something as good for *NIX, or if they will simply live in denial of MS's genuine advancement/advantage. I think that we now need to update all of our *NIX/Windows Advantage/Disadvantage tables and move the "scriptability" check to the other column.
It's not even clear that you could create something similar for *NIX given that MSH is build on.Net so actually has lots of Objects to script whereas an Object-based shell and *NIX would be lacking any Objects to script. Actually, UNIX is an OO system in a very limited fashion, be it one with only one interface: File.
I asked James Gosling whether the Solaris team at Sun was doing anything with Java to add MSH-like capabilities to Solaris. To make a long answer short, he basically said "no".
Many of the high-order functional programming aspects of MSH remind me of a UNIX shell from around 1990 called "Es". You can read about it here:
Es: A shell with higher-order functions.
I always found note taking a waste of time. How long has it been since we invented the printing press, projector, photocopy machine, or internet? Couldn't we find a better way to distribute content than to have a highly-paid professor copy his notes onto a blackboard so that they can then be copied by a bunch of highly-paying students into their notes or laptops?
I always preferred classes where notes were made available ahead of time and then all you had to do was add a few extra annotations during class. This allows you to concentrate on the material being presented rather than on its copying.
I'm not saying that "liberal arts people" have some agenda to push witchcraft or UFO's, but rather, that they do not appear to have an agenda to push mathematics. Or perhaps, they simply cater to the demands of library patrons, who themselves have not expressed a desire for mathematics resources. In either case, mathematics seems to be greatly under represented (in my local library at least).
While browsing the stacks at my local library I came upon the mathematics section. It only contained about five or six books: two grade four or five textbooks and a couple books on math puzzles. I found this very disappointing given the importance of mathematics in so many fields, but then, to make things even worse, I happened to notice that the nearby sections on U.F.O's and Witchcraft were actually far better stocked. It made me wonder if this was caused by society's indifference towards mathematics or if it was merely caused by the liberal arts bias of most librarians.
Slashdot Mirror
I thought that I read somewhere that she also played the dancing green alien which appeared during the credits. Does anyone know if this is true?
My Java solution can solve the 100x100 board in 5.5ms (on my 2.5GHz Intel Core 2 Duo laptop). (Actually, it can solve the the 100x100 board 10,000 times in 55 seconds.) I actually provide two solutions: a very small heuristic-less solution, and a longer one based on Warnsdorff's heuristic.
// Simple Heuristic-less solution
// Perform more iterators for more accurate benchmarks
/**
* Knight.java
* author: Kevin Greer
* date: Dec 1, 2008
Gives the following output for SIZE = 8
1 50 15 32 61 28 13 30
16 33 64 55 14 31 60 27
51 2 49 44 57 62 29 12
34 17 56 63 54 47 26 59
3 52 45 48 43 58 11 40
18 35 20 53 46 41 8 25
21 4 37 42 23 6 39 10
36 19 22 5 38 9 24 7
**/
public class Knight {
static final int SIZE = 100;
static final int[][] b = new int[SIZE][SIZE];
static final int[][] M = { {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1} };
static void displayBoard() {
for ( int c = 0 ; c < SIZE ; c++ ) {
for ( int r = 0 ; r < SIZE ; r++ ) System.out.print(String.format(" %4d", b[r][c]));
System.out.println("\n");
}
}
static boolean s(int x,int y, int i) {
if ( x < 0 || y < 0 || x >= SIZE || y >= SIZE || b[x][y] != 0 ) return false;
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
return s(x+2,y+1,i) || s(x+2,y-1,i) || s(x-2,y+1,i) || s(x-2,y-1,i) || s(x+1,y+2,i) || s(x+1,y-2,i) || s(x-1,y+2,i) || s(x-1,y-2,i) || ( b[x][y] = 0 ) == 1;
}
// Solution using Warnsdorff's Heuristic
static boolean isGood(int x, int y) { return x >= 0 && y >= 0 && x < SIZE && y < SIZE && b[x][y] == 0; }
static boolean solve(int x, int y, int i) {
if ( ! isGood(x, y) ) return false;
try {
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
int[] friends = new int[M.length];
for ( int m = 0 ; m < M.length ; m++ ) if ( isGood(x+M[m][0], y+M[m][1]) ) for ( int m2 = 0 ; m2 < M.length ; m2++ ) if ( isGood(x+M[m][0]+M[m2][0], y+M[m][1]+M[m2][1]) ) friends[m]++;
for ( int n = 0 ; n < M.length ; n++ ) for ( int m = 0 ; m < M.length ; m++ ) if ( friends[m] == n && solve(x+M[m][0], y+M[m][1], i) ) return true;
return false;
} finally { b[x][y] = 0; }
}
public static void main(String[] argv) {
for ( int i = 0 ; i < 1 ; i++ ) {
solve(0,0,1);
}
}
}
1. This sounds kinda strange until you consider that most animals actually have skins rather than shells.
2. You could make the whole car be one giant airbag. Just before you detect an imminent crash you could inflate the whole car.
3. While driving you could extend the bumpers by a foot or two to improve safety. As you slow down to park the bumpers could retract. This would also improve your aerodynamics.
4. If this were used for a sedan or mini-van you could collapse the rear-half or passenger-side when not being used to improve aerodynamics.
5. For cold (or hot) climates you could add insulation by using fabric with (synthetic) fur. It might be better to put the fur on the inside.
6. Rather than having the front wheels turn for steering, you could put a large pivot in the center of the car and keep all of the wheels fixed.
Links:
There are plenty of compelling easy-entry programming environments out there and they're all better than BASIC. Logo, Squeak, Scratch, StarLogo TNG, Linda, MS's Kid's Programming Language, etc. More information with links on my blog.
- The Morris Worm - it didn't improve anything and it was buggy to boot
Replace:- Excel with Visicalc - Excel just represents the inventiable progression of the idea. They didn't really do anything unexpected or exceptional with the idea (like say Lotus Improv did).
They can't pick Mosaic over Firefox and then not pick Visicalc over Excel.
Add the following to make it a top 14 list.- Xerox Star (including Bravo, the first WYSIWYG word processor), I would actually put this one very near the top.
- Smalltalk 80
- Douglas Englebart's NLS
- Napster
- Ivan Sutherland's Sketchpad
Honourable Mentions- Lotus Improv for Next
- Adobe Photoshop
- Final Fantasy VII
- TRS-80 Deskmate
- PalmOS
- OpenGL
- Lisp 1.5
- Emacs
- QNX
Some people argue that the 'C' programming language should be included but I think that it would be redundant considering that it is a part of Unix.I'm glad to see Java included and I think that he got #1 (BSD Unix) correct.
CORBA supports low-level asynchronous communications in the form of "one-way" methods which return immediately. The higher-level "Event" and "Notification" services provide higher-level async/Message-Oriented-Middleware (MOM) solutions.
CORBA is used extensively in telecom, and I don't see the situation changing anytime soon. The reason for this is that CORBA is the only (relatively) mainstream high-performance middleware to support heterogeneous environments. WebServices are (mostly) heterogeneous and RMI is high-performance, but if you want both, then CORBA is the only game in town. There is still no replacement for CORBA.
Another thing that many don't realize is that EJB's use CORBA for remoting (but they can also use RMI).
Ten years ago many developers found CORBA difficult to use but I think a lot of the problem was really that they found "distributed computing" difficult in general. I think that you'll find that if you do a side-by-side comparison of CORBA and a full WebServices stack, you'll probably conclude that CORBA is actually the much simpler of the two.
It's not even clear that you could create something similar for *NIX given that MSH is build on .Net so actually has lots of Objects to script whereas an Object-based shell and *NIX would be lacking any Objects to script. Actually, UNIX is an OO system in a very limited fashion, be it one with only one interface: File.
I asked James Gosling whether the Solaris team at Sun was doing anything with Java to add MSH-like capabilities to Solaris. To make a long answer short, he basically said "no".
Many of the high-order functional programming aspects of MSH remind me of a UNIX shell from around 1990 called "Es". You can read about it here: Es: A shell with higher-order functions.
I always found note taking a waste of time. How long has it been since we invented the printing press, projector, photocopy machine, or internet? Couldn't we find a better way to distribute content than to have a highly-paid professor copy his notes onto a blackboard so that they can then be copied by a bunch of highly-paying students into their notes or laptops?
I always preferred classes where notes were made available ahead of time and then all you had to do was add a few extra annotations during class. This allows you to concentrate on the material being presented rather than on its copying.
I'm not saying that "liberal arts people" have some agenda to push witchcraft or UFO's, but rather, that they do not appear to have an agenda to push mathematics. Or perhaps, they simply cater to the demands of library patrons, who themselves have not expressed a desire for mathematics resources. In either case, mathematics seems to be greatly under represented (in my local library at least).
While browsing the stacks at my local library I came upon the mathematics section. It only contained about five or six books: two grade four or five textbooks and a couple books on math puzzles. I found this very disappointing given the importance of mathematics in so many fields, but then, to make things even worse, I happened to notice that the nearby sections on U.F.O's and Witchcraft were actually far better stocked. It made me wonder if this was caused by society's indifference towards mathematics or if it was merely caused by the liberal arts bias of most librarians.