Kuromasu Solver using Java
As defined in Wikipedia, Kuromasu (also named Kurodoku) is a binary-determination logic puzzle published by Nikoli. You may read the Wikipedia article for a complete description of the rules. See this link for an academic study of different possible methodologies to solve the problem.
After looking around on the Internet for a computer solution to this problem, I decided to create my own solver as I did not find any free solution. The search engine uses a depth first search to assign the four black cells surrounding a numbered cell and immediately check that all of the rules are still valid for all of the already processed numbered cells, then proceed to solve the next numbered cell. When a candidate solution is found, it is checked to ensure that all of the white cells are connected. The solution for the Wikipedia sample problem is found in less that one second. As of December 19, 2011, added the ability to search all possible solutions. To keep the GUI responsive while the search proceeds, a second thread is used.
The source code can be found by following this link.
To run the solver follow this link. Clicking on “load” will load the wikipedia sample problem.
- Improve GUI: Make the buttons with equal widths. Disable buttons according to the state of the application.
- Allow to run application via Java Web Start.
- Add feature to import/export problems in ASCII format and/or XML.
- Add more sample problems.
This grid found here is solved in less than 5 seconds. That same site solves it in more than 34 seconds.